---
title: Rational Canonical Form
module: Modules over PIDs and Canonical Forms
moduleNumber: 9
lessonNumber: 2
order: 902
summary: >
  A linear operator turns its vector space into a module over the polynomial ring
  $F[x]$, with $x$ acting as the operator. The structure theorem's invariant
  factors then become polynomials, each cyclic summand becomes a companion matrix,
  and the block-diagonal assembly is the rational canonical form. It is unique, it
  is computed inside the base field, and two matrices are similar exactly when
  their rational canonical forms agree.
topics: [Modules over PIDs and Canonical Forms]
draft: false
sources:
  - book: Dummit & Foote
    ref: "Ch. 12 — Modules over Principal Ideal Domains; §12.2 The Rational Canonical Form"
---

Two square matrices over a field are **similar** when $B = P^{-1}AP$ 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](/abstract-algebra/modules-over-pids/structure-theorem-over-pids)
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](/abstract-algebra/module-theory/vector-spaces-and-linear-maps) $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$:
$$
\bigl(c_k x^k + \cdots + c_1 x + c_0\bigr) \cdot v \;=\; c_k T^k(v) + \cdots + 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.

> **Definition ($F[x]$-module of an operator).** For a vector space $V$ over $F$
> and a linear map $T : V \to V$, let $V_T$ denote $V$ made into an $F[x]$-module
> by $x \cdot v = T(v)$. Submodules of $V_T$ coincide with the $T$-invariant
> subspaces.

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.

> **Definition (Characteristic and minimal polynomials).** The **characteristic
> polynomial** of $T$ (or of a matrix $A$) is $c_T(x) = \det(xI - T)$, a monic
> polynomial of degree $n$ whose roots are the eigenvalues of $T$. The **minimal
> polynomial** $m_T(x)$ is the unique monic generator of the annihilator ideal
> $\operatorname{Ann}(V_T) \subseteq F[x]$ — the monic polynomial of least degree
> with $m_T(T) = 0$.

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

$$
% caption: The invariant-factor chain of an operator: the top factor is the minimal polynomial, and the product of all factors is the characteristic polynomial.
\begin{tikzpicture}[font=\small, >=stealth]
\definecolor{acc}{HTML}{4A6FA5}
\node[draw, minimum size=10mm] (a1) at (0,0) {$a_1$};
\node[draw, minimum size=10mm] (a2) at (2.2,0) {$a_2$};
\node at (3.7,0) {...};
\node[draw, minimum size=10mm, draw=acc, thick] (am) at (5.2,0) {$a_m$};
\draw[->, acc] (a1) -- (a2);
\draw[->, acc] (a2) -- (3.4,0);
\draw[->, acc] (4.0,0) -- (am);
\node[acc, font=\footnotesize] at (2.6,0.95) {each divides the next};
\node[acc, anchor=north, font=\footnotesize, align=center] at (5.2,-0.8) {minimal\\polynomial};
\node[black, anchor=north, font=\footnotesize, align=center] at (1.6,-0.8) {product $=$ characteristic\\polynomial};
\end{tikzpicture}
$$

> **Proposition (Minimal polynomial is the largest invariant factor).** With
> invariant factors $a_1(x) \mid a_2(x) \mid \cdots \mid a_m(x)$ of $V_T$, the
> minimal polynomial is $m_T(x) = a_m(x)$. Every invariant factor divides
> $m_T(x)$.

> **Proof.** The annihilator of a direct sum is the least common multiple of the
> annihilators of the summands, and the divisibility chain makes $a_m$ that least
> common multiple.[^df-minpoly] $\square$
## 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} + \cdots + 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} \longmapsto x^k = -b_0 - b_1 x - \cdots - b_{k-1} x^{k-1},
$$
using the relation $a(x) = 0$ in the quotient. In matrix form:

> **Definition (Companion matrix).** The **companion matrix** of the monic
> polynomial $a(x) = x^k + b_{k-1}x^{k-1} + \cdots + b_0$ is the $k \times k$
> matrix
> $$
> C_{a(x)} =
> \begin{pmatrix}
> 0 & 0 & \cdots & 0 & -b_0 \\
> 1 & 0 & \cdots & 0 & -b_1 \\
> 0 & 1 & \cdots & 0 & -b_2 \\
> \vdots & \vdots & \ddots & \vdots & \vdots \\
> 0 & 0 & \cdots & 1 & -b_{k-1}
> \end{pmatrix},
> $$
> with $1$'s down the first subdiagonal, the negated coefficients down the last
> column, and zeros elsewhere.

