Suppose is an matrix over a field . Consider the matrix , which has entries in the ring . As usual in linear algebra, we will perform three basic types of row/column operations on this matrix. The three operations are:
Swap a pair of rows/columns.
Add a multiple (in ) of one row/column to another.
Multiply a row/column by a unit in .
We call these the elementary row/column operations.
Computing the invariant factors
The main computational algorithm relies on the following fact:
The Smith Normal Form
Let be an matrix over a field . Using the three elementary row and column operations above, the matrix can be put into the following diagonal form, called the Smith Normal Form for :
where the are nonzero nonconstant monic polynomials satisfying .
The polynomials are the invariant factors of .
Computing a change-of-basis matrix
There is an addendum to the above result, which says that if we keep track of the row operations used to obtain the Smith Normal Form for , then we can also write down a change-of-basis matrix such that is the rational canonical form for . See pages 480-482 in Dummit & Foote for the full details, but here is a short summary:
Begin with the identity matrix , and then for each row operation used to diagonalize the matrix , change the matrix by the following rules:
If rows and are swapped in the computation of the Smith Normal Form, then swap columns and in .
If in the computation of the Smith Normal Form, then perform in . (Notice that the indices have switched!)
If we multiply row by a unit in the computation of the Smith Normal Form, then multiply column by in the computation of .
Once we have computed the Smith Normal Form for , we will be left with a matrix for which the first columns are zero and the last columns are nonzero. These last nonzero columns correspond to -module generators for the summands corresponding to each invariant factor. In particular, there will be exactly one nonzero column in for each invariant factor.
Let be the nonzero column vector in , so that is the vector in that corresponds to the -module generator in . Since a full -vector space basis for is , the corresponding -vector space basis for that invariant subspace of is . Do this for each nonzero column of . Listing the vectors produced (in this order) gives a desired change-of-basis matrix .
Warning
This auxiliary matrix is not quite unique. The nonzero columns of correspond to -module generators of the invariant summands. Those summands are cyclic as -modules, but the generators for those summands are only unique up to scaling by units.
In particular, different sequences of elementary row/column operations (when computing the Smith Normal Form) can lead to slightly different auxiliary matrices. This will lead, in turn, to slightly different change-of-basis matrices. This is exactly the same situation that occurs when diagonalizing a (diagonalizable) matrix: each eigenbasis provides a suitable change-of-basis, but there is no unique eigenbasis.
Examples
Example 1: Following the general algorithm
Let be the matrix
The goal is to diagonalize the matrix using row and column operations over the ring . 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):
By our general theory, it follows that the invariant factors of are and . We can now conclude that the minimal polynomial of is , the characteristic polynomial of is , and the rational canonical form of is
Moreover, if we keep track of the row operations used to diagonalize the matrix , we can also compute a change-of-basis matrix such that 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 , and then write down the corresponding column operations as describe above. Starting from the identity matrix , we perform the following column operations:
This sequence of column operations will yield the matrix
The first nonzero column of then gives column of the matrix , namely the column
The second column of gives columns of the matrix , namely the columns
Thus, a change-of-basis matrix is
Example 2: Shortcuts for small matrices
For small square matrices (sizes and below), it's possible to compute the rational canonical form without going through the diagonalization process outlined above. For example, for the matrix above, we can first directly compute the characteristic polynomial of :
This immediately tells us that the product of the invariant factors of is . By the divisibility condition on the invariant factors, and the fact that the largest invariant factor is the minimal polynomial , we also know that has the same roots as . In this case, that means there are only two possibilities for : it's either or . To determine which it is, simply recall that is the smallest degree monic polynomial which evaluates at to zero. Then check that
Thus, .
Now observe that the invariant factors of are nonzero nonconstant monic polynomials such that:
.
There is only one such possible list, namely
We now know the invariant factors of and hence the rational canonical form of .
For and matrices, this method is generally the fastest way to determine the rational canonical form. However, it has two downsides:
It does not produce the change-of-basis matrix .
It does not usually work for matrices larger than .
Example 3: A larger matrix
Consider the matrix
It is not difficult to show that the characteristic polynomial of is , which gives four possibilities for the minimal polynomial of , namely . It is then not too terrible to verify that , simply by noting and verifying . However, that leaves two possibilities for the invariant factors of :
On the other hand, diagonalizing the matrix we eventually obtain
Thus, the invariant factors of are and . It now follows that the rational canonical form of is
Moreover, using the actual row and column operations used to diagonalize allows us to compute a change-of-basis matrix. One first finds an auxiliary matrix to be
From this, we can now compute a change-of-basis matrix , ultimately finding one to be
See pages 485-486 of Dummit & Foote for the list of row and column operations used, and how they produce the matrix , above.