Rational Canonical Form

Two square matrices over a field are similar when $B = P^{- 1} A P$ for some invertible $P$ — the same operator written in two bases. Deciding similarity by searching for $P$ is hopeless. The structure theorem for modules over a PID replaces the search with a computation: attach to each matrix a canonical form that depends only on its similarity class, then compare.

The idea is to read a linear operator as a module. Fix a finite-dimensional vector space $V$ over a field $F$ and a linear transformation $T : V \to V$ . The polynomial ring $F [x]$ is a PID, and $V$ carries an $F [x]$ -module structure in which $x$ acts as $T$ .

The vector space as an $F [x]$ -module

A polynomial acts on a vector by substituting $T$ for $x$ :

(c_{k} x^{k} + \dots + c_{1} x + c_{0}) \cdot v = c_{k} T^{k} (v) + \dots + c_{1} T (v) + c_{0} v .

Multiplication by $x$ alone is application of $T$ . Choosing a different operator $T$ gives a different module on the same underlying space.

Because $dim_{F} V = n < \infty$ , the module $V_{T}$ is finitely generated (any basis generates it) and torsion: the $n^{2} + 1$ powers $I, T, T^{2}, \dots$ are linearly dependent in the $n^{2}$ -dimensional space of operators, so some nonzero polynomial annihilates $V_{T}$ . Two polynomials measure this torsion.

Applying the structure theorem to the torsion $F [x]$ -module $V_{T}$ gives its invariant factors, now monic polynomials.

The invariant-factor chain of an operator: the top factor is the minimal polynomial, and the product of all factors is the characteristic polynomial.

Companion matrices

Each cyclic summand $F [x] / (a (x))$ has a natural basis, and $T$ acts on it by a matrix read straight off the coefficients of $a$ .

For a monic $a (x) = x^{k} + b_{k - 1} x^{k - 1} + \dots + b_{1} x + b_{0}$ , the quotient $F [x] / (a (x))$ has $F$ -basis $1, x, x^{2}, \dots, x^{k - 1}$ . Multiplication by $x$ sends $x^{i} \mapsto x^{i + 1}$ for $i < k - 1$ , and

x^{k - 1} ⟼ x^{k} = - b_{0} - b_{1} x - \dots - b_{k - 1} x^{k - 1},

using the relation $a (x) = 0$ in the quotient. In matrix form:

The companion matrix, drawn at size

4

: ones on the first subdiagonal, the entries

c_{i} = - b_{i}

(negated coefficients) in the last column, zeros elsewhere.

The characteristic polynomial of $C_{a (x)}$ is exactly $a (x)$ , and the minimal polynomial is also $a (x)$ : the single cyclic module has $a (x)$ as its annihilator.

The rational canonical form

Assembling the companion matrices of the invariant factors along a diagonal gives the canonical form.

The rational canonical form: companion blocks of the invariant factors stacked on the diagonal, zeros in the off-diagonal blocks.

Similarity becomes a statement about modules.

Similarity as a change of basis. The matrix

P

of basis vectors conjugates

A

into its rational canonical form; the two matrices represent one operator in two bases.

Rationality

The name records where the arithmetic happens. Every step — factoring $V_{T}$ , building companion blocks — stays inside $F$ , so the entries of the canonical form lie in the smallest field containing the entries of $A$ .

Enlarging the field cannot merge or split similarity classes. This fails for the Jordan form, which needs the eigenvalues to lie in the field and so is not rational.³

Reading the invariant factors from the polynomials

Two relations connect the invariant factors to the two familiar polynomials, and they often determine the whole list by hand.

For small matrices these constraints pin everything down. The invariant factors multiply to $c_{A} (x)$ , each divides the next, and the largest is $m_{A} (x)$ . For $2 \times 2$ and $3 \times 3$ matrices, knowing $c_{A}$ and $m_{A}$ determines the full list; for $n \geq 4$ it need not, and the general algorithm is required.

Computing by Smith normal form

The systematic method diagonalizes the matrix $x I - A$ over $F [x]$ . Because $F [x]$ is a Euclidean domain, the same row-and-column reduction that computes a stacked basis works with polynomial entries.

Algorithm:

\textsc{RationalCanonicalForm}(A)

over

F[x]

1
form the matrix $xI - A$ with entries in $F[x]$
2
while $xI - A$ is not diagonal do
3
bring a lowest-degree entry into the pivot position by row/column swaps
4
using division in $F[x]$ , clear the pivot's row and column by
5
adding multiples of the pivot row/column to the others
6
if some entry is not divisible by the pivot then
7
move it into the pivot's row and repeat the clearing
8
rescale each diagonal entry to be monic
9
discard leading $1$ 's; the remaining monic entries $a_1 \mid \cdots \mid a_m$
10
are the invariant factors
11
return $\bigoplus_i C_{a_i(x)}$

Tracking the operations also yields the change-of-basis matrix $P$ with $P^{- 1} A P$ in rational canonical form.

Worked examples

Worked example. Decide which of the following matrices over $Q$ are similar:

A = 200 - 2 30 14 - 7 2, B = 200120003, C = 200220 - 1 33 .

All three are upper triangular with diagonal $2, 3, 2$ or $2, 2, 3$ , so all three have characteristic polynomial $(x - 2)^{2} (x - 3)$ and eigenvalues alone cannot separate them. Since $c$ and $m$ share roots, the minimal polynomial is $(x - 2) (x - 3)$ or $(x - 2)^{2} (x - 3)$ . Direct substitution decides it:

(A - 2 I) (A - 3 I) = 0, (B - 2 I) (B - 3 I) \neq = 0, (C - 2 I) (C - 3 I) \neq = 0,

so $m_{A} = (x - 2) (x - 3)$ while $m_{B} = m_{C} = (x - 2)^{2} (x - 3)$ . For $A$ , the invariant factors multiply to $c_{A}$ and end in $m_{A}$ , giving $a_{1} = x - 2$ and $a_{2} = (x - 2) (x - 3) = x^{2} - 5 x + 6$ . For $B$ and $C$ the minimal polynomial already has degree $3$ , so it is the only invariant factor. Writing $(x - 2)^{2} (x - 3) = x^{3} - 7 x^{2} + 16 x - 12$ , the rational canonical forms are

RCF (A) = 200001 0 - 6 5, RCF (B) = RCF (C) = 010001 12 - 16 7 .

$B$ and $C$ share a rational canonical form, so they are similar; neither is similar to $A$ .

	$c (x)$	$m (x)$	invariant factors	RCF blocks
$A$	$(x - 2)^{2} (x - 3)$	$(x - 2) (x - 3)$	$x - 2, (x - 2) (x - 3)$	$[2] \oplus$ a $2 \times 2$ block
$B$	$(x - 2)^{2} (x - 3)$	$(x - 2)^{2} (x - 3)$	$(x - 2)^{2} (x - 3)$	one $3 \times 3$ block
$C$	$(x - 2)^{2} (x - 3)$	$(x - 2)^{2} (x - 3)$	$(x - 2)^{2} (x - 3)$	one $3 \times 3$ block

The shortcut above used $c_{A}$ and $m_{A}$ ; the Smith reduction reaches the same invariant factors with no guessing, and it is the method that scales past $3 \times 3$ .

Worked example. Compute the invariant factors of the matrix $A$ above by reducing $x I - A$ over $Q [x]$ :

x I - A = x - 2 00 2 x - 3 0 - 14 7 x - 2 .

The entry $2$ is a unit of $Q [x]$ sitting in position $(1, 2)$ ; move it into the pivot and rescale:

C_{1} \leftrightarrow C_{2} 2 x - 3 0 x - 2 00 - 14 7 x - 2 R_{1} \to \frac{1}{2} R_{1} 1 x - 3 0 \frac{x - 2}{2} 00 - 7 7 x - 2 .

Clear the pivot's column, then its row:

R_{2} \to R_{2} - (x - 3) R_{1} 100 \frac{x - 2}{2} - \frac{( x - 2 ) ( x - 3 )}{2} 0 - 7 7 (x - 2) x - 2

C_{2} \to C_{2} - \frac{x - 2}{2} C_{1} C_{3} \to C_{3} + 7 C_{1} 100 0 - \frac{( x - 2 ) ( x - 3 )}{2} 0 0 7 (x - 2) x - 2 .

In the remaining $2 \times 2$ block the lowest-degree entry is $x - 2$ ; bring it to the pivot position by a row and a column swap:

R_{2} \leftrightarrow R_{3} 100 00 - \frac{( x - 2 ) ( x - 3 )}{2} 0 x - 2 7 (x - 2) C_{2} \leftrightarrow C_{3} 100 0 x - 2 7 (x - 2) 00 - \frac{( x - 2 ) ( x - 3 )}{2} .

The pivot $x - 2$ divides $7 (x - 2)$ , so one subtraction and a final rescale finish the reduction:

R_{3} \to R_{3} - 7 R_{2} 100 0 x - 2 0 00 - \frac{( x - 2 ) ( x - 3 )}{2} R_{3} \to - 2 R_{3} 100 0 x - 2 0 00 (x - 2) (x - 3) .

Discarding the leading $1$ leaves the invariant factors $x - 2$ and $(x - 2) (x - 3) = x^{2} - 5 x + 6$ , matching the shortcut. Both diagonal entries are monic, the chain $(x - 2) ∣ (x - 2) (x - 3)$ holds, and the product $(x - 2)^{2} (x - 3)$ is the characteristic polynomial, as it must be.

The operator-module dictionary

The dictionary between operators and $F [x]$ -modules turns questions about matrices into module questions about $V_{T}$ , term for term. The characteristic polynomial plays the role of the order of a finite abelian group and the minimal polynomial the role of its exponent, both being the same invariants — one over the PID $Z$ , the other over the PID $F [x]$ . So the problems solved for abelian groups have exact analogues here:

Find the canonical form of a matrix (decompose $V_{T}$ into cyclic factors).
Decide similarity of two matrices (test module isomorphism).
List all similarity classes with a given characteristic polynomial (enumerate invariant-factor chains multiplying to it).
List all classes with a given minimal polynomial and dimension (enumerate chains ending in it).

When the base field contains all the eigenvalues, the elementary-divisor form of the same module gives a nearly diagonal matrix, the Jordan canonical form.

Dummit & Foote, §12.2 — Proposition 13: the minimal polynomial of $T$ is the largest invariant factor of the $F [x]$ -module $V_{T}$ , and every invariant factor divides it. ↩
Dummit & Foote, §12.2 — Theorems 14–17: existence and uniqueness of the rational canonical form for operators and matrices, and the equivalence of similarity with $F [x]$ -module isomorphism. ↩
Dummit & Foote, §12.2 — Corollary 18: the rational canonical form, minimal and characteristic polynomials, and invariant factors are unchanged under field extension, so similarity is field-independent. ↩
Dummit & Foote, §12.2 — Lemma 19 and Proposition 20: the characteristic polynomial of a companion matrix is the polynomial itself; the characteristic polynomial is the product of the invariant factors; and the Cayley–Hamilton theorem. Theorem 21 states the Smith normal form of $x I - A$ . The first worked example follows Example 1 of §12.2 ( $A$ is its first matrix); $B$ and $C$ are two matrices sharing the invariant factor $(x - 2)^{2} (x - 3)$ , neither similar to $A$ . The Smith reduction of $x I - A$ is the computation of §12.2, Example 2, run with a different but equivalent sequence of operations. ↩