Rational Canonical Form III - Computation

We have a wonderful result about rational canonical forms, but how do we actually compute the rational canonical form of a given square matrix? Fortunately, there is a very straightforward algorithm. Given an $n\times n$ matrix, $A$, both its invariant factors and the change-of-basis matrix needed to put $A$ into rational canonical form can be obtained from the computation of something called the Smith normal form for $A$.

The Smith normal form

Suppose $A$ is an $n\times n$ matrix over a field $F$. Consider the $n\times n$ matrix $x{I}_n-A$, which has entries in the ring $F[x]$. As usual in linear algebra, we will perform three basic types of row/column operations on this matrix. The three operations are:

1. Swap a pair of rows/columns.
2. Add an $F[x]$-multiple of one row/column to another.
3. Multiply a row/column by a unit in $F[x]$.

We call these the elementary row/column operations. We will use these operations to transform $x{I}_n-A$ into a very particular form, in some ways analogous to the classic reduced row-echelon form.

We first quote (without proof^[1]) the following fact.

As a bonus, in computing the Smith normal form for $A$ it turns out that we can also deduce the change-of-basis matrix that will conjugate $A$ into rational canonical form. Although this will initially seem a bit strange, if we keep track of the row operations used to obtain the Smith normal form for $A$, then we can also write down a change-of-basis matrix, $P$, such that $P^{-1}AP$ is the rational canonical form for $A$. See pages Dummit & Foote for the full details, but here is a short summary:

Begin with the identity matrix $I_n=:P^{\prime }$, and then for each row operation used to put the matrix $x{I}_n-A$ into Smith normal form, change the matrix $P^{\prime }$ by the following rules:

1. If rows $i$ and $j$ are swapped in the computation of the Smith normal form for $A$, then swap columns $j$ and $i$ in $P^{\prime }$.
2. If $R_i+p(x)R_j\mapsto R_i$ in the computation of the Smith normal form for $A$, then perform $C_j-p(A)C_i\mapsto C_j$ in $P^{\prime }$. (Notice that the indices have switched!)
3. If we multiply row $i$ by a unit $u$ in the computation of the Smith normal form for $A$, then multiply column $i$ by $u^{-1}$ in the computation of $P^{\prime }$.

By the end of our computations, we will be left with a matrix $P^{\prime }$ for which the first $n-m$ columns are zero and the last $m$ columns are nonzero. These last nonzero columns correspond to $F[x]$-module generators for the summands for each invariant factor. In particular, there will be exactly one nonzero column in $P^{\prime }$ for each invariant factor.

Let ${\mathbf{v}}_i$ be the $i^{\text{th}}$ nonzero column vector in $P^{\prime }$, so that ${\mathbf{v}}_i$ is the vector in $V$ that corresponds to the $F[x]$-module generator $\bar{1}$ for $F[x]/⟨a_i(x)⟩$. Since a full $F$-vector space basis for $F[x]/⟨a_i(x)⟩$ is $\{1,\bar{x},\dots ,{\bar{x}}^{\mathrm{deg}(a(x))-1}\}$, the corresponding $F$-vector space basis for that invariant subspace of $V$ is $\{{\mathbf{v}}_i,A{\mathbf{v}}_i,\dots ,A^{\mathrm{deg}(a_i(x))-1}{\mathbf{v}}_i\}$. Do this for each nonzero column of $P^{\prime }$. Listing the vectors produced (in this order) gives a desired change-of-basis matrix $P$.

Examples

Example 1: Following the general algorithm

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

The goal is to diagonalize the matrix $x{I}_3-A$ using row and column operations over the ring $\mathbf{Q}[x]$. See pages 483-484 in Dummit & Foote for the actual row and column operations used to transform the matrix

to the diagonal matrix

For quick reference, the operations used were (in order):

• $R_1+R_2\mapsto R_1$
• $C_1-C_2\mapsto C_1$
• $-R_1$
• $R_2+(x-3)R_1\mapsto R_2$
• $C_2+(x-1)C_1\mapsto C_2$
• $C_3-7C_1\mapsto C_3$
• $-C_2$
• $R_2-7R_3\mapsto R_2$
• $R_2\leftrightarrow R_3$
• $C_2\leftrightarrow C_3$

