linalg::charpoly --
characteristic polynomial of a matrix
Introductionlinalg::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.
Call(s)linalg::charpoly(A, x)
ParametersA |
- | a square matrix of a domain of category Cat::Matrix |
x |
- | an indeterminate |
Returnsa polynomial of the domain
Dom::DistributedPolynomial([x],R), where
R is the component ring of A.
Related
Functionslinalg::charmat,
linalg::det, linalg::hessenberg, linalg::minpoly
DetailsA must be a commutative ring,
i.e., a domain of category Cat::CommutativeRing.
Example
1We 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)
Example
2We 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}
Backgroundlinalg::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