4. Some Results in Matrix Algebra
Let T: V → V be a linear transformation, where V is a vector space of dimension n over C. Recall that there is a natural isomorphism between EndC (V), the set of linear transformations on V and M (n, C), the set of all n×n matrices over C, specified by a given isomorphism between V and Cn.
1. Theorem. With V and T as above, there exists a nontrivial polynomial q(x) ∈ C[x], the ring of complex polynomials in one indeterminate, such q(T) = 0.
Proof. The space EndC (V) is n2 dimensional, so every set of n2 elements in this space is linearly dependent. Hence
Tn2 = a0I + a1T + ... + an2 - 1Tn2 - 1.
for some complex numbers a0, a1 + ... + an2 - 1Tn2 - 1. Set
q(x) = xn2 - an2 - 1xn2 - 1 - ... - a1x - a0
Then q(T) = 0 as required.
2. Corollary. Let J = {p(x) ∈ C[x] | p(T) = 0}. Then every element of J is a multiple of some polynomial qmin(x) such that qmin(T) = 0.
Proof. J is an ideal in C[x], which is a principal ideal domain. Thus J is generated by an element qmin(x) and clearly qmin(T) = 0.
3. Definition. The element qmin(x) in the above Corollary is called the minimal polynomial of T.
4. Definition. Suppose that
Tv = av
for some nonzero v ∈ V, with a ∈ C. Then v is called an eigenvector of T with eigenvalue a. a is an eigenvalue of T iff T - aI is nonsingular or, equivalently
det (T - aI) = 0.
The polynomial det (T - λI), which is of degree n and has leading coefficient ±1, is called the characteristic polynomial, and the equation det (T - λI) = 0 the characteristic equation of T.
5. The Cayley-Hamilton Theorem. Every matrix satisfies its own characteristic equation.
Proof. For the n×n matrix A, we can write
det (A - λI) = (-1)n + (-1)n - 1an - 1λn - 1 + ... + a2λ2 - a1λ + a0
We recall that
A . adj (A) = det (A) I
where adj (A) is the adjoint matrix of A. The adjoint of (A - λI) is a polynomial of degree n - 1 with matrix coefficients:
adj (A - λI) = C0 + C1λ + C2λ2 + ... + Cn - 1λn - 1
Hence
(A - λI)(C0 + C1λ + C2λ2 + ... + Cn - 1λn - 1)
= (a0 + a1λ + a2λ2 + ... + (-1)n - 1an - 1λn - 1 + (-1)nλn)I
Comparing coefficients of the powers of λ
AC0 = a0I
AC1 - C0 = - a1I
AC2 - C1 = a2I
..........
ACn - 2 - Cn - 1 = (-1)n - 1I
- Cn - 1 = (-1)nI
Multiplying these equations on the left by I, A, A2, ... , An, we get
a0I - a1A + a2A2 - ... + (-1)nAn = 0
which proves the theorem.
Remark. This theorem was actually fully proved by George Frobenius in 1878.
6. Proposition. Suppose p(x) = b0 + b1x + ... + bn - 1xn - 1 + xn ∈ C[x] is a monic polynomial. Then the matrix
C(p) = | / | 0 | 1 | 0 | ... | 0 | \ |
| | 0 | 0 | 1 | ... | 0 | | | |
| | ........ | | | |||||
| | 0 | 0 | 0 | ... | 1 | | | |
\ | - b0 | - b1 | - b2 | ... | - bn - 1 | / |
has minimal polynomial p(x).
C(p) is callled the companion matrix of p.
Proof. If e1, e2, ... , en are the standard basis vectors, that is, ei is the column vector with 1 in the i-th row and zero elsewhere, then
T ei = ei + 1, 1 ≤ i ≤ n - 1
and
T en = - (b0e1 + b1e2 + ... + bn - 1en)
Thus
en = - (b0 + b1T + ... + bn - 1Tn - 1)e1
But
en = T en - 1 = Tn - 1 e1
giving
p(T) e1 = 0
Since ei + 1 = Ti e1, 1 ≤ i ≤ n - 1, it follows that p(T) ei = 0 for all i; hence p(T) = 0.
Thus p(x) is a multiple of the minimal polynomial, and if it is a nontrivial multiple, the minimal polynomial would have lower degree, and we would have a relation er = ∑1 ≤ i ≤ r - 1 ei for some r ≤ n, a contradiction.
Remark. It is easily seen that the characteristic polynomial is (-1)n p(x).
7. Some Remarks on Computation.
7.1. By the above Proposition, the problem of finding the roots of a polynomial reduces to that of finding the eigenvalues of its companion matrix. This is believed to be the method used by MATHLAB.
7.2. From the Cayley-Hamilton Theorem, we see that if the first n - 1 powers of a matrix are known, as is the case with the companion matrix of a polynomial, the problem of finding higher powers reduces to polynomial multiplication modulo the characteristic polynomial. The naive algorithm for matrix multiplication has time complexity O(m*n), where m and n are the degrees of the polynomials, but we can do better than that.