This post proves the existence of rational canonical form, using the structure theoerm of finite modules over PID.

Another common canonical form is the rational canonical form. While Jordan form is more like a substitute for non-diagonalizable matrix and thus does not exist when the eigenvalues do not lie in the ground field, the rational canonical form exploits the properties of the characteristic/minimal polynomial.

Theorem 1 (Existence of rational canonical form, invariant factor version) Let $A$ be an $n \times n$ matrix with coefficients in a field $F$. Then it is similar to a direct sum of companion matrices $C_{p_i(t)}$ such that $p_1(t) | p_2(t) | \cdots | p_k(t)$.

Recall that a companion matrix is a matrix of the form

$C_{p(t)} = \left(\begin{array}{ccccc} 0 & 0 & \cdots & 0 & -a_0 \\ 1 & 0 & \cdots & 0 & -a_1 \\ 0 & 1 & \cdots & 0 & -a_2 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 & -a_{k-1}\end{array}\right)$

with the property that both the characteristic polynomial and the minimal polynomial are exactly $p_(t) = a_0 + a_1t + \cdots + a_{k-1}t^{k-1} + t^k$.

Proof

Regard $A$ as the matrix of a linear map $T:V \rightarrow V$, where $V$ is a finite dimensional vector space over $F$. Regard $V$ as an $F[T]$-module and apply the structure theorem for finitely generated modules over PID. Then we may write

$\displaystyle V = \bigoplus_{i=1}^m \frac{F[T]}{p_i(T)}$

such that $p_1 | p_2 | \cdots | p_m$ are the invariant factors, up to units.

Finite dimensionality of $V$ implies that there is no free part in the decomposition. For each $p_i(T) = a_0 + a_1T + \cdots + T^k$, it is clear that with respect to the basis $\{ 1, T, \cdots, T^{k-1}\}$,
$T$ acting on $\frac{F[T]}{p_i(T)}$ takes the form of a companion matrix $C = \left(\begin{array}{ccccc} 0 & 0 & \cdots & 0 & -a_0 \\ 1 & 0 & \cdots & 0 & -a_1 \\ 0 & 1 & \cdots & 0 & -a_2 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 & -a_{k-1}\end{array}\right)$. Putting all these companion matrices together, we have shown the desired result. $\Box$

Using rational canonical form, it is then clear that

1. The minimal polynomial of $A$is $p_m(t)$, the characteristic polynomial of the largest cyclic block.
2. The characteristic polynomial of $A$ is $p_1(t)p_2(t) \cdots p_m(t)$.

Similarly, we also have the elementary divisor version by using the “primary decomposition” in the structure theorem of finitely generated modules over PID.

Theorem 1′ (Existence of rational canonical form, primary decomposition version) Let $A$ be an $n \times n$ matrix with coefficients in a field $F$. Then it is similar to a direct sum of companion matrices $C_{p_i(t)}$ such that each $p_i(t)$ is a prime power.

So how can we compute the rational canonical form? The first question is how should the rational canonical form look like, and the second question is how to find one such basis.

To answer the first question, it suffices to find the invariant factors provided by the structure theorem. This is obtained by

• finding a presentation for the finitely generated module. In our case, we need to find a presentation for $V$ as an $F[T]$-module if we regard $A$ as the matrix of the linear map $T: V \rightarrow T$.
• Find the relations matrix, and apply Smith normal form to it. The resulting invariants are the invariant factors we want.

1. A presentation for $V$

Let $V$ has an $F$-basis $\{e_1, \cdots, e_n\}$ for which $T$ is represented by the matrix $A$. The most natural presentation is to consider the map $p: F[T]^n \rightarrow V$ defined by

$(f_1(T), \cdots, f_n(T)) \rightarrow f_1(T)e_1 + \cdots + f_n(T)e_n$

We then need to find the relations matrix, i.e. the kernel of $p$.

Claim 1 The kernel of $p$ is the $F[T]$-submodule generated by $Tf_j - \sum_{i} a_{ij}f_j$.

Proof

It is obvious that $Tf_j - \sum_{i} a_{ij}f_i$ lies in $\mathrm{Ker} \, p$.

For the other inclusion, let $h_1(T)f_1 + \cdots + h_n(T)f_n \in \mathrm{Ker} \, p$, i.e. $h_1(T)e_1 + \cdots + h_n(T)e_n = 0$. For each $T(e_j)$ involved, we rewrite it as $\left(T(e_j) - \sum_{i} a_{ij}e_i\right) + \sum_{i} a_{ij}e_i$, and take the first term out. This way the degree of the polynomials in $T$ will decrease by 1. Repeat this process until all the $T$s are eliminated. We are left with a linear expression in $e_j$ that equals 0. Therefore every coefficient in this last relation is 0.

Therefore $h_1(T)f_1 + \cdots + h_n(T)f_n$ equals the parts taken away. Since each part taken away is a multiple of $\left(T(e_j) - \sum_{i} a_{ij}e_i\right)$, we have shown the other inclusion. $\Box$

2. We now have the relations matrix $TI - A^t$, where $T$ is just an independent variable. Working out its Smith Normal Form give us the invariants needed.

Primary decomposition

If we factorize the invariants factors and put the prime powers separately (using Chinese remainder theorem), we would get the required primary decomposition.