Short cuts to computing eigenvalues.

Abstract

We suggest some short cuts to compute eigenvalues be incorporated into standard elementary linear algebra texts. These shortcuts, whose proofs are quite elementary, have been classroom-tested and favored by our students over the usual methods. In addition to saving time and effort, these short cuts also underline and shed some light on the relationships that exist between several important concepts in linear algebra such as trace, determinant, block matrices, and eigenvalues.

Introduction

Whether one needs to find the stable state of the populations of coyotes and road runners living in Arizona, or to predict the long term winning record of a baseball team under certain assumptions based on its past record, or even to classify a quadratic form axsup(2) + 2bxy + cysup(2) + dx + ey + f = 0 as a parabola, hyperbola, ellipse, or a circle (we use xsup(n) to denote x raised to the power n), as well as to solve a host of other problems ranging from physics and economics to differential equations and dynamical systems, one customarily use techniques from linear algebra that depend on computing the eigenvalues of some associated matrices [4], Chapter 9. The eigenvalues of an n by n matrix A are the zeros of the characteristic polynomial of A. This is a polynomial f(x) of degree n that is equal to the determinant of the matrix A--xI(n) where I(n) represents the identity matrix of order n. Thus, finding the eigenvalues of an n by n matrix A involves the computation of the zeros of the characteristic polynomial of the matrix. For n = 2, the computation does not present any difficulty as one can use the quadratic formula. However, if the degree of the characteristic polynomial is larger than 2, the problem of computing its zeros may be very difficult, if not impossible, to compute exactly. Fortunately, the matrices considered in introductory linear algebra texts have been selected to ensure that they have eigenvalues that are not hard to compute.

In this note, we discuss several short cuts to compute the eigenvalues of a given matrix. These short cuts, although simple to present to elementary linear algebra students, are rarely presented in standard textbooks (there are a few textbooks, [1] and [2], that discuss one or two of these methods but never all of these methods). For typographical convenience, we will use the notation of the software MATLAB to write a matrix. For instance, A = [1, 2; 2, 3] denotes the 2 by 2 matrix

1 2

2 3

with rows [1, 2] and [2, 3]. In addition to the notation already used above for xsup(n) and I(n), the notation a(i, j) will be used to denote the entry in row i and column j, x(n) will denote that the subscript of x is n.

Definition

If A is an n by n matrix, then the trace of A, Tr(A), is defined as the sum of all elements on the main diagonal of A. Let x(1), ..., x(2), x(n) be the eigenvalues of A, listed with algebraic multiplicities.

Property 1 The determinant of A, det(A), is equal to the product of all the eigenvalues.

Property 2 Tr(A) is equal to the sum of all eigenvalues.

Proof of Property 1 Under the given assumptions, the characteristic polynomial factors completely, and we can write det(A - xI(n)) = (x(1) - x)(x(2) - x) ... (x(n) - x). Letting x = 0 gives det(A) = x(1)x(2)... x(n).

Proof of 2 The characteristic polynomial f(x) can be written as (- x)sup(n) + Tr(A)(- x)sup(n-1) + .... + det(A) (see [1], page 308). It can also be written as the product (x(l) - x)(x(2) - x) ...(x(n) - x). Equating the coefficients of (-x)sup(n-1) in both expressions yields Tr(A) = x(1) + ... + x(n).

Property 3 Let A be a matrix of the form [M, N; O, P] where M and P are square matrices, O is a zero matrix, and N is a matrix not necessarily square. The characteristic polynomial of A is the product of the characteristic polynomials of the matrices M and P. The proof is based on the fact that the determinant of IX, Y; O, Z] is equal to the product of the determinants of X and Z. This implies that the characteristic polynomial of A is equal to the product of the characteristics polynomials of M and P. This result can be proved by induction on the size of P. First, we fix the size of M as n, say. Keeping n fixed, we prove the result when the size of P is 1 by 1 (write the determinant of A as an expansion along row n + 1). Assuming the result is true when the size of P is m and we prove it true for when the size of P is m + 1. This can be done by writing the determinant of A as an expansion along row n + m.

Note The same result holds if the matrix is of the form [X, O; Y, Z].

Property 4 If the sum of the entries of each row in A is equal to the same number k, then k itself is an eigenvalue that corresponds to the eigenvector [1; 1; ... ; 1]. (A probability matrix A, for instance, will have 1 as an eigenvalue associated with the eigenvector [l; 1; ... ;1].)

The proof is based on the fact that a number k is an eigenvalue of A if A times X is equal to k times X for some non-zero vector X. We prove that [l 1; ...; l] is an eigenvector. In fact, the product of A and the vector [l;...;i] is equal to [a(l, 1)+a(1,2)+ ...+a(1,n); ....; a(n, 1)+ ... + a(n, n)]. This is equal to [k; k; ...;k] or k[1; 1; ...;1].

Note If the entries in each column of A add up to the same number k, then k will still be an eigenvalue although [1, 1; ... ; 1] may not still be an eigenvector. Now we are ready to show some specific examples.

