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.]

Post a comment or leave a trackback: Trackback URL.

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: