Jordan Canonical Form II - Computation

#module_theory

We have an algorithm for computing the rational canonical form of a matrix. How about computing the Jordan canonical form? Well, there's at least a straightforward way to convert the rational canonical form to the Jordan canonical form.

Computing the Jordan blocks

To compute the Jordan canonical form for an $n \times n$ matrix $A$ , we first compute the invariant factors $a_{1} (x), \dots, a_{m} (x)$ . For each invariant factor $a (x)$ , we factor $a (x)$ completely into linear factors:

a (x) = (x - λ_{1})^{α_{1}} \dots (x - λ_{s})^{α_{s}},

where the $λ_{i}$ are the distinct roots. For this factor, the corresponding elementary divisors are $(x - λ_{1})^{α_{1}}, \dots, (x - λ_{s})^{α_{s}}$ . We can then write down the corresponding Jordan blocks $J_{1}, \dots, J_{s}$ . Doing this for every invariant factor allows us to write down the Jordan canonical form $J$ for $A$ .

Computing the change-of-basis matrix

How about if we want to find a change-of-basis matrix $Q$ such that $Q^{- 1} A Q = J$ ? We can compute that, as well. First note that if $v \in V$ is the $F [x]$ -module generator for the summand corresponding to $F [x] / ⟨ a (x) ⟩$ , then the elements

\frac{a (x)}{(x - λ_{1})^{α_{1}}} \cdot v, \dots, \frac{a (x)}{(x - λ_{s})^{α_{s}}} \cdot v

are $F [x]$ -module generators for the summands corresponding to the quotients

F [x] / ⟨ (x - λ_{1})^{α_{1}} ⟩, \dots, F [x] / ⟨ (x - λ_{s})^{α_{s}} ⟩

To see why this is true, first note that for each $i$ the polynomials $(x - λ_{i})^{α_{i}}$ and $\frac{a (x)}{(x - λ_{i})^{α_{i}}}$ are relatively prime; the former is the annihilator of the summand $F [x] / ⟨ x - λ_{i})^{α_{i}} ⟩$ , while the latter is the annihilator of the complement of that summand in the invariant summand $F [x] / ⟨ a (x) ⟩$ . As such, multiplication by $\frac{a (x)}{(x - λ_{i})^{α_{i}}}$ provides a surjective morphism $F [x] / ⟨ a (x) ⟩ \to F [x] / ⟨ (x - λ_{i})^{α_{i}} ⟩$ .

For each one of these summands, if $w = \frac{a (x)}{(x - λ)^{α}} \cdot v$ is the $F [x]$ -module generator for the summand corresponding to $F [x] / ⟨ (x - λ)^{α} ⟩$ , then an $F$ -vector space basis for that summand is

(A - λ I_{n})^{α - 1} w, \dots, (A - λ I_{n}) w, w .

Note that the basis vectors have been listed in this order so that the corresponding matrix for $T$ (on that summand) is the Jordan block, matching the way in which we chose the basis ${(\overset{―}{x} - λ)^{α - 1}, \dots, \overset{―}{x} - λ, 1}$ for $F [x] / (x - λ)^{α}$ .

