No Title

Notes on Jordan Normal (Canonical) Form
Math 5718 - Spring 2001

We have seen several results that give conditions under which certain special classes of matrices (operators) can be diagonalized. Remember that diagonalizing a matrix requires finding a basis with respect to which the matrix is diagonal. Equivalently, it means finding a diagonal matrix that is similar to the given matrix. For general $n \times n$ matrices with fewer than n linearly independent eigenvectors, diagonalization is not possible. The best we can do (the closest we can come to representing the matrix in diagonal form) is the Jordan form. We begin by stating the theorem; then we will look at examples to understand how to interpret it.¹ Theorem. An $n \times n$ matrix with s linearly independent eigenvectors is similar to a matrix J that has the form

$\begin{displaymath}J = P^{-1}AP = \left( \begin{array}{ccccc} J_1 &&&&\\ & J... ...ts &&\\ && \ddots &&\\ &&&J_s &\\ \end{array} \right), \end{displaymath}$

where the diagonal blocks (called Jordan blocks) have the form

$\begin{displaymath}J_i = \left( \begin{array}{ccccc} \lambda_i &1 &&&\\ & \lam... ... &&\\ && \ddots &&\\ &&&\lambda_i &\\ \end{array} \right), \end{displaymath}$

and $\lambda_i$ is an eigenvalue of A. In the special case that A has n linearly independent eigenvectors, the diagonal blocks are $1 \times 1$ , and J is a strictly diagonal matrix. In the general case, the diagonal blocks are ``nearly diagonal,'' and J is block diagonal. Let's look at a specific example. Suppose that A is a $5 \times 5$ matrix with eigenvalues $\lambda= 0$ and $\lambda=4$ that is already in Jordan form:

$\begin{displaymath}J = A = \left( \begin{array}{ccccc} 4 &1 &0&0&0\\ 0& 4 &0 &... ...\ 0&0&0&1&0\\ 0&0&0&0&0\\ 0&0&0&0&0\\ \end{array} \right). \end{displaymath}$

The position of the 1's on the off diagonal are important in identifying the blocks. In this case, there are three blocks:

