University Mathematics — Year 3 · Bachelor Year 3

3Modules over a Principal Ideal Domain

Linear algebra over a ring instead of a field: this small change of hypothesis produces one of algebra’s great unification theorems. A module over $\Z$ is an abelian group; a module over $K[X]$ is a vector space equipped with an endomorphism. The structure theorem for finitely generated modules over a PID therefore classifies, in one stroke, all finitely generated abelian groups and all endomorphisms up to similarity — Jordan’s reduction, which Year 2 obtained by delicate inductions, falls out as a corollary, together with its subtler sibling, the rational canonical form, valid over every field. The computational engine is the Smith normal form, an arithmetic of matrices worthy of Euclid.

Throughout, $A$ is a commutative ring, soon a PID; “module” means $A$ -module.

3.1 Modules, free modules

Definition 3.1

An $A$ -module is an abelian group $(M, +)$ with a scalar multiplication $A \times M \to M$ satisfying the vector-space axioms: $a(x + y) = ax + ay$ , $(a + b)x = ax + bx$ , $(ab)x = a(bx)$ , $1x = x$ . Submodules, quotients $M/N$ , morphisms ( $A$ -linear maps), direct sums $\bigoplus_i M_i$ , and the isomorphism theorems are defined and proved word for word as for vector spaces and abelian groups; in particular $M/\ker f \cong \operatorname{im} f$ for a morphism $f$ .

Example 3.2

The three motivating cases.

$A = K$ a field: modules are vector spaces.
$A = \Z$ : modules are exactly abelian groups ( $nx$ is forced to be $x + \dots + x$ ), submodules are subgroups.
$A = K[X]$ : a module is a $K$ -vector space $V$ together with the $K$ -linear map $u\colon x \mapsto X\cdot x$ — conversely, every pair $(V, u)$ with $u \in \mathcal L(V)$ becomes a $K[X]$ -module by $P \cdot x = P(u)(x)$ . The submodules are precisely the $u$ -stable subspaces.

An ideal of $A$ is exactly a submodule of $A$ ; a quotient ring $A/I$ is an $A$ -module. Unlike vector spaces, modules can have torsion: in $\Z/6\Z$ , the element $\bar 3 \ne 0$ is killed by $2 \neq 0$ .

Definition 3.3

$M$ is finitely generated if $M = Ax_1 + \dots + Ax_n$ for some $x_i$ . $M$ is free of rank $n$ if $M \cong A^n$ , i.e. if it has a basis (a generating family that is $A$ -linearly independent). Every finitely generated $M$ is a quotient of a free module: $(a_1, \dots, a_n) \mapsto \sum a_ix_i$ maps $A^n$ onto $M$ .

Proposition 3.4 (Invariance of rank)

If $A \neq 0$ and $A^m \cong A^n$ , then $m = n$ .

Proof. Pick a maximal ideal $\mathfrak m$ of $A$ (Theorem 2.8) and set $k = A/\mathfrak m$ , a field. An isomorphism $f \colon A^m \to A^n$ maps $\mathfrak m A^m$ into $\mathfrak m A^n$ (linearity), hence induces an isomorphism of quotients

A^m/\mathfrak m A^m \;\cong\; A^n/\mathfrak m A^n, \qquad\text{i.e.}\qquad k^m \cong k^n

as $k$ -vector spaces (the quotient $A^m/\mathfrak m A^m$ is killed by $\mathfrak m$ , so the $A$ -action factors through $k$ ; the images of the standard basis form a $k$ -basis). Dimension theory over the field $k$ gives $m = n$ . ∎

Theorem 3.5 (Submodules of free modules)

Let $A$ be a PID and $M \subseteq A^n$ a submodule. Then $M$ is free of rank $\leq n$ .

Proof. Induction on $n$ . For $n = 1$ : $M$ is an ideal, so $M = (0)$ (free of rank $0$ ) or $M = dA \cong A$ ( $x \mapsto dx$ is injective: domain). For $n > 1$ : let $\pi \colon A^n \to A$ be the last coordinate. Then $\pi(M)$ is an ideal, $(0)$ or $dA$ . If $(0)$ : $M \subseteq A^{n-1} \times \{0\}$ and induction applies. Otherwise choose $x_0 \in M$ with $\pi(x_0) = d$ . Every $x \in M$ writes uniquely

x = \underbrace{\frac{\pi(x)}{d}}_{\in A}\, x_0 + \Bigl(x - \tfrac{\pi(x)}d x_0\Bigr), \qquad x - \tfrac{\pi(x)}d x_0 \in M \cap \ker\pi

( $\pi(x) \in dA$ , so the coefficient is in $A$ ). Thus $M = Ax_0 \oplus (M \cap \ker \pi)$ : the sum is direct since $\pi(ax_0) = ad = 0$ forces $a = 0$ . By induction $M \cap \ker\pi \subseteq \ker \pi \cong A^{n-1}$ is free of rank $\leq n - 1$ ; adjoining $x_0$ (independent from $\ker\pi$ as just seen) gives a basis of $M$ of cardinality $\leq n$ . ∎

Remark 3.6

Consequently, over a PID every finitely generated module $M$ has a finite presentation: a surjection $\varphi\colon A^n \to M$ has free kernel with basis $c_1, \dots, c_k$ ( $k \leq n$ ), and $M \cong A^n / \operatorname{im}(C)$ where $C \in M_{n,k}(A)$ is the matrix whose columns are the $c_j$ . Understanding $M$ means understanding a matrix over $A$ up to change of bases in source and target — the subject of the next section.

3.2 Smith normal form

Definition 3.7

Two matrices $B, C \in M_{n,k}(A)$ are equivalent if $C = QBP$ with $Q \in GL_n(A)$ , $P \in GL_k(A)$ (invertible over $A$ : determinant in $A^\times$ ). Equivalent presentation matrices define isomorphic modules $A^n/ \operatorname{im}$ (change bases in $A^n$ and $A^k$ ).

Theorem 3.8 (Smith normal form)

Let $A$ be a PID and $B \in M_{n,k}(A)$ . Then $B$ is equivalent to a diagonal matrix

\operatorname{diag}(d_1, d_2, \dots, d_r, 0, \dots, 0), \qquad d_1 \mid d_2 \mid \cdots \mid d_r \neq 0 ,

and the $d_i$ are unique up to associates: $d_1 \cdots d_i$ is a gcd of the $i \times i$ minors of $B$ (in particular that gcd is an invariant of equivalence). The $d_i$ are the invariant factors of $B$ .

Proof. Existence. If $B = 0$ , done. Otherwise, consider the set of ideals $(b)$ generated by entries of matrices equivalent to $B$ ; since $A$ is Noetherian, choose a matrix $B'$ equivalent to $B$ and an entry $d$ of $B'$ with $(d)$ maximal in this set. Move $d$ to position $(1,1)$ by row and column swaps.

Claim: $d$ divides every entry of $B'$ . First, column 1: if $b_{i1}$ is not a multiple of $d$ , let $e = \gcd(d, b_{i1}) = ud + vb_{i1}$ (Bézout), so $(e) \supsetneq (d)$ . The $2 \times 2$ matrix trick: acting on rows $1$ and $i$ by

\begin{pmatrix} u & v \\ -\dfrac{b_{i1}}e & \dfrac de \end{pmatrix} \in GL_2(A) \qquad \Bigl(\det = \tfrac{ud + v b_{i1}}e = 1\Bigr)

produces an equivalent matrix with entry $e$ in position $(1,1)$ : this contradicts maximality of $(d)$ . So $d$ divides column $1$ , and symmetrically row $1$ . Subtracting multiples of row 1 and column 1 clears them: $B'$ is equivalent to $\begin{pmatrix} d & 0\\ 0 & B''\end{pmatrix}$ . Next, $d$ divides every entry $b$ of $B''$ : add the row of $b$ to row 1 (an elementary operation; the new first row contains $d$ and $b$ -entries), and repeat the column-clearing argument: a non-multiple would again improve $(d)$ . Now induct on the size: $B''$ , all of whose entries are divisible by $d$ , has a Smith form $\operatorname{diag}(d_2, \dots)$ whose entries remain divisible by $d$ (every entry of any $QB''P$ is an $A$ -combination of entries of $B''$ ); set $d_1 = d$ .

Uniqueness. Let $D_i(B)$ denote a gcd of all $i \times i$ minors. Row and column operations, and more generally multiplication by any matrix, cannot shrink the gcd: the $i \times i$ minors of $QB$ are $A$ -combinations of those of $B$ (Cauchy–Binet expansion; or directly: each row of $QB$ is a combination of rows of $B$ , and minors are multilinear in rows). So $D_i(QBP)$ and $D_i(B)$ divide each other: $D_i$ is an equivalence invariant. On the diagonal form, the nonzero $i \times i$ minors are the products of $i$ of the $d_j$ ’s, and divisibility $d_1 \mid \dots \mid d_r$ makes $d_1 \cdots d_i$ the gcd. Hence $d_1 \cdots d_i = D_i(B)$ up to units, and $d_i = D_i/D_{i-1}$ is determined. ∎

Method 3.9

