Eigenvalues

$\newenvironment {prompt}{}{} \newcommand {\Sec }[2]{\section {#1}} \newcommand {\trademark }[0]{{R\!\!\!\!\!\bigcirc }} \newcommand {\EXER }[0]{\section *{Exercises}} \newcommand {\CEXER }[0]{} \newcommand {\TEXER }[0]{} \newcommand {\R }[0]{\mbox {$\Bbb {R}$}} \newcommand {\C }[0]{\mbox {$\Bbb {C}$}} \newcommand {\Z }[0]{\mbox {$\Bbb {Z}$}} \newcommand {\N }[0]{\mbox {$\Bbb {N}$}} \newcommand {\D }[0]{\mbox {{\bf D}}} \newcommand {\setmin }[0]{\;\mbox {--}\;} \newcommand {\Matlab }[0]{{M\small {AT\-LAB}} } \newcommand {\Matlabp }[0]{{M\small {AT\-LAB}}} \newcommand {\computer }[0]{\Matlab Instructions} \newcommand {\half }[0]{\mbox {$\frac {1}{2}$}} \newcommand {\compose }[0]{\raisebox {.15ex}{\mbox {{\scriptsize $\circ $}}}} \newcommand {\AND }[0]{\quad \mbox {and}\quad } \newcommand {\vect }[2]{\left (\begin {array}{c} #1_1 \\ \vdots \\ #1_{#2}\end {array}\right )} \newcommand {\mattwo }[4]{\left (\begin {array}{rr} #1 & #2\\ #3 &#4\end {array}\right )} \newcommand {\mattwoc }[4]{\left (\begin {array}{cc} #1 & #2\\ #3 &#4\end {array}\right )} \newcommand {\vectwo }[2]{\left (\begin {array}{r} #1 \\ #2\end {array}\right )} \newcommand {\vectwoc }[2]{\left (\begin {array}{c} #1 \\ #2\end {array}\right )} \newcommand {\inv }[0]{^{-1}} \newcommand {\CC }[0]{{\cal C}} \newcommand {\CCone }[0]{\CC ^1} \newcommand {\Span }[0]{{\rm span}} \newcommand {\rank }[0]{{\rm rank}} \newcommand {\trace }[0]{{\rm tr}} \newcommand {\RE }[0]{{\rm Re}} \newcommand {\IM }[0]{{\rm Im}} \newcommand {\nulls }[0]{{\rm null\;space}} \newcommand {\dps }[0]{\displaystyle } \newcommand {\arraystart }[0]{\renewcommand {\arraystretch }{1.8}} \newcommand {\arrayfinish }[0]{\renewcommand {\arraystretch }{1.2}} \newcommand {\Start }[1]{\vspace {0.08in}\noindent {\bf Section~\ref {#1}}} \newcommand {\exer }[1]{\noindent {\bf \ref {#1}}} \newcommand {\ans }[0]{} \newcommand {\matthree }[9]{\left (\begin {array}{rrr} #1 & #2 & #3 \\ #4 & #5 & #6 \\ #7 & #8 & #9\end {array}\right )} \newcommand {\cvectwo }[2]{\left (\begin {array}{c} #1 \\ #2\end {array}\right )} \newcommand {\cmatthree }[9]{\left (\begin {array}{ccc} #1 & #2 & #3 \\ #4 & #5 & #6 \\ #7 & #8 & #9\end {array}\right )} \newcommand {\vecthree }[3]{\left (\begin {array}{r} #1 \\ #2 \\ #3\end {array}\right )} \newcommand {\cvecthree }[3]{\left (\begin {array}{c} #1 \\ #2 \\ #3\end {array}\right )} \newcommand {\cmattwo }[4]{\left (\begin {array}{cc} #1 & #2\\ #3 &#4\end {array}\right )} \newcommand {\thehelp }[0]{\thesection .\arabic {equation}} \newcommand {\matlabEquation }[0]{\let \oldtheequation \theequation \renewcommand {\theequation }{\oldtheequation *}\begin {equation}} \newcommand {\HyperFirstAtBeginDocument }[0]{\AtBeginDocument } \newcommand {\epstopdfsetup }[0]{\setkeys {ETE}} changed the theorem header of amsthm failed\MessageBreak }}} \newcommand {\GetTitleStringSetup }[0]{\setkeys {gettitlestring}} \newcommand {\Sectionformat }[2]{#1}$ $% This file was *autogenerated* from eigenvalues.sagetex.sage with % sagetex.py version 2015/08/26 v3.0-92d9f7a %c2e111f11438d2d16f981246f907655f% md5sum of corresponding .sage file (minus "goboom","current_tex_line",and pause/unpause lines)$

In this section we discuss how to find eigenvalues for an $n\times n$ matrix $A$ . This discussion parallels the discussion for $2\times 2$ matrices given in Section ??. As we noted in that section, $\lambda$ is a real eigenvalue of $A$ if there exists a nonzero eigenvector $v$ such that

$\begin{equation} \label{e:eigen} Av = \lambda v. \end{equation}$ It follows that the matrix $A-\lambda I_n$ is singular since $(A-\lambda I_n)v = 0.$ Theorem ?? implies that $\det (A-\lambda I_n) = 0.$ With these observations in mind, we can make the following definition.

Let $A$ be an $n\times n$ matrix. The characteristic polynomial of $A$ is: $p_A(\lambda ) = \det (A-\lambda I_n).$

In Theorem ?? we show that $p_A(\lambda )$ is indeed a polynomial of degree $n$ in $\lambda$ . Note here that the roots of $p_A$ are the eigenvalues of $A$ . As we discussed, the real eigenvalues of $A$ are roots of the characteristic polynomial. Conversely, if $\lambda$ is a real root of $p_A$ , then Theorem ?? states that the matrix $A-\lambda I_n$ is singular and therefore that there exists a nonzero vector $v$ such that (??) is satisfied. Similarly, by using this extended algebraic definition of eigenvalues we allow the possibility of complex eigenvalues. The complex analog of Theorem ?? shows that if $\lambda$ is a complex eigenvalue, then there exists a nonzero complex $n$ -vector $v$ such that (??) is satisfied.

Let $A$ be an $n\times n$ lower triangular matrix. Then the diagonal entries are the eigenvalues of $A$ . We verify this statement as follows. $A-\lambda I_n = \left (\begin {array}{ccc} a_{11}-\lambda & & 0 \\ & \ddots & \\ (*) & & a_{nn}-\lambda \end {array}\right ).$ Since the determinant of a triangular matrix is the product of the diagonal entries, it follows that $\begin{equation} \label{e:triangpoly} p_A(\lambda) = (a_{11}-\lambda)\cdots(a_{nn}-\lambda), \end{equation}$ and hence that the diagonal entries of $A$ are roots of the characteristic polynomial. A similar argument works if $A$ is upper triangular.

It follows from (??) that the characteristic polynomial of a triangular matrix is a polynomial of degree $n$ and that

$\begin{equation} \label{e:leadingterm} p_A(\lambda) = (-1)^n \lambda^n + b_{n-1}\lambda^{n-1} + \cdots +b_0. \end{equation}$ for some real constants $b_0, \ldots , b_{n-1}$ . In fact, this statement is true in general.

Let $A$ be an $n\times n$ matrix. Then $p_A$ is a polynomial of degree $n$ of the form (??).

Proof

Let $C$ be an $n\times n$ matrix whose entries have the form $c_{ij}+d_{ij}\lambda$ . Then $\det (C)$ is a polynomial in $\lambda$ of degree at most $n$ . We verify this statement by induction. It is easily verified when $n=1$ , since then $C=(c+d\lambda )$ for some real numbers $c$ and $d$ . Then $\det (C)=c+d\lambda$ which is a polynomial of degree at most one. (It may have degree zero, if $d=0$ .) So assume that this statement is true for $(n-1)\times (n-1)$ matrices. Recall from (??) that $\det (C) = (c_{11}+d_{11}\lambda )\det (C_{11}) +\cdots +(-1)^{n+1}(c_{1n}+d_{1n}\lambda )\det (C_{1n}).$ By induction each of the determinants $C_{1j}$ is a polynomial of degree at most $n-1$ . It follows that multiplication by $c_{1j}+d_{1j}\lambda$ yields a polynomial of degree at most $n$ in $\lambda$ . Since the sum of polynomials of degree at most $n$ is a polynomial of degree at most $n$ , we have verified our assertion.

Since $A-\lambda I_n$ is a matrix whose entries have the desired form, it follows that $p_A(\lambda )$ is a polynomial of degree at most $n$ in $\lambda$ . To complete the proof of this theorem we need to show that the coefficient of $\lambda ^n$ is $(-1)^n$ . Again, we verify this statement by induction. This statement is easily verified for $1\times 1$ matrices — we assume that it is true for $(n-1)\times (n-1)$ matrices. Again use (??) to compute

$\begin{align*} \det(A-\lambda I_n) &= (a_{11}-\lambda)\det(B_{11})-a_{12}\det(B_{12}) +\cdots \\ &\quad +(-1)^{n+1}a_{1n}\det(B_{1n}). \end{align*}$

where $B_{1j}$ are the cofactor matrices of $A-\lambda I_n$ . Using our previous observation all of the terms $\det (B_{1j})$ are polynomials of degree at most $n-1$ . Thus, in this expansion, the only term that can contribute a term of degree $n$ is: $-\lambda \det (B_{11}).$ Note that the cofactor matrix $B_{11}$ is the $(n-1)\times (n-1)$ matrix $B_{11} = A_{11} -\lambda I_{n-1},$ where $A_{11}$ is the first cofactor matrix of the matrix $A$ . By induction, $\det (B_{11})$ is a polynomial of degree $n-1$ with leading term $(-1)^{n-1}\lambda ^{n-1}$ . Multiplying this polynomial by $-\lambda$ yields a polynomial of degree $n$ with the correct leading term. $\blacksquare$

General Properties of Eigenvalues

The fundamental theorem of algebra states that every polynomial of degree $n$ has exactly $n$ roots (counting multiplicity). For example, the quadratic formula shows that every quadratic polynomial has exactly two roots. In general, the proof of the fundamental theorem is not easy and is certainly beyond the limits of this course. Indeed, the difficulty in proving the fundamental theorem of algebra is in proving that a polynomial $p(\lambda )$ of degree $n>0$ has one (complex) root. Suppose that $\lambda _0$ is a root of $p(\lambda )$ ; that is, suppose that $p(\lambda _0)=0$ . Then it is easy to show that

$\begin{equation} \label{e:factoring} p(\lambda) = (\lambda-\lambda_0)q(\lambda) \end{equation}$ for some polynomial $q$ of degree $n-1$ . So once we know that $p$ has a root, then we can argue by induction to prove that $p$ has $n$ roots.

Recall that a polynomial need not have any real roots. For example, the polynomial $p(\lambda )=\lambda ^2+1$ has no real roots, since $p(\lambda )> 0$ for all real $\lambda$ . This polynomial does have two complex roots $\pm i =\pm \sqrt {-1}$ .

However, a polynomial with real coefficients has either real roots or complex roots that come in complex conjugate pairs. To verify this statement, we need to show that if $\lambda _0$ is a complex root of $p(\lambda )$ , then so is $\overline {\lambda _0}$ . We claim that $p(\overline {\lambda })=\overline {p(\lambda )}.$ To verify this point, suppose that $p(\lambda ) = c_n\lambda ^n + c_{n-1}\lambda ^{n-1} + \cdots + c_0,$ where each $c_j\in \R$ . Then

$\begin{align*} \overline{p(\lambda)} \\ &=\overline{c_n\lambda^n + c_{n-1}\lambda^{n-1} + \cdots + c_0} \\ &= c_n\overline{\lambda}^n + c_{n-1}\overline{\lambda}^{n-1} + \cdots + c_0 \\ = p(\overline{\lambda}) \end{align*}$

If $\lambda _0$ is a root of $p(\lambda )$ , then $p(\overline {\lambda _0}) = \overline {p(\lambda _0)}=\overline {0}=0.$ Hence $\overline {\lambda _0}$ is also a root of $p$ .

It follows that

Every (real) $n\times n$ matrix $A$ has exactly $n$ eigenvalues $\lambda _1,\ldots ,\lambda _n$ . These eigenvalues are either real or complex conjugate pairs. Moreover,

(a): $p_A(\lambda ) = (\lambda _1-\lambda )\cdots (\lambda _n-\lambda )$ ,
(b): $\det (A) = \lambda _1\cdots \lambda _n$ .

Proof: Since the characteristic polynomial $p_A$ is a polynomial of degree $n$ with real coefficients, the first part of the theorem follows from the preceding discussion. In particular, it follows from (??) that $p_A(\lambda ) = c(\lambda _1-\lambda )\cdots (\lambda _n-\lambda ),$ for some constant $c$ . Formula (??) implies that $c=1$ — which proves (a). Since $p_A(\lambda )=\det (A-\lambda I_n)$ , it follows that $p_A(0)=\det (A)$ . Thus (a) implies that $p_A(0)=\lambda _1\cdots \lambda _n$ , thus proving (b). $\blacksquare$

The eigenvalues of a matrix do not have to be different. For example, consider the extreme case of a strictly triangular matrix $A$ . Example ?? shows that all of the eigenvalues of $A$ are zero.

We now discuss certain properties of eigenvalues.

Let $A$ be an $n\times n$ matrix. Then $A$ is invertible if and only if zero is not an eigenvalue of $A$ .

Proof: The proof follows from Theorem ?? and Theorem ??(b). $\blacksquare$

Let $A$ be a singular $n\times n$ matrix. Then the null space of $A$ is the span of all eigenvectors whose associated eigenvalue is zero.

Proof: An eigenvector $v$ of $A$ has eigenvalue zero if and only if $Av=0.$ This statement is valid if and only if $v$ is in the null space of $A$ . $\blacksquare$

Let $A$ be an invertible $n\times n$ matrix with eigenvalues $\lambda _1,\cdots ,\lambda _n$ . Then the eigenvalues of $A\inv$ are $\lambda _1\inv ,\cdots ,\lambda _n\inv$ .

Proof: We claim that $p_A(\lambda ) = (-1)^n \det (A) \lambda ^n p_{A\inv }(\frac {1}{\lambda }).$ It then follows that $\frac {1}{\lambda }$ is an eigenvalue for $A\inv$ for each eigenvalue $\lambda$ of $A$ . This makes sense, since the eigenvalues of $A$ are nonzero.
Compute:
$\begin{eqnarray*} (-1)^n \det(A) \lambda^n p_{A\inv}(\frac{1}{\lambda}) & = & (-\lambda)^n \det(A)\det(A\inv-\frac{1}{\lambda}I_n) \\ & = & \det(-\lambda A)\det(A\inv-\frac{1}{\lambda}I_n)\\ & = & \det(-\lambda A (A\inv-\frac{1}{\lambda}I_n))\\ & = & \det(A-\lambda I_n) \\ & = & p_A(\lambda), \end{eqnarray*}$
which verifies the claim. $\blacksquare$

Let $A$ and $B$ be similar $n\times n$ matrices. Then $p_A = p_B,$ and hence the eigenvalues of $A$ and $B$ are identical.

Proof: Since $B$ and $A$ are similar, there exists an invertible $n\times n$ matrix $S$ such that $B=S\inv AS$ . It follows that $\begin{align*} \det(B-\lambda I_n) &= \det(S\inv AS-\lambda I_n) \\ &= \det(S\inv(A-\lambda I_n)S) = \det(A-\lambda I_n), \end{align*}$
which verifies that $p_A=p_B$ . $\blacksquare$

Recall that the trace of an $n\times n$ matrix $A$ is the sum of the diagonal entries of $A$ ; that is ${\rm tr}(A) = a_{11} +\cdots + a_{nn}.$ We state without proof the following theorem:

Let $A$ be an $n\times n$ matrix with eigenvalues $\lambda _1,\ldots ,\lambda _n$ . Then ${\rm tr}(A) = \lambda _1 + \cdots + \lambda _n.$

It follows from Theorem ?? that the traces of similar matrices are equal.

MATLAB Calculations

The commands for computing characteristic polynomials and eigenvalues of square matrices are straightforward in MATLAB . In particular, for an $n\times n$ matrix $A$ , the MATLAB command poly(A) returns the coefficients of $(-1)^np_A(\lambda )$ .

For example, reload the $4\times 4$ matrix $A$ of (??) by typing e8_1_11. The characteristic polynomial of $A$ is found by typing

poly(A)

to obtain

ans =
1.0000 -5.0000 15.0000 -10.0000 -46.0000

Thus the characteristic polynomial of $A$ is: $p_A(\lambda ) = \lambda ^4 -5\lambda ^3+15\lambda ^2-10\lambda -46.$ The eigenvalues of $A$ are found by typing eig(A) and obtaining

ans =
  -1.2224
   1.6605 + 3.1958i
   1.6605 - 3.1958i
   2.9014

Thus $A$ has two real eigenvalues and one complex conjugate pair of eigenvalues. Note that MATLAB has preprogrammed not only the algorithm for finding the characteristic polynomial, but also numerical routines for finding the roots of the characteristic polynomial.

The trace of $A$ is found by typing trace(A) and obtaining

ans =
 
     5

Using the MATLAB command sum we can verify the statement of Theorem ??. Indeed sum(v) computes the sum of the components of the vector $v$ and typing

sum(eig(A))

we obtain the answer 5.0000, as expected.

Exercises

In Exercises ?? – ?? determine the characteristic polynomial and the eigenvalues of the given matrices.

$A = \left (\begin {array}{rrr} -9 & -2 & -10 \\ 3 & 2 & 3 \\ 8 & 2 & 9 \end {array}\right )$ .

$B = \left (\begin {array}{rrrr} 2 & 1 & -5 & 2 \\ 1 & 2 & 13 & 2 \\ 0 & 0 & 3 & -1 \\ 0 & 0 & 1 & 1 \end {array}\right )$ .

Find a basis for the eigenspace of $A = \left (\begin {array}{rrr} 3 & 1 & -1 \\ -1 & 1 & 1 \\ 2 & 2 & 0 \end {array}\right )$ corresponding to the eigenvalue $\lambda =2$ .

Consider the matrix $A = \left (\begin {array}{rrr} -1 & 1 & 1 \\ 1 & -1 & 1 \\ 1 & 1 & -1 \end {array}\right ).$

Verify that the characteristic polynomial of $A$ is $p_\lambda (A)=(\lambda -1)(\lambda +2)^2$ .
Show that $(1,1,1)$ is an eigenvector of $A$ corresponding to $\lambda =1$ .
Show that $(1,1,1)$ is orthogonal to every eigenvector of $A$ corresponding to the eigenvalue $\lambda =-2$ .

Consider the matrix $A=\mattwo {8}{5}{-10}{-7}$ .

Find the eigenvalues and eigenvectors of $A$ .
Show that the eigenvectors found in (a) form a basis for $\R ^2$ .
Find the coordinates of the vector $(x_1,x_2)$ relative to the basis in part (b).

Find the characteristic polynomial and the eigenvalues of $A = \left (\begin {array}{rrr} -1 & 2 & 2 \\ 2 & 2 & 2 \\ -3 & -6 & -6 \end {array}\right ).$ Find eigenvectors corresponding to each of the three eigenvalues.

Let $A$ be an $n\times n$ matrix. Suppose that $A^2 + A + I_n = 0.$ Prove that $A$ is invertible.

In Exercises ?? – ?? decide whether the given statements are true or false. If the statements are false, give a counterexample; if the statements are true, give a proof.

If the eigenvalues of a $2\times 2$ matrix are equal to $1$ , then the four entries of that matrix are each less than $500$ .

The trace of the product of two $n\times n$ matrices is the product of the traces.

When $n$ is odd show that every real $n\times n$ matrix has a real eigenvalue.

In Exercises ?? – ??, use MATLAB to compute (a) the eigenvalues, traces, and characteristic polynomials of the given matrix. (b) Use the results from part (a) to confirm Theorems ?? and ??.

$\begin{equation} A=\left( \begin{array}{rrrrr} -12 & -19 & -3 & 14 & 0\\ -12 & 10 & 14 & -19 & 8\\ 4 & -2 & 1 & 7 & -3\\ -9 & 17 & -12 & -5 & -8\\ -12 & -1 & 7 & 13 & -12 \end{array} \right). \end{equation}$

$\begin{equation} B=\left( \begin{array}{rrrrrr} -12 & -5 & 13 & -6 & -5 & 12\\ 7 & 14 & 6 & 1 & 8 & 18\\ -8 & 14 & 13 & 9 & 2 & 1\\ 2 & 4 & 6 & -8 & -2 & 15\\ -14 & 0 & -6 & 14 & 8 & -13\\ 8 & 16 & -8 & 3 & 5 & 19 \end{array} \right). \end{equation}$

Use MATLAB to compute the characteristic polynomial of the following matrix: $A = \left ( \begin {array}{rrr} 4 & -6 & 7\\ 2 & 0 & 5\\ -10 & 2 & 5 \end {array} \right )$ Denote this polynomial by $p_A(\lambda ) = -(\lambda ^3 + p_2 \lambda ^2 + p_1 \lambda + p_0)$ . Then compute the matrix $B = -(A^3 + p_2 A^2 + p_1 A + p_0 I).$ What do you observe? In symbols $B=p_A(A)$ . Compute the matrix $B$ for examples of other square matrices $A$ and determine whether or not your observation was an accident.