Building the Rational Canonical Form

The companion matrix of a polynomial

Each cyclic piece F[x]/(d_i) is represented by the companion matrix of d_i: the operator 'multiply by x' written in the basis {1, x, x^2, ...}. Its last column holds the (negated) coefficients of the polynomial, with a subdiagonal of 1's doing the shifting.

For monic d(x) = x^n + c_{n-1} x^{n-1} + ... + c_1 x + c_0,
the companion matrix C(d) is

  [ 0  0  ...  0   -c_0     ]
  [ 1  0  ...  0   -c_1     ]
  [ 0  1  ...  0   -c_2     ]
  [ .        .       .      ]
  [ 0  0  ...  1   -c_{n-1} ]

Key fact: char poly of C(d) = min poly of C(d) = d(x).

Example  d = (x-1)^2 = x^2 - 2x + 1:

  C(d) = [ 0  -1 ]
         [ 1   2 ]

Stacking the blocks

The rational canonical form of A is the block-diagonal matrix whose blocks are the companion matrices of the invariant factors d1 | d2 | ... | dk, in divisibility order. Because the structure theorem produces the d_i uniquely, this matrix is forced — giving the existence and uniqueness of RCF.

1. Form xI - A and reduce it to Smith normal form over F[x].
2. Discard the constant 1's; the remaining diagonal entries are the invariant factors d1 | ... | dk.
3. Replace each d_i by its companion matrix C(d_i).
4. Place the C(d_i) along the diagonal; the block-diagonal result is the RCF of A.

Free polynomials from the form

The form hands you two invariants for free, via min/char poly from invariant factors: the characteristic polynomial is the product d1 d2 ... dk of all invariant factors, and the minimal polynomial is the largest one, dk (it is a multiple of every other d_i by the divisibility chain).