# What is the purpose of these extra steps in the algorithm for converting to rational canonical form?

I have been reading chapter 12 of Dummit and Foote lately, and they give an algorithm for converting an arbitrary $n \times n$ matrix into rational canonical form.

Before getting to my question, I need to state a definition and a theorem for reference:

Definition. A matrix is said to be in rational canonical form if it is the direct sum of companion matrices for monic polynomials $a_1(x), \cdots , a_m(x)$ of degree at least one with $a_1(x) \, | \, a_2(x) \, | \, \cdots \, | \, a_m(x)$. The polynomials $a_i(x)$ are called the invariant factors of the matrix.

Theorem 21. Let $A$ be an $n \times n$ matrix over the field $F$. Using the three elementary row and column operations, the $n \times n$ matrix $xI - A$ with entries from $F[x]$ can be put into the diagonal form (called the Smith normal form for A):

\begin{equation*} \begin{pmatrix} 1 & & & & & \\ & \ddots & & & & \\ & & 1 & & & \\ & & & a_1(x) & & \\ & & & & \ddots & \\ & & & & & \\ & & & & & a_m(x) \\ \end{pmatrix} \end{equation*} The polynomials $a_1(x), \cdots, a_m(x) \in F[x]$ are all monic and of degree at least one, and satisfy the divisibility conditions: \begin{equation*} a_1(x) \,| \, a_2(x) \, | \, \cdots \, | \, a_m(x) \end{equation*}

Moreover, the polynomials $a_1(x), \cdots , a_m(x)$ are the invariant factors of the matrix $A$.

The algorithm that they give for converting an arbitrary $n \times n$ matrix $A$ into rational canonical form is fairly long. Below is an outline of their algorithm:

1. Use elementary row and column operations to diagonalize the matrix $xI - A$ over $F[x]$ to the form in theorem 21, i.e. into Smith normal form.

2. There will be monic polynomials $a_1(x), \cdots, a_m(x)$ on the diagonal of this newly diagonalized matrix. Define $d_i$ to be the degree of $a_i(x)$.

3. Start with an $n \times n$ identity matrix (they call this matrix $P'$), and do various operations to $P'$ depending on the operations used in step 1. [Example: If rows $i$ and $j$ were swapped in the process of diagonalizing $xI - A$ during step 1, then swap the columns $i$ and $j$ in the matrix $P'$.]

4. [quoting directly here] When $xI - A$ has been diagonalized to the form in Theorem 21, the first $n - m$ columns of the matrix $P'$ are $0$, and the remaining $m$ columns of $P'$ are nonzero. For each $i = 1, 2, \cdots, m$, multiply the $i$th nonzero column of $P'$ successively by $A^0 = I, A^1, \cdots, A^{d_i -1}$, and use the resulting column vectors (in this order) as the next $d_i$ columns of an $n \times n$ matrix $P$. Then $P^{-1}A P$ is in rational canonical form (whose diagonal blocks are the companion matrices for the polynomials $a_1(x), \cdots, a_m(x)$.)

But what is the point of steps 2-4? Why not just use elementary row and column operations to get $xI - A$ into Smith normal form, read off the invariant factors and then form the companion matrix for each $a_i(x)$. Taking the direct sum of these companion matrices should give the rational canonical form of $A$, right?

This method that I outlined above seems substantially easier than the algorithm they gave. So I'm guessing that either (a) there is some benefit of following their approach that I am missing or (b) the shorter approach is not valid.

• I think the point is that by computing $P$, you find the basis that puts the linear transformation in rational canonical form. – André 3000 Apr 19 '17 at 23:48
• @Quasicoherent I was thinking the same thing. I guess it is helpful to know the matrix that conjugates $A$ into rational canonical form? – Sam Y. Apr 19 '17 at 23:50

Their algorithm does more than just put $A$ in the desired format - it also provides a change of basis so we can actually use this format. Unless you are analyzing the matrix purely for eigenvalues, the determinant, or intuition - you can't actually use the resulting matrix for computation in the original space.
Suppose you wanted to multiply a series of vectors $v_i$ by $A$. Diagonalization is one way to speed up this computation, but because we've changed our basis we'll also need to change the basis of our vectors. This can be done via applying $P^{-1}$ to $v_i$. Then $$P^{-1} A P P^{-1} v_i = P^{-1} A v_i$$ Gives the product under the new basis. In general this will be different than $A v_i$ or $P^{-1} A P v_i$. Likewise, we may want to multiply $A$ with another matrix $B$, this can now be done by $$P^{-1}APP^{-1}BP=P^{-1}ABP$$ which is now in the diagonalized basis.