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

Spencer Graves spencer.graves at pdf.com
Sat Dec 4 03:56:01 CET 2004

	  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

>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.
>
>
>
>--------------------------------------------------------------------------
>
>
>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
>
>
>--------------------------------------------------------------------------
>
>
>
>
>	[[alternative HTML version deleted]]
>
>______________________________________________
>R-help at stat.math.ethz.ch mailing list
>https://stat.ethz.ch/mailman/listinfo/r-help