[R] Computing the minimal polynomial or, at least, its degree

[Spencer Graves]

	  How about the following:


library(polynom)
help(package="polynom")
A <- diag(c(1:2, 2))
eigVals <- eigen(A)$values
multEig <- table(eigVals)
k <- length(multEig)
ratPoly <- minPoly <- 1
for(i in 1:k){
   poly.i <- polynomial(c(-as.numeric(names(multEig)[i]), 1))
   minPoly <- (minPoly*poly.i)
   if(multEig[i]>1)
     ratPoly <- (ratPoly*poly.i^(multEig[i]-1))
}

 > minPoly
2 - 3*x + x^2
 > ratPoly
-2 + x
 >
	  hope this helps.  spencer graves

###############################
Spencer,

One could do this by a brute force approach. Suppose A is an nxn matrix, and
the distinct eigenvalues are: lambda_1, ..., lambda_k, with multiplicities
m_1, ..., m_k, such that they sum to n. Then the characteristic polynomial
is:
C(lambda) = \prod_i (lambda - lambda_i)^{m_i}
The minimal polynomial is given by:
M(lambda) = \prod_i (lambda - lambda_i)^{p_i},
where 1 \leq p_i \leq m_i.
So, one could run through all possible p_i, starting with the smallest
degree polynomial (within constraint), and stop when we find one that
exactly divides C(lambda).

Is there a cleverer way to do this?

Ravi.
#################################################
      Have you looked at library(polynom)?  Will that with
unique(eigen(A)$values) allow you to compute what you want?

      hope this helps.
      spencer graves

Ravi Varadhan wrote:

>Hi,
>
> 
>
>I would like to know whether there exist algorithms to compute the
>coefficients or, at least, the degree of the minimal polynomial of a square
>matrix A (over the field of complex numbers)? I don't know whether this
>would require symbolic computation.  If not, has any of the algorithms been
>implemented in R?  
>
> 
>
>Thanks very much,
>
>Ravi.
>
> 
>
>P.S.  Just for the sake of completeness, a minimal polynomial is a monic
>polynomial (whose leading coefficient is unity) of least degree, which
>divides all the annihilating polynomial of A. In particular, the minimal
>polynomial divides the characteristic polynomial.  Knowing the degree of the
>minimal polynomial is useful in characterizing the convergence properties of
>a certain class of numerical schemes for iteratively solving linear (and
>nonlinear) system of equations.
>
> 
>
>--------------------------------------------------------------------------
>
>Ravi Varadhan, Ph.D.
>
>Assistant Professor,  The Center on Aging and Health
>
>Division of Geriatric Medicine and Gerontology
>
>Johns Hopkins Univerisity
>
>Ph: (410) 502-2619
>
>Fax: (410) 614-9625
>
>Email:   <mailto:rvaradhan at jhmi.edu> rvaradhan at jhmi.edu
>
>--------------------------------------------------------------------------
>
> 
>
>
>	[[alternative HTML version deleted]]
>
>______________________________________________
>R-help at stat.math.ethz.ch mailing list
>https://stat.ethz.ch/mailman/listinfo/r-help
>PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html
>  
>

-- 
Spencer Graves, PhD, Senior Development Engineer
O:  (408)938-4420;  mobile:  (408)655-4567