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 End_C (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 Cⁿ.

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 End_C (V) is n² dimensional, so every set of n² elements in this space is linearly dependent. Hence

Tⁿ² = a₀I + a₁T + ... + a_{n² - 1}T^{n2 - 1}.

for some complex numbers a₀, a₁ + ... + a_{n² - 1}T^{n2 - 1}. Set

q(x) = xⁿ² - a_{n² - 1}x^{n2 - 1} - ... - a₁x - a₀

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 q_min(x) such that q_min(T) = 0.

Proof. J is an ideal in C[x], which is a principal ideal domain. Thus J is generated by an element q_min(x) and clearly q_min(T) = 0.

3. Definition. The element q_min(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)ⁿ + (-1)^{n - 1}a_{n - 1}λ^{n - 1} + ... + a₂λ² - a₁λ + a₀

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) = C₀ + C₁λ + C₂λ² + ... + C_{n - 1}λ^{n - 1}

Hence

(A - λI)(C₀ + C₁λ + C₂λ² + ... + C_{n - 1}λ^{n - 1})

= (a₀ + a₁λ + a₂λ² + ... + (-1)^{n - 1}a_{n - 1}λ^{n - 1} + (-1)ⁿλⁿ)I

Comparing coefficients of the powers of λ

AC₀ = a₀I

AC₁ - C₀ = - a₁I

AC₂ - C₁ = a₂I

..........

AC_{n - 2} - C_{n - 1} = (-1)^{n - 1}I

- C_{n - 1} = (-1)ⁿI

Multiplying these equations on the left by I, A, A², ... , Aⁿ, we get

a₀I - a₁A + a₂A² - ... + (-1)ⁿAⁿ = 0

which proves the theorem.

Remark. This theorem was actually fully proved by George Frobenius in 1878.

6. Proposition. Suppose p(x) = b₀ + b₁x + ... + b_{n - 1}x^{n - 1} + xⁿ ∈ C[x] is a monic polynomial. Then the matrix

has minimal polynomial p(x).

C(p) is callled the companion matrix of p.

Proof. If e₁, e₂, ... , e_n are the standard basis vectors, that is, e_i is the column vector with 1 in the i-th row and zero elsewhere, then

T e_i = e_{i + 1},   1 ≤ i ≤ n - 1

and

T e_n = - (b₀e₁ + b₁e₂ + ... + b_{n - 1}e_n)

Thus

e_n = - (b₀ + b₁T + ... + b_{n - 1}T^{n - 1})e₁

But

e_n = T e_{n - 1} = T^{n - 1} e₁

giving

p(T) e₁ = 0

Since e_{i + 1} = Tⁱ e₁, 1 ≤ i ≤ n - 1, it follows that p(T) e_i = 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 e_r = ∑_{1 ≤ i ≤ r - 1} e_i for some r ≤ n, a contradiction.

Remark. It is easily seen that the characteristic polynomial is (-1)ⁿ 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 -----