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

Mon Dec 6 16:21:49 CET 2004

Dear Spencer,

Thank you very much for your help. Your solution is almost correct, but not
quite completely (it is correct for your example of A, but not in general).
The problem is that the minimal polynomial is related to the characteristic
polynomial in a not-so-straightforward manner.  The following theorem shows
the relationship between the two polynomials:

If C(\lambda), and M(\lambda) are the characteristic and minimal polynomial
of a square matrix A, respectively, and D_{n-1}(\lambda) be the greatest
common divisor of the elements of the adjoint of (\lambda I - A), then
C(\lambda) = D_{n-1}(\lambda) M(\lambda).

Is there a way to use this theorem and the "polynomial" library to compute
the minimal polynomial?

Thanks once again,
Ravi.

--------------------------------------------------------------------------
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
--------------------------------------------------------------------------
-----Original Message-----
From: Spencer Graves [mailto:spencer.graves at pdf.com]
Sent: Friday, December 03, 2004 9:56 PM
Cc: r-help at r-project.org
Subject: Re: [R] Computing the minimal polynomial or, at least, its degree

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