Skip to content

Rational Canonical Form

July 28, 2009

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 Ais 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 Ts 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.

Advertisements
No comments yet

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: