10.7 Polynomial Matrices and the Smith Normal Form

The rational canonical form of the previous section is a complete answer to the similarity problem, but the proof did not tell us how to find the invariant factors of a given matrix. This section supplies the missing algorithm, and it comes from an unexpected place: instead of working with $\mathbf{A}$ , we work with the single polynomial matrix $x\mathbf{I} - \mathbf{A}$ , and we reduce it by row and column operations whose scalars are allowed to be polynomials. The reduced form is diagonal, its non-constant diagonal entries are the invariant factors, and two matrices are similar exactly when their reduced forms agree. On the way we finally pay off a promise from Chapter 4: every square matrix is similar to its transpose, over every field.

10.7.1. The space as a module over the polynomials

Everything in this chapter is built by applying polynomials in $T$ to vectors: the $T$ -annihilator of a vector, the cyclic subspace $Z(\mathbf{v}; T)$ , the kernels $\operatorname{ker} p(T)$ . Name that structure once. For $V$ a vector space over $F$ and $T \in \mathcal{L}(V)$ , the product $F[x] \times V \to V, \qquad p \cdot \mathbf{v} \mathrel{:=} p(T)\,\mathbf{v}$ satisfies, by Theorem 6.7.1, exactly the vector space axioms with $F$ replaced by $F[x]$ : it is additive in each factor, $(pq)\cdot\mathbf{v} = p\cdot(q\cdot\mathbf{v})$ , and $1\cdot\mathbf{v} = \mathbf{v}$ . A set with an addition and a product by the elements of a commutative ring $R$ obeying these rules is an $R$ -module, so the pair $(V, T)$ is the same thing as an $F[x]$ -module that is finite-dimensional over the constants $F$ . We develop no general theory of modules; the point is the dictionary:

$F[x]$ -module language	operator language
submodule of $V$	$T$ -invariant subspace (Definition 9.1.1)
submodule generated by $\mathbf{v}$ , that is $F[x]\cdot\mathbf{v}$	cyclic subspace $Z(\mathbf{v}; T)$ (Definition 10.5.1)
the annihilator of $\mathbf{v}$ in $F[x]$	the $T$ -annihilator of $\mathbf{v}$
$V$ is generated by one element	$T$ has a cyclic vector

A subspace closed under multiplication by $x$ is closed under multiplication by every polynomial, which is why the first two lines match.

Where does $x\mathbf{I} - \mathbf{A}$ come from here? Fix $\mathcal{B} = (\mathbf{b}_1, \dots, \mathbf{b}_n)$ with $\mathbf{A} = [T]_{\mathcal{B}}^{\mathcal{B}}$ . As an $F[x]$ -module, $V$ is generated by $\mathbf{b}_1, \dots, \mathbf{b}_n$ , subject to the $n$ relations $x\cdot\mathbf{b}_j = \sum_i a_{ij}\mathbf{b}_i$ , whose coefficient vectors are the columns of $x\mathbf{I} - \mathbf{A}$ . So $x\mathbf{I} - \mathbf{A}$ is the matrix of relations, and changing generators or replacing one relation by a combination of relations should not change $V$ . That is the intuition behind the operations we now allow; the proofs below are matrix proofs and do not rely on it.

10.7.2. Row and column operations with polynomial multipliers

A matrix in $M_n(F[x])$ will be called a polynomial matrix. Over a field we reduced a matrix by three kinds of row operation (Definition 3.2.1). Over $F[x]$ we must be careful with one of them: multiplying a row by $x$ cannot be undone, because $x$ has no inverse in $F[x]$ . So the scaling operation keeps its scalar in $F$ , while the operation that adds a multiple of one row to another may use any polynomial multiplier.

Definition 10.7.1 (Elementary Operations over

F\lbrack x\rbrack

)

Let $\mathbf{M} \in M_n(F[x])$ . An elementary row operation over $F[x]$ on $\mathbf{M}$ is one of:

(E1) interchanging two rows;
(E2) multiplying one row by a non-zero scalar $c \in F$ ;
(E3) adding $h$ times one row to a different row, where $h \in F[x]$ is any polynomial.

Elementary column operations over $F[x]$ are defined the same way with “column” in place of “row”.

In words: (E1) and (E3) are as over a field, except that (E3) now permits a polynomial multiplier; (E2) is restricted, because only the non-zero constants have inverses in $F[x]$ . Each of the three is reversible by an operation of the same kind: swap back, scale by $c^{-1}$ , add $-h$ times the row back.

Two polynomial matrices reachable from one another by such operations should count as the same. As over a field (Definition 4.3.1), the clean way to say this is with invertible matrices on both sides — but “invertible” must now mean invertible inside $M_n(F[x])$ .

Proposition 10.7.1 (Invertible Polynomial Matrices)

Let $\mathbf{U} \in M_n(F[x])$ . Then $\mathbf{U}$ has an inverse in $M_n(F[x])$ if and only if $\det \mathbf{U}$ is a non-zero constant.

Proof. $(\Rightarrow)$ Suppose $\mathbf{U} \mathbf{W} = \mathbf{I}$ with $\mathbf{W} \in M_n(F[x])$ . Taking determinants and using multiplicativity over the commutative ring $F[x]$ (Theorem 7.5.4 and the remark on commutative rings after it), $\det \mathbf{U} \cdot \det \mathbf{W} = 1$ . By Theorem 0.8.3, $\deg(\det \mathbf{U}) + \deg(\det \mathbf{W}) = \deg 1 = 0$ , and degrees of non-zero polynomials are $\ge 0$ , so $\deg(\det \mathbf{U}) = 0$ ; that is, $\det \mathbf{U} \in F \setminus\{0\}$ .

$(\Leftarrow)$ Suppose $\det \mathbf{U} = c \in F \setminus\{0\}$ . The adjugate identity $\mathbf{U} \operatorname{adj} \mathbf{U} = \operatorname{adj} \mathbf{U}\; \mathbf{U} = (\det \mathbf{U})\,\mathbf{I}$ holds over any commutative ring (Theorem 7.6.2 and the remark on commutative rings following it), and $\operatorname{adj} \mathbf{U} \in M_n(F[x])$ , since its entries are minors of $\mathbf{U}$ . So $\mathbf{W} = c^{-1}\operatorname{adj} \mathbf{U} \in M_n(F[x])$ satisfies $\mathbf{U} \mathbf{W} = \mathbf{W} \mathbf{U} = \mathbf{I}$ .

Definition 10.7.2 (Equivalence over

F\lbrack x\rbrack

)

Let $\mathbf{M}, \mathbf{M}' \in M_n(F[x])$ . We say $\mathbf{M}$ and $\mathbf{M}'$ are equivalent over $F[x]$ , written $\mathbf{M} \approx \mathbf{M}'$ , if there are $\mathbf{U}, \mathbf{V} \in M_n(F[x])$ , each invertible in $M_n(F[x])$ , with $\mathbf{M}' = \mathbf{U} \mathbf{M} \mathbf{V} .$

Proposition 10.7.2 (Operations and Equivalence)

Let $\mathbf{M}, \mathbf{M}' \in M_n(F[x])$ .

(a) $\approx$ is an equivalence relation on $M_n(F[x])$ .
(b) If $\mathbf{M}'$ is obtained from $\mathbf{M}$ by a finite sequence of elementary row and column operations over $F[x]$ , then $\mathbf{M} \approx \mathbf{M}'$ .

Proof.

(a) Take $\mathbf{U} = \mathbf{V} = \mathbf{I}$ for reflexivity. If $\mathbf{M}' = \mathbf{U} \mathbf{M} \mathbf{V}$ , then $\mathbf{M} = \mathbf{U}^{-1}\mathbf{M}'\mathbf{V}^{-1}$ , and $\mathbf{U}^{-1}, \mathbf{V}^{-1}$ are invertible in $M_n(F[x])$ ; this gives symmetry. If $\mathbf{M}' = \mathbf{U} \mathbf{M} \mathbf{V}$ and $\mathbf{M}'' = \mathbf{U}'\mathbf{M}'\mathbf{V}'$ , then $\mathbf{M}'' = (\mathbf{U}'\mathbf{U})\mathbf{M}(\mathbf{V} \mathbf{V}')$ , and a product of invertible matrices is invertible, which gives transitivity.
(b) Each elementary row operation over $F[x]$ is left multiplication by the matrix obtained by performing that operation on $\mathbf{I}_n$ , exactly as over a field (Theorem 3.4.1, whose proof uses only the ring operations). Those three matrices are $\mathbf{P}_{ij}$ , $\mathbf{D}_i(c)$ and $\mathbf{I} + h\mathbf{E}_{ij}$ with $i \ne j$ , of determinants $-1$ , $c \ne 0$ and $1$ respectively (Theorem 7.4.6 and Theorem 7.5.1, valid over a commutative ring), hence invertible in $M_n(F[x])$ by Proposition 10.7.1. Column operations are right multiplication by the same matrices. Now use (a).

Warning. Multiplying a row by a non-constant polynomial is not an allowed operation. It changes the answer. The matrix $\mathbf{M} = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$ becomes $\begin{pmatrix} x & 0 \\ 0 & 1 \end{pmatrix}$ after “multiplying row 1 by $x$ ”, and the two are not equivalent: their determinants are $1$ and $x$ , and by Proposition 10.7.1 the first is invertible over $F[x]$ while the second is not. The rule to remember is that only the units of $F[x]$ — the non-zero constants — may be used as scaling factors.

10.7.3. The Smith normal form

Every polynomial matrix can be brought to a diagonal form whose diagonal entries divide one another in turn, and that form is unique.

The existence proof is Euclidean division, run on whichever non-zero entry has the smallest degree: if that entry fails to divide one of its neighbors in the same row or column, the remainder gives a non-zero entry of strictly smaller degree, and degrees cannot decrease forever.

Theorem 10.7.3 (Smith Normal Form)

Let $F$ be a field, $n \ge 1$ and $\mathbf{M} \in M_n(F[x])$ . Then:

(a) (Existence) $\mathbf{M}$ is equivalent over $F[x]$ , by a finite sequence of elementary row and column operations, to a diagonal matrix $\mathbf{D} = \operatorname{diag}(d_1, d_2, \dots, d_n)$ in which every $d_i$ is monic or zero and $d_i \mid d_{i+1}$ for $i = 1, \dots, n-1$ .
(b) (Uniqueness) The list $(d_1, \dots, d_n)$ is determined by $\mathbf{M}$ : if $\mathbf{M} \approx \operatorname{diag}(d_1, \dots, d_n) \approx \operatorname{diag}(e_1, \dots, e_n)$ with both lists as in (a), then $d_i = e_i$ for every $i$ .

The matrix $\mathbf{D}$ is called the Smith normal form of $\mathbf{M}$ , and $d_1, \dots, d_n$ its invariant divisors.

Since $0 \mid f$ holds only for $f = 0$ , the divisibility chain forces the zero entries, if any, to be the last ones.

Idea. Step roadmap for existence. ① Among all matrices reachable from $\mathbf{M}$ by operations, pick one whose smallest non-zero entry degree is least, and move that entry to the corner. ② That corner entry $f$ must divide every other entry of its row and column: otherwise divide with remainder and produce an entry of smaller degree, contradicting the choice in ①. ③ Clear the first row and column with $f$ ; the same remainder trick, after adding a row to the first one, shows $f$ divides every entry of what is left. ④ Induct on the size. The divisibility $d_1 \mid d_2$ survives the induction because operations replace entries by $F[x]$ -combinations of entries.

For uniqueness, find a quantity that can be read off both $\mathbf{M}$ and $\mathbf{D}$ . The greatest common divisor of all $k \times k$ minors is such a quantity: minors of a product are $F[x]$ -combinations of minors of the factors (Cauchy–Binet), so the gcd cannot change under equivalence, and for a diagonal matrix with a divisibility chain it is simply $d_1d_2\cdots d_k$ .

Proof.

(a) If $\mathbf{M} = 0$ , it is already of the stated form. So assume $\mathbf{M} \ne 0$ .
For a non-zero $\mathbf{N} \in M_n(F[x])$ put $\delta(\mathbf{N}) \mathrel{:=} \min\{\, \deg n_{ij} : n_{ij} \ne 0 \,\} \in \mathbb{N} ,$ the least degree of a non-zero entry. Let $\mathcal{S}$ be the set of all non-zero matrices obtainable from $\mathbf{M}$ by finite sequences of elementary row and column operations over $F[x]$ ; it contains $\mathbf{M}$ . The set $\{\delta(\mathbf{N}) : \mathbf{N} \in \mathcal{S}\}$ is a non-empty subset of $\mathbb{N}$ , so it has a least element; fix $\mathbf{N} \in \mathcal{S}$ with $\delta(\mathbf{N})$ least.

Step 1. Put a least-degree entry in the corner, monic. Choose $(i, j)$ with $n_{ij} \ne 0$ and $\deg n_{ij} = \delta(\mathbf{N})$ . Swapping row $i$ with row $1$ and column $j$ with column $1$ (operations (E1)), and then scaling the new first row by the inverse of the leading coefficient of the corner entry (operation (E2)), we obtain a matrix in $\mathcal{S}$ whose $(1,1)$ -entry $f$ is monic of degree $\delta(\mathbf{N})$ . These operations permute the entries and rescale some of them, so the new matrix still has least non-zero entry degree $\delta(\mathbf{N})$ . Rename it $\mathbf{N}$ .

Step 2. $f$ divides every entry of the first row and the first column. Suppose $f \nmid n_{1j}$ for some $j \ge 2$ . By Theorem 6.1.1, $n_{1j} = qf + r$ with $r \ne 0$ and $\deg r < \deg f$ . Adding $-q$ times column $1$ to column $j$ (operation (E3)) produces a matrix $\mathbf{N}' \in \mathcal{S}$ whose $(1, j)$ -entry is $r \ne 0$ with $\deg r < \deg f = \delta(\mathbf{N})$ . Then $\delta(\mathbf{N}') < \delta(\mathbf{N})$ , contradicting the minimality of $\delta(\mathbf{N})$ . Hence $f \mid n_{1j}$ for every $j$ , and the same argument with rows in place of columns gives $f \mid n_{i1}$ for every $i$ .

Step 3. Clear the first row and column. For $j \ge 2$ add $-(n_{1j}/f)$ times column $1$ to column $j$ ; the multipliers are polynomials by Step 2, and after these operations the first row is $(f, 0, \dots, 0)$ while the first column is unchanged. Then for $i \ge 2$ add $-(n_{i1}/f)$ times row $1$ to row $i$ ; since the first row is now $(f, 0, \dots, 0)$ , this clears the first column and changes nothing else. The result is $\begin{pmatrix} f & 0 \\ 0 & \mathbf{M}' \end{pmatrix} \in \mathcal{S}, \qquad \mathbf{M}' \in M_{n-1}(F[x]),$ and its least non-zero entry degree is still $\delta(\mathbf{N})$ : it is $\ge \delta(\mathbf{N})$ by minimality, and $f$ is an entry of degree $\delta(\mathbf{N})$ .

