## On the relations matrix of a given module homomorphism

Let $V$, $T$, and so on be as described in this previous exercise. Compute the relations matrix of $\varphi$ with respect to the generating set $\{\omega_1,\ldots,\omega_n\}$ for $\mathsf{ker}\ \varphi$. Conclude that Theorem 21 and the algorithm described on page 480-481 in D&F for determining the invariant factor decomposition of an $F[x]$-module follow from the algorithm described in the series of exercises beginning here.

Recall that $\omega_i = \sum_j (\delta_{j,i}x - a_{j,i})\xi_j$, where $\delta_{j,i}$ is the Kronecker delta. So $\varphi(\omega_i) = \sum_j (\delta_{j,i}x - a_{j,i})v_j$, and thus by definition the relations matrix of $\varphi$ is $[\delta_{j,i}x - a_{j,i}] = xI - A^\mathsf{T}$ $= (xI-A)^\mathsf{T}$.

By the algorithm we discussed here, using a sequence of elementary row and column operations we can transform this relations matrix into a diagonal matrix $D = D^\mathsf{T}$ whose diagonal entries are ordered by divisibility and are precisely the invariant factors of $V$ as an $F[x]$ module. This diagonal matrix is the Smith Normal Form of $xI-A^\mathsf{T}$. Recall that each elementary row or column operation can be achieved by left (row) or right (column) multiplying by an appropriate elementary matrix (as described here) and that these elementary matrices are invertible. So we have products $P$ and $Q$ of elementary matrices such that $P(xI-A)^\mathsf{T})Q = D$. Now $P^\mathsf{T}$ and $Q^\mathsf{T}$ are also products of elementary matrices, and we have $(P(xI-A)^\mathsf{T}Q)^\mathsf{T} = Q^\mathsf{T}(xI-A)P^\mathsf{T} = D^\mathsf{T} = D$. In particular, $xI-A$ and $xI-A^\mathsf{T}$ have the same invariant factors, and so $D$ is also the Smith Normal Form of $xI-A$. This proves Theorem 21 in D&F.

Now we will verify the correctness of the algorithm given on page 480-481 of D&F. Fix the standard basis on an $n$-dimensional vector space $V$, let $T$ be a linear transformation on $V$, and let $A$ be the matrix of $T$ with respect to the standard basis. By Theorem 21, there are products $P$ and $Q$ of elementary matrices such that $P(xI-A)Q = D$ is in Smith Normal Form. ($P$ is the row operations used in reverse order, and $Q$ is the column operations used in order.) With respect to the generators $\omega_i$, $\varphi$ has relations matrix $xI-A^\mathsf{T}$, and $Q^\mathsf{T}(xI-A^\mathsf{T})P^\mathsf{T} = D$ is in Smith Normal Form. Now recall (from here) that elementary column operations on a relations matrix correspond to ‘elementary perturbations’ of the generating set of $F[x]^n$. In particular, letting $I$ be the standard basis of $F[x]$ as a matrix, performing these elementary perturbations in order corresponds precisely to the column operations described in part (2) of the algorithm on page 480. The resulting generating set consists of elements of $F[x]$-linear combinations of the $e_i$, which we convert to $F$-linear combinations of the $e_i$ via $x \cdot e_i \mapsto Ae_i$ (that is, by ‘evaluating at $A$‘). The nonzero elements of the resulting generating set, $\{f_1,\ldots,f_m\}$, then generate $V$ (homomorphically) so that $V = F[x]f_1 \oplus \cdots \oplus F[x]f_m$, and moreover the annihilator of $f_i$ is the corresponding invariant factor $(a_i(x))$.

In particular, the elements $T^k(f_i)$ with $0 \leq k < \mathsf{deg}(a_i)$ are $F$-linearly independent (since $a_i(x)$ is the monic polynomial of least degree which annihilates $f_i$), and so by dimension considerations are a basis for the $F$-vector space $F[x]/(a_i(x))$. Let $P$ be the matrix whose columns are these basis vectors in order; note that $P$ is invertible by this previous exercise. Now if $A$ is the matrix for $T$ with respect to the standard bases, then $P^{-1}AP$ is the matrix for $T$ with respect to the basis forming the columns of $P$. (This is the standard ‘change of basis’ procedure.)We can see then (by evaluating $T$ on each $T^kf_i$) that $P^{-1}AP$ is precisely the direct sum of the companion matrices of the invariant factors $a_i(x)$. That is, $P^{-1}AP$ is in rational canonical form.

[This is kind of rough. I would probably rearrange the material a bit, compared to the book’s ordering of results. No time to think about that now though.]