Skip to content

Jordan form II: Computations

July 26, 2009

This post talks about computation of Jordan form and Jordan basis, along with a few examples.

In this post we focus on computing the Jordan form of a given matrix.

Proposition 1 (Calculating the number of Jordan blocks/sizes)

For each eigenvalue \lambda_i, the number of corresponding Jordan blocks is \mathrm{dim} \, \mathrm{Ker} \, \left(T - \lambda_i I\right). More generally, let

c_j = the number of Jordan blocks of size \ge j

Then \mathrm{dim} \, \mathrm{Ker} \, \left(T - \lambda_i I\right)^j = c_1 + \cdots + c_j, i.e.

c_j = \mathrm{dim} \, \mathrm{Ker} \, \left(T - \lambda_i I\right)^j - \mathrm{dim} \, \mathrm{Ker} \, \left(T - \lambda_i I\right)^{j-1}

This further shows that the number of Jordan blocks of size j is c_{j} - c_{j+1} =2 \mathrm{dim} \, \mathrm{Ker} \, \left(T - \lambda_i I\right)^{j} - \mathrm{dim} \, \mathrm{Ker} \, \left(T - \lambda_i I\right)^{j+1}- \mathrm{dim} \, \mathrm{Ker} \, \left(T - \lambda_i I\right)^{j-1}

This is obvious by looking at the Jordan form. A nice way to keep track of all these numbers is to use Young tableaux, which will be done later.

The next question would be how to find a Jordan basis. A possible procedure is outlined here,

1. Fix an eigenvalue \lambda. Find the smallest k such that \mathrm{Ker} \, (T - \lambda I)^k stabilizes, i.e. \mathrm{Ker} \, (T - \lambda I)^k = \mathrm{Ker} \, (T - \lambda I)^{k+1} = \cdots. This is the size of the largest Jordan block.

2. Find a basis of \frac{\mathrm{Ker} \, (T - \lambda I)^k}{\mathrm{Ker} \, (T - \lambda I)^{k-1}}. Pull this basis back to\mathrm{Ker} \, (T - \lambda I)^k; this set is clearly linearly independent. Let this pullback set be \{v_1, \cdots, v_m\}. Notice that the set B_k defined by

\displaystyle \{v_1, \cdots, v_m, (T - \lambda I)v_1, \cdots, (T-\lambda I)v_m, \cdots, (T-\lambda I)^{k-1} v_1, \cdots, (T-\lambda I)^{k-1}v_m \}

is also linearly independent. Moreover, it spans a T-invariant subspace, where the matrix of T with respect to this basis is m blocks of Jordan block of size k.

3. Consider \frac{\mathrm{Ker} \, (T - \lambda I)^{k-1}}{\mathrm{Ker} \, (T - \lambda I)^{k-2}}. We already have a linearly independent set \{ (T - \lambda I)v_1, \cdots, (T-\lambda I)v_m \}. Extend this to a basis, say we concatenate it by a set \{w_1, \cdots, w_l\}. The set

B_{k-1} = B_k \cup \{w_1, \cdots, w_l,\cdots, (T-\lambda I)^{k-2} w_1, \cdots, (T-\lambda I)^{k-2}w_l \}

is again linearly independent.

4. Iterate, the final set B_1 would be a Jordan basis, since it is a set of linearly independent elements with the right dimension (why?) such that T has Jordan form with respect to it.

Example 1 Find the Jordan form of A = \left(\begin{array}{ccc} 1 & 1 & 1 \\ & 1 & 1 \\ & & 1 \\ \end{array}\right).

The eigenvalues are clearly all 1. It is clear that \mathrm{dim} \, \mathrm{Ker} \, (A-I) = 1, which means that there is only one Jordan block. Thus its Jordan form is \left(\begin{array}{ccc} 1 & 1 & \\ & 1 & 1 \\ & & 1 \\ \end{array}\right).

To find a Jordan basis, notice that as there is only one Jordan block, the basis must be a cyclic one. Thus we only have to compute the image of (A-I)^2.

(A-I)^2 = \left(\begin{array}{ccc} & & 1 \\ & & \\ & & \\ \end{array}\right)