$\begin{displaymath}J_1 = \left( \begin{array}{cc} 4 &1 \\ 0& 4 \\ \end{arr... ...d J_3 = \left( \begin{array}{c} 0 \\ \end{array} \right) \end{displaymath}$

We might already anticipate that A has three linearly independent eigenvectors, corresponding to the three diagonal blocks; but we need to understand why the blocks have the sizes they do and why the eigenvalue 0 appears in two different blocks. We can learn a lot by examining the representation J = P^-1AP. Suppose that the columns of P are denoted v_i for $i=1, \ldots n$ . Writing J = P^-1AP in the form AP=PJ, we have

$\begin{displaymath}A \left( \begin{array}{ccccc} v_1 &v_2 &v_3 &v_4 &v_5 \\ \v... ...\ 0&0&0&1&0\\ 0&0&0&0&0\\ 0&0&0&0&0\\ \end{array} \right). \end{displaymath}$

Looking at these products by columns, we see that

Av₁ = 4 v₁	$\textstyle \quad$	Av₂ = 4 v₂+v₁	(1)
$\displaystyle Av_3 = 0 \cdot v_3$	$\textstyle \quad$	$\displaystyle Av_4 = 0 \cdot v_4+v_3$	(2)
$\displaystyle Av_5= 0 \cdot v_5$	$\textstyle \quad$		(3)

It is clear that v₁,v₃, and v₅ are ordinary eigenvectors, as they satisfy $Ax=\lambda x$ . Notice that these eigenvectors correspond to the upper left element of each Jordan block. However, v₂ and v₄ do not satisfy the usual eigenvector-eigenvalue relations; instead they are related to one of the other ordinary eigenvectors. These ``near eigenvectors'' are called generalized eigenvectors. We say that v₁ and v₂ form a string corresponding to equations (

). The length of this string corresponds to the $2 \times 2$ dimensions of the first Jordan block. Similarly, equations (

) define another string of length two consisting of v₃ and v₄ (corresponding to the dimensions of the second Jordan block). Finally, v₅ forms a string of length one. The process of finding the Jordan form of a matrix A amounts to finding the columns of P, which are the eigenvectors and generalized eigenvectors of A. Said differently, finding the Jordan form for a matrix A amounts to finding a basis with respect to which A can be represented in Jordan form. Such a basis is called a Jordan basis. We have defined a generalized eigenvector as a vector v_i that satisfies a relation of the form

$\begin{displaymath}Av_i = \lambda_i v_i + v_{i-1}, \end{displaymath}$

where v_i-1 is an ordinary eigenvector. It's useful to make a connection to an equivalent definition of generalized eigenvector (the one used by Axler). If v_i-1 is an ordinary eigenvector corresponding to the eigenvalue $\lambda_i$ , then we have $(A-\lambda_i I) v_{i-1} = 0$ ; of course, it follows that $(A-\lambda_i I)^k v_{i-1} = 0$ for all positive integers k. For a generalized eigenvector, v_i, we have

$\begin{displaymath}(A-\lambda_i I) v_i = v_{i-1} \quad \mbox{and} \quad (A-\lambda_i I)^2 v_i = (A-\lambda_i I) v_{i-1} = 0. \end{displaymath}$

It follows that $(A-\lambda_i I)^k v_i = 0$ for all positive integers $k \ge 2$ . Thus, a generalized eigenvector can also be defined as a vector for which $(A-\lambda_i I)^k v_i = 0$ for all positive integers $k \ge m$ . The integer m gives the dimension of the Jordan block associated with $\lambda_i$ and v_i-1. These observations should make the following conclusions evident. These statements cover the situation in which there may be more than one generalized eigenvector associated with a particular Jordan block. Suppose that J is an $m \times m$ Jordan block with $\lambda$ on the diagonal. Then

$(J-\lambda I) v_i = v_{i-1}$ for $1 < i \le m$ , and $(J-\lambda I) v_1 =0$ (that is, v₁ is an ordinary eigenvector and $v_2, \ldots, v_m$ are generalized eigenvectors).
$(J-\lambda I)^m=0$ , but $(J-\lambda I)^i \ne 0$ for i<m.

Example: Another example should help clarify and extend these ideas. Now consider the following matrix in Jordan form.

$\begin{displaymath}J=\left( \begin{array}{ccccccc} 4 &1 &0&0&0&0&0\\ 0& 4 &1... ... 0&0&0&0&0&-2&1\\ 0&0&0&0&0&0&-2\\ \end{array} \right). \end{displaymath}$

We see that J consists of three Jordan blocks, one of which is $3 \times 3$ and two of which are $2 \times 2$ . Let's begin by finding the effect of J on the standard basis vectors, e_i, of ${\bf R}^7$ (for example, e₄=(0,0,0,1,0,0)). The first Jordan block forms a string consists of e₁,e₂, and e₃:

$\begin{displaymath}Je_3=4e_3+e_2 \quad Je_2=4e_2+e_1 \quad Je_1=4e_1 \quad \mbox{or} \quad e_3 \rightarrow e_2 \rightarrow e_1. \end{displaymath}$

The second Jordan block forms a string consisting of e₄ and e₅:

$\begin{displaymath}Je_5=4e_5+e_4 \quad Je_4=4e_4 \quad \mbox{or} \quad e_5 \rightarrow e_4. \end{displaymath}$

The third Jordan block forms a string consisting of e₆ and e₇:

$\begin{displaymath}Je_7=-2e_7+e_6 \quad Je_6=-2e_6 \quad \mbox{or} \quad e_7 \rightarrow e_6. \end{displaymath}$

We see that J has two eigenvalues, $\lambda=4$ (corresponding to e₁ and e₄) and $\lambda= -2$ (corresponding to e₆). Let's recall some terminology already introduced in class. We say that $\lambda=4$ has algebraic multiplicity 5, as it appears on the diagonal 5 times. (Alternatively, the characteristic polynomial for J would have a term $(\lambda-4)^5$ .) Because (J-4I)e₁=0 and (J-4I)e₄=0, we see that null (J-4I) is spanned by $\{e_1,e_4\}$ and dim null (J-4I) =2. Thus, the geometric multiplicity of $\lambda=4$ is 2. Similarly, $\lambda= -2$ has algebraic multiplicity 2 and because null (J+2I) is spanned by e₆, dim null (J+2I) =1. Thus, the geometric multiplicity of $\lambda= -2$ is 1. Notice that if the geometric multiplicity of an eigenvalue equals its algebraic multiplicity, then all blocks associated with the eigenvalue are $1 \times 1$ . If this equality holds for all eigenvalues of the matrix, the Jordan form is strictly diagonal (the matrix is diagonalizable). A general rule emerges from these observations: The algebraic multiplicity of an eigenvalue is the number of times that eigenvalue appears on the diagonal, while the geometric multiplicity of an eigenvalue is the number of different blocks that contain the eigenvalue. But these observations are not enough to tell us the exact size of each block; for example, an eigenvalue with algebraic multiplicity 5 and geometric multiplicity 2 could have blocks of size (1,4) or (2,3). So we need to look again at the strings associated with the eigenvalue. We will return to the previous example and look at the powers of $(J- \lambda I)$ . We have already seen that null (J-4I) is spanned by $\{e_1,e_4\}$ and has dimension 2. It is easy to check that null (J-4I)² is spanned by $\{e_1,e_2,e_4,e_5\}$ and has dimension 4. Equally important, these four vectors are related by the strings

$\begin{displaymath}e_2 \rightarrow e_1 \quad \mbox{and} \quad e_5 \rightarrow e_4. \end{displaymath}$

We also have that null (J-4I)³ is spanned by $\{e_1,e_2,e_3,e_4,e_5\}$ and has dimension 5. These five vectors are related by the strings

$\begin{displaymath}e_3 \rightarrow e_2 \rightarrow e_1 \quad \mbox{and} \quad e_5 \rightarrow e_4. \end{displaymath}$

Finally notice that for $k\ge 3$ , null (J-4I)^k is also spanned by $\{e_1,e_2,e_3,e_4,e_5\}$ and has dimension 5. We have now accounted for all five eigenvectors and generalized eigenvectors associated with $\lambda=4$ . The lengths of the strings leading to each eigenvector (3 and 2) give the size of the Jordan blocks. Similarly, for $\lambda= -2$ , null (J+2I) is spanned by e₆ and has dimension 1, while null (J-4I)² is spanned by $\{e_6,e_7 \}$ and has dimension 2. The relevant string is

$\begin{displaymath}e_7 \rightarrow e_6. \end{displaymath}$

For $k \ge 2$ , null (J-4I)^k is also spanned by $\{e_6,e_7 \}$ and has dimension 2. The length of this string gives us the size of the Jordan block associated with $\lambda= -2$ . It's time to put all these ideas together and find the Jordan form and a Jordan basis for a specific matrix A. The process consists of four steps:

Find the eigenvalues of A and their algebraic multiplicity.
Determine the geometric multiplicity of the eigenvalues by finding dim null $(A-\lambda I)$ .
Form the strings associated with each ordinary eigenvector by examining the powers of $(A-\lambda I)$ .
Use all this information to assemble the Jordan form and find a Jordan basis.

Example: Find the Jordan form for the matrix²

$\begin{displaymath}A= \left( \begin{array}{ccccc} 2 &5 &0&0&1\\ 0& 2 &0 &0&0\\... ...&-1&0&0\\ 0&0&0&-1&0\\ 0&0&0&0&-1\\ \end{array} \right). \end{displaymath}$

The eigenvalues of this upper triangular matrix are on the diagonal. We see that $\lambda_1=2$ has algebraic multiplicity 2 and $\lambda_2=-1$ has algebraic multiplicity 3. To analyze $\lambda_1$ , we consider

$\begin{displaymath} A-\lambda_1 I = A-2I = \left( \begin{array}{ccccc} 0 &5 ... ...&-3&0&0\\ 0&0&0&-3&0\\ 0&0&0&0&-3\\ \end{array} \right). \end{displaymath}$

(4)

Perhaps the easiest way to find the dimension of null (A-2I) is to note that rank (A-2I) = 4 (because there are four linearly independent rows); therefore, dim null (A-2I)=5-4=1 (note that $A: {\bf R}^5 \rightarrow {\bf R}^5$ ). A little work shows that

$\begin{displaymath} (A-\lambda_1 I)^2 = (A-2I)^2 = \left( \begin{array}{ccccc... ...\ 0&0&9&0&0\\ 0&0&0&9&0\\ 0&0&0&0&9\\ \end{array} \right). \end{displaymath}$

(5)

We see that (A-2I)² has three linearly independent rows, which means that rank (A-2I)²=3 and dim null (A-2I)²=5-3=2. Note also that the upper left $2 \times 2$ block corresponding to $\lambda_1$ consists of zeros. One more calculation shows us that

$\begin{displaymath}(A-\lambda_1 I)^3 = (A-2I)^3 = \left( \begin{array}{ccccc} ... ...7&0&0\\ 0&0&0&-27&0\\ 0&0&0&0&-27\\ \end{array} \right). \end{displaymath}$

We see that dim null (A-2I)³ = 2, which is the same as dim null (A-2I)². Thus, we expect to have one ordinary eigenvector that satisfies Av₁=2v₁ and one generalized eigenvector that satisfies Av₂=2v₂+v₁. From this observation, we see that the eigenvalue $\lambda_1=2$ has the single Jordan block

$\begin{displaymath}J_1 = \left( \begin{array}{cc} 2 &1 \\ 0& 2 \end{array} \right). \end{displaymath}$

Let's also find the eigenvectors associated with this block. The ordinary eigenvector satisfies Av₁=2v₁. Referring to (

), we see that v₁ is any multiple of (1,0,0,0,0)^T. The generalized eigenvector satisfies Av₂=2v₂+v₁, which gives us v₂=(0,1/5,0,0,0)^T. Alternatively, we could have first found v₂ as any vector in null (A-2I)² that is not in null (A-2I). Using (

) we see that v₂ can be any multiple of (0,1,0,0,0)^T. We can then use Av₂=2v₂+v₁ or v₁ = Av₂-2v₂ to find v₁=(5,0,0,0,0)^T. A similar analysis of the eigenvalue $\lambda_2=-1$ requires

$\begin{displaymath} A-\lambda_2 I = A+I = \left( \begin{array}{ccccc} 3 &5 &... ...\ 0&0&0&0&0\\ 0&0&0&0&0\\ 0&0&0&0&0\\ \end{array} \right). \end{displaymath}$

(6)

We see that rank (A+I)=2 and dim null (A+I)=5-2=3. Thus, both the algebraic and geometric multiplicity of $\lambda_2$ are 3. This means that there are three $1 \times 1$ Jordan blocks associated with $\lambda_2=-1$ ; they are J₂=J₃=J₄ = [-1]. Alternatively, you can check that dim null (A+I)²=3 which equals dim null (A+I). The eigenvectors associated with $\lambda_2$ must form a basis for null (A+I). Referring to (

), we see that null (A+I) is spanned by (0,0,1,0,0)^T, (0,0,0,1,0)^T, (-1,0,0,0,3)^T. Assembling all of these observations, the Jordan form for A is

$\begin{displaymath}J= \left( \begin{array}{ccccc} 2 &1 &0&0&1\\ 0& 2 &0 &0&0\\... ...&-1&0&0\\ 0&0&0&-1&0\\ 0&0&0&0&-1\\ \end{array} \right). \end{displaymath}$

The matrix P that gives the similarity transformation between A and J has columns consisting of the eigenvectors:

$\begin{displaymath}P= \left( \begin{array}{ccccc} 5 &0 &0&0&-1\\ 0& 1 &0 &0&0\\ 0&0&1&0&0\\ 0&0&0&1&0\\ 0&0&0&0&-3\\ \end{array} \right). \end{displaymath}$

You can verify that J=P^-1AP. Example: Find the Jordan form for an $11 \times 11$ matrix A with the following properties.

dim null (A-3I)=2.
dim null (A-3I)²=4.
dim null (A-3I)^k=5 for $k\ge 3$ .
dim null (A+2I)=1.
dim null (A+2I)²=2.
dim null (A+2I)³=3.
dim null (A+2I)^k=4 for $k \ge 4$ .
dim null (A-I)=2.
dim null (A-I)^k=2 for $k \ge 2$ .

We see that there are three distinct eigenvalues, $\lambda_1=3, \lambda_2=-2$ , and $\lambda_3=1$ . For each eigenvalue, we must at least count the ordinary and generalized eigenvectors. $\lambda_1=3$ : Because dim null (A-3I)=2, the geometric multiplicity of $\lambda_1$ is 2 and we should expect two Jordan blocks. We also expect to have two ordinary eigenvectors for this eigenvalue; call them v₁ and v₄ . To determine the size of the blocks, we must look at higher powers of (A-3I). Because dim null (A-3I)²=4, there are four eigenvectors that span (A-3I)²: the two ordinary eigenvectors and two new generalized eigenvectors. Call the new generalized eigenvectors v₂ and v₅. Now note that dim null (A-3I)³=5, so there is another generalized eigenvector; call it v₃. Because dim null (A-3I)^k=5 for $k\ge 3$ , there are no additional generalized eigenvectors. This analysis produces two strings associated with $\lambda_1$ ; they are

$\begin{displaymath}v_3 \rightarrow v_2 \rightarrow v_1 \quad \mbox{and} \quad v_5 \rightarrow v_5. \end{displaymath}$

Knowing that there are five eigenvectors associated with $\lambda_1=3$ , we conclude that 3 will appear on the diagonal of the Jordan form 5 times and that the algebraic multiplicity of $\lambda_1=2$ is 5. $\lambda_2=-2$ : We see that the geometric multiplicity of $\lambda_2$ is 1, so we will have one Jordan block corresponding to $\lambda_2$ and one ordinary eigenvector; call it v₁. To find the size of the block, we need to find the number of generalized eigenvectors. The fact that dim null (A+2I)²=2 means that there is a generalized eigenvector that satisfies (A+2I)v₂ = v₁ or (A+2I)²v₂=0. The fact that dim null (A+2I)³=3 means that there is another generalized eigenvector that satisfies (A+2I)v₃ = v₂ or (A+2I)³v₃=0. And the fact that dim null (A+2I)⁴=4 means that there is another generalized eigenvector that satisfies (A+2I)v₄ = v₃ or (A+2I)⁴v₄=0. Because dim null (A+2I)^k=4 for $k \ge 4$ , there are no more generalized eigenvectors. The string we have uncovered here is

$\begin{displaymath}v_4 \rightarrow v_3 \rightarrow v_2 \rightarrow v_1. \end{displaymath}$

Thus, the Jordan block corresponding to $\lambda_2$ is $4 \times 4$ , and the algebraic multiplicity of $\lambda_2$ is 4. $\lambda_3=1$ : The geometric multiplicity of $\lambda_3=1$ is 2, meaning there are two Jordan blocks and two ordinary eigenvectors. The fact that dim null (A-I)²=2 (no increase over dim null (A-I)²) means that there are no additional generalized eigenvectors and the algebraic multiplicity is also 2. Thus, there are two $1 \times 1$ Jordan blocks corresponding to $\lambda_3$ . Assembling all of this information, we conclude that the Jordan form for A is

$\begin{displaymath}J= \left( \begin{array}{ccccccccccc} 3&1&0&0&0&0&0&0&0&0&0 ... ...0&0&1&0 \\ 0&0&0&0&0&0&0&0&0&0&1 \\ \end{array} \right). \end{displaymath}$

Note that the Jordan blocks have sizes 3, 2, 4, 1, 1. The Jordan form is unique up to ordering of the blocks.