Over a Euclidean domain ( $\Z$ , $K[X]$ ), Smith reduction is an algorithm — no maximality argument needed: bring the entry of smallest Euclidean size to position $(1,1)$ ; if it fails to divide some entry of its row or column, a Euclidean division leaves a strictly smaller remainder there — swap it in and restart (termination: sizes decrease); when it divides its whole row and column, clear them; if it fails to divide an inner entry, add that row to row $1$ and restart; recurse on the inner block. In practice on integer matrices: compute $D_1 = \gcd$ of entries, $D_2$ , … via minors for small sizes, or run the algorithm.

Example 3.10 (A Smith reduction, in full)

Reduce $M = \begin{pmatrix} 1 & 2 & 3\\ 4 & 5 & 6\\ 7 & 8 & 9 \end{pmatrix}$ over $\Z$ . The corner $1$ divides everything: clear its row and column ( $L_2 \leftarrow L_2 - 4L_1$ , $L_3 \leftarrow L_3 - 7L_1$ , then $C_2 \leftarrow C_2 - 2C_1$ , $C_3 \leftarrow C_3 - 3C_1$ ):

M \sim \begin{pmatrix} 1 & 0 & 0\\ 0 & -3 & -6\\ 0 & -6 & -12 \end{pmatrix} .

In the inner block, the corner $-3$ divides all entries: $L_3 \leftarrow L_3 - 2L_2$ and $C_3 \leftarrow C_3 - 2C_2$ clear it to $\operatorname{diag}(-3, 0)$ . Adjusting signs (multiply a row by $-1$ , a legal operation):

M \sim \operatorname{diag}(1, 3, 0), \qquad \Z^3/M\Z^3 \cong \Z/3\Z \times \Z .

Cross-check by determinantal divisors: $D_1 = \gcd(\text{entries}) = 1$ ; every $2\times2$ minor of $M$ is a multiple of $3$ (e.g. $\det\bigl(\begin{smallmatrix}1 & 2\\ 4 & 5\end{smallmatrix}\bigr) = -3$ ) and one equals $-3$ : $D_2 = 3$ ; $D_3 = \det M = 0$ . Hence $d_1 = 1$ , $d_2 = 3$ , $d_3 = 0$ : same answer. Two lessons: a zero invariant factor records the rank drop (the cokernel picks up a free $\Z$ summand), and the divisibility chain $1 \mid 3 \mid 0$ is the Smith certificate — a diagonal reduction that violates the chain (say $\operatorname{diag}(2, 3)$ , which the careless can produce from $\bigl(\begin{smallmatrix}2 & 0\\ 0 & 3\end{smallmatrix}\bigr)$ by stopping too early: correct Smith form $\operatorname{diag}(1, 6)$ , as $D_1 = 1$ here!) is not finished.

The sublattice L = ℤ(2,0) + ℤ(1,3) of ℤ2 (red points). The Smith normal form of ( smallmatrix 2 & 1\\ 0 & 3 smallmatrix ) is diag(1, 6): in the adapted basis f_1 = (1,3), f_2 = (0,1) of ℤ2, one has L = ℤ f_1 ℤ\,6f_2, so ℤ2/L ℤ/6ℤ — the index equals | | = 6, the area of the shaded fundamental domain. — The sublattice $L = \Z(2,0) + \Z(1,3)$ of $\Z^2$ (red points). The Smith normal form of $\bigl(\begin{smallmatrix} 2 & 1\\ 0 & 3\end{smallmatrix}\bigr)$ is $\operatorname{diag}(1, 6)$ : in the adapted basis $f_1 = (1,3)$ , $f_2 = (0,1)$ of $\Z^2$ , one has $L = \Z f_1 \oplus \Z\,6f_2$ , so $\Z^2/L \cong \Z/6\Z$ — the index equals $\abs{\det} = 6$ , the area of the shaded fundamental domain.

3.3 The structure theorem

Definition 3.11

Let $A$ be a domain and $M$ an $A$ -module. The torsion submodule is

T(M) = \{x \in M : ax = 0 \text{ for some } a \neq 0\}

(a submodule: if $ax = by = 0$ then $ab(x + y) = 0$ , $ab \ne 0$ ). $M$ is torsion-free if $T(M) = 0$ , a torsion module if $T(M) = M$ .

Theorem 3.12 (Structure of finitely generated modules over a PID)

Let $A$ be a PID and $M$ a finitely generated $A$ -module. There exist a unique $r \in \N$ and nonzero nonunits $d_1 \mid d_2 \mid \cdots \mid d_s$ , unique up to associates, with

M \;\cong\; A^r \,\oplus\, A/(d_1) \oplus \cdots \oplus A/(d_s).

Moreover $T(M) \cong A/(d_1)\oplus\dots\oplus A/(d_s)$ and $M/T(M) \cong A^r$ : a finitely generated torsion-free module over a PID is free.

Proof. Existence. Present $M \cong A^n/\operatorname{im}(C)$ (Remark 3.6) and put $C$ in Smith form: after the two base changes, $M \cong A^n / (d_1A \times \dots \times d_rA \times 0 \times \dots \times 0) \cong A/(d_1) \oplus \dots \oplus A/(d_r) \oplus A^{\,n - r}$ . Discard the factors where $d_i$ is a unit ( $A/(d_i) = 0$ ); the divisibility chain survives.

The torsion identification. In the decomposition, $A^r$ is torsion-free (a domain has no zero divisors) and each $A/(d_i)$ is torsion (killed by $d_i \ne 0$ ); a direct sum splits torsion accordingly: $T(M) = \bigoplus_i A/(d_i)$ and $M/T(M) \cong A^r$ .

Uniqueness of $r$ : $M/T(M) \cong A^r$ depends only on $M$ , and Proposition 3.4 pins $r$ down.

Uniqueness of the $d_i$ : it suffices to treat the torsion module $T = T(M)$ . Decompose each $d_i$ into primes and split by the Chinese remainder theorem (Theorem 2.9; distinct primes generate comaximal ideals):

A/(d) \cong \bigoplus_{p \mid d} A/\bigl(p^{v_p(d)}\bigr): \qquad T \cong \bigoplus_{p} \bigoplus_{j} A/\bigl(p^{k_{p,j}}\bigr),

the elementary divisors $p^{k_{p,j}}$ . Conversely the $d_i$ are reconstructed from the multiset of elementary divisors ( $d_s$ = product of the highest power of each prime, etc.), so it suffices to prove the multiset $\{k_{p,j}\}_j$ is determined by $T$ , for each prime $p$ . Fix $p$ ; for $j \geq 1$ consider the $A/(p)$ -vector spaces $p^{j-1}T/p^jT$ . On a cyclic factor $A/(p^k)$ :

p^{j-1}\bigl(A/(p^k)\bigr)\big/p^{j}\bigl(A/(p^k)\bigr) \cong \begin{cases} A/(p) & \text{if } j \leq k,\\ 0 & \text{if } j > k, \end{cases}

and on a factor $A/(q^k)$ , $q \neq p$ : multiplication by $p$ is bijective there ( $p$ invertible mod $q^k$ : Bézout), so the quotient is $0$ . Direct sums pass through: $\dim_{A/(p)} p^{j-1}T/p^jT = \#\{i : k_{p,i} \geq j\}$ . These intrinsic dimensions determine the multiset of exponents. ∎

Corollary 3.13 (Finitely generated abelian groups)

Every finitely generated abelian group is $\Z^r \times \Z/d_1\Z\times\dots\times\Z/d_s\Z$ with $d_1 \mid \dots \mid d_s$ , uniquely. Every finite abelian group is a product of cyclic groups of prime-power order, unique as a multiset.

Example 3.14

The abelian groups of order $p^n$ correspond to partitions of $n$ : for $p^4$ : $\Z/p^4$ , $\Z/p^3\times\Z/p$ , $(\Z/p^2)^2$ , $\Z/p^2 \times (\Z/p)^2$ , $(\Z/p)^4$ — five groups, as $4$ has five partitions. Mixed orders multiply the counts prime by prime (CRT): there are $5 \times 2$ abelian groups of order $2^4 \cdot 3^2 = 144$ .

3.4 Application: canonical forms of endomorphisms

Let $K$ be a field, $V$ a $K$ -vector space of finite dimension $n$ , and $u \in \mathcal L(V)$ ; make $V$ a $K[X]$ -module via $P \cdot x = P(u)(x)$ (Example 3.2). This module is finitely generated (a $K$ -basis generates) and torsion: for each $x$ , the $n+1$ vectors $x, u(x), \dots, u^n(x)$ are $K$ -dependent, providing a nonzero annihilating polynomial.

Definition 3.15

For $P = X^m + a_{m-1}X^{m-1} + \dots + a_0$ monic, the companion matrix is

C_P = \begin{pmatrix} 0 & & & -a_0\\ 1 & \ddots & & -a_1\\ & \ddots & 0 & \vdots\\ & & 1 & -a_{m-1} \end{pmatrix} :

the matrix of “multiplication by $X$ ” on $K[X]/(P)$ in the basis $1, \bar X, \dots, \bar X^{m-1}$ .

Theorem 3.16 (Frobenius: rational canonical form)

There is a unique sequence of monic nonconstant polynomials $P_1 \mid P_2 \mid \dots \mid P_s$ (the similarity invariants of $u$ ) such that, as $K[X]$ -modules,

V \cong K[X]/(P_1) \oplus \cdots \oplus K[X]/(P_s):

in a suitable basis, $u$ has block-diagonal matrix $\operatorname{diag}(C_{P_1}, \dots, C_{P_s})$ . Moreover:

$P_s = \mu_u$ (minimal polynomial) and $P_1\cdots P_s = \chi_u$ (characteristic polynomial); in particular $\mu_u \mid \chi_u$ (Cayley–Hamilton re-proved) and $\chi_u \mid \mu_u^{\,s}$ , so $\chi_u$ and $\mu_u$ have the same irreducible factors.
Two endomorphisms (or square matrices) are similar iff they have the same similarity invariants.

Proof. The structure theorem (Theorem 3.12) applied to the PID $K[X]$ : the torsion module $V$ decomposes with invariant factors $P_i$ , normalized monic (units of $K[X]$ are $K^\times$ ); no free part occurs ( $V$ is torsion). On each cyclic factor $K[X]/(P_i)$ , multiplication by $X$ has matrix $C_{P_i}$ in the basis of powers of $\bar X$ : concatenating bases gives the block form.

(1) The annihilator of $V = \bigoplus K[X]/(P_i)$ is $(P_1)\cap \dots\cap(P_s) = (P_s)$ (divisibility chain: $P_s$ is a common multiple, and the class of $1$ in the last factor is killed exactly by $(P_s)$ ): $\mu_u = P_s$ . For $\chi_u$ : on a cyclic factor, $\chi_{C_P} = P$ , by induction on $m = \deg P$ . Expanding $\det(XI_m - C_P)$ along the first row (whose entries are $X$ , then zeros, then $a_0$ in the last column):

\det(XI_m - C_P) = X\,\det\bigl(XI_{m-1} - C_{\tilde P}\bigr) + (-1)^{1+m}\,a_0\,\det L ,

where $\tilde P = X^{m-1} + a_{m-1}X^{m-2} + \dots + a_1$ (same shape, one size down) and $L$ is triangular with diagonal $(-1, \dots, -1)$ , so $\det L = (-1)^{m-1}$ . By induction the first term is $X\tilde P$ , and the second is $a_0$ : the total is $X\tilde P + a_0 = P$ (base case $m=1$ : $\det(X + a_0) = P$ ). Determinants multiply over blocks: $\chi_u = \prod P_i$ . Cayley–Hamilton: $\chi_u \in (\mu_u)$ since $P_s \mid$ each… conversely each $P_i \mid P_s$ , so $\chi_u = \prod P_i$ divides $P_s^{\,s} = \mu_u^s$ ; and $\mu_u = P_s$ divides $\chi_u$ as one of its factors.

(2) Similar endomorphisms are conjugate module structures, hence have equal invariants (uniqueness in Theorem 3.12); conversely equal invariants give isomorphic $K[X]$ -modules, and a module isomorphism is exactly a linear bijection intertwining the two endomorphisms: a similarity. ∎

Corollary 3.17 (Similarity is insensitive to field extension)

Let $K \subseteq L$ be fields and $M, N \in M_n(K)$ . If $M$ and $N$ are similar over $L$ , they are similar over $K$ .

Proof. The similarity invariants of $M$ are computed by Smith’s minor formula (Theorem 3.8) applied to the presentation matrix $XI_n - M$ over $K[X]$ — indeed the $K[X]$ -module $V_M = K^n$ has presentation $XI_n - M$ : the map $K[X]^n \to V_M$ , $(Q_i) \mapsto \sum Q_i(M)e_i$ , is onto with kernel generated by the columns of $XI_n - M$ (a direct verification: modulo those columns, every element of $K[X]^n$ reduces to a constant vector, and constant vectors map bijectively; the weekend problem spells this out). Gcds of polynomials do not change under field extension: if $d$ is the monic gcd in $K[X]$ of a family $(f_j)$ , Bézout gives $d = \sum u_jf_j$ with $u_j \in K[X]$ , so every common divisor of the $f_j$ in $L[X]$ divides $d$ ; as $d$ is itself a common divisor, it is the gcd in $L[X]$ too. Hence the invariant factors of $XI_n - M$ , quotients of successive minor gcds, are the same over $K$ and over $L$ : $M, N$ have the same similarity invariants over $L$ iff over $K$ ; conclude by Theorem 3.16(2). ∎

Theorem 3.18 (Jordan form, re-derived)

Suppose $\chi_u$ splits over $K$ (e.g. $K = \C$ ). Applying to $V$ the elementary-divisor decomposition (proof of Theorem 3.12) instead of invariant factors:

V \cong \bigoplus_{\lambda, j} K[X]\big/\bigl((X - \lambda)^{k_{\lambda,j}}\bigr),

and in the basis $\bigl(\overline{(X-\lambda)^{k-1}}, \dots, \overline{(X - \lambda)}, \bar 1\bigr)$ of each factor, $u$ acts as the Jordan block $J_k(\lambda)$ : every endomorphism with split characteristic polynomial has a Jordan basis, and the multiset of blocks $(\lambda, k)$ is unique.

Proof. The elementary divisors of the torsion module $V$ are the $(X - \lambda)^k$ with $X - \lambda$ ranging over the irreducible factors of $\mu_u$ (which splits, since $\chi_u$ does and both have the same irreducible factors, Theorem 3.16). In $W = K[X]/((X-\lambda)^k)$ , put $f_j = \overline{(X - \lambda)^{k-j}}$ for $j = 1, \dots, k$ : then $(X - \lambda)f_j = f_{j-1}$ (with $f_0 = 0$ ), i.e. $u(f_j) = \lambda f_j + f_{j-1}$ : the matrix of $u$ on $(f_1, \dots, f_k)$ is exactly $J_k(\lambda)$ (ones above the diagonal). Uniqueness of the multiset of elementary divisors is Theorem 3.12. ∎

Remark 3.19

The hierarchy of canonical forms is now transparent: the rational form exists over every field and detects similarity absolutely (Corollary 3.17); the Jordan form is its refinement when $\chi_u$ splits. Year 2’s dimension-counting proofs of Jordan’s theorem are subsumed: all the combinatorics was the arithmetic of the PID $K[X]$ .

3.5 Exercises

Exercise 3.1 ★

(a) Show that $\Q$ is not finitely generated as a $\Z$ -module. (b) Show that $\Q$ is torsion-free but not free. (c) Why does neither statement contradict Theorem 3.12?

Solution

Solution of Exercise 3.1.

(a) If $\Q = \Z q_1 + \dots + \Z q_k$ , let $d$ be a common denominator of the $q_i$ : every combination lies in $\frac1d\Z$ , but $\frac1{2d} \notin \frac1d\Z$ . Contradiction.

(b) Torsion-free: $nq = 0$ with $n \neq 0$ forces $q = 0$ in $\Q$ . Not free: any two nonzero rationals $\frac ab, \frac cd$ satisfy the nontrivial relation $(bc)\frac ab - (ad)\frac cd = 0$ , so a basis has at most one element; $\Q \cong \Z$ would make $\Q = \Z q$ cyclic, but $\frac q2 \notin \Z q$ . (And $\Q \neq 0$ .)

(c) Theorem 3.12 assumes finite generation, which (a) denies: no contradiction — rather, $\Q$ shows the hypothesis is necessary in the statement “torsion-free $\Rightarrow$ free”.

Exercise 3.2 ★

List the abelian groups of order $360$ up to isomorphism, in both elementary-divisor and invariant-factor forms. How many abelian groups of order $p^5$ are there?

Solution

Solution of Exercise 3.2.

$360 = 2^3\cdot3^2\cdot5$ . Partitions: of $3$ : $(3), (2,1), (1,1,1)$ ; of $2$ : $(2), (1,1)$ ; of $1$ : $(1)$ . Hence $3 \times 2 \times 1 = 6$ groups. Elementary divisors $\to$ invariant factors:

$\Z/8 \times \Z/9 \times \Z/5$	$\Z/360$
$\Z/8 \times \Z/3 \times \Z/3 \times \Z/5$	$\Z/3 \times \Z/120$
$\Z/4 \times \Z/2 \times \Z/9 \times \Z/5$	$\Z/2 \times \Z/180$
$\Z/4 \times \Z/2 \times \Z/3 \times \Z/3 \times \Z/5$	$\Z/6 \times \Z/60$
$(\Z/2)^3 \times \Z/9 \times \Z/5$	$\Z/2 \times \Z/2 \times \Z/90$
$(\Z/2)^3 \times \Z/3 \times \Z/3 \times \Z/5$	$\Z/2 \times \Z/6 \times \Z/30$

(To pass to invariant factors: the largest $d_s$ collects the highest prime power of each prime, and so on down.) Of order $p^5$ : as many as partitions of $5$ , namely $7$ .

Exercise 3.3 ★

Compute the Smith normal form over $\Z$ of

B = \begin{pmatrix} 2 & 4\\ 6 & 8 \end{pmatrix}, \qquad C = \begin{pmatrix} 2 & 0 & 0\\ 0 & 3 & 0\\ 0 & 0 & 12 \end{pmatrix},

and identify the abelian groups $\Z^2/B\Z^2$ and $\Z^3/C\Z^3$ .

Solution

Solution of Exercise 3.3.

$B$ : $D_1 = \gcd(2,4,6,8) = 2$ ; $D_2 = \abs{\det B} = \abs{16 - 24} = 8$ . Invariant factors $d_1 = 2$ , $d_2 = 8/2 = 4$ : Smith form $\operatorname{diag}(2, 4)$ , and $\Z^2/B\Z^2 \cong \Z/2\Z \times \Z/4\Z$ .

$C$ : diagonal but not Smith ( $2 \nmid 3$ ). $D_1 = \gcd(2,3,12) = 1$ ; $D_2 = \gcd(2\cdot3,\, 2\cdot12,\, 3\cdot12) = \gcd(6, 24, 36) = 6$ ; $D_3 = 72$ . So $d = (1, 6, 12)$ and $\Z^3/C\Z^3 \cong \Z/6\Z\times\Z/12\Z$ — consistently with the CRT: $\Z/2\times\Z/3\times\Z/12 \cong \Z/6\times\Z/12$ .

Exercise 3.4 ★★

Let $L \subseteq \Z^n$ be a subgroup of rank $n$ with basis the columns of $B \in M_n(\Z)$ , $\det B \neq 0$ . Show that $\Z^n/L$ is finite of cardinality $\abs{\det B}$ , and that $\Z^n/L \cong \prod_i \Z/d_i\Z$ for the invariant factors $d_i$ of $B$ . Illustrate with $L = \Z(2,0) + \Z(1,3)$ .

Solution

Solution of Exercise 3.4.

Write $B = Q\,\operatorname{diag}(d_1, \dots, d_n)\,P$ with $Q, P \in GL_n(\Z)$ (Theorem 3.8; no zero $d_i$ since $\det B \neq 0$ ). Then $\Z^n/B\Z^n \cong \Z^n/ \operatorname{diag}(d)\Z^n = \prod_i \Z/d_i\Z$ (the composed isomorphism $x \mapsto Q^{-1}x$ of $\Z^n$ maps $B\Z^n$ onto $\operatorname{diag}(d)P\Z^n = \operatorname{diag}(d)\Z^n$ ). Its cardinality is $\prod \abs{d_i} = \abs{\det \operatorname{diag}(d)} = \abs{\det B}$ , as $\det Q, \det P = \pm 1$ . For $L = \Z(2,0) + \Z(1,3)$ : $B = \bigl(\begin{smallmatrix}2 & 1\\ 0 & 3\end{smallmatrix}\bigr)$ , $D_1 = 1$ , $D_2 = 6$ : $\Z^2/L \cong \Z/6\Z$ , of cardinality $\abs{\det B} = 6$ .

Exercise 3.5 ★★

Let $A$ be a domain. (a) Verify that $T(M)$ is a submodule and that $M/T(M)$ is torsion-free. (b) Show that the ideal $(X, Y)$ of $K[X,Y]$ , as a $K[X,Y]$ -module, is torsion-free but not free: the structure theorem genuinely needs the PID hypothesis.

Solution

Solution of Exercise 3.5.

(a) Submodule: done in Definition 3.11. If $a(x + T(M)) = 0$ in $M/T(M)$ with $a \neq 0$ , then $ax \in T(M)$ : $bax = 0$ for some $b \neq 0$ , and $ba \neq 0$ (domain), so $x \in T(M)$ : the class is zero. $M/T(M)$ is torsion-free.

(b) $(X, Y) \subseteq K[X,Y]$ is torsion-free (a submodule of the domain $K[X,Y]$ acting on itself). Suppose it were free; any two elements $P, Q$ satisfy $Q\cdot P - P \cdot Q = 0$ , a nontrivial relation when $P \ne Q$ are nonzero, so a basis has one element: $(X, Y) = (P)$ principal — contradicting Exercise 2.6(a). Torsion-free and finitely generated ( $X, Y$ generate), yet not free: over the non-PID $K[X,Y]$ , the structure theorem fails.

Exercise 3.6 ★★

(a) Show that $2\Z$ has no direct complement in the $\Z$ -module $\Z$ : submodules of free modules are free (Theorem 3.5), but direct summands they need not be. (b) Show that if $M \subseteq A^n$ ( $A$ a PID) satisfies: $A^n/M$ is torsion-free, then $M$ is a direct summand.

Solution

Solution of Exercise 3.6.

(a) If $\Z = 2\Z \oplus C$ , the projection $\Z \to \Z/2\Z$ restricts to an isomorphism $C \cong \Z/2\Z$ : $C$ would be a subgroup of $\Z$ whose nonzero element $x$ satisfies $2x \in C \cap 2\Z = 0$ . But $\Z$ is torsion-free: $C = 0$ , forcing $\Z = 2\Z$ — false.

(b) $A^n/M$ is finitely generated and torsion-free, hence free (Theorem 3.12): $A^n/M \cong A^r$ with basis $f_1, \dots, f_r$ . Choose preimages $y_i \in A^n$ of the $f_i$ and set $F = Ay_1 + \dots + Ay_r$ . Every $x \in A^n$ has $\pi(x) = \sum a_if_i$ , so $x - \sum a_iy_i \in M$ : $A^n = M + F$ . If $\sum a_iy_i \in M$ , applying $\pi$ gives $\sum a_if_i = 0$ , hence all $a_i = 0$ (basis): $M \cap F = 0$ . So $A^n = M \oplus F$ .

Exercise 3.7 ★★

Solve in $\Z^2$ the system

\begin{cases} 2x + 4y \equiv b_1 \pmod{20},\\ 6x + 8y \equiv b_2 \pmod{20}, \end{cases}

for which pairs $(b_1, b_2)$ solutions exist, using the Smith form of Exercise 3.3 (invertible changes of variables on both sides).

Solution

Solution of Exercise 3.7.

The reduction of Exercise 3.3 was effective: with

L = \begin{pmatrix} 1 & 0\\ -3 & 1\end{pmatrix}, \qquad R = \begin{pmatrix} 1 & 2\\ 0 & -1 \end{pmatrix}, \qquad LBR = \begin{pmatrix} 2 & 0\\ 0 & 4\end{pmatrix}

(row operation $R_2 \leftarrow R_2 - 3R_1$ , column operations $C_2 \leftarrow C_2 - 2C_1$ then $C_2 \leftarrow -C_2$ ). Setting $y = R^{-1}x$ (a bijection of $(\Z/20\Z)^2$ , $R$ being invertible over $\Z$ ), the system $Bx \equiv b \pmod{20}$ is equivalent to

2y_1 \equiv b_1, \qquad 4y_2 \equiv -3b_1 + b_2 \pmod{20}.

The congruence $ky \equiv c \pmod{20}$ is solvable iff $\gcd(k, 20) \mid c$ : solutions exist iff $2 \mid b_1$ and $4 \mid b_2 - 3b_1$ , i.e. $b_1$ even and $b_2 \equiv 3b_1 \pmod 4$ . When solvable there are $2 \times 4 = 8$ solutions modulo $20$ .

Exercise 3.8 ★★

(a) Determine all similarity invariants and possible Jordan forms of a nilpotent $4 \times 4$ matrix, sorted by the partition of $4$ they realize. (b) Exhibit two $4\times4$ complex matrices with the same characteristic and minimal polynomials that are not similar, and prove that for $n \leq 3$ this cannot happen.

Solution

Solution of Exercise 3.8.

(a) A nilpotent $u$ has $\mu_u = X^k$ ; the elementary divisors are $X^{k_1} \geq \dots$ , one Jordan block $J_{k_i}(0)$ per part of a partition of $4$ :

partition	Jordan form	invariant factors
$(4)$	$J_4$	$X^4$
$(3,1)$	$J_3 \oplus J_1$	$X,\ X^3$
$(2,2)$	$J_2 \oplus J_2$	$X^2,\ X^2$
$(2,1,1)$	$J_2 \oplus J_1 \oplus J_1$	$X,\ X,\ X^2$
$(1,1,1,1)$	$0$	$X, X, X, X$

(b) Take $u = J_2\oplus J_2$ and $v = J_2 \oplus J_1 \oplus J_1$ : both have $\chi = X^4$ , $\mu = X^2$ , but different invariant factors — not similar (Theorem 3.16); one can also compare ranks: $\operatorname{rk} u = 2 \neq 1 = \operatorname{rk} v$ . For $n \leq 3$ : $\chi$ and $\mu$ determine, for each eigenvalue $\lambda$ (over a splitting field), the total size $m_\lambda \leq 3$ of the $\lambda$ -blocks and the largest block $r_\lambda$ ; a partition of $m \leq 3$ is determined by its largest part ( $m = 3, r = 2$ forces $(2,1)$ , etc.). So the elementary divisors coincide, and Corollary 3.17 descends the similarity to the base field.

Exercise 3.9 ★★★

Let $u \in \mathcal L(V)$ , $\dim V = n$ . Show that the following are equivalent: (i) $V$ is a cyclic $K[X]$ -module (there is $x$ with $V = K[u]x$ , a cyclic vector); (ii) $\mu_u = \chi_u$ ; (iii) $s = 1$ in Theorem 3.16. Deduce that a companion matrix has a cyclic vector, and determine when a diagonal matrix has one.

Solution

Solution of Exercise 3.9.

