INTRODUCTION

It is sometimes important to be able to quickly compute a power A^m, m a positive integer, of an n × n matrix A:

Of course, computation of A^m could be done with the appropriate software or by writing a short computer program, but even then, you should be aware that it is inefficient to simply use brute force to carry out repeated multiplications: A² = AA, A³ = AA², A⁴ = AAAA = A(A³) = A²A², and so on.

Computation of A^m

We are going to sketch an alternative method for computing A^m by means of the following theorem known as the Cayley–Hamilton theorem.

If (−1)ⁿλⁿ + c_n−1λⁿ⁻¹ + . . . + c₁λ + c₀ = 0 is the characteristic equation of A, then Theorem 8.9.1 states that by replacing λ by A we have

(−1)ⁿAⁿ + c_n−1Aⁿ⁻¹ + . . . + c₁A + c₀I = 0. (1)

Matrices of Order 2

The characteristic equation of the 2 × 2 matrix A = is λ² − λ − 2 = 0, and the eigenvalues of A are λ₁ = −1 and λ₂ = 2. Theorem 8.9.1 implies A² − A − 2I = 0, or, solving for the highest power of A,

A² = 2I + A. (2)

Now if we multiply (2) by A, we get A³ = 2A + A², and if we use (2) again to eliminate A² on the right side of this new equation, then

A³ = 2A + A² = 2A + (2I + A) = 2I + 3A.

Continuing in this manner—in other words, multiplying the last result by A and using (2) to eliminate A²—we obtain in succession powers of A expressed solely in terms of the identity matrix I and A:

(3)

and so on (verify). Thus, for example,

(4)

Now we can determine the c_k without actually carrying out the repeated multiplications and resubstitutions as we did in (3). First, note that since the characteristic equation of the matrix A = can be written λ² = 2 + λ, results analogous to (3) must also hold for the eigenvalues λ₁ = −1 and λ₂ = 2; that is, λ³ = 2 + 3λ, λ⁴ = 6 + 5λ, λ⁵ = 10 + 11λ, λ⁶ = 22 + 21λ, . . . . It follows then that the equations

A^m = c₀I + c₁A and λ^m = c₀ + c₁λ (5)

hold for the same pair of constants c₀ and c₁. We can determine the constants c₀ and c₁ by simply setting λ = −1 and λ = 2 in the last equation in (5) and solving the resulting system of two equations in two unknowns. The solution of the system

is c₀ = [2^m + 2(−1)^m], c₁ = [2^m − (−1)^m]. Now by substituting these coefficients in the first equation in (5), adding the two matrices and simplifying each entry, we obtain

(6)

You should verify the result in (4) by setting m = 6 in (6). Note that (5) and (6) are valid for m ≥ 0 since A⁰ = I and A¹ = A.

Matrices of Order n

If the matrix A were 3 × 3, then the characteristic equation (1) is a cubic polynomial equation, and the analogue of (2) would enable us to express A³ in terms of I, A, and A². We could proceed as just illustrated to write any power A^m in terms of I, A, and A². In general, for an n × n matrix A, we can write

A^m = c₀I + c₁A + c₂A² + . . . + c_n−1Aⁿ⁻¹,

and where each of the coefficients c_k, k = 0, 1, . . ., n − 1, depends on the value of m.

EXAMPLE 1 A^m for a 3 × 3 Matrix

Compute A^m for A = .

SOLUTION

The characteristic equation of A is −λ³ + 2λ² + λ − 2 = 0 or λ³ = −2 + λ + 2λ², and the eigenvalues are λ₁ = −1, λ₂ = 1, and λ₃ = 2. From the preceding discussion we know that the same coefficients hold in both of the following equations:

A^m = c₀I + c₁A + c₂A² and λ^m = c₀ + c₁λ + c₂λ². (7)

Setting, in turn, λ = −1, λ = 1, λ = 2 in the last equation generates three equations in three unknowns:

(8)

Solving (8) gives

After computing A², we substitute these coefficients into the first equation of (7) and simplify the entries of the resulting matrix. The result is

For example, with m = 10,

≡

Finding the Inverse

Suppose A is a nonsingular matrix. The fact that A satisfies its own characteristic equation can be used to compute A⁻¹ as a linear combination of powers of A. For example, we have just seen that the nonsingular matrix A = satisfies A² − A − 2I = 0. Solving for the identity matrix gives I = A² − A. By multiplying the last result by A⁻¹, we find A⁻¹ = A − I. In other words,

(9)

8.9 Exercises Answers to selected odd-numbered problems begin on page ANS-19.

In Problems 1 and 2, verify that the given matrix satisfies its own characteristic equation.

In Problems 3–10, use the method of this section to compute A^m. Use this result to compute the indicated power of the matrix A.

In Problems 11 and 12, show that the given matrix has an eigenvalue λ₁ of multiplicity two. As a consequence, the equations λ^m = c₀ + c₁λ (Problem 11) and λ^m = c₀ + c₁λ + c₂λ² (Problem 12) do not yield enough independent equations to form a system for determining the coefficients c_i. Use the derivative (with respect to λ) of each of these equations evaluated at λ₁ as the extra needed equation to form a system. Compute A^m and use this result to compute the indicated power of the matrix A.

11. 
12. 
13. Show that λ = 0 is an eigenvalue of each matrix. In this case, the coefficient c₀ in the characteristic equation (1) is 0. Compute A^m in each case. In parts (a) and (b), explain why we do not have to solve any system for the coefficients c_i in determining A^m.

    (a)

    (b)

    (c)

14. Leonardo of Pisa (1170–c.1250), also known as Fibonacci, was an Italian mathematician from the Republic of Pisa. His work Liber Abaci (Book of Calculation), first published in 1202, was a strong advocation of the value and practical use of the new Hindu-Arabic numeral system. In Liber Abaci Leonardo also speculated on the reproduction of rabbits:

    How many pairs of rabbits will be produced in a year beginning with a single pair, if every month each pair bears a new pair which become productive from the second month on?

    The answer to his question is contained in a sequence known as a Fibonacci sequence.

    

    Each of the three rows describing rabbit pairs is a Fibonacci sequence and can be defined recursively by a second-order difference equation x_n = x_n−2 + x_n−1, n = 2, 3, . . . , where x₀ and x₁ depend on the row. For example, for the first row designating adult pairs of rabbits, x₀ = 1, x₁ = 1.

    1. If we let y_n−1 = x_n−2, then y_n = x_n−1, and the difference equation can be written as a system of first-order difference equations

       

       Write this system in the matrix form X_n = AX_n−1, n = 2, 3, . . . .

    2. Show that

       

       or

       

       where λ₁ = (1 − ) and λ₂ = (1 + ) are the distinct eigenvalues of A.

    3. Use the result in part (a) to show X_n = Aⁿ⁻¹X₁. Use the last result and the result in part (b) to find the number of adult pairs, baby pairs, and total pairs of rabbits after the twelfth month.

In Problems 15 and 16, use the procedure illustrated in (9) to find A⁻¹.

15. 
16. 
17. A nonzero n × n matrix A is said to be nilpotent of index m if m is the smallest positive integer for which A^m = 0. Which of the following matrices are nilpotent? If nilpotent, what is its index?

    (a)

    (b)

    (c)

    (d)

    (e)

    (f)

18. (a) Explain why any nilpotent matrix A is singular. [Hint: Review Section 8.5.] (b) Show that all the eigenvalues of a nilpotent matrix A are 0. [Hint: Use (1) of Section 8.8.]