Rational Canonical Form III - Computation

The algorithm

Suppose A is an nΓ—n matrix over a field F. Consider the nΓ—n matrix xInβˆ’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 a multiple (in F[x]) 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.

Computing the invariant factors

The main computational algorithm relies on the following fact:

The Smith Normal Form

Let A be an nΓ—n matrix over a field F. Using the three elementary row and column operations above, the nΓ—n matrix xInβˆ’A can be put into the following diagonal form, called the Smith Normal Form for A:

[1β‹±1a1(x)a2(x)β‹±am(x)],

where the ai(x) are nonzero nonconstant monic polynomials satisfying a1(x)∣a2(x)βˆ£β‹―βˆ£am(x).

The polynomials a1(x),…,am(x) are the invariant factors of A.

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 A, then we can also write down a change-of-basis matrix such that Pβˆ’1AP is the rational canonical form for A. See pages 480-482 in Dummit & Foote for the full details, but here is a short summary:

Begin with the identity matrix In=Pβ€², and then for each row operation used to diagonalize the matrix xInβˆ’A, change the matrix Pβ€² by the following rules:

  1. If rows i and j are swapped in the computation of the Smith Normal Form, then swap columns i and j in Pβ€².
  2. If Ri+p(x)Rj↦Ri in the computation of the Smith Normal Form, then perform Cjβˆ’p(A)Ci↦Cj in Pβ€². (Notice that the indices have switched!)
  3. If we multiply row i by a unit u in the computation of the Smith Normal Form, then multiply column i by uβˆ’1 in the computation of Pβ€².

Once we have computed the Smith Normal Form for A, we will be left with a matrix Pβ€² 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 corresponding to each invariant factor. In particular, there will be exactly one nonzero column in Pβ€² for each invariant factor.

Let vi be the ith nonzero column vector in Pβ€², so that vi is the vector in V that corresponds to the F[x]-module generator 1 in F[x]/(ai(x)). Since a full F-vector space basis for F[x]/(ai(x)) is {1,x―,…,x―deg⁑(a(x))βˆ’1}, the corresponding F-vector space basis for that invariant subspace of V is {vi,Avi,…,Adeg⁑(ai(x))βˆ’1vi}. Do this for each nonzero column of Pβ€². Listing the vectors produced (in this order) gives a desired change-of-basis matrix P.

Warning

This auxiliary matrix Pβ€² is not quite unique. The nonzero columns of Pβ€² correspond to F[x]-module generators of the invariant summands. Those summands are cyclic as F[x]-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 A be the 3Γ—3 matrix

A=[2βˆ’21403βˆ’7002]

The goal is to diagonalize the matrix xI3βˆ’A using row and column operations over the ring Q[x]. See pages 483-484 in Dummit & Foote for the actual row and column operations used to transform the matrix

xI3βˆ’A=[xβˆ’22βˆ’140xβˆ’3700xβˆ’2]

to the diagonal matrix

[1000xβˆ’2000x2βˆ’5x+6]

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

R=[20000βˆ’6015]

Moreover, if we keep track of the row operations used to diagonalize the matrix xI3βˆ’A, we can also compute a change-of-basis matrix P such that Pβˆ’1AP 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 I3, we perform the following column operations:

Pβ€²=[0βˆ’7βˆ’1071010]

The first nonzero column of Pβ€² then gives deg⁑(a1(x))=1 column of the matrix P, namely the column

p1=v1=[βˆ’771]

The second column of Pβ€² gives deg⁑(a2(x))=2 columns of the matrix P, namely the columns

p2=v2=[βˆ’110],p3=Av2=[2βˆ’21403βˆ’7002][βˆ’110]=[βˆ’430]

Thus, a change-of-basis matrix P is

P=[βˆ’7βˆ’1βˆ’4713100]

Example 2: Shortcuts for small matrices

For small square matrices (sizes 3Γ—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:

cA(x)=det(xI3βˆ’A)=(xβˆ’2)2(xβˆ’3).

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 mA(x), we also know that mA(x) has the same roots as cA(x). In this case, that means there are only two possibilities for mA(x): it's either (xβˆ’2)(xβˆ’3) or (xβˆ’2)2(xβˆ’3). To determine which it is, simply recall that mA(x) is the smallest degree monic polynomial which evaluates at A to zero. Then check that

(Aβˆ’2I3)(Aβˆ’3I3)=A2βˆ’5A+6I3=0.

Thus, mA(x)=(xβˆ’2)(xβˆ’3).

Now observe that the invariant factors of A are nonzero nonconstant monic polynomials a1(x),…,am(x) such that:

  1. a1(x)∣a2(x)βˆ£β‹―βˆ£am(x)
  2. am(x)=mA(x)=(xβˆ’2)(xβˆ’3)
  3. a1(x)a2(x)β‹―am(x)=cA(x)=(xβˆ’2)2(xβˆ’3).
    There is only one such possible list, namely
a1(x)=xβˆ’2,a2(x)=(xβˆ’2)(xβˆ’3)

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

For 2Γ—2 and 3Γ—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Γ—3.

Example 3: A larger matrix

Consider the 4Γ—4 matrix

A=[12βˆ’442βˆ’14βˆ’8101βˆ’201βˆ’23]

It is not difficult to show that the characteristic polynomial of A is cA(x)=(xβˆ’1)4, which gives four possibilities for the minimal polynomial of A, namely mA(x)=xβˆ’1,(xβˆ’1)2,(xβˆ’1)3,(xβˆ’1)4. It is then not too terrible to verify that mA(x)=(xβˆ’1)2, simply by noting Aβˆ’I4β‰ 0 and verifying (Aβˆ’I4)2=0. However, that leaves two possibilities for the invariant factors of A:

xβˆ’1,xβˆ’1,(xβˆ’1)2or(xβˆ’1)2,(xβˆ’1)2.

On the other hand, diagonalizing the matrix xI4βˆ’A we eventually obtain

[1000010000(xβˆ’1)20000(xβˆ’1)2].

Thus, the invariant factors of A are a1(x)=(xβˆ’1)2 and a2(x)=(xβˆ’1)2. It now follows that the rational canonical form of A is

R=[0βˆ’1001200000βˆ’10012].

Moreover, using the actual row and column operations used to diagonalize xI4βˆ’A allows us to compute a change-of-basis matrix. One first finds an auxiliary matrix Pβ€² to be

Pβ€²=[0010000100000000]

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

P=[1102021βˆ’101000001]

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