(i) $\Rightarrow$ (ii): if $V = K[u]x$ , then $V \cong K[X]/\operatorname{Ann}(x)$ , and $\operatorname{Ann}(x) = (\mu_u)$ (a polynomial kills $x$ iff it kills all of $V = K[u]x$ , since $P(u)Q(u)x = Q(u)P(u)x$ ). So $n = \dim V = \deg \mu_u$ ; as $\mu_u \mid \chi_u$ and $\deg\chi_u = n$ , monicity gives $\mu_u = \chi_u$ .

(ii) $\Rightarrow$ (iii): $\deg\chi_u = \sum_i \deg P_i$ and $\mu_u = P_s$ (Theorem 3.16); equality of degrees forces $s = 1$ .

(iii) $\Rightarrow$ (i): $V \cong K[X]/(P_1)$ is cyclic, generated by the preimage of $\bar 1$ .

A companion matrix is the case $V = K[X]/(P)$ itself: $x = \bar 1$ , i.e. $e_1$ , is cyclic. For a diagonal matrix $\operatorname{diag}(\lambda_1, \dots, \lambda_n)$ : $\chi = \prod (X - \lambda_i)$ , $\mu = \prod_{\lambda \text{ distinct}} (X - \lambda)$ ; they agree iff the $\lambda_i$ are pairwise distinct: a diagonal matrix has a cyclic vector iff its diagonal entries are pairwise distinct (then $x = (1, \dots, 1)$ works: Vandermonde).

Exercise 3.10 ★★★

For $M \in M_n(\Z)$ viewed as an endomorphism of $\Z^n$ , prove the index formula: if $\det M \ne 0$ , then $[\Z^n : M\Z^n] = \abs{\det M}$ , and deduce that $M \in GL_n(\Z)$ iff $\det M = \pm 1$ . Application: the group $\Z^2$ has exactly $\sigma_1(m) = \sum_{d \mid m} d$ subgroups of index $m$ . (Count matrices in Hermite form $\bigl(\begin{smallmatrix} a & b\\ 0 & d\end{smallmatrix}\bigr)$ , $ad = m$ , $0 \leq b < d$ .)

Solution

Solution of Exercise 3.10.

Smith: $M = Q\operatorname{diag}(d_1,\dots,d_n)P$ ; Exercise 3.4 gives $[\Z^n : M\Z^n] = \prod\abs{d_i} = \abs{\det M}$ . If $\det M = \pm 1$ : the adjugate formula $M^{-1} = (\det M)^{-1}\,{}^{t}\!\operatorname{com}(M)$ has integer entries, so $M \in GL_n(\Z)$ ; conversely $MM^{-1} = I$ gives $\det M \cdot \det M^{-1} = 1$ in $\Z$ , so $\det M = \pm1$ .

Subgroups of index $m$ in $\Z^2$ : such a subgroup $L$ has rank $2$ (finite index) and a unique basis in Hermite normal form $\bigl(\begin{smallmatrix} a & b\\ 0 & d\end{smallmatrix}\bigr)$ : $d$ is characterized by $L \cap (\{0\} \times \Z) = \{0\} \times d\Z$ , $a$ by $\pi_1(L) = a\Z$ (first coordinates), and $b$ is then unique modulo $d$ ; normalize $a, d > 0$ and $0 \leq b < d$ . The index is $ad = m$ . Counting: for each divisor $d \mid m$ ( $a = m/d$ ), there are $d$ choices of $b$ : total $\sum_{d \mid m} d = \sigma_1(m)$ .

Exercise 3.11 ★★

(Equations $x^k = e$ in abelian groups) Let $G$ be a finite abelian group with invariant factors $d_1 \mid d_2 \mid \dots \mid d_s$ . (a) Show that for every $k \geq 1$ ,

\#\{x \in G : x^k = e\} \;=\; \prod_{i=1}^{s}\gcd(k, d_i) .

(b) Deduce: a finite abelian group is cyclic if and only if for every $k$ , the equation $x^k = e$ has at most $k$ solutions. (c) Recover the cyclicity of finite subgroups of $K^\times$ ( $K$ a field, Chapter 4): why does the polynomial $X^k - 1$ guarantee the criterion of (b)?

Solution

Solution of Exercise 3.11.

(a) By the structure theorem, $G \cong \prod_i\Z/d_i\Z$ , and $x^k = e$ decouples coordinatewise. In $\Z/d\Z$ : $kx \equiv 0 \pmod d$ has exactly $\gcd(k, d)$ solutions ( $x$ must be a multiple of $d/\gcd(k,d)$ , and there are $\gcd(k, d)$ of those). Multiply over the factors.

(b) If $G = \Z/d_s\Z$ is cyclic ( $s = 1$ ), the count is $\gcd(k, d_s) \leq k$ . If $s \geq 2$ : take $k = d_1$ ; the count is $\prod_i\gcd(d_1, d_i) = d_1^{\,s} > d_1$ (each $\gcd$ equals $d_1$ by the divisibility chain): the equation $x^{d_1} = e$ has more than $d_1$ solutions.

(c) In a field, $X^k - 1$ has at most $k$ roots (Chapter 2: a nonzero polynomial of degree $k$ over a domain), so every finite subgroup $G \leq K^\times$ satisfies the criterion of (b): $G$ is cyclic — the one-line structural proof of the cyclicity of $\mathbb F_q^\times$ , complementing the counting proof of Chapter 4.

Exercise 3.12 ★★★

(Elementary matrices generate) (a) Show that $M \in M_n(\Z)$ is invertible in $M_n(\Z)$ iff $\det M = \pm1$ . (b) Show that $SL_2(\Z)$ is generated by the two elementary matrices $E = \bigl(\begin{smallmatrix}1 & 1\\ 0 & 1\end{smallmatrix}\bigr)$ and $F = \bigl(\begin{smallmatrix}1 & 0\\ 1 & 1\end{smallmatrix}\bigr)$ . (Run the Euclidean algorithm on the first column of $M \in SL_2(\Z)$ by left multiplications by powers of $E, F$ , reaching $\pm\bigl(\begin{smallmatrix}1 & *\\ 0 & 1\end{smallmatrix}\bigr)$ ; finish by hand — note $-I = (EF^{-1}E)^2$ .) (c) Explain the connection with Smith reduction: over $\Z$ , row and column operations of determinant $1$ suffice to diagonalize, up to signs.

Solution

Solution of Exercise 3.12.

(a) If $MN = I$ with integer $N$ : $\det M\det N = 1$ with both integers, so $\det M = \pm1$ . Conversely if $\det M = \pm1$ , the cofactor formula $M^{-1} = \frac1{\det M}\,{}^t\!\operatorname{com}(M)$ has integer entries.

(b) Left multiplication by $E^{-k}$ subtracts $k$ times row $2$ from row $1$ ; by $F^{-k}$ , $k$ times row $1$ from row $2$ . Given $M = \bigl(\begin{smallmatrix}a & *\\ c & *\end{smallmatrix}\bigr) \in SL_2(\Z)$ , the first column $(a, c)$ is a unimodular vector ( $\gcd(a, c) = 1$ : it divides $\det M = 1$ ). Run Euclid on $(a, c)$ by these row operations: after finitely many steps the column becomes $(\pm1, 0)$ . The matrix is now $\pm \bigl(\begin{smallmatrix}1 & b\\ 0 & 1\end{smallmatrix} \bigr) = \pm E^{b}$ (the determinant stayed $1$ ). It remains to write $-I$ in the generators: $(EF^{-1}E)^2 = \bigl(\begin{smallmatrix}0 & 1\\ -1 & 0\end{smallmatrix}\bigr)^2 = -I$ (check the square of the rotation matrix). Unwinding, $M$ is a word in $E^{\pm1}, F^{\pm1}$ .

(c) The Smith algorithm (Method 3.9) uses exactly such row and column operations (plus swaps and sign changes, themselves products of elementary operations up to determinant sign): over $\Z$ , every matrix is $U\,D\,V$ with $U, V$ products of elementary matrices and $D$ the Smith form — (b) is the $2\times2$ , determinant- $1$ instance of the general fact that $E$ -type matrices generate $SL_n(\Z)$ .

3.6 Problem: the commutant and the double commutant

Problem 3.1

Weekend problem — rational form, commutant, bicommutant

Let $K$ be a field, $V$ a $K$ -vector space of dimension $n \geq 1$ , and $u \in \mathcal L(V)$ . We study the commutant

\mathcal C(u) = \{v \in \mathcal L(V) : uv = vu\},

a subalgebra of $\mathcal L(V)$ containing $K[u] = \{P(u) : P \in K[X]\}$ , and we prove Frobenius’ dimension formula and the double commutant theorem: $\mathcal C(\mathcal C(u)) = K[u]$ . Throughout, $V$ is the $K[X]$ -module defined by $u$ , with invariant factors $P_1 \mid \cdots \mid P_s$ and cyclic decomposition $V = \bigoplus_{i=1}^s V_i$ , $V_i = K[u]\,x_i \cong K[X]/(P_i)$ , $n_i = \deg P_i$ (Theorem 3.16).

Part I — The presentation matrix $XI - M$ , and warm-ups.

Let $M \in M_n(K)$ and let $\varphi \colon K[X]^n \to V_M = K^n$ send $(Q_1, \dots, Q_n)$ to $\sum_i Q_i(M)e_i$ . Show that $\varphi$ is a surjective morphism of $K[X]$ -modules and that every column of $XI_n - M$ lies in $\ker\varphi$ .
Show that, modulo the columns of $XI_n - M$ , every element of $K[X]^n$ is congruent to a constant vector (reduce degrees using $Xe_i \equiv \sum_j m_{ji}e_j$ ), and deduce $\ker\varphi = (XI_n - M)\,K[X]^n$ : the module $V_M$ has presentation matrix $XI_n - M$ . Recover Corollary 3.17’s starting point: the similarity invariants of $M$ are the nonunit invariant factors of $XI_n - M$ .
Compute the similarity invariants of: a scalar matrix $\lambda I_n$ ; a diagonal matrix with distinct diagonal entries; the $n \times n$ Jordan block $J_n(0)$ ; $\operatorname{diag}(J_2(0), J_1(0))$ for $n = 3$ .
Show that $\dim K[u] = \deg \mu_u = n_s$ .

Part II — Morphisms between cyclic modules.

Let $P, Q$ be monic nonconstant. Show that a $K[X]$ -morphism $f \colon K[X]/(P) \to K[X]/(Q)$ is determined by $f(\bar 1)$ , and that $\bar c \in K[X]/(Q)$ can serve as $f(\bar 1)$ iff $P\bar c = 0$ in $K[X]/(Q)$ .
Deduce

$\operatorname{Hom}_{K[X]}\bigl(K[X]/(P),\, K[X]/(Q)\bigr) \;\cong\; K[X]\big/\bigl(\gcd(P, Q)\bigr),$

of dimension $\deg \gcd(P, Q)$ over $K$ . (Show that the solutions $\bar c$ of $P\bar c = 0$ in $K[X]/(Q)$ form the cyclic submodule generated by $\overline{Q/\gcd(P,Q)}$ .)
Prove Frobenius’ formula:

$\dim_K \mathcal C(u) = \sum_{i,j=1}^{s} \deg\gcd(P_i, P_j) = \sum_{i=1}^{s} (2s - 2i + 1)\, n_i .$

(A commuting $v$ is exactly a $K[X]$ -endomorphism of $V$ ; decompose $\operatorname{End}(\bigoplus_i V_i)$ as matrices of morphisms $V_j \to V_i$ and use the divisibility chain.)
Deduce $\dim \mathcal C(u) \geq n$ , with equality iff $u$ is cyclic ( $s = 1$ ), and compute $\dim\mathcal C(u)$ for $u = \lambda\,\mathrm{id}$ : both extremes of the formula.
Verify Frobenius’ formula directly for $\operatorname{diag}(J_2(0), J_1(0))$ by computing the commutant explicitly as $3\times3$ matrices.

Part III — The double commutant theorem. Let $w \in \mathcal C(\mathcal C(u))$ ; we prove $w \in K[u]$ .

Show $K[u] \subseteq \mathcal C(\mathcal C(u))$ , and that every $w \in \mathcal C(\mathcal C(u))$ commutes with $u$ — so the inclusion to be proved, $\mathcal C(\mathcal C(u)) \subseteq K[u]$ , is a genuine sharpening of $w \in \mathcal C(u)$ .
Suppose first that $u$ is cyclic, $V = K[u]x$ . Show directly that $\mathcal C(u) = K[u]$ (evaluate a commuting $v$ on $x$ : $v(x) = P(u)x$ for some $P$ , and compare $v$ with $P(u)$ on the basis $u^k x$ ), and conclude the theorem in this case.
Back to the general case. For each $i$ , let $\pi_i\colon V \to V_i$ be the projection along the other summands. Show $\pi_i \in \mathcal C(u)$ , and deduce that $w$ preserves each $V_i$ and commutes with $u_i = u\restriction_{V_i}$ ; conclude via question 11 applied to the cyclic $u_i$ : there are polynomials $Q_i$ with $w\restriction_{V_i} = Q_i(u)\restriction_{V_i}$ .
It remains to glue the $Q_i$ into one polynomial. For $i \leq j$ (so $P_i \mid P_j$ ), show that $\eta_{ij} \colon V_j \to V_i$ , $R(u)x_j \mapsto R(u)x_i$ , is a well-defined $K[X]$ -morphism (what must be checked is that $R(u)x_j = 0$ implies $R(u)x_i = 0$ ), and that $\tilde\eta_{ij} = \eta_{ij}\circ\pi_j$ , extended by $0$ on the other summands, lies in $\mathcal C(u)$ .
Using $w\tilde\eta_{ij} = \tilde\eta_{ij}w$ , show $Q_i \equiv Q_j \pmod{P_i}$ for $i \leq j$ . Deduce that $Q = Q_s$ satisfies $Q \equiv Q_i \pmod {P_i}$ for all $i$ , hence $w = Q(u)$ on every $V_i$ , hence on $V$ :

$\boxed{\ \mathcal C(\mathcal C(u)) = K[u].\ }$
(Coda) Deduce from the theorem: if $v$ commutes with every matrix commuting with $u$ , and $u$ is cyclic, then $v$ is a polynomial in $u$ ; and give an example showing $\mathcal C(u) = K[u]$ fails for $u = \mathrm{id}$ , $n \geq 2$ — where exactly does cyclicity enter?

Part IV — Dividends of the similarity invariants. The rational canonical form is a machine; here are five of its classical outputs.

(Transpose) Show that every $M \in M_n(K)$ is similar to its transpose ${}^tM$ . (The operations that bring $XI - M$ to Smith form, transposed, bring $XI - {}^tM$ to the same Smith form: equal similarity invariants.)
(Descent of similarity) Let $K \subseteq L$ be a field extension and $M, N \in M_n(K)$ . Show that if $M$ and $N$ are similar over $L$ , they are similar over $K$ . (The Smith form of $XI - M$ computed in $K[X]$ is still a Smith form in $L[X]$ — why do the invariant factors not change?) Consequence worth memorizing: two real matrices conjugate in $GL_n(\C)$ are conjugate in $GL_n(\R)$ .
(Nilpotent classification) Let $u$ be nilpotent. Show that the number of blocks of size $\geq k$ in its decomposition into nilpotent Jordan blocks equals $\operatorname{rk}u^{k-1} - \operatorname{rk}u^k$ , and deduce: nilpotent classes of $M_n(K)$ , for any field $K$ , are in bijection with the partitions of $n$ . How many nilpotent classes in $M_5(K)$ ?
(A concrete pair) Determine the similarity invariants of the derivation $D\colon P \mapsto P'$ acting on the space $K_{n-1}[X]$ of polynomials of degree $< n$ : (a) for $K = \Q$ ; (b) for $K = \mathbb F_p$ with $p < n$ (in characteristic $p$ , $(X^p)' = 0$ : compute $\ker D^k$ and use question 18).
(Conjugacy classes of $GL_2(\mathbb F_q)$ ) Using invariant factors, show that every class of $GL_2(\mathbb F_q)$ is of exactly one of four types: central $aI$ ; diagonalizable with two distinct eigenvalues $a \neq b$ in $\mathbb F_q^\times$ ; non-semisimple with minimal polynomial $(X - a)^2$ ; cyclic with irreducible characteristic polynomial.
Count the classes of each type and conclude: $GL_2(\mathbb F_q)$ has exactly $q^2 - 1$ conjugacy classes. (Count monic irreducible quadratics over $\mathbb F_q$ ; unordered pairs $\{a, b\}$ ; remember invertibility constrains constant terms.)
(Cyclic is generic) Show that $M \in M_2(\mathbb F_q)$ fails to be cyclic iff $M$ is scalar, and deduce that a uniformly random $2\times2$ matrix over $\mathbb F_q$ is cyclic with probability $1 - q^{-3}$ . State the analogous heuristic for $M_n$ and large $q$ (no proof required): non-cyclic matrices are rare — which is why Problem 3.1’s Part III needed real work only past the generic case.

Part V — Complements.

(Center of the commutant) Show that the center of the algebra $\mathcal C(u)$ is exactly $K[u]$ (combine the two inclusions of Part III). Deduce that $\mathcal C(u)$ is commutative iff $u$ is cyclic — recovering the equality case of question 8 by a purely structural route.
(Which dimensions occur?) Deduce from Frobenius’ formula that $\dim\mathcal C(u) \equiv n \pmod 2$ for every $u$ . Then determine the exact set of values taken by $\dim \mathcal C(u)$ as $u$ ranges over $\mathcal L(V)$ with $\dim V = 4$ : show it is $\{4, 6, 8, 10, 16\}$ (enumerate the degree sequences $n_1 \leq \dots \leq n_s$ summing to $4$ and realize each by a nilpotent). In particular $12$ and $14$ , though of the right parity, are not attained: the parity constraint is necessary but not sufficient.
(Class equation of $GL_2(\mathbb F_3)$ ) For $q = 3$ , compute the size of each conjugacy class of question 20 via orbit–stabilizer: the centralizer of a cyclic $M$ in $GL_2(\mathbb F_q)$ is the unit group of $K[M]$ (question 11). Identify $K[M]$ in the three noncentral types, list the three monic irreducible quadratics over $\mathbb F_3$ , and verify the class equation

$48 = \abs{GL_2(\mathbb F_3)} = 2\cdot1 + 1\cdot12 + 2\cdot8 + 3\cdot6,$

with $2 + 1 + 2 + 3 = 8 = q^2 - 1$ classes, as predicted by question 21.

Solution

Solution of Problem 3.1.