$$
% caption: 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.
\begin{tikzpicture}[font=\small]
\definecolor{acc}{HTML}{4A6FA5}
\draw[black] (0,0) rectangle (4,4);
\foreach \i in {1,2,3} \node[fill=acc!12, draw=acc, minimum size=8mm, inner sep=0pt] at ({\i-0.5},{4-\i-0.5}) {$1$};
\foreach \i/\c in {1/{c_0},2/{c_1},3/{c_2},4/{c_3}} \node[minimum size=8mm, inner sep=0pt, acc] at (3.5,{4-\i+0.5}) {$\c$};
\node[black] at (1.5,3.5) {$0$};
\node[black] at (2.5,3.5) {$0$};
\node[black] at (0.5,1.5) {$0$};
\node[black, anchor=south, font=\footnotesize] at (2,4.15) {last column $c_i$};
\node[acc, anchor=north, font=\footnotesize] at (1.2,-0.3) {subdiagonal ones};
\draw[acc, ->] (1.45,-0.1) -- (2.3,0.35);
\end{tikzpicture}
$$

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.

> **Theorem (Rational canonical form).** Let $T$ be a linear operator on a
> finite-dimensional space $V$ over $F$, with invariant factors $a_1(x) \mid
> \cdots \mid a_m(x)$. There is a basis of $V$ in which $T$ is the block-diagonal
> matrix
> $$
> \operatorname{RCF}(T) = C_{a_1(x)} \oplus C_{a_2(x)} \oplus \cdots \oplus C_{a_m(x)}.
> $$
> This matrix is unique; it is **the** rational canonical form of $T$.

$$
% caption: The rational canonical form: companion blocks of the invariant factors stacked on the diagonal, zeros in the off-diagonal blocks.
\begin{tikzpicture}[font=\small]
\definecolor{acc}{HTML}{4A6FA5}
\draw[black] (0,0) rectangle (5,5);
\node[draw=acc, fill=acc!12, minimum size=11mm] at (0.9,4.1) {$C_{a_1}$};
\node[draw=acc, fill=acc!12, minimum size=13mm] at (2.4,2.6) {$C_{a_2}$};
\node[draw=acc, fill=acc!12, minimum size=15mm] at (4.0,0.9) {$C_{a_m}$};
\node[black] at (3.6,4.1) {$0$};
\node[black] at (0.9,1.2) {$0$};
\node[black] at (3.5,3.6) {$\ddots$};
\end{tikzpicture}
$$

> **Proof of uniqueness.** The construction is reversible: any basis putting $T$
> in block-companion form exhibits $V$ as a direct sum of cyclic $F[x]$-modules
> whose annihilators are the block polynomials, and the structure theorem's
> uniqueness forces those to be the invariant factors.[^df-rcf] $\square$
Similarity becomes a statement about modules.

> **Theorem (Similarity classification).** For operators $S, T$ on $V$ the
> following are equivalent:
> - $S$ and $T$ are similar;
> - the $F[x]$-modules $V_S$ and $V_T$ are isomorphic;
> - $S$ and $T$ have the same rational canonical form.

> **Proof.** The middle condition is the bridge. A change of basis $U$ with
> $S = UTU^{-1}$ is exactly an $F[x]$-module isomorphism $V_T \to V_S$, since
> $U(x \cdot v) = U T v = S U v = x \cdot U(v)$. Isomorphic modules share
> invariant factors, hence share a rational canonical form; conversely a shared
> canonical form is a shared matrix representative, and conjugating one basis
> change against the other exhibits the similarity. $\square$