Thus \left\{ (A-I)^2\left[\begin{array}{c} 0 \\ 0 \\ 1 \end{array}\right] = \left[\begin{array}{c} 1 \\ 0 \\ 0 \end{array}\right], (A-I)\left[\begin{array}{c}0 \\ 0 \\ 1\end{array}\right] = \left[\begin{array}{c}1 \\ 1 \\ 0\end{array}\right], \left[\begin{array}{c}0 \\ 0 \\ 1\end{array}\right]\right\} is one Jordan basis.

Example 2 Find the Jordan form of B = \left(\begin{array}{ccc} 0 & -1 & 2 \\ 3 & -4 & 6\\2 & -2 & 3\\ \end{array}\right).

After computations, the characteristic polynomial is (t-1)(t+1)^2. Therefore it suffices to check the number of Jordan blocks for the eigenvalue -1.

B+I = \left(\begin{array}{ccc} 1 & -1 & 2 \\ 3 & -3 & 6\\2 & -2 & 4\\ \end{array}\right) is clearly of rank 1. So the kernel has rank 2, meaning that there are 2 Jordan blocks, i.e. B is diagonalizable and is similar to \left(\begin{array}{ccc} 1 & & \\ & -1 & \\ & & -1\\ \end{array}\right).

To find a Jordan basis, we first consider the eigenvalue 1.

B-I = \left(\begin{array}{ccc} -1 & -1 & 2 \\ 3 & -5 & 6\\2 & -2 & 2\\ \end{array}\right)

After performing Gaussian elimination, we get

\left(\begin{array}{ccc} 1 & & -\frac{1}{2} \\ & 1 & \\ & & 0 \\ \end{array}\right)

Then clearly the kernel is spanned by \left[\begin{array}{c} 1 \\ 0 \\ 2 \end{array}\right].

For the eigenvalue -1,

B+I = \left(\begin{array}{ccc} 1 & -1 & 2 \\ 3 & -3 & 6\\2 & -2 & 4\\ \end{array}\right)

thus after Gaussian elimination, it becomes

\left(\begin{array}{ccc} 1 & -1 & 2 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \\ \end{array}\right)

yielding a basis of \left\{\left[\begin{array}{c} 1 \\ 1 \\ 0 \end{array}\right], \left[\begin{array}{c} -2 \\ 0 \\ 1 \end{array}\right]\right\}.

Example 3 Find the Jordan form of C = \left(\begin{array}{cccc} 2 & 0 & 0 & 0 \\ -1 & 1 & 0 & 0\\ 0 & -1 & 0 & -1\\ 1 & 1 & 1 & 2 \\ \end{array}\right).

After computations, the characteristic polynomial is (t-1)^3(t-2). Therefore it suffices to check the number of Jordan blocks for the eigenvalue 1.

C - I = \left(\begin{array}{cccc} 1 & 0 & 0 & 0 \\ -1 & 0 & 0 & 0\\ 0 & -1 & -1 & -1\\ 1 & 1 & 1 & 1 \\ \end{array}\right)

is clearly of rank 2. Thus the kernel is of 2 dimension, meaning that the Jordan form has to be

\left(\begin{array}{cccc} 1 & 1 & & \\ & 1 & & \\ & & 1 & \\ & & & 2\end{array}\right).

To find a Jordan basis, for the eigenvalue 2,

C - 2I = \left(\begin{array}{cccc} 0 & 0 & 0 & 0 \\ -1 & -1 & 0 & 0\\ 0 & -1 & -2 & -1\\ 1 & 1 & 1 & 0 \\ \end{array}\right)

After some row reduction, we get

\left(\begin{array}{cccc} 1 & 0 & 0 & -1\\ 0 & 1 & 0 & 1\\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 \\ \end{array}\right)

Therefore the kernel is spanned by \left[\begin{array}{c} 1 \\ -1 \\ 0 \\ 1 \end{array}\right].

For the eigenvalue 1,

1. By some computations, \mathrm{Ker} \, (C-I) is spanned by \left\{ \left[\begin{array}{c} 0 \\ 1 \\ -1 \\ 0 \end{array}\right], \left[\begin{array}{c} 0 \\ 1 \\ 0 \\ -1 \end{array}\right]\right\}.

(C-I)^2 = \left(\begin{array}{cccc} 1 & 0 & 0 & 0 \\ -1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0\end{array}\right)

The kernel contains \left\{ \left[\begin{array}{c} 0 \\ 1 \\ -1 \\ 0 \end{array}\right], \left[\begin{array}{c} 0 \\ 1 \\ 0 \\ -1 \end{array}\right]\right\}. One can extend this to a basis by adding \left[\begin{array}{c} 0 \\ 1 \\ 0 \\ 0 \end{array}\right].

2. Compute

(C-I) \left[\begin{array}{c} 0 \\ 1 \\ 0 \\ 0 \end{array}\right] = \left(\begin{array}{cccc} 1 & 0 & 0 & 0 \\ -1 & 0 & 0 & 0\\ 0 & -1 & -1 & -1\\ 1 & 1 & 1 & 1 \\ \end{array}\right)\left(\begin{array}{c} 0 \\ 1 \\ 0 \\ 0 \end{array}\right) = \left(\begin{array}{c} 0 \\ 0 \\ -1 \\ 1 \end{array}\right)

Then \left\{ \left[\begin{array}{c} 0 \\ 1 \\ 0 \\ 0 \end{array}\right], \left[\begin{array}{c} 0 \\ 0 \\ -1 \\ -1 \end{array}\right]\right\} is the basis for the Jordan block of size 2.

3. Extend \left[\begin{array}{c} 0 \\ 0 \\ -1 \\ 1 \end{array}\right] to a basis of \mathrm{Ker} \, (C-I) by adding \left[\begin{array}{c} 0 \\ 1 \\ -1 \\ 0 \end{array}\right]. Thus

\left\{ \left[\begin{array}{c} 0 \\ 1 \\ -1 \\ 0 \end{array}\right],\left[\begin{array}{c} 0 \\ 1 \\ 0 \\ 0\end{array}\right],\left[\begin{array}{c} 0 \\ 0 \\ -1 \\ 1 \end{array}\right]\right\}

spans \mathrm{Ker} \, (C-I)^2.

Conclusion: A Jordan basis is \left\{ \left[\begin{array}{c} 0 \\ 1 \\ -1 \\ 0 \end{array}\right],\left[\begin{array}{c} 0 \\ 1 \\ 0 \\ 0\end{array}\right],\left[\begin{array}{c} 0 \\ 0 \\ -1 \\ 1 \end{array}\right], \left[\begin{array}{c} 1 \\ -1 \\ 0 \\ 1 \end{array}\right]\right\}.

Young tableaux

It is a convenient tool to track the number/size of Jordan blocks for each eigenvalue.

For example in the above case, we have exactly one Jordan block of size 3, we then give it a horizontal bar

\Box\Box\Box

If instead we have one Jordan block of size 2, and another of size 1, we give it a tableau

\begin{array}{cc}\Box & \Box \\ \Box & \end{array}

In general, each row represents one Jordan block, and the number of boxes represent the dimension. We list each block according to its size in a descending order. When we read this figure horizontally, we then obtain the numbers c_j defined previously, i.e. the number of Jordan blocks with size \ge j.

Therefore if we merely wish to find the Jordan form, we may, for each eigenvalue \lambda,

1. Calculate \mathrm{dim} \, \mathrm{Ker} \, (T-\lambda I)^k until it stabilizes.

2. Calculate c_j = \mathrm{dim} \, \mathrm{Ker} \, \left(T - \lambda I\right)^j - \mathrm{dim} \, \mathrm{Ker} \, \left(T - \lambda I\right)^{j-1}, where c_j is the number of Jordan blocks with size \ge j.

3. Draw c_j boxes in the j-th column, aligned to the top.

4. We then obtain a Young tableau, and we can just read off the number of Jordan blocks (the number of rows), and their sizes (the number of boxes in each row).

Remark

The last two examples are taken from the last page of http://www.math.uga.edu/~roy/rev.lin.alg.pdf .

\mathrm{Ker} \, (T – \lambda I)^k = \mathrm{Ker} \, (T – \lambda I)^k
from → Canonical Form, Linear algebra
2 Comments leave one →
  1. forsixthirty permalink
    October 4, 2012 6:05 am

    Reblogged this on forsixthirty and commented:
    nice.

    Reply

Trackbacks

  1. Similarity and normal forms « My thoughts/summaries

Leave a comment