By our general theory, it follows that the invariant factors of $A$ are $a_1(x)=x-2$ and $a_2(x)=x^2-5x+6$. We can now conclude that the minimal polynomial of $A$ is $m_A(x)=x^2-5x+6=(x-2)(x-3)$, the characteristic polynomial of $A$ is $c_A(x)=(x-2)(x^2-5x+6)=(x-2{)}^2(x-3)$, and the rational canonical form of $A$ is

Moreover, if we keep track of the row operations used to diagonalize the matrix $x{I}_3-A$, we can also compute a change-of-basis matrix $P$ such that $P^{-1}AP$ is the rational canonical form matrix above. For a quick rundown on his this computation looks, first look at the row operations we used to compute the Smith normal form for $A$, and then write down the corresponding column operations as describe above. Starting from the identity matrix $I_3$, we perform the following column operations:

• $C_2-C_1\mapsto C_2$
• $-C_1$
• $C_1-(A-3I_3)C_2\mapsto C_1$
• $C_3+7C_2\mapsto C_3$
• $C_2\leftrightarrow C_3$

This sequence of column operations will yield the matrix

The first nonzero column of $P^{\prime }$ then gives $\mathrm{deg}(a_1(x))=1$ column of the matrix $P$, namely the column

The second column of $P^{\prime }$ gives $\mathrm{deg}(a_2(x))=2$ columns of the matrix $P$, namely the columns

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

Example 2: Shortcuts for small matrices

For small square matrices (sizes $3\times 3$ and below), it's possible to compute the rational canonical form without going through the diagonalization process outlined above. For example, for the matrix $A$ above, we can first directly compute the characteristic polynomial of $A$:

This immediately tells us that the product of the invariant factors of $A$ is $(x-2{)}^2(x-3)$. By the divisibility condition on the invariant factors, and the fact that the largest invariant factor is the minimal polynomial $m_A(x)$, we also know that $m_A(x)$ has the same roots as $c_A(x)$. In this case, that means there are only two possibilities for $m_A(x)$: it's either $(x-2)(x-3)$ or $(x-2{)}^2(x-3)$. To determine which it is, simply recall that $m_A(x)$ is the smallest degree monic polynomial which evaluates at $A$ to zero. Then check that

Thus, $m_A(x)=(x-2)(x-3)$.

Now observe that the invariant factors of $A$ are nonzero nonconstant monic polynomials $a_1(x),\dots ,a_m(x)$ such that:

1. $a_1(x)\mid a_2(x)\mid \cdots \mid a_m(x)$
2. $a_m(x)=m_A(x)=(x-2)(x-3)$
3. $a_1(x)a_2(x)\cdots a_m(x)=c_A(x)=(x-2{)}^2(x-3)$.

There is only one such possible list, namely

We now know the invariant factors of $A$ and hence the rational canonical form of $A$.

For $2\times 2$ and $3\times 3$ matrices, this method is generally the fastest way to determine the rational canonical form. However, it has two downsides:

1. It does not produce the change-of-basis matrix $P$.
2. It does not usually work for matrices larger than $3\times 3$.

Example 3: A larger matrix

Consider the $4\times 4$ matrix

It is not difficult to show that the characteristic polynomial of $A$ is $c_A(x)=(x-1{)}^4$, which gives four possibilities for the minimal polynomial of $A$, namely $m_A(x)=x-1,(x-1{)}^2,(x-1{)}^3,(x-1{)}^4$. It is then not too terrible to verify that $m_A(x)=(x-1{)}^2$, simply by noting $A-I_4\ne 0$ and verifying $(A-I_4{)}^2=0$. However, that leaves two possibilities for the invariant factors of $A$:

On the other hand, computing the Smith normal form of the matrix $x{I}_4-A$ we eventually obtain

Thus, the invariant factors of $A$ are $a_1(x)=(x-1{)}^2=x^2-2x+1$ and $a_2(x)=(x-1{)}^2=x^2-2x+1$. It now follows that the rational canonical form of $A$ is

Moreover, using the row operations used to compute the Smith normal form allows us to compute a change-of-basis matrix. We first compute the auxiliary matrix, $P^{\prime }$, finding it to be

From this, we can now compute a change-of-basis matrix, $P$, ultimately finding it to be

See pages 485-486 of Dummit & Foote for the list of row and column operations used, and how they produce the matrix, $P$, above.

Suggested next note

Jordan Canonical Form I - Definition