[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
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
More information about the R-help
mailing list