1. $\varphi$ is additive, and $K[X]$ -linear: $\varphi(X \cdot (Q_i)_i) = \sum_i (XQ_i)(M)e_i = M\sum_i Q_i(M)e_i = X \cdot \varphi\bigl((Q_i)_i\bigr)$ , the module structure of $V_M$ being $X \cdot v = Mv$ . It is surjective: constant vectors give all of $K^n$ . Column $j$ of $XI - M$ is $Xe_j - \sum_i m_{ij}e_i$ , whose image is $Me_j - \sum_i m_{ij}e_i = 0$ .

2. Modulo the columns, $Xe_j \equiv \sum_i m_{ij}e_i$ : any vector of polynomials reduces, by induction on the top degree, to a constant vector $c \in K^n$ . If the original vector is in $\ker\varphi$ , then $\varphi(c) = c = 0$ (on constants, $\varphi$ is the identification $K^n = V_M$ ), so the vector lies in the column span: $\ker\varphi = (XI_n - M)K[X]^n$ . Hence $V_M \cong K[X]^n/(XI - M)K[X]^n$ , and Smith over $K[X]$ (all invariant factors nonzero, their product being $\det(XI - M) = \chi_M$ ) gives $V_M \cong \bigoplus_i K[X]/(f_i)$ : the nonconstant $f_i$ are the similarity invariants, computable as quotients of minor gcds (Theorem 3.8).

3. $\lambda I_n$ : $XI - \lambda I$ is already Smith: invariants $(X - \lambda, \dots, X - \lambda)$ , $n$ of them. Distinct diagonal entries: $V \cong \bigoplus_i K[X]/(X - \lambda_i)$ with pairwise comaximal moduli, so CRT compresses to the single cyclic $K[X]/\bigl(\prod_i(X - \lambda_i)\bigr)$ : one invariant, $\chi$ . $J_n(0)$ : $\mu = X^n = \chi$ forces a single invariant $X^n$ . $\operatorname{diag}(J_2(0), J_1(0))$ : elementary divisors $X^2, X$ : invariants $P_1 = X \mid P_2 = X^2$ .

4. $P \mapsto P(u)$ maps $K[X]$ onto $K[u]$ , with kernel $(\mu_u)$ by definition of the minimal polynomial: $K[u] \cong K[X]/(\mu_u)$ , of dimension $\deg\mu_u = \deg P_s = n_s$ .

5. $K[X]$ -linearity forces $f(\bar Q) = f(Q\cdot\bar 1) = Q\,f(\bar 1)$ . The class $\bar 1$ satisfies $P \bar 1 = 0$ , so $P f(\bar 1) = 0$ is necessary. Conversely if $P\bar c = 0$ , then $f(\bar Q) = Q\bar c$ is well defined ( $Q \equiv Q' \bmod P \Rightarrow (Q - Q')\bar c \in$ multiples of $P\bar c = 0$ ) and $K[X]$ -linear.

