linalg::charpoly
--
characteristic polynomial of a matrixlinalg::charpoly
(A, x)
computes the
characteristic polynomial of the matrix A. The
characteristic polynomial of a n x n matrix is defined by
pA(x):=det(x*I-A), where I denotes the n x
n identity matrix.
linalg::charpoly(A, x)
A |
- | a square matrix of a domain of category Cat::Matrix |
x |
- | an indeterminate |
a polynomial of the domain
Dom::DistributedPolynomial
([x],R)
, where
R
is the component ring of A
.
linalg::charmat
,
linalg::det
, linalg::hessenberg
, linalg::minpoly
A
must be a commutative ring,
i.e., a domain of category Cat::CommutativeRing
.We define a matrix over the rational numbers:
>> A := Dom::Matrix(Dom::Rational)([[1, 2], [3, 4]])
+- -+ | 1, 2 | | | | 3, 4 | +- -+
Then the characteristic polynomial pA(x) is given by:
>> linalg::charpoly(A, x)
2 x - 5 x - 2
It is of the domain type:
>> domtype(%)
Dom::DistributedPolynomial([x], Dom::Rational, LexOrder)
We define a matrix over Z7:
>> B := Dom::Matrix(Dom::IntegerMod(7))([[1, 2], [3, 0]])
+- -+ | 1 mod 7, 2 mod 7 | | | | 3 mod 7, 0 mod 7 | +- -+
The characteristic polynomial pB(x) of
B
is given by:
>> p := linalg::charpoly(B, x)
2 (1 mod 7) x + (6 mod 7) x + (1 mod 7)
We compute the zeros of pB(x), i.e., the
eigenvalues of the matrix B
:
>> solve(p)
x in {3 mod 7, 5 mod 7}
linalg::charpoly
implements Hessenberg's algorithm to
compute the characteristic polynomial of a square matrix A.
See: Henri Cohen: A Course in Computational Algebraic Number
Theory, GTM 138, Springer Verlag.
This algorithm works for any field and requires only O(n^3) field operations, in contrast to O(n^4) when computing the determinant of the characteristic matrix of A.
Since the size of the components of A in intermediate
computations of Hessenberg's algorithm can swell extremely, it is only
applied for matrices over Dom::Float
and Dom::IntegerMod
.
For any other component ring, the characteristic polynomial is computed using the Berkowitz algorithm. Reference: A. Jounaidi: The Berkowitz Algorithm, Maple and Computing the Characteristic Polynomial in an Arbitrary Commutative Ring. Equipe de Mathèmatiques de Besancon, Universitè de Franche - Comtè, 25030 Besancon Cedex, May 1996.
linalg::charPolynomial