Ravi Varadhan
2004-Dec-03 14:20 UTC
[R] Computing the minimal polynomial or, at least, its degree
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@jhmi.edu> rvaradhan@jhmi.edu -------------------------------------------------------------------------- [[alternative HTML version deleted]]
Ravi Varadhan
2004-Dec-03 15:24 UTC
[R] Computing the minimal polynomial or, at least, its degree
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@jhmi.edu> rvaradhan@jhmi.edu -------------------------------------------------------------------------- [[alternative HTML version deleted]]
Spencer Graves
2004-Dec-03 16:13 UTC
[R] Computing the minimal polynomial or, at least, its degree
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
Spencer Graves
2004-Dec-04 02:56 UTC
[R] Computing the minimal polynomial or, at least, its degree
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