6. Let $g = \gcd(P, Q)$ , $P = gP'$ , $Q = gQ'$ with $\gcd(P', Q') = 1$ . In $K[X]/(Q)$ : $P\bar c = 0 \iff Q \mid Pc \iff Q' \mid P'c \iff Q' \mid c$ (Euclid, $\gcd(P', Q') = 1$ ). So the admissible $\bar c$ form the submodule generated by $\bar{Q'}$ , whose annihilator is $\{R : Q \mid RQ'\} = (g)$ : that submodule is $\cong K[X]/(g)$ . With question 5, $\operatorname{Hom}(K[X]/(P), K[X]/(Q)) \cong K[X]/(\gcd(P,Q))$ , of dimension $\deg\gcd(P,Q)$ .

7. $v$ commutes with $u$ iff $v$ commutes with every $P(u)$ , iff $v$ is $K[X]$ -linear: $\mathcal C(u) = \operatorname{End}_{K[X]}(V)$ . Writing morphisms of $V = \bigoplus_j V_j$ as matrices $(f_{ij})$ , $f_{ij} \in \operatorname{Hom}(V_j, V_i)$ (compose with injections and projections), question 6 gives

\dim \mathcal C(u) = \sum_{i,j} \deg\gcd(P_i, P_j) = \sum_{i,j} n_{\min(i,j)} = \sum_{k=1}^{s} \bigl(2(s - k) + 1\bigr)\,n_k ,

using the divisibility chain ( $\gcd(P_i, P_j) = P_{\min(i,j)}$ ) and, for the last step, that $\min(i,j) = k$ happens for exactly $2(s - k) + 1$ pairs $(i, j)$ .

8. Since $2(s-k)+1 \geq 1$ , $\dim\mathcal C(u) \geq \sum_k n_k = n$ , with equality iff $s = 1$ , i.e. iff $u$ is cyclic (Exercise 3.9). For $u = \lambda\,\mathrm{id}$ : $s = n$ , all $n_k = 1$ : $\dim = \sum_{k=1}^n (2(n-k)+1) = n^2$ — correct, since $\mathcal C(\lambda\,\mathrm{id}) = \mathcal L(V)$ .

9. Formula: invariants $(X, X^2)$ , so $s = 2$ , $n_1 = 1$ , $n_2 = 2$ : $\dim = 3\cdot1 + 1\cdot2 = 5$ . Directly: in the basis $(e_1, e_2, e_3)$ with $u e_2 = e_1$ , $ue_1 = ue_3 = 0$ , writing $Au = uA$ for $A = (a_{ij})$ yields the conditions $a_{21} = a_{23} = a_{31} = 0$ and $a_{11} = a_{22}$ : five free parameters $a_{11}{=}a_{22}, a_{12}, a_{13}, a_{32}, a_{33}$ .

10. A polynomial $P(u)$ commutes with anything that commutes with $u$ (it is a sum of powers of $u$ ): $K[u] \subseteq \mathcal C(\mathcal C(u))$ . And $u \in \mathcal C(u)$ , so any $w \in \mathcal C(\mathcal C(u))$ commutes with $u$ .

11. Let $V = K[u]x$ and $v \in \mathcal C(u)$ . Write $v(x) = P(u)x$ (cyclicity). For $y = Q(u)x$ arbitrary: $v(y) = vQ(u)x = Q(u)v(x) = Q(u)P(u)x = P(u)y$ . So $v = P(u)$ : $\mathcal C(u) = K[u]$ . Then $\mathcal C(\mathcal C(u)) = \mathcal C(K[u]) = \mathcal C(u) = K[u]$ (commuting with all of $K[u]$ is the same as commuting with $u$ ). The theorem holds in the cyclic case.

12. $\pi_i$ is $K[X]$ -linear (the decomposition is a direct sum of submodules), so $\pi_i \in \mathcal C(u)$ , and $w$ commutes with it: $w(V_i) = w\pi_i(V) = \pi_i w(V) \subseteq V_i$ . The restriction $w_i = w\restriction_{V_i}$ commutes with the cyclic $u_i = u\restriction_{V_i}$ (question 10), and $w_i \in \mathcal C(u_i) = K[u_i]$ (question 11): $w_i = Q_i(u_i) = Q_i(u)\restriction_{V_i}$ for some $Q_i \in K[X]$ .

13. Well-definedness of $\eta_{ij}(R(u)x_j) = R(u)x_i$ : if $R(u)x_j = 0$ then $P_j \mid R$ , and $P_i \mid P_j$ gives $P_i \mid R$ , so $R(u)x_i = 0$ ( $\operatorname{Ann}(x_i) = (P_i)$ ). $\eta_{ij}$ is then $K[X]$ -linear by construction, and $\tilde\eta_{ij} = \eta_{ij}\pi_j$ is a composition of $K[X]$ -morphisms $V \to V$ : $\tilde\eta_{ij} \in \mathcal C(u)$ .

14. Evaluate $w\tilde\eta_{ij} = \tilde\eta_{ij}w$ at $x_j$ : the left side is $w(x_i) = Q_i(u)x_i$ ; the right side is $\eta_{ij}\bigl(Q_j(u)x_j\bigr) = Q_j(u)x_i$ . Hence $(Q_i - Q_j)(u)\,x_i = 0$ : $P_i \mid Q_i - Q_j$ for all $i \leq j$ . In particular, with $Q = Q_s$ : $Q \equiv Q_i \pmod{P_i}$ , so $Q(u)$ and $Q_i(u)$ agree on $V_i$ (which $P_i(u)$ kills). Therefore $w = Q(u)$ on each $V_i$ , hence on $V$ : $\mathcal C(\mathcal C(u)) \subseteq K[u]$ , and with question 10, $\mathcal C(\mathcal C(u)) = K[u]$ .

15. The first assertion is questions 10–14 (or, for cyclic $u$ , question 11 alone). For $u = \mathrm{id}$ , $n \geq 2$ : $\mathcal C(u) = \mathcal L(V)$ has dimension $n^2$ , while $\dim K[u] = \deg\mu_u = 1$ . So $\mathcal C(u) = K[u]$ fails badly; yet the bicommutant theorem holds ( $\mathcal C(\mathcal L(V)) = K\,\mathrm{id} = K[u]$ : the center of the matrix algebra is the scalars). Cyclicity is what makes the single commutant already polynomial; the double commutant is polynomial always.

16. If $P(XI - M)Q = S$ is a Smith reduction ( $P, Q$ invertible over $K[X]$ ), transposing gives ${}^tQ\,(XI - {}^tM)\,{}^tP = {}^tS = S$ : same Smith form, so $XI - M$ and $XI - {}^tM$ have the same invariant factors, i.e. $M$ and ${}^tM$ have the same similarity invariants (Corollary 3.17): they are similar.

17. The similarity invariants of $M$ over $L$ are the invariant factors of $XI - M$ in $L[X]$ . A Smith reduction of $XI - M$ over $K[X]$ — invertible $P, Q$ over $K[X]$ , diagonal with the divisibility chain — is also a valid Smith reduction over $L[X]$ ( $P, Q$ stay invertible: their determinants are nonzero constants), and monic invariant factors are unique: the invariant factors computed over $K$ and over $L$ coincide. So $M \sim_L N$ iff they have the same invariant factors iff $M \sim_K N$ . In particular $\C$ -conjugate real matrices are $\R$ -conjugate — a statement often proved analytically (specialize an invertible $P + \iu Q$ ), here structurally.

18. Decompose $u = \bigoplus J_{m_t}(0)$ into nilpotent Jordan blocks. In one block of size $m$ , $\operatorname{rk}J_m^k = \max(m - k, 0)$ , so $\operatorname{rk}J_m^{k-1} - \operatorname{rk}J_m^k = 1$ if $m \geq k$ , $0$ otherwise. Summing over blocks: $\operatorname{rk}u^{k-1} - \operatorname{rk}u^k = \#\{t : m_t \geq k\}$ . The rank sequence therefore determines the multiset $(m_t)$ — a partition of $n$ — and conversely each partition is realized: nilpotent classes $\leftrightarrow$ partitions of $n$ , over every field. $M_5$ : $p(5) = 7$ classes ( $5$ ; $4{+}1$ ; $3{+}2$ ; $3{+}1{+}1$ ; $2{+}2{+}1$ ; $2{+}1{+}1{+}1$ ; $1^5$ ).

19. (a) Over $\Q$ (or any characteristic- $0$ field), $D^n = 0$ , $D^{n-1}(X^{n-1}) = (n-1)!\, \neq 0$ : $D$ is nilpotent of index $n$ on an $n$ -dimensional space, hence cyclic with single invariant $X^n$ ( $x = X^{n-1}$ generates: its iterated derivatives span). (b) Over $\mathbb F_p$ with $p < n$ : $D^p = 0$ , because the $p$ -th derivative of every monomial $X^m$ carries the factor $m(m-1)\cdots(m-p+1)$ , a product of $p$ consecutive integers, hence $\equiv 0 \bmod p$ . Write $n = ap + r$ , $0 \leq r < p$ . Then $\ker D^k$ is spanned by the monomials $X^m$ with $D^kX^m = 0$ ; counting exponents $m < n$ by their residue mod $p$ : $\dim\ker D^k = ak + \min(r, k)$ for $0 \leq k \leq p$ , so $\operatorname{rk}D^{k-1} - \operatorname{rk}D^k = \dim\ker D^k - \dim\ker D^{k-1} = a + \mathbf 1_{k \leq r}$ . By question 18, the partition has $a$ blocks of size exactly $p$ and (if $r > 0$ ) one block of size $r$ : similarity invariants $X^r \mid X^p \mid \dots \mid X^p$ . Characteristic changes the canonical form of the most familiar operator in mathematics.

20. $M \in GL_2$ has $s \in \{1, 2\}$ invariant factors. If $s = 2$ : $P_1 = P_2 = X - a$ ( $a \neq 0$ : invertibility), i.e. $M = aI$ , central. If $s = 1$ : $M$ is cyclic with characteristic $=$ minimal polynomial $\chi$ of degree $2$ , and the classes correspond to the possible $\chi$ with $\chi(0) \neq 0$ : $\chi$ split with distinct roots $a \neq b$ (companion $\sim$ diagonal); $\chi = (X - a)^2$ (companion, non-semisimple); $\chi$ irreducible. Exactly one type each — the invariant factors are a complete invariant.

21. Central: $q - 1$ choices of $a$ . Distinct split eigenvalues: unordered pairs $\{a, b\} \subseteq \mathbb F_q^\times$ , $a \neq b$ : $\binom{q-1}2$ classes. Minimal $(X-a)^2$ : $q - 1$ classes. Irreducible quadratics with nonzero constant term: all irreducible quadratics qualify (their roots are nonzero), and there are $\frac{q^2 - q}2$ monic irreducible quadratics (the $q^2$ monic quadratics minus the $\binom q2 + q = \frac{q^2+q}2$ split ones). Total:

(q - 1) + \frac{(q-1)(q-2)}2 + (q - 1) + \frac{q^2 - q}2 = q^2 - 1 .

22. If $M$ is not cyclic, $s = 2$ and $M$ is scalar (question 20’s dichotomy holds in $M_2$ , invertible or not: two invariant factors of degree $1$ with $P_1 \mid P_2$ and $P_1 = P_2$ forces $M = aI$ ). Scalars number $q$ among the $q^4$ matrices: cyclic probability $1 - q^{-3}$ . In general the non-cyclic locus of $M_n$ is where the $(n-1)\times(n-1)$ minors of $XI - M$ share a factor — a proper algebraic condition — so its proportion is $O(1/q)$ -small for large $q$ : matrices with $\chi = \mu$ are the rule, and Part III’s gluing argument is the price paid for the exceptions.

23. An element of the center of $\mathcal C(u)$ lies in $\mathcal C(u)$ and commutes with every element of $\mathcal C(u)$ , i.e. lies in $\mathcal C(\mathcal C(u)) = K[u]$ (question 14). Conversely $K[u] \subseteq \mathcal C(u)$ , and every $P(u)$ commutes with every $v \in \mathcal C(u)$ (such a $v$ commutes with $u$ , hence with each power of $u$ ): $K[u]$ is central in $\mathcal C(u)$ . Hence $Z(\mathcal C(u)) = K[u]$ . Consequently $\mathcal C(u)$ is commutative iff $\mathcal C(u) = Z(\mathcal C(u)) = K[u]$ ; in that case $\dim\mathcal C(u) = \dim K[u] = n_s \leq n$ , while question 8 gives $\dim\mathcal C(u) \geq n$ : so $n_s = n$ and $s = 1$ , i.e. $u$ is cyclic. Conversely, for $u$ cyclic question 11 gives $\mathcal C(u) = K[u]$ , commutative. Structurally: a matrix algebra equal to its own center is exactly a polynomial algebra $K[u]$ of a cyclic $u$ .

24. Each coefficient $2s - 2i + 1$ in Frobenius’ formula is odd, so

\dim\mathcal C(u) = \sum_{i=1}^s(2s - 2i + 1)\,n_i \equiv \sum_{i=1}^s n_i = n \pmod 2 .

For $n = 4$ , the possible degree sequences $n_1 \leq \dots \leq n_s$ of the invariant factors, summing to $4$ , are $(4)$ , $(1, 3)$ , $(2, 2)$ , $(1, 1, 2)$ , $(1, 1, 1, 1)$ ; every one is realized, e.g. by the nilpotent with $P_i = X^{n_i}$ (the divisibility chain holds automatically). The formula gives, respectively,

1\cdot4 = 4, \quad 3 + 3 = 6, \quad 6 + 2 = 8, \quad 5 + 3 + 2 = 10, \quad 7 + 5 + 3 + 1 = 16 .

So the value set is $\{4, 6, 8, 10, 16\}$ : even numbers of the right parity, but $12$ and $14$ never occur — between the almost-cyclic sequences and the scalar’s $n^2$ there is a gap.

25. $\abs{GL_2(\mathbb F_3)} = (q^2 - 1)(q^2 - q) = 8 \cdot 6 = 48$ . Central type: $I$ and $2I$ , two classes of size $1$ . In the three other types $M$ is cyclic (question 20), so its centralizer in $GL_2$ is the group of invertible elements of $\mathcal C(M) = K[M]$ (question 11), and class size $=48/\abs{K[M]^\times}$ by orbit–stabilizer. Distinct split eigenvalues: only the pair $\{1, 2\}$ , one class; $K[M] \cong \mathbb F_3 \times \mathbb F_3$ (CRT on $\chi = (X-1) (X-2)$ ), units $2 \cdot 2 = 4$ , size $48/4 = 12$ . Minimal $(X - a)^2$ , $a \in \{1, 2\}$ : two classes; $K[M] \cong \mathbb F_3[X]/((X-a)^2)$ , units $q^2 - q = 6$ (constant term of the unit $\neq 0$ after centering), size $48/6 = 8$ . Irreducible $\chi$ : the monic irreducible quadratics over $\mathbb F_3$ number $(9 - 3)/2 = 3$ , namely

X^2 + 1, \qquad X^2 + X + 2, \qquad X^2 + 2X + 2,

(no roots in $\mathbb F_3$ : check $0, 1, 2$ ); three classes, $K[M] \cong \mathbb F_9$ , units $q^2 - 1 = 8$ , size $48/8 = 6$ . Class equation: $2\cdot1 + 1\cdot12 + 2\cdot8 + 3\cdot6 = 2 + 12 + 16 + 18 = 48$ ; and $2 + 1 + 2 + 3 = 8 = q^2 - 1$ classes, matching question 21.