Example 1 Consider the matrix [1, l; -2, 4]. In display form, this looks like

1 1

-2 4.

The trace is equal to 5 and the determinant is equal to 6. By Properties 1 and 2, we know that the sum of the eigenvalues is 5 and that their product is 6. Therefore the two eigenvalues must be 3 and 2.

Example 2 Consider the matrix [1, 0, 1, 0, 1, 1, 1, 1, 0]. Since the rows add up to 2, by Property 4, 2 must be an eigenvalue. Since the trace is equal to 2, the other two eigenvalues must add up to zero. Since the determinant is -2, we have two numbers that add up to zero and that their product is -l. The eigenvalues must be 2, l, and -1.

Example 3 Consider the matrix [k, k, k; k, k, k; k, k, k]. First, by a well-known property of determinants, the determinant of this matrix is equal to zero (two identical rows). By Property 4, one eigenvalue must be equal to 3k (the sum of each row). By Property 1, another eigenvalue must be equal to 0 (since the determinant is zero). Since the trace is equal to 3k, by Property 2, the third and last eigenvalue must also be equal to 0.

Example 4 Consider the matrix [1, 0, 2; 2, 1, 1; 0, 0, 1]. Instead of computing the eigenvalues of a 3 by 3 matrix, we partition the matrix into smaller submatrices called blocks. Using Property 3, we can compute the eigenvalues of the block [1, 0; 2, 1] and [1]. For the first block, we have the sum of the eigenvalues equal 2 and their product equal 1. So they must be both equal to 1. The eigenvalue of the matrix [1] is 1. So all three eigenvalues are equal to 1.

Example 5 Consider the matrix [5, 3, 0; -3, -5, 0; 2, -3, 1]. We look at the block matrices [5, 3; -3, 5] and [1]. Using Properties 1 and 2, since the trace is 0 and the determinant is 16 for the block [5, 3; -3, 5], its eigenvalues are 4 and -4. So the eigenvalues of the original matrix are -4, 1, and 4.

Example 6 Consider the matrix [3, -1, 1, 1, 2; -2, 2, 5, 4, 3; 0, 0, 1, 0, 2; 0, 0, 2, 3, -2; 0, 0, 2, 2, 5]. In display form, this looks as follows:

 3   -1   1   1   2
-2    2   5   4   3
 0    0   1   0   2
 0    0   2   2   5.

By Property 3, we can look at the blocks [3, -1; -2, 2] and [1, 0, 2; 2, 3, -3, -2; 2, 2, 5]. For the first block, we have the trace is 5 and the determinant is 4. So the eigenvalues here have sum 5 and product 4 and so they must be 1 and 4. For the block [1, 0, 2; 2, 3, -2; 2, 2, 5], we notice that each column adds up to 5. Therefore, 5 is an eigenvalue by Property 4. We also have the trace equal 9 and the determinant equal 15 for this block. It follows that the remaining two eigenvalues for this block have sum 4 and product 3. So they must be 1 and 3. Hence the eigenvalues for the original matrix are 1 (multiplicity 2), 3, 4, 5.

Conclusion

As can be seen from the above examples, there are easy short cuts to computing eigenvalues that are simple to present to elementary linear algebra students. We think it is worthwhile for these short cuts to be incorporated into the standard textbooks for the benefit of the students. In addition to offering a tremendous simplification in calculations, as Examples 3 through 6 illustrate, which allows for more class time spent on concepts, they also offer insights into problem solving techniques at work. Namely, the idea of breaking a problem into several easier ones (Example 6) and the idea of recognizing a pattern in order to generalize a solution to a certain problem (Example 3). These short cuts also show a connection between several concepts within the strand. Namely, the relation between the trace, the determinant, and the blocks of a certain matrix. It is worthwhile to mention in this context that usually it is impossible to find the exact eigenvalues of a matrix. Even approximating eigenvalues, as numerical analysts tell us, could be challenging as far as the techniques used for the approximation. In fact, a recent text in numerical linear algebra [1] characterizes the eigenvalue problem as "the third major problem area in matrix computations," after linear equations and least squares.

References

[1] O. Brestcher, Linear Algebra with Applications, Third edition, Pearson Prentice Hall, 2005.

[2] M. R. Adams and T. Shifrin, Linear Algebra, A Geometric Approach, Freeman and Company, 2002.

[3] G.H. Golub and C.F. Van Loan, Matrix Computation, Third edition, Johns Hopkins University To Press, 1996.

[4] D. Hill and B. Kolman, Introductory Linear Algebra, An Applied Course, Eighth edition, Pearson Prentice Hall, 2005.

Russell Euler, Northwest Missouri State University Jawad Sadek, Northwest Missouri State University

Russell Euler, Ph.D, is a Professor of Mathematics at Northwest Missouri State University, and Jawad Sadek, Ph.D, is an Associate Professor of Mathematics at Northwest Missouri State University. Both authors are interested in ways to improve undergraduate curriculum.