Step 4. $f$ divides every entry of $\mathbf{M}'$ . Suppose $f \nmid (\mathbf{M}')_{kl}$ for some $k, l$ . Add row $k+1$ to row $1$ . The new first row is $\bigl(f, (\mathbf{M}')_{k1}, \dots, (\mathbf{M}')_{k,n-1}\bigr)$ , so the $(1, l+1)$ -entry of the resulting matrix $\mathbf{N}'' \in \mathcal{S}$ is $(\mathbf{M}')_{kl}$ , which is not divisible by $f$ , while the $(1,1)$ -entry is still $f$ , monic of degree $\delta(\mathbf{N})$ . By minimality $\delta(\mathbf{N}'') = \delta(\mathbf{N})$ , so Step 2 applies to $\mathbf{N}''$ and says that $f$ divides every entry of the first row of $\mathbf{N}''$ — a contradiction.

Step 5. Induct on $n$ . We prove (a) by induction on $n$ . For $n = 1$ , scale the single entry to be monic (or leave it $0$ ). For $n \ge 2$ , Steps 1–4 give a sequence of operations taking $\mathbf{M}$ to $f \oplus \mathbf{M}'$ with $f$ monic and $f$ dividing every entry of $\mathbf{M}'$ . By the induction hypothesis there are operations taking $\mathbf{M}'$ to $\mathbf{D}' = \operatorname{diag}(d_2, \dots, d_n)$ with every $d_i$ monic or zero and $d_2 \mid \dots \mid d_n$ ; performing the corresponding operations on rows and columns $2, \dots, n$ of $f \oplus \mathbf{M}'$ takes it to $f \oplus \mathbf{D}' = \operatorname{diag}(f, d_2, \dots, d_n)$ .

It remains to see that $f \mid d_2$ . By Proposition 10.7.2, $\mathbf{D}' = \mathbf{U}'\mathbf{M}'\mathbf{V}'$ for some $\mathbf{U}', \mathbf{V}' \in M_{n-1}(F[x])$ , so every entry of $\mathbf{D}'$ is a sum of products $u'_{ik}(\mathbf{M}')_{kl}v'_{lj}$ (Definition 0.9.9) and is therefore divisible by $f$ , since every $(\mathbf{M}')_{kl}$ is. In particular $f \mid d_2$ . Setting $d_1 = f$ finishes the induction.
(b) Call a set $I \subseteq [n]$ with $|I| = k$ a $k$ -set. For $\mathbf{M} \in M_n(F[x])$ and $1 \le k \le n$ define the $k$ -th determinantal divisor $\Delta_k(\mathbf{M}) \mathrel{:=} \text{the monic generator of the ideal } \big\langle\, \det \mathbf{M}_{I,J} : I, J \ k\text{-sets} \,\big\rangle \subseteq F[x],$ and $\Delta_k(\mathbf{M}) \mathrel{:=} 0$ if all the $k \times k$ minors of $\mathbf{M}$ vanish. This is well defined by Proposition 6.2.1 and Theorem 6.2.2: the ideal generated by the finitely many $k \times k$ minors is $\langle \Delta_k(\mathbf{M})\rangle$ for exactly one monic $\Delta_k(\mathbf{M})$ unless the ideal is $\{0\}$ . Equivalently, $\Delta_k(\mathbf{M})$ is the monic greatest common divisor of the $k \times k$ minors: it divides each of them, and every common divisor of them divides it (Theorem 6.2.3, extended from two polynomials to finitely many by the same ideal argument).

Claim 1. $\mathbf{M} \approx \mathbf{M}'$ implies $\Delta_k(\mathbf{M}) = \Delta_k(\mathbf{M}')$ for every $k$ .

Proof. Let $\mathbf{M}' = \mathbf{U} \mathbf{M} \mathbf{V}$ with $\mathbf{U}, \mathbf{V}$ invertible over $F[x]$ , and let $I, J$ be $k$ -sets. The submatrix of a product on rows $I$ and columns $J$ is the product of the submatrix of the left factor on rows $I$ and all columns with the submatrix of the right factor on all rows and columns $J$ (Definition 0.9.9, read off entry by entry). Applying this twice and then Theorem 7.7.2 over the commutative ring $F[x]$ — legitimate by the remark after that theorem — to the $k \times n$ times $n \times k$ products involved, $\det \mathbf{M}'_{I,J} = \sum_{S} \det \mathbf{U}_{I,S} \, \det (\mathbf{M} \mathbf{V})_{S,J} = \sum_{S} \sum_{R} \det \mathbf{U}_{I,S}\, \det \mathbf{M}_{S,R}\, \det \mathbf{V}_{R,J},$ with $S$ and $R$ running over the $k$ -sets. So every $k \times k$ minor of $\mathbf{M}'$ is an $F[x]$ -combination of $k \times k$ minors of $\mathbf{M}$ , hence lies in $\langle \det \mathbf{M}_{S,R} \rangle$ . Therefore $\Delta_k(\mathbf{M})$ divides every $k \times k$ minor of $\mathbf{M}'$ , and so $\Delta_k(\mathbf{M}) \mid \Delta_k(\mathbf{M}')$ . Exchanging the roles of $\mathbf{M}$ and $\mathbf{M}'$ using $\mathbf{M} = \mathbf{U}^{-1}\mathbf{M}'\mathbf{V}^{-1}$ gives $\Delta_k(\mathbf{M}') \mid \Delta_k(\mathbf{M})$ . Two monic polynomials dividing each other are equal (Proposition 6.1.2), and if one is $0$ so is the other.

Claim 2. If $\mathbf{D} = \operatorname{diag}(d_1, \dots, d_n)$ with $d_1 \mid d_2 \mid \dots \mid d_n$ , then $\Delta_k(\mathbf{D}) = d_1d_2\cdots d_k$ .

Proof. Let $I, J$ be $k$ -sets. If $I \ne J$ , pick $i \in I \setminus J$ ; row $i$ of $\mathbf{D}$ has its only possibly non-zero entry in column $i \notin J$ , so the submatrix $\mathbf{D}_{I,J}$ has a zero row and $\det \mathbf{D}_{I,J} = 0$ . If $I = J = \{i_1 < \dots < i_k\}$ , then $\mathbf{D}_{I,I} = \operatorname{diag}(d_{i_1}, \dots, d_{i_k})$ and $\det \mathbf{D}_{I,I} = d_{i_1}\cdots d_{i_k}$ (Theorem 7.4.6, valid over the commutative ring $F[x]$ by the remark after it). Since $i_j \ge j$ , the chain gives $d_j \mid d_{i_j}$ for each $j$ , hence $d_1d_2\cdots d_k \mid d_{i_1}d_{i_2}\cdots d_{i_k} .$ So $d_1 \cdots d_k$ divides every $k \times k$ minor of $\mathbf{D}$ , and it is itself the minor for $I = J = \{1, \dots, k\}$ . Hence the ideal generated by the $k \times k$ minors is $\langle d_1\cdots d_k \rangle$ . If $d_1\cdots d_k \ne 0$ it is monic, being a product of monic polynomials, and equals $\Delta_k(\mathbf{D})$ . If $d_1 \cdots d_k = 0$ , say $d_m = 0$ with $m \le k$ , then for every $k$ -set $I$ we have $i_k \ge k \ge m$ , so $d_m \mid d_{i_k}$ forces $d_{i_k} = 0$ and the minor vanishes; thus $\Delta_k(\mathbf{D}) = 0 = d_1\cdots d_k$ .

Now let $\mathbf{M} \approx \operatorname{diag}(d_1, \dots, d_n)$ with the $d_i$ as in (a). By Claims 1 and 2, $\Delta_k(\mathbf{M}) = d_1d_2\cdots d_k \qquad (k = 1, \dots, n),$ a quantity depending only on $\mathbf{M}$ . Reading this backwards recovers the $d_i$ : first $d_1 = \Delta_1(\mathbf{M})$ ; and for $k \ge 2$ , if $\Delta_{k-1}(\mathbf{M}) \ne 0$ then $d_k = \Delta_k(\mathbf{M})/\Delta_{k-1}(\mathbf{M})$ , while if $\Delta_{k-1}(\mathbf{M}) = 0$ then $d_1\cdots d_{k-1} = 0$ , so some $d_m = 0$ with $m \le k - 1$ , and the chain forces $d_k = 0$ . Hence any second list $(e_1, \dots, e_n)$ as in (a) satisfies the same recipe and equals $(d_1, \dots, d_n)$ . This proves the theorem.

The proof is an algorithm, and it is the one to use by hand: hunt for the entry of least degree, divide, and repeat.

Algorithm. Smith normal form of $\mathbf{M} \in M_n(F[x])$ .

If $\mathbf{M} = 0$ , stop. Otherwise find a non-zero entry of least degree and move it to position $(1,1)$ by a row and a column swap; scale row $1$ so that the entry is monic. Call it $f$ .
For each other entry $g$ in row $1$ or column $1$ with $f \nmid g$ , replace $g$ by its remainder on division by $f$ (subtract a multiple of column $1$ , resp. row $1$ ), move the remainder to the corner, and go back to step 1.
When $f$ divides all of row $1$ and column $1$ , clear them. If some entry $g$ of the remaining block is not divisible by $f$ , add its row to row $1$ and go back to step 2.
Repeat on the remaining $(n-1) \times (n-1)$ block.
Check the answer: $\Delta_k$ must equal $d_1\cdots d_k$ . In particular $d_1\cdots d_n$ is $\det \mathbf{M}$ rescaled by a non-zero constant to be monic, and $d_1$ is the monic gcd of the entries.

Quick check. Two polynomial matrices in $M_2(F[x])$ have determinants $x^2$ and $x^2$ , and in both the greatest common divisor of the four entries is $1$ . Are they equivalent over $F[x]$ ?

Solution. Yes. Here $\Delta_1 = 1$ (the gcd of the $1 \times 1$ minors, that is, of the entries) and $\Delta_2$ is the determinant rescaled to be monic, so $\Delta_2 = x^2$ for both. By Theorem 10.7.3 both have Smith normal form $\operatorname{diag}(1, x^2)$ , and since $\approx$ is an equivalence relation (Proposition 10.7.2 (a)) they are equivalent to each other. For $2 \times 2$ matrices the pair $(\Delta_1, \Delta_2)$ is therefore a complete invariant.

Example (A Smith Normal Form Computed by Hand)

Let $\mathbf{A} = \begin{pmatrix} 2 & 1 & -2 \\ 1 & 2 & -2 \\ 1 & 1 & -1 \end{pmatrix} \in M_3(\mathbb{Q}).$ Find the Smith normal form of $x\mathbf{I} - \mathbf{A}$ over $\mathbb{Q}[x]$ , naming every operation, and check the answer with determinantal divisors.

Solution. We have $x\mathbf{I} - \mathbf{A} = \begin{pmatrix} x - 2 & -1 & 2 \\ -1 & x - 2 & 2 \\ -1 & -1 & x + 1 \end{pmatrix}.$

Find the corner. The entries of least degree are the three entries equal to $-1$ . Swap columns $1$ and $2$ , then multiply the first row by $-1$ : $\begin{pmatrix} -1 & x - 2 & 2 \\ x - 2 & -1 & 2 \\ -1 & -1 & x + 1 \end{pmatrix} \longrightarrow \begin{pmatrix} 1 & -(x-2) & -2 \\ x - 2 & -1 & 2 \\ -1 & -1 & x + 1 \end{pmatrix}.$ The corner is now $1$ , which divides everything, so no division step is needed.

Clear the first column. Add $-(x-2)$ times row $1$ to row $2$ , and add row $1$ to row $3$ . In row $2$ this gives entries $-1 + (x-2)^2 = (x-1)(x-3)$ and $2 + 2(x-2) = 2(x-1)$ ; in row $3$ it gives $-1 - (x-2) = -(x-1)$ and $x + 1 - 2 = x - 1$ : $\begin{pmatrix} 1 & -(x-2) & -2 \\ 0 & (x-1)(x-3) & 2(x-1) \\ 0 & -(x-1) & x - 1 \end{pmatrix}.$

Clear the first row. Add $(x-2)$ times column $1$ to column $2$ , and $2$ times column $1$ to column $3$ . Since the first column below the corner is zero, nothing else changes: $\begin{pmatrix} 1 & 0 & 0 \\ 0 & (x-1)(x-3) & 2(x-1) \\ 0 & -(x-1) & x - 1 \end{pmatrix} = \operatorname{diag}(1) \oplus \begin{pmatrix} (x-1)(x-3) & 2(x-1) \\ -(x-1) & x-1 \end{pmatrix}.$ Every entry of the $2 \times 2$ block is divisible by $1$ , so we move on to the block.

The block. Its entries of least degree are the three of degree $1$ . Swap rows $2$ and $3$ and scale the new row $2$ by $-1$ , putting the monic $x - 1$ in the corner of the block: $\begin{pmatrix} 1 & 0 & 0 \\ 0 & x-1 & -(x-1) \\ 0 & (x-1)(x-3) & 2(x-1) \end{pmatrix}.$ Now $x - 1$ divides every entry of its row and column. Add column $2$ to column $3$ , which clears the block’s first row and turns the $(3,3)$ -entry into $2(x-1) + (x-1)(x-3) = (x-1)(x-1)$ : $\begin{pmatrix} 1 & 0 & 0 \\ 0 & x-1 & 0 \\ 0 & (x-1)(x-3) & (x-1)^2 \end{pmatrix}.$ Add $-(x-3)$ times row $2$ to row $3$ to clear the block’s first column: $\mathbf{D} = \operatorname{diag}\big(1,\ x-1,\ (x-1)^2\big),$ and $1 \mid x-1 \mid (x-1)^2$ , so this is the Smith normal form.

The check. The matrix $x\mathbf{I} - \mathbf{A}$ has an entry $-1$ , so $\Delta_1 = 1$ . Its determinant is $p_{\mathbf{A}} = (x-1)^3$ — expanding along the first row, $\begin{aligned} &(x-2)\big[(x-2)(x+1) + 2\big] + \big[-(x+1) + 2\big] + 2\big[1 + (x-2)\big] \\ &\qquad = (x-2)(x^2 - x) + (1 - x) + 2(x-1), \end{aligned}$ which is $(x-2)x(x-1) + (x-1) = (x-1)(x^2 - 2x + 1) = (x-1)^3$ — so $\Delta_3 = (x-1)^3$ . For $\Delta_2$ , the minor on rows $\{2,3\}$ and columns $\{1,2\}$ is $\det\begin{pmatrix} -1 & x-2 \\ -1 & -1\end{pmatrix} = 1 + (x-2) = x-1$ , so $\Delta_2 \mid x - 1$ ; and every $2 \times 2$ minor is divisible by $x - 1$ , as Claim 2 predicts from $\mathbf{D}$ . Hence $\Delta_2 = x-1$ , and $(d_1, d_2, d_3) = \Big(\Delta_1,\ \tfrac{\Delta_2}{\Delta_1},\ \tfrac{\Delta_3}{\Delta_2}\Big) = \big(1,\ x-1,\ (x-1)^2\big),$ in agreement. As a sanity check on $\mathbf{A}$ itself: $\mathbf{A} - \mathbf{I}$ has rank $1$ , so $g_{\mathbf{A}}(1) = 2$ and the Jordan form of $\mathbf{A}$ is $\mathbf{J}_2(1) \oplus \mathbf{J}_1(1)$ (Corollary 10.3.2).

10.7.4. Similarity read off from a polynomial matrix

We can now state the theorem that makes all of this useful. It converts a question about $\mathbf{A}$ and $\mathbf{B}$ — is there an invertible $\mathbf{P} \in M_n(F)$ with $\mathbf{B} = \mathbf{P}^{-1}\mathbf{A} \mathbf{P}$ ? — into a question about the two polynomial matrices $x\mathbf{I} - \mathbf{A}$ and $x\mathbf{I} - \mathbf{B}$ , which the Smith algorithm answers by computation.

One direction is immediate. The other needs a tool: polynomial matrices can be divided by $x\mathbf{I} - \mathbf{A}$ , with a constant remainder.

Lemma 10.7.4 (Division of a Polynomial Matrix by

x\mathbf{I} - \mathbf{A}

)

Let $\mathbf{A} \in M_n(F)$ and $\mathbf{M} \in M_n(F[x])$ . Then there are $\mathbf{Q} \in M_n(F[x])$ and $\mathbf{R} \in M_n(F)$ with $\mathbf{M} = (x\mathbf{I} - \mathbf{A})\,\mathbf{Q} + \mathbf{R} .$

Idea. Write $\mathbf{M}$ as a polynomial $\sum_k \mathbf{M}_kx^k$ with constant matrix coefficients. The scalar identity $x^k - a^k = (x-a)(x^{k-1} + \dots + a^{k-1})$ has a matrix version $x^k\mathbf{I} - \mathbf{A}^k = (x\mathbf{I} - \mathbf{A})\mathbf{S}_k$ , in which the second factor is a polynomial in $x$ and $\mathbf{A}$ and so commutes with $x\mathbf{I} - \mathbf{A}$ . Replacing each $x^k\mathbf{I}$ by $(x^k\mathbf{I} - \mathbf{A}^k) + \mathbf{A}^k$ puts a factor $x\mathbf{I} - \mathbf{A}$ in front of everything except a constant matrix.

Proof. Collecting the coefficients of each power of $x$ in the entries of $\mathbf{M}$ , write $\mathbf{M} = \sum_{k=0}^{m} x^{k}\mathbf{M}_k$ with $\mathbf{M}_0, \dots, \mathbf{M}_m \in M_n(F)$ ; note that $x^k$ is a scalar polynomial, so $x^k\mathbf{M}_k = \mathbf{M}_kx^k$ . For $k \ge 1$ put $\mathbf{S}_k \mathrel{:=} \sum_{j=0}^{k-1} x^{\,k-1-j}\mathbf{A}^{\,j} \in M_n(F[x]), \qquad \mathbf{S}_0 \mathrel{:=} 0 .$ Expanding the product and telescoping, $(x\mathbf{I} - \mathbf{A})\mathbf{S}_k = \sum_{j=0}^{k-1}x^{\,k-j}\mathbf{A}^{\,j} - \sum_{j=0}^{k-1}x^{\,k-1-j}\mathbf{A}^{\,j+1} = x^{k}\mathbf{I} - \mathbf{A}^{k}$ for every $k \ge 0$ . Therefore $\begin{aligned} \mathbf{M} &= \sum_{k=0}^{m} \big(x^{k}\mathbf{I}\big)\mathbf{M}_k = \sum_{k=0}^{m}\big(x^k\mathbf{I} - \mathbf{A}^k\big)\mathbf{M}_k + \sum_{k=0}^{m}\mathbf{A}^k\mathbf{M}_k \\ &= (x\mathbf{I} - \mathbf{A})\underbrace{\sum_{k=0}^{m}\mathbf{S}_k\mathbf{M}_k}_{=\,\mathbf{Q}} + \underbrace{\sum_{k=0}^{m}\mathbf{A}^k\mathbf{M}_k}_{=\,\mathbf{R}}, \end{aligned}$ with $\mathbf{Q} \in M_n(F[x])$ and $\mathbf{R} \in M_n(F)$ , as claimed.

Theorem 10.7.5 (Similarity as Equivalence of

x\mathbf{I} - \mathbf{A}

and

x\mathbf{I} - \mathbf{B}

)

Let $F$ be a field, $n \ge 1$ and $\mathbf{A}, \mathbf{B} \in M_n(F)$ . Then $\mathbf{A} \sim \mathbf{B} \quad \text{over } F \qquad \Longleftrightarrow \qquad x\mathbf{I} - \mathbf{A} \approx x\mathbf{I} - \mathbf{B} \quad \text{over } F[x].$

Idea. $(\Rightarrow)$ is a one-line computation: a constant invertible $\mathbf{P}$ is also an invertible polynomial matrix.

$(\Leftarrow)$ is the substance, and the whole difficulty is that the matrices $\mathbf{U}, \mathbf{V}$ witnessing the equivalence have polynomial entries, while we must produce a constant $\mathbf{P}$ . The trick is to divide $\mathbf{U}$ by $x\mathbf{I} - \mathbf{B}$ and keep only the constant remainder $\mathbf{P}$ . Comparing degrees in the resulting identity shows that $\mathbf{P}$ alone already conjugates: $\mathbf{P}(x\mathbf{I} - \mathbf{A}) = (x\mathbf{I} - \mathbf{B})\mathbf{P}$ , that is, $\mathbf{P} \mathbf{A} = \mathbf{B} \mathbf{P}$ . Running the same argument on the inverted relation produces a second constant $\mathbf{P}'$ with $\mathbf{P}'\mathbf{B} = \mathbf{A} \mathbf{P}'$ , and multiplying the two expressions for $\mathbf{V}^{-1}$ and $\mathbf{V}$ shows $\mathbf{P} \mathbf{P}' = \mathbf{I}$ , so $\mathbf{P}$ is invertible.

Proof. $(\Rightarrow)$ Suppose $\mathbf{B} = \mathbf{P}^{-1}\mathbf{A} \mathbf{P}$ with $\mathbf{P} \in M_n(F)$ invertible. Then, inside $M_n(F[x])$ , $x\mathbf{I} - \mathbf{B} = \mathbf{P}^{-1}(x\mathbf{I})\mathbf{P} - \mathbf{P}^{-1}\mathbf{A} \mathbf{P} = \mathbf{P}^{-1}(x\mathbf{I} - \mathbf{A})\mathbf{P} ,$ and $\mathbf{P}^{-1}, \mathbf{P} \in M_n(F) \subseteq M_n(F[x])$ have non-zero constant determinants, hence are invertible over $F[x]$ (Proposition 10.7.1). So $x\mathbf{I} - \mathbf{A} \approx x\mathbf{I} - \mathbf{B}$ .

$(\Leftarrow)$ Suppose $x\mathbf{I} - \mathbf{B} = \mathbf{U}(x\mathbf{I} - \mathbf{A})\mathbf{V} \tag{$\ast$}$ with $\mathbf{U}, \mathbf{V} \in M_n(F[x])$ invertible over $F[x]$ .

Step 1. Divide $\mathbf{U}$ by $x\mathbf{I} - \mathbf{B}$ . By Lemma 10.7.4 there are $\mathbf{Q} \in M_n(F[x])$ and $\mathbf{P} \in M_n(F)$ with $\mathbf{U} = (x\mathbf{I} - \mathbf{B})\mathbf{Q} + \mathbf{P}$ . Substituting into $(\ast)$ , $x\mathbf{I} - \mathbf{B} = (x\mathbf{I} - \mathbf{B})\,\mathbf{Q}(x\mathbf{I} - \mathbf{A})\mathbf{V} + \mathbf{P}(x\mathbf{I} - \mathbf{A})\mathbf{V} ,$ so $\mathbf{P}(x\mathbf{I}-\mathbf{A})\mathbf{V} = (x\mathbf{I}-\mathbf{B})\bigl[\mathbf{I} - \mathbf{Q}(x\mathbf{I}-\mathbf{A})\mathbf{V}\bigr]$ . Multiplying on the right by $\mathbf{V}^{-1}$ and putting $\mathbf{S} \mathrel{:=} \mathbf{V}^{-1} - \mathbf{Q}(x\mathbf{I} - \mathbf{A}) \in M_n(F[x]),$ we get $\mathbf{P}(x\mathbf{I} - \mathbf{A}) = (x\mathbf{I} - \mathbf{B})\,\mathbf{S} . \tag{1}$

Step 2. $\mathbf{S}$ is a constant matrix, and $\mathbf{P} \mathbf{A} = \mathbf{B} \mathbf{P}$ . Suppose $\mathbf{S} \ne 0$ and write $\mathbf{S} = \sum_{k=0}^{d}x^k\mathbf{S}_k$ with $\mathbf{S}_k \in M_n(F)$ and $\mathbf{S}_d \ne 0$ . The coefficient of $x^{d+1}$ in $(x\mathbf{I} - \mathbf{B})\mathbf{S}$ is $\mathbf{S}_d \ne 0$ , while the left-hand side of (1) is $x\mathbf{P} - \mathbf{P} \mathbf{A}$ , whose coefficients vanish beyond $x^1$ . Hence $d + 1 \le 1$ , that is $d = 0$ . So in every case $\mathbf{S} \in M_n(F)$ . Comparing the coefficients of $x^1$ in (1) gives $\mathbf{P} = \mathbf{S}$ , and comparing the constant terms gives $-\mathbf{P} \mathbf{A} = -\mathbf{B} \mathbf{P}$ . Therefore $\mathbf{P} \mathbf{A} = \mathbf{B} \mathbf{P}, \qquad \text{equivalently} \qquad \mathbf{P}(x\mathbf{I} - \mathbf{A}) = (x\mathbf{I} - \mathbf{B})\mathbf{P} , \tag{2}$ the second form because $\mathbf{P}(x\mathbf{I}-\mathbf{A}) = x\mathbf{P} - \mathbf{P} \mathbf{A} = x\mathbf{P} - \mathbf{B} \mathbf{P} = (x\mathbf{I}-\mathbf{B})\mathbf{P}$ . Moreover $\mathbf{S} = \mathbf{P}$ turns the definition of $\mathbf{S}$ into $\mathbf{V}^{-1} = \mathbf{P} + \mathbf{Q}(x\mathbf{I} - \mathbf{A}). \tag{3}$

Step 3. The same argument, inverted. From $(\ast)$ , $x\mathbf{I} - \mathbf{A} = \mathbf{U}^{-1}(x\mathbf{I} - \mathbf{B})\mathbf{V}^{-1}$ , which is $(\ast)$ with $\mathbf{A}, \mathbf{B}$ interchanged and $\mathbf{U}, \mathbf{V}$ replaced by the invertible polynomial matrices $\mathbf{U}^{-1}, \mathbf{V}^{-1}$ . So Steps 1 and 2 apply and give $\mathbf{Q}' \in M_n(F[x])$ and $\mathbf{P}' \in M_n(F)$ with $\mathbf{P}'(x\mathbf{I} - \mathbf{B}) = (x\mathbf{I} - \mathbf{A})\mathbf{P}' \qquad \text{and} \qquad \mathbf{V} = \mathbf{P}' + \mathbf{Q}'(x\mathbf{I} - \mathbf{B}). \tag{4}$

Step 4. $\mathbf{P}$ is invertible. Multiplying (3) by (4), $\begin{aligned} \mathbf{I} = \mathbf{V}^{-1}\mathbf{V} &= \bigl[\mathbf{P} + \mathbf{Q}(x\mathbf{I}-\mathbf{A})\bigr]\bigl[\mathbf{P}' + \mathbf{Q}'(x\mathbf{I}-\mathbf{B})\bigr] \\ &= \mathbf{P} \mathbf{P}' + \mathbf{P} \mathbf{Q}'(x\mathbf{I}-\mathbf{B}) + \mathbf{Q}(x\mathbf{I}-\mathbf{A})\mathbf{P}' \\ &\qquad + \mathbf{Q}(x\mathbf{I}-\mathbf{A})\mathbf{Q}'(x\mathbf{I}-\mathbf{B}). \end{aligned}$ By the first identity in (4), $(x\mathbf{I}-\mathbf{A})\mathbf{P}' = \mathbf{P}'(x\mathbf{I}-\mathbf{B})$ , so the third summand is $\mathbf{Q} \mathbf{P}'(x\mathbf{I}-\mathbf{B})$ and $\mathbf{I} - \mathbf{P} \mathbf{P}' = \mathbf{Y}(x\mathbf{I} - \mathbf{B}), \qquad \mathbf{Y} \mathrel{:=} \mathbf{P} \mathbf{Q}' + \mathbf{Q} \mathbf{P}' + \mathbf{Q}(x\mathbf{I}-\mathbf{A})\mathbf{Q}' \in M_n(F[x]).$ If $\mathbf{Y} \ne 0$ , write $\mathbf{Y} = \sum_{k=0}^{e}x^k\mathbf{Y}_k$ with $\mathbf{Y}_e \ne 0$ ; the coefficient of $x^{e+1}$ on the right is $\mathbf{Y}_e \ne 0$ , while the left-hand side is constant. Hence $\mathbf{Y} = 0$ and $\mathbf{P} \mathbf{P}' = \mathbf{I}$ . By Theorem 3.4.5, $\mathbf{P}$ is invertible with $\mathbf{P}^{-1} = \mathbf{P}'$ .

Step 5. Conclude. By (2), $\mathbf{P} \mathbf{A} = \mathbf{B} \mathbf{P}$ , so $\mathbf{B} = \mathbf{P} \mathbf{A} \mathbf{P}^{-1}$ and $\mathbf{A} \sim \mathbf{B}$ . This proves the theorem.

Two by-products are worth recording. Whenever $x\mathbf{I} - \mathbf{B} = \mathbf{U}(x\mathbf{I} - \mathbf{A})\mathbf{V}$ with $\mathbf{U}, \mathbf{V}$ invertible over $F[x]$ , taking determinants gives $p_{\mathbf{B}} = (\det \mathbf{U})(\det \mathbf{V})\,p_{\mathbf{A}}$ with $\det \mathbf{U}, \det \mathbf{V}$ non-zero constants (Proposition 10.7.1); both $p_{\mathbf{A}}$ and $p_{\mathbf{B}}$ are monic of degree $n$ , so $p_{\mathbf{A}} = p_{\mathbf{B}} \qquad \text{and} \qquad (\det \mathbf{U})(\det \mathbf{V}) = 1 ,$ which recovers the invariance of the characteristic polynomial. And, by Theorem 10.7.3, the test is now decidable by a finite computation in $F[x]$ : reduce $x\mathbf{I} - \mathbf{A}$ and $x\mathbf{I} - \mathbf{B}$ to Smith normal form and compare.

Corollary 10.7.6 (The Smith Form of

x\mathbf{I} - \mathbf{A}

Carries the Invariant Factors)

Let $\mathbf{A} \in M_n(F)$ with invariant factors $d_1 \mid d_2 \mid \dots \mid d_r$ as in Theorem 10.6.5. Then the Smith normal form of $x\mathbf{I} - \mathbf{A}$ is $\operatorname{diag}\big(\underbrace{1, \dots, 1}_{n - r},\, d_1,\, d_2,\, \dots,\, d_r\big) .$ In particular the invariant factors of $\mathbf{A}$ are exactly the non-constant diagonal entries of the Smith normal form of $x\mathbf{I} - \mathbf{A}$ , read from the top down, and two matrices in $M_n(F)$ are similar if and only if $x\mathbf{I} - \mathbf{A}$ and $x\mathbf{I} - \mathbf{B}$ have the same Smith normal form.

Proof. By Theorem 10.6.5, $\mathbf{A} \sim \mathbf{C}(d_1) \oplus \dots \oplus \mathbf{C}(d_r)$ with $d_i$ monic, $\deg d_i = k_i \ge 1$ and $\sum k_i = n$ . By the $(\Rightarrow)$ direction of Theorem 10.7.5 it is enough to find the Smith normal form of $x\mathbf{I}_n - \big(\mathbf{C}(d_1) \oplus \dots \oplus \mathbf{C}(d_r)\big) = \big(x\mathbf{I}_{k_1} - \mathbf{C}(d_1)\big) \oplus \dots \oplus \big(x\mathbf{I}_{k_r} - \mathbf{C}(d_r)\big),$ the equality by Theorem 8.1.4 (a).

One block. Let $d$ be monic of degree $k \ge 1$ . By Definition 10.5.3, the only non-zero entries of $x\mathbf{I}_k - \mathbf{C}(d)$ are $x$ on the diagonal (with $x + a_{k-1}$ in the corner), $-1$ in each position $(i+1, i)$ , and the entries of the last column. Delete row $1$ and column $k$ . In the remaining $(k-1) \times (k-1)$ matrix, the entry in position $(p, q)$ is the $(p+1, q)$ -entry of $x\mathbf{I}_k - \mathbf{C}(d)$ : it is $-1$ when $q = p$ , it is $x$ when $q = p+1$ , and it is $0$ when $q < p$ . So that matrix is upper triangular with every diagonal entry $-1$ , and its determinant is $(-1)^{k-1} \ne 0$ by Theorem 7.4.6, again over $F[x]$ . Hence $\Delta_{k-1}(x\mathbf{I}_k - \mathbf{C}(d)) = 1$ . By Claim 2 in the proof of Theorem 10.7.3, the determinantal divisors of any matrix are the partial products $d_1\cdots d_j$ of its Smith diagonal, so $\Delta_j \mid \Delta_{k-1} = 1$ and therefore $\Delta_j = 1$ for every $j \le k-1$ . Also $\Delta_k = \det(x\mathbf{I}_k - \mathbf{C}(d)) = p_{\mathbf{C}(d)} = d$ by Theorem 10.5.3. By the uniqueness part of Theorem 10.7.3, the Smith normal form of $x\mathbf{I}_k - \mathbf{C}(d)$ is $\operatorname{diag}(1, \dots, 1, d)$ . (For $k = 1$ read this as $\operatorname{diag}(d)$ .)

Assembling. If $\mathbf{M}_i \approx \mathbf{M}_i'$ with witnesses $\mathbf{U}_i, \mathbf{V}_i$ , then $\bigoplus_i \mathbf{M}_i \approx \bigoplus_i \mathbf{M}_i'$ with witnesses $\bigoplus_i \mathbf{U}_i$ and $\bigoplus_i \mathbf{V}_i$ , which are invertible with inverses $\bigoplus_i \mathbf{U}_i^{-1}$ , $\bigoplus_i \mathbf{V}_i^{-1}$ (Theorem 8.1.4 (a), (c)). So $x\mathbf{I}_n - \mathbf{A}$ is equivalent to the direct sum of the matrices $\operatorname{diag}(1, \dots, 1, d_i)$ , a diagonal matrix whose diagonal entries are $n - r$ ones and the polynomials $d_1, \dots, d_r$ . Simultaneous row and column swaps — each a pair of elementary operations — reorder these entries at will, so $x\mathbf{I}_n - \mathbf{A}$ is equivalent to $\operatorname{diag}(1, \dots, 1, d_1, d_2, \dots, d_r),$ and this is already in the shape required by Theorem 10.7.3 (a), because $1 \mid d_1 \mid d_2 \mid \dots \mid d_r$ and all the entries are monic. By uniqueness it is the Smith normal form of $x\mathbf{I} - \mathbf{A}$ . The final claim combines this with Theorem 10.7.5 and the uniqueness in Theorem 10.7.3.

So the determinantal divisors of $x\mathbf{I} - \mathbf{A}$ compute the invariant factors of $\mathbf{A}$ without any factorization of polynomials: $\Delta_k$ is a gcd, obtained from the Euclidean algorithm alone. Moreover $\Delta_n(x\mathbf{I} - \mathbf{A}) = p_{\mathbf{A}}$ and $\Delta_n/\Delta_{n-1} = d_r = m_{\mathbf{A}}$ .

10.7.5. Every matrix is similar to its transpose

Chapter 4 asked whether $\mathbf{A}$ and $\mathbf{A}^{\top}$ are always similar and postponed the answer; Exercise (C1: A matrix is similar to its transpose) settled it whenever $p_{\mathbf{A}}$ splits. The Smith form removes that hypothesis, because transposing a matrix does not change its minors.

Corollary 10.7.7 (A Matrix Is Similar to Its Transpose)

Let $F$ be any field and $\mathbf{A} \in M_n(F)$ . Then $\mathbf{A} \sim \mathbf{A}^{\top}$ .

Proof. Let $\mathbf{M} = x\mathbf{I} - \mathbf{A}$ , so that $\mathbf{M}^{\top} = x\mathbf{I} - \mathbf{A}^{\top}$ . For $k$ -sets $I, J$ we have $(\mathbf{M}^{\top})_{I,J} = (\mathbf{M}_{J,I})^{\top}$ by Definition 0.9.10, so $\det (\mathbf{M}^{\top})_{I,J} = \det \mathbf{M}_{J,I}$ by Theorem 7.4.5, valid over the commutative ring $F[x]$ . Hence the $k \times k$ minors of $\mathbf{M}^{\top}$ are exactly the $k \times k$ minors of $\mathbf{M}$ , listed in a different order, and $\Delta_k(x\mathbf{I} - \mathbf{A}^{\top}) = \Delta_k(x\mathbf{I} - \mathbf{A}) \qquad (k = 1, \dots, n).$ By Theorem 10.7.3, each of $x\mathbf{I} - \mathbf{A}$ and $x\mathbf{I} - \mathbf{A}^{\top}$ is equivalent over $F[x]$ to the diagonal matrix built from its own determinantal divisors, and these two diagonal matrices coincide. Since $\approx$ is an equivalence relation (Proposition 10.7.2 (a)), $x\mathbf{I} - \mathbf{A} \approx x\mathbf{I} - \mathbf{A}^{\top}$ . By Theorem 10.7.5, $\mathbf{A} \sim \mathbf{A}^{\top}$ .

Two sentences of consequence. An operator and its dual have the same invariants: by Theorem 5.4.2 the matrix of $T'$ in the dual basis is $\bigl([T]_{\mathcal{B}}^{\mathcal{B}}\bigr)^{\top}$ , so $T$ and $T'$ share their characteristic polynomial, their minimal polynomial and their invariant factors. And a matrix and its transpose always have the same Jordan form when one exists, which says that the rows of $\mathbf{A} - \lambda \mathbf{I}$ are exactly as informative as its columns.

Warning. Similar is not the same as “equivalent over $F[x]$ ” for the matrices themselves. The theorem compares $x\mathbf{I} - \mathbf{A}$ with $x\mathbf{I} - \mathbf{B}$ , not $\mathbf{A}$ with $\mathbf{B}$ . As polynomial matrices, any two invertible $\mathbf{A}, \mathbf{B} \in M_n(F)$ are equivalent over $F[x]$ — take $\mathbf{U} = \mathbf{A}^{-1}$ , $\mathbf{V} = \mathbf{B}$ — whether or not they are similar. The whole content of Theorem 10.7.5 is that inserting the variable $x$ on the diagonal remembers the conjugation.

10.7.6. Exercises

A. Check your understanding

Exercise (A1)

(a) List the three elementary operations over $F[x]$ , and say which one differs from its counterpart over a field and why.
(b) State a criterion for a matrix $\mathbf{U} \in M_n(F[x])$ to be invertible in $M_n(F[x])$ .
(c) State the Smith Normal Form theorem, including the uniqueness clause.
(d) Define the $k$ -th determinantal divisor of a polynomial matrix, and say why it is unchanged by equivalence.
(e) True or false: if $\det(x\mathbf{I} - \mathbf{A}) = \det(x\mathbf{I} - \mathbf{B})$ , then $x\mathbf{I} - \mathbf{A} \approx x\mathbf{I} - \mathbf{B}$ . Justify your answer.
(f) How do you read $m_{\mathbf{A}}$ off the Smith normal form of $x\mathbf{I} - \mathbf{A}$ ?

Solution.

(a) Swap two rows; multiply a row by a non-zero scalar of $F$ ; add a polynomial multiple of one row to a different row (Definition 10.7.1). The scaling operation is restricted, because only the non-zero constants are invertible in $F[x]$ ; multiplying a row by $x$ is not reversible.
(b) $\mathbf{U}$ is invertible over $F[x]$ if and only if $\det \mathbf{U}$ is a non-zero constant (Proposition 10.7.1).
(c) Every $\mathbf{M} \in M_n(F[x])$ is equivalent over $F[x]$ , by elementary operations, to a diagonal $\operatorname{diag}(d_1, \dots, d_n)$ with each $d_i$ monic or zero and $d_i \mid d_{i+1}$ ; this diagonal is unique (Theorem 10.7.3).
(d) $\Delta_k(\mathbf{M})$ is the monic generator of the ideal generated by all $k \times k$ minors of $\mathbf{M}$ , equivalently their monic gcd. It is unchanged by equivalence because every $k \times k$ minor of $\mathbf{U} \mathbf{M} \mathbf{V}$ is an $F[x]$ -combination of $k \times k$ minors of $\mathbf{M}$ , by the Cauchy–Binet formula (Theorem 7.7.2; Claim 1 in the proof of Theorem 10.7.3).
(e) False. Equality of determinants says only $\Delta_n(x\mathbf{I}-\mathbf{A}) = \Delta_n(x\mathbf{I}-\mathbf{B})$ ; the lower determinantal divisors can differ. For $\mathbf{A} = \mathbf{J}_2(0) \oplus \mathbf{J}_2(0)$ and $\mathbf{B} = \mathbf{J}_3(0) \oplus \mathbf{J}_1(0)$ in $M_4(F)$ , both determinants are $x^4$ , but the Smith normal forms are $\operatorname{diag}(1,1,x^2,x^2)$ and $\operatorname{diag}(1,1,x,x^3)$ . (Equivalently, the matrices are not similar, by Corollary 10.3.3.)
(f) $m_{\mathbf{A}}$ is the last diagonal entry of the Smith normal form of $x\mathbf{I} - \mathbf{A}$ , that is $\Delta_n/\Delta_{n-1} = p_{\mathbf{A}}/\Delta_{n-1}$ (Corollary 10.7.6, since the last diagonal entry is $d_r = m_{\mathbf{A}}$ in the notation there).

B. Practice

Exercise (B1: Smith normal forms)

Find the Smith normal form over $\mathbb{Q}[x]$ of each of the following, naming the operations you use.

(a) $\mathbf{M}_1 = \begin{pmatrix} x & x+1 \\ x-1 & x \end{pmatrix}$ .
(b) $\mathbf{M}_2 = \begin{pmatrix} x^2 - 1 & 0 \\ 0 & x^2 - x \end{pmatrix}$ .
(c) $\mathbf{M}_3 = \begin{pmatrix} x & 0 & 1 \\ -1 & x & 0 \\ 0 & -1 & x \end{pmatrix}$ .

Solution.

(a) $\det \mathbf{M}_1 = x^2 - (x+1)(x-1) = 1$ , so $\mathbf{M}_1$ is invertible over $\mathbb{Q}[x]$ (Proposition 10.7.1) and $\Delta_1 = \Delta_2 = 1$ . The Smith normal form is $\operatorname{diag}(1,1) = \mathbf{I}_2$ . (Concretely: subtract column $1$ from column $2$ to get $\begin{pmatrix} x & 1 \\ x - 1 & 1\end{pmatrix}$ , then subtract row $1$ from row $2$ , swap columns, and clear.)
(b) Here $\Delta_1 = \gcd(x^2-1, x^2-x) = \gcd\big((x-1)(x+1), x(x-1)\big) = x - 1$ and $\Delta_2 = \det \mathbf{M}_2 = x(x-1)^2(x+1)$ . So the Smith normal form is $\operatorname{diag}\Big(x-1,\ \tfrac{x(x-1)^2(x+1)}{x-1}\Big) = \operatorname{diag}\big(x - 1,\ x(x-1)(x+1)\big),$ and indeed $x - 1$ divides $x(x-1)(x+1)$ . By operations: add column $2$ to column $1$ , giving first column $(x^2-1, x^2-x)$ ; subtract row $1$ from row $2$ to get $(x^2-1, 1-x)$ in column $1$ ; the entry $1 - x$ has least degree, so swap it into the corner, scale by $-1$ , and continue.
(c) The $2 \times 2$ minor on rows $\{2,3\}$ and columns $\{1,2\}$ is $\det\begin{pmatrix} -1 & x \\ 0 & -1\end{pmatrix} = 1$ , so $\Delta_2 = 1$ , and then $\Delta_1 = 1$ as well (it divides $\Delta_2$ ). Expanding $\det \mathbf{M}_3$ along the first row, $x(x^2 - 0) + 1\cdot(1 - 0) = x^3 + 1$ , so $\Delta_3 = x^3 + 1$ and the Smith normal form is $\operatorname{diag}(1, 1, x^3+1)$ . Note $\mathbf{M}_3 = x\mathbf{I} - \mathbf{C}$ with $\mathbf{C} = \begin{pmatrix} 0 & 0 & -1 \\ 1 & 0 & 0 \\ 0 & 1 & 0\end{pmatrix} = \mathbf{C}(x^3+1)$ , and Corollary 10.7.6 predicts exactly this, since a companion matrix has the single invariant factor $x^3 + 1$ .

Exercise (B2: Invariant factors from determinantal divisors)

For each matrix $\mathbf{A}$ , compute $\Delta_1, \dots, \Delta_n$ of $x\mathbf{I} - \mathbf{A}$ , write down the Smith normal form, and read off the invariant factors, $m_{\mathbf{A}}$ and the Jordan form.

(a) $\mathbf{A} = \mathbf{J}_2(0) \oplus \mathbf{J}_2(0) \in M_4(\mathbb{Q})$ .
(b) $\mathbf{A} = \mathbf{J}_3(0) \oplus \mathbf{J}_1(0) \in M_4(\mathbb{Q})$ .
(c) $\mathbf{A} = \begin{pmatrix} 3 & 1 \\ 0 & 3 \end{pmatrix} \in M_2(\mathbb{Q})$ .

Solution. One remark makes the minors easy. If $\mathbf{M} = \mathbf{M}_1 \oplus \mathbf{M}_2$ with square blocks, and $I, J$ are $k$ -sets, split $I = I_1 \cup I_2$ and $J = J_1 \cup J_2$ according to the blocks. If $|I_1| \ne |J_1|$ , then $\mathbf{M}_{I,J}$ has a zero row or a zero column and $\det \mathbf{M}_{I,J} = 0$ ; if $|I_1| = |J_1|$ , then $\mathbf{M}_{I,J} = (\mathbf{M}_1)_{I_1,J_1} \oplus (\mathbf{M}_2)_{I_2,J_2}$ and the determinant is the product of the two, by Theorem 7.8.4, whose proof uses only sums and products of entries and so applies over $F[x]$ (the remark after that theorem). So the minors of a block diagonal matrix are the products of matching-size minors of the blocks. Here $x\mathbf{I} - \mathbf{A}$ is the direct sum of the blocks $x\mathbf{I}_k - \mathbf{J}_k(0)$ , each upper triangular with $x$ on the diagonal and $-1$ on the superdiagonal.

(a) $x\mathbf{I} - \mathbf{A} = \mathbf{N} \oplus \mathbf{N}$ with $\mathbf{N} = \begin{pmatrix} x & -1 \\ 0 & x\end{pmatrix}$ , whose minors are the entries $x, -1, 0$ for $k = 1$ and $x^2$ for $k = 2$ . By the remark, the minors of $\mathbf{N} \oplus \mathbf{N}$ are $\{x, -1, 0\}$ for $k = 1$ ; the products of two $1 \times 1$ minors together with $x^2$ for $k = 2$ ; $x^2$ times a $1 \times 1$ minor for $k = 3$ ; and $x^4$ for $k = 4$ . Hence $\Delta_1 = 1, \qquad \Delta_2 = 1 \ \ (\text{from } (-1)(-1) = 1), \qquad \Delta_3 = x^{2}, \qquad \Delta_4 = x^{4},$ so the Smith normal form is $\operatorname{diag}(1, 1, x^2, x^2)$ , the invariant factors are $x^2 \mid x^2$ , $m_{\mathbf{A}} = x^2$ is the last of them, and the Jordan form is $\mathbf{J}_2(0) \oplus \mathbf{J}_2(0)$ .
(b) Now $x\mathbf{I} - \mathbf{A} = \mathbf{N}_3 \oplus (x)$ with $\mathbf{N}_3 = \begin{pmatrix} x & -1 & 0 \\ 0 & x & -1 \\ 0 & 0 & x\end{pmatrix}$ . The minors of $\mathbf{N}_3$ are $\{x, -1, 0\}$ for $k = 1$ ; $\{x^2, -x, 1, 0\}$ for $k = 2$ , the value $1$ coming from rows $\{1,2\}$ and columns $\{2,3\}$ ; and $x^3$ for $k = 3$ . By the remark, the $k \times k$ minors of $x\mathbf{I} - \mathbf{A}$ are those of $\mathbf{N}_3$ together with $x$ times its $(k-1) \times (k-1)$ minors, so $\begin{aligned} \Delta_1 &= 1, \\ \Delta_2 &= \gcd(x^2, -x, 1, x\cdot x, -x) = 1, \\ \Delta_3 &= \gcd(x^3,\ x\cdot x^2,\ -x\cdot x,\ x\cdot 1) = x, \\ \Delta_4 &= x^{4}. \end{aligned}$ The Smith normal form is $\operatorname{diag}(1, 1, x, x^3)$ : the invariant factors are $x \mid x^3$ , $m_{\mathbf{A}} = x^3$ is the last of them, and the Jordan form is $\mathbf{J}_3(0) \oplus \mathbf{J}_1(0)$ . Compared with (a) the determinants agree but $\Delta_3$ does not, which is exactly why the two matrices are not similar.
(c) $x\mathbf{I} - \mathbf{A} = \begin{pmatrix} x - 3 & -1 \\ 0 & x-3\end{pmatrix}$ . Then $\Delta_1 = 1$ and $\Delta_2 = (x-3)^2$ , so the Smith normal form is $\operatorname{diag}(1, (x-3)^2)$ , the only invariant factor is $(x-3)^2 = m_{\mathbf{A}} = p_{\mathbf{A}}$ , and the Jordan form is $\mathbf{J}_2(3)$ . Consistently, $\mathbf{A}$ is a companion matrix up to similarity, since $m_{\mathbf{A}} = p_{\mathbf{A}}$ (Theorem 10.5.6).

Exercise (B3: Deciding similarity)

Determine whether each pair is similar over the stated field. Justify your answer using Theorem 10.7.5.

(a) $\mathbf{A} = \begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix}$ and $\mathbf{B} = \begin{pmatrix} 0 & 1 \\ -1 & 0\end{pmatrix}$ over $\mathbb{Q}$ .
(b) $\mathbf{A} = \begin{pmatrix} 2 & 1 & -2 \\ 1 & 2 & -2 \\ 1 & 1 & -1 \end{pmatrix}$ and $\mathbf{B} = \mathbf{J}_2(1) \oplus \mathbf{J}_1(1)$ over $\mathbb{Q}$ .
(c) $\mathbf{A} = \begin{pmatrix} 0 & -2 \\ 1 & 0 \end{pmatrix}$ and $\mathbf{B} = \begin{pmatrix} 0 & -1 \\ 2 & 0\end{pmatrix}$ over $\mathbb{Q}$ .

Solution.

(a) Similar. Here $\mathbf{B} = \mathbf{A}^{\top}$ , so Corollary 10.7.7 applies. (Explicitly, $\Delta_1 = 1$ and $\Delta_2 = x^2 + 1$ for both, so both Smith normal forms are $\operatorname{diag}(1, x^2+1)$ .)
(b) Similar. By Example (A Smith Normal Form Computed by Hand) the Smith normal form of $x\mathbf{I} - \mathbf{A}$ is $\operatorname{diag}(1, x-1, (x-1)^2)$ . For $\mathbf{B}$ , $x\mathbf{I} - \mathbf{B} = \begin{pmatrix} x-1 & -1 \\ 0 & x-1\end{pmatrix} \oplus (x-1)$ . Its entry $-1$ gives $\Delta_1 = 1$ . By the block-minor rule in the solution to Exercise (B2: Invariant factors from determinantal divisors), the $2 \times 2$ minors are $(x-1)^2$ , from the $2 \times 2$ block, together with the products of a $1 \times 1$ minor of each block, that is $(x-1)^2, -(x-1)$ and $0$ ; so $\Delta_2 = x - 1$ . Finally $\Delta_3 = \det(x\mathbf{I} - \mathbf{B}) = (x-1)^3$ . The Smith normal forms agree, so $x\mathbf{I} - \mathbf{A} \approx x\mathbf{I} - \mathbf{B}$ and $\mathbf{A} \sim \mathbf{B}$ .
(c) Similar. Here $x\mathbf{I} - \mathbf{A} = \begin{pmatrix} x & 2 \\ -1 & x\end{pmatrix}, \qquad x\mathbf{I} - \mathbf{B} = \begin{pmatrix} x & 1 \\ -2 & x\end{pmatrix},$ and each has an entry that is a non-zero constant, so $\Delta_1 = 1$ in both cases; and $\Delta_2 = \det(x\mathbf{I} - \mathbf{A}) = x^2 + 2 = \det(x\mathbf{I} - \mathbf{B})$ . So both Smith normal forms are $\operatorname{diag}(1, x^2+2)$ , hence $x\mathbf{I} - \mathbf{A} \approx x\mathbf{I} - \mathbf{B}$ and $\mathbf{A} \sim \mathbf{B}$ by Theorem 10.7.5. Note that $x^2 + 2$ is irreducible over $\mathbb{Q}$ , so no Jordan form exists over $\mathbb{Q}$ and Exercise (C1: A matrix is similar to its transpose) would not have decided this pair. (Here $\mathbf{B} \ne \mathbf{A}^{\top}$ , so Corollary 10.7.7 does not apply directly; the Smith forms settle it anyway.)

C. Going deeper

Exercise (C1: The same algorithm over the integers)

The proof of Theorem 10.7.3 used only one property of $F[x]$ : division with remainder, where the “size” of a non-zero element is its degree. The integers $\mathbb{Z}$ have the same property, with $|a|$ in place of $\deg$ .

(a) State the version of Theorem 10.7.3 for $\mathbf{M} \in M_n(\mathbb{Z})$ that the same proof gives, saying what replaces “monic”.
(b) Compute the Smith normal form over $\mathbb{Z}$ of $\mathbf{M} = \begin{pmatrix} 2 & 4 \\ 6 & 4 \end{pmatrix}$ , naming the operations.
(c) Every finite abelian group $G$ with $n$ generators is $\mathbb{Z}^n$ modulo the column span of some $\mathbf{M} \in M_n(\mathbb{Z})$ , the matrix of relations, exactly as $V$ was $F[x]^n$ modulo the columns of $x\mathbf{I} - \mathbf{A}$ . Using (b), identify the group with relation matrix $\mathbf{M}$ as a product of cyclic groups.

Hint: for (c), a diagonal relation matrix $\operatorname{diag}(d_1, \dots, d_n)$ presents the product of the cyclic groups $\mathbb{Z}/d_i\mathbb{Z}$ .

Solution.

(a) Every $\mathbf{M} \in M_n(\mathbb{Z})$ can be brought by integer elementary operations — swap two rows or columns, multiply a row or column by $\pm 1$ (the units of $\mathbb{Z}$ ), add an integer multiple of one row or column to another — to a diagonal matrix $\operatorname{diag}(d_1, \dots, d_n)$ with every $d_i \ge 0$ and $d_i \mid d_{i+1}$ , and this diagonal is unique. “Monic” is replaced by “non-negative”, which is the normalization available because the units of $\mathbb{Z}$ are $\pm 1$ . Uniqueness again follows from the determinantal divisors $\Delta_k$ , now non-negative integer gcds of the $k \times k$ minors, using the Cauchy–Binet formula (Theorem 7.7.2, valid over any commutative ring by the remark after it) over the commutative ring $\mathbb{Z}$ .
(b) The least absolute value among the entries is $2$ , already in the corner. It divides $4$ and $6$ . Subtract $2$ times column $1$ from column $2$ , and $3$ times row $1$ from row $2$ : $\begin{pmatrix} 2 & 4 \\ 6 & 4\end{pmatrix} \longrightarrow \begin{pmatrix} 2 & 0 \\ 6 & -8 \end{pmatrix} \longrightarrow \begin{pmatrix} 2 & 0 \\ 0 & -8\end{pmatrix} \longrightarrow \begin{pmatrix} 2 & 0 \\ 0 & 8 \end{pmatrix},$ the last step multiplying row $2$ by $-1$ . Since $2 \mid 8$ , the Smith normal form is $\operatorname{diag}(2, 8)$ . Check: $\Delta_1 = \gcd(2,4,6,4) = 2$ and $\Delta_2 = |\det \mathbf{M}| = |8 - 24| = 16 = 2 \cdot 8$ .
(c) By (b) and the hint, the group is $\mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/8\mathbb{Z}$ , of order $16 = |\det \mathbf{M}|$ . This is the structure theorem for finite abelian groups in miniature: the invariant divisors $d_1 \mid \dots \mid d_n$ of the relation matrix are the orders of the cyclic factors.

Exercise (C2: Uniqueness by hand in the smallest case)

Let $\mathbf{M} \in M_2(F[x])$ be non-zero.

(a) Prove directly, without using determinantal divisors, that $\Delta_1(\mathbf{M})$ — the monic gcd of the four entries of $\mathbf{M}$ — is unchanged by each of the six elementary operations of Definition 10.7.1.
(b) Prove that $\det(\mathbf{U} \mathbf{M} \mathbf{V}) = c\det \mathbf{M}$ for a non-zero constant $c$ whenever $\mathbf{U}, \mathbf{V}$ are invertible over $F[x]$ .
(c) Deduce that if $\operatorname{diag}(d_1, d_2) \approx \operatorname{diag}(e_1, e_2)$ with all four entries monic or zero, $d_1 \mid d_2$ and $e_1 \mid e_2$ , then $d_1 = e_1$ and $d_2 = e_2$ .

Solution.

(a) Write $d = \Delta_1(\mathbf{M})$ , the monic gcd of the entries, that is, the monic generator of the ideal $\langle m_{11}, m_{12}, m_{21}, m_{22}\rangle$ (Theorem 6.2.2). A swap permutes the entries, so the ideal is unchanged. Scaling a row by $c \in F\setminus\{0\}$ replaces two generators $g$ by $cg$ , and $\langle cg \rangle = \langle g \rangle$ since $c$ is a unit, so the ideal is unchanged. Adding $h$ times row $1$ to row $2$ replaces $m_{2j}$ by $m_{2j} + hm_{1j}$ , which lies in the old ideal; so the new ideal is contained in the old one, and the operation is reversed by adding $-h$ times row $1$ to row $2$ , which gives the reverse containment. The same three arguments apply to columns. Hence $d$ is unchanged.
(b) By multiplicativity of the determinant over the commutative ring $F[x]$ (Theorem 7.5.4 and the remark on commutative rings), $\det(\mathbf{U} \mathbf{M} \mathbf{V}) = \det \mathbf{U} \cdot \det \mathbf{M} \cdot \det \mathbf{V}$ , and $\det \mathbf{U}, \det \mathbf{V}$ are non-zero constants by Proposition 10.7.1. Take $c = \det \mathbf{U} \det \mathbf{V}$ .
(c) By Proposition 10.7.2 and (a), $\Delta_1$ is an invariant of equivalence as far as elementary operations go; and for a general equivalence $\mathbf{M}' = \mathbf{U} \mathbf{M} \mathbf{V}$ the argument of (a) applies verbatim with the generators of the ideal replaced using $m'_{ij} = \sum_{k,l} u_{ik}m_{kl}v_{lj} \in \langle m_{kl}\rangle$ , and symmetrically. For the two diagonal matrices, $\Delta_1(\operatorname{diag}(d_1,d_2)) = \gcd(d_1, d_2) = d_1$ since $d_1 \mid d_2$ and $d_1$ is monic (or $d_1 = d_2 = 0$ ); likewise $\Delta_1(\operatorname{diag}(e_1,e_2)) = e_1$ . Hence $d_1 = e_1$ . By (b), $d_1d_2 = c\,e_1e_2$ for some non-zero constant $c$ ; if $d_1 = e_1 \ne 0$ then $d_2 = c\,e_2$ , and two monic polynomials (or two zeros) differing by a constant factor are equal, so $d_2 = e_2$ . If $d_1 = e_1 = 0$ , then $d_2 = e_2 = 0$ by the divisibility chain.