We can use this to algorithmically compute a change-of-basis matrix $Q$ . We first compute an auxiliary matrix $P^{'}$ just as we did for the rational canonical form. The nonzero columns of $P^{'}$ correspond to vectors that generate the invariant factor summands as $F [x]$ -modules. We can thus follow the recipe describe above, where $v$ takes the role of a nonzero column of $P^{'}$ . It's easiest to follow this through specific examples.

Examples

Example 1

Let $A$ be the $3 \times 3$ matrix

[\begin{matrix} 2 & - 2 & 14 \\ 0 & 3 & - 7 \\ 0 & 0 & 2 \end{matrix}]

We have seen that the invariant factors of $A$ are $a_{1} (x) = x - 2$ and $a_{2} (x) = x^{2} - 5 x + 6 = (x - 2) (x - 3)$ . The elementary divisors of $A$ are therefore $x - 2$ , $x - 2$ , $x - 3$ , and so the Jordan canonical form is

J = [\begin{matrix} 2 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 3 \end{matrix}]

For a change-of-basis matrix $P$ , first recall an auxiliary matrix $P^{'}$ for this matrix was

P^{'} = [\begin{matrix} 0 & - 7 & - 1 \\ 0 & 7 & 1 \\ 0 & 1 & 0 \end{matrix}]

For the first nonzero column $v_{1}$ of $P^{'}$ (which is a $Q [x]$ -module generator for the summand corresponding to the first invariant factor $a_{1} (x) = x - 2$ ), we compute

w_{1} = \frac{a_{1} (x)}{(x - 2)} \cdot v_{1} = v_{1} = [\begin{matrix} - 7 \\ 7 \\ 1 \end{matrix}] .

Since the summand $Q [x] / ⟨ x - 2 ⟩$ is 1-dimensional, the single vector $w_{1}$ is our $Q$ -basis for that summand.

For the second nonzero column $v_{2}$ of $P^{'}$ (which is a $Q [x]$ -module generator for the summand corresponding to the second invariant factor $a_{2} (x) = (x - 2) (x - 3)$ ), we compute the projections of $v_{2}$ into the two summands $Q [x] / ⟨ x - 2 ⟩$ and $Q [x] / ⟨ x - 3 ⟩$ , respectively:

\begin{aligned} w_{2} & = \frac{a_{2} (x)}{(x - 2)} \cdot v_{2} = (A - 3 I) v_{2} = (A - 3 I) [\begin{array}{c} - 1 \\ 1 \\ 0 \end{array}] = [\begin{array}{c} - 1 \\ 0 \\ 0 \end{array}] \\ w_{3} & = \frac{a_{2} (x)}{(x - 3)} \cdot v_{2} = (A - 2 I) v_{2} = (A - 2 I) [\begin{array}{c} - 1 \\ 1 \\ 0 \end{array}] = [\begin{array}{c} - 2 \\ 1 \\ 0 \end{array}] \end{aligned}

Again, since each of those summands is 1-dimensional, these are our $Q$ -bases for those two summands.

A change-of-basis matrix is then

Q = [\begin{matrix} - 7 & - 1 & - 2 \\ 7 & 0 & 1 \\ 1 & 0 & 0 \end{matrix}]

One can verify $Q^{- 1} A Q = J$ .

Example 2

Consider the $4 \times 4$ matrix

A = [\begin{matrix} 1 & 2 & - 4 & 4 \\ 2 & - 1 & 4 & - 8 \\ 1 & 0 & 1 & - 2 \\ 0 & 1 & - 2 & 3 \end{matrix}]

We have seen that the invariant factors of this matrix are $a_{1} (x) = (x - 1)^{2}$ , $a_{2} (x) = (x - 1)^{2}$ . The elementary divisors of $A$ are therefore $(x - 1)^{2}$ , $(x - 1)^{2}$ , and so the Jordan canonical form is

J = [\begin{matrix} 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \end{matrix}]

An auxiliary matrix for $A$ was

P^{'} = [\begin{matrix} 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{matrix}]

The first nonzero column $v_{1}$ of $P^{'}$ is a $Q [x]$ -module generator for the summand $Q [x] / ⟨ (x - 1)^{2} ⟩$ . There is nothing to project here, since this summand does not decompose further. (In other words, the invariant factor $a_{1} (x) = (x - 1)^{2}$ is also an elementary divisor). That summand is 2-dimensional over $Q$ , so we compute its $Q$ -basis:

w_{1} = (A - I)^{1} v_{1} = [\begin{matrix} 0 \\ 2 \\ 1 \\ 0 \end{matrix}]

w_{2} = v_{1} = [\begin{matrix} 2 \\ - 1 \\ 0 \\ 1 \end{matrix}]

The second nonzero column $v_{2}$ of $P^{'}$ is a $Q [x]$ -module generator for the second summand $Q [x] / ⟨ (x - 1)^{2} ⟩$ . By the identical reasoning used for the previous summand, a $Q$ -basis for this summand is then

\begin{aligned} w_{3} & = (A - I)^{1} v_{2} = [\begin{array}{c} 2 \\ - 2 \\ 0 \\ 1 \end{array}] \\ w_{4} & = v_{2} = [\begin{array}{c} 0 \\ 1 \\ 0 \\ 0 \end{array}] \end{aligned}

Thus, a change-of-basis matrix $Q$ is

Q = [\begin{matrix} 0 & 1 & 2 & 0 \\ 2 & 0 & - 2 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{matrix}]

Suggested next notes

Consider looking into some category theory.