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 + xnC[x] is a monic polynomial. Then the matrix

C(p) = /010...0\
|001...0|
|........|
|000...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.

----- PREVIOUS | CONTENTS | NEXT -----