$$
% caption: 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.
\begin{tikzpicture}[font=\small, >=stealth]
\definecolor{acc}{HTML}{4A6FA5}
\node[draw, minimum size=11mm] (A) at (0,0) {$A$};
\node[draw, fill=acc!10, minimum size=11mm, draw=acc] (R) at (4.5,0) {$\operatorname{RCF}$};
\draw[->, acc, thick] (A) -- (R) node[midway, above, font=\footnotesize] {conjugate by $P$};
\node[anchor=north, font=\footnotesize, black] at (2.25,-0.5) {same operator, two bases};
\node[anchor=north, font=\footnotesize] at (0,-0.75) {standard basis};
\node[anchor=north, font=\footnotesize] at (4.5,-0.75) {cyclic-generator basis};
\end{tikzpicture}
$$

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

> **Corollary (Field independence).** Let $A, B$ be $n \times n$ matrices over $F$
> and let $K \supseteq F$ be a larger field. The rational canonical form,
> characteristic polynomial, minimal polynomial, and invariant factors of $A$ are
> the same computed over $F$ or over $K$. Consequently $A$ and $B$ are similar
> over $K$ if and only if they are similar over $F$.

Enlarging the field cannot merge or split similarity classes. This fails for the
[Jordan form](/abstract-algebra/modules-over-pids/jordan-canonical-form), which
needs the eigenvalues to lie in the field and so is not "rational."[^df-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.

> **Proposition (Characteristic polynomial and Cayley–Hamilton).** For an
> $n \times n$ matrix $A$:
> - $c_A(x)$ is the product of all invariant factors of $A$;
> - $m_A(x)$ divides $c_A(x)$ (the **Cayley–Hamilton theorem**: $c_A(A) = 0$);
> - $c_A(x)$ divides a power of $m_A(x)$, so the two share the same roots (the
>   eigenvalues), ignoring multiplicity.

> **Proof of the first bullet.** The characteristic polynomial of a block-diagonal
> matrix is the product of the blocks' characteristic polynomials, and each
> companion block $C_{a_i}$ contributes exactly $a_i(x)$.[^df-cayley] $\square$
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 \ge 4$ it need not, and the general algorithm is required.

## Computing by Smith normal form

The systematic method diagonalizes the matrix $xI - 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.

> **Theorem (Smith normal form).** Using the three elementary operations — swap two
> rows or columns, add an $F[x]$-multiple of one row or column to another, multiply
> a row or column by a nonzero element of $F$ — the matrix $xI - A$ reduces to a
> diagonal matrix
> $$
> \operatorname{diag}\bigl(1, \dots, 1,\; a_1(x),\; a_2(x),\; \dots,\; a_m(x)\bigr),
> $$
> with monic nonconstant $a_1(x) \mid a_2(x) \mid \cdots \mid a_m(x)$. These are the
> invariant factors of $A$.

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

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

## Worked examples

> **Worked example.** Decide which of the following matrices over $\mathbb{Q}$ are
> similar:
>
> $$
> A = \begin{pmatrix} 2 & -2 & 14 \\ 0 & 3 & -7 \\ 0 & 0 & 2 \end{pmatrix},
> \quad
> B = \begin{pmatrix} 2 & 1 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 3 \end{pmatrix},
> \quad
> C = \begin{pmatrix} 2 & 2 & -1 \\ 0 & 2 & 3 \\ 0 & 0 & 3 \end{pmatrix}.
> $$
>
> 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 - 2I)(A - 3I) = 0, \qquad (B - 2I)(B - 3I) \ne 0, \qquad (C - 2I)(C - 3I) \ne 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 - 5x + 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 - 7x^2 + 16x - 12$, the rational canonical forms are
>
> $$
> \operatorname{RCF}(A) = \begin{pmatrix} 2 & 0 & 0 \\ 0 & 0 & -6 \\ 0 & 1 & 5 \end{pmatrix},
> \qquad
> \operatorname{RCF}(B) = \operatorname{RCF}(C) = \begin{pmatrix} 0 & 0 & 12 \\ 1 & 0 & -16 \\ 0 & 1 & 7 \end{pmatrix}.
> $$
>
> $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 $xI - A$ over $\mathbb{Q}[x]$:
>
> $$
> xI - A = \begin{pmatrix} x-2 & 2 & -14 \\ 0 & x-3 & 7 \\ 0 & 0 & x-2 \end{pmatrix}.
> $$
>
> The entry $2$ is a unit of $\mathbb{Q}[x]$ sitting in position $(1,2)$; move it
> into the pivot and rescale:
>
> $$
> \xrightarrow{\;C_1 \leftrightarrow C_2\;}
> \begin{pmatrix} 2 & x-2 & -14 \\ x-3 & 0 & 7 \\ 0 & 0 & x-2 \end{pmatrix}
> \xrightarrow{\;R_1 \to \frac{1}{2}R_1\;}
> \begin{pmatrix} 1 & \frac{x-2}{2} & -7 \\ x-3 & 0 & 7 \\ 0 & 0 & x-2 \end{pmatrix}.
> $$
>
> Clear the pivot's column, then its row:
>
> $$
> \xrightarrow{\;R_2 \to R_2 - (x-3)R_1\;}
> \begin{pmatrix} 1 & \frac{x-2}{2} & -7 \\ 0 & -\frac{(x-2)(x-3)}{2} & 7(x-2) \\ 0 & 0 & x-2 \end{pmatrix}
> $$
>
> $$
> \xrightarrow{\substack{C_2 \to C_2 - \frac{x-2}{2}C_1 \\ C_3 \to C_3 + 7C_1}}
> \begin{pmatrix} 1 & 0 & 0 \\ 0 & -\frac{(x-2)(x-3)}{2} & 7(x-2) \\ 0 & 0 & x-2 \end{pmatrix}.
> $$
>
> 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:
>
> $$
> \xrightarrow{\;R_2 \leftrightarrow R_3\;}
> \begin{pmatrix} 1 & 0 & 0 \\ 0 & 0 & x-2 \\ 0 & -\frac{(x-2)(x-3)}{2} & 7(x-2) \end{pmatrix}
> \xrightarrow{\;C_2 \leftrightarrow C_3\;}
> \begin{pmatrix} 1 & 0 & 0 \\ 0 & x-2 & 0 \\ 0 & 7(x-2) & -\frac{(x-2)(x-3)}{2} \end{pmatrix}.
> $$
>
> The pivot $x - 2$ divides $7(x-2)$, so one subtraction and a final rescale
> finish the reduction:
>
> $$
> \xrightarrow{\;R_3 \to R_3 - 7R_2\;}
> \begin{pmatrix} 1 & 0 & 0 \\ 0 & x-2 & 0 \\ 0 & 0 & -\frac{(x-2)(x-3)}{2} \end{pmatrix}
> \xrightarrow{\;R_3 \to -2R_3\;}
> \begin{pmatrix} 1 & 0 & 0 \\ 0 & x-2 & 0 \\ 0 & 0 & (x-2)(x-3) \end{pmatrix}.
> $$
>
> Discarding the leading $1$ leaves the invariant factors $x - 2$ and
> $(x-2)(x-3) = x^2 - 5x + 6$, matching the shortcut. Both diagonal entries are
> monic, the chain $(x-2) \mid (x-2)(x-3)$ holds, and the product
> $(x-2)^2(x-3)$ is the characteristic polynomial, as it must be.

> **Worked example.** List all similarity classes of $3 \times 3$ matrices over
> $\mathbb{Q}$ with characteristic polynomial $(x-2)^2(x-3)$. A class is an
> invariant-factor chain $a_1 \mid \cdots \mid a_m$ with product $(x-2)^2(x-3)$.
> Since $a_m$ is divisible by every other factor, $a_m$ must contain both primes'
> top powers except what earlier factors carry:
>
> - $m = 1$: the single factor $(x-2)^2(x-3)$ — the class of $B$ and $C$;
> - $m = 2$: the split $a_1 = x-2$, $a_2 = (x-2)(x-3)$ — the class of $A$; the
>   alternative split $a_1 = x - 3$ fails the chain, since $x - 3 \nmid (x-2)^2$.
>
> Exactly two similarity classes exist, with representatives
> $\operatorname{RCF}(B)$ and $\operatorname{RCF}(A)$.

## 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 $\mathbb{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](/abstract-algebra/modules-over-pids/jordan-canonical-form).

[^df-minpoly]: 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.
[^df-rcf]: 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.
[^df-rational]: 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.
[^df-cayley]: 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 $xI - 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 $xI - A$ is the computation of §12.2, Example 2, run with a different but equivalent sequence of operations.