# Rational Canonical Form III - Computation

## The algorithm

Suppose

- 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:

Let **Smith Normal Form for **:

where the

The polynomials

### 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

Begin with the identity matrix *row* operation used to diagonalize the matrix

- 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

Let

This auxiliary matrix

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

The goal is to diagonalize the matrix *and column* operations over the ring

to the diagonal matrix

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

By our general theory, it follows that the invariant factors ofare 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 *row* operations we used to compute the Smith Normal Form for

This sequence of column operations will yield the matrix

The first nonzero column of

The second column of

Thus, a change-of-basis matrix

### Example 2: Shortcuts for small matrices

For small square matrices (sizes

This immediately tells us that the product of the invariant factors of

Thus,

Now observe that the invariant factors of

.

There is only one such possible list, namely

We now know the invariant factors of

For

- 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

It is not difficult to show that the characteristic polynomial of

On the other hand, diagonalizing the matrix

Thus, the invariant factors of

Moreover, using the actual row and column operations used to diagonalize

From this, we can now compute a change-of-basis matrix

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