Smith normal form

Recall that similar matrices represent the same abstract linear operator $T:V\to V$ up to a change of basis. We generalize this notion to maps between different spaces:

Definition 405.1(Equivalent matrices).

Two matrices $P,Q\in {\mathcal{M}}_{m,n}(R)$ are equivalent if they represent the same homomorphism of free modules $R^n\to R^m$ up to a choice of basis. In other words, $Q$ is of the form $MPN$, where $M$ and $N$ are invertible matrices.

This is clearly an equivalence relation. Thus, an ‘abstract’ homomorphism $\alpha :F\to G$ between two free modules is not represented by one matrix as much as by the whole equivalence class with respect to this relation.

Our goal is now the following: given a homomorphism $\alpha :F\to G$ between two free modules, find ‘special’ bases in $F$ and $G$ so that the matrix of $\alpha$ takes a particularly convenient form.

Given a matrix $P$ with entries in $R$, recall that the following elementary (row/column) operations can be realized by (left/right) multiplication by (invertible) elementary matrices:

• swap tow rows (columns) of $P$;
• add to one row (column) a multiple of another row (column);
• multiply all entries in one row (column) of $P$ by a unit of $R$.

Thus, it follows that if $Q$ can be obtained from $P$ by a sequence of elementary operations, then $P$ and $Q$ are equivalent. When $R=k$ is a field, $G{L}_n(k)$ is generated by elementary matrices ( Aluffi (2009) VI.2.9), and the converse is true too: two matrices are equivalent over a field iff they are linked by a sequence of elementary operations. If the process described in the proof of Aluffi (2009) VI.2.9 is applied to any rectangular matrix, we get the following¹

Proposition 405.2(Aluffi (2009) VI.2.10).

Over a field, every $m\times n$ matrix is equivalent to a matrix of the form

$$\left[\begin{array}{cc}{I}_r& 0\\ 0& 0\end{array}\right],$$

where $r⩽\min (m,n)$.

We can’t hope for such a result when working with arbitrary rings: We can’t do it for $1\times 1$ integer matrices. However, over euclidean domains, we can get pretty close - we can coax via elementary operations any matrix into what we call Smith normal form.

Proposition 405.3(Artin (2011) 14.4.6).

Let $R$ be a Euclidean domain, and let $P\in {\mathcal{M}}_{m,n}(R)$. Then $P$ is equivalent to a matrix of the form

$$\left[\begin{array}{cc}\left[\begin{array}{ccc}{d}_1& & \\ & \ddots & \\ & & d_k\end{array}\right]& \\ & 0\end{array}\right],$$

with $d_1|\dots |d_r$. This is called the Smith normal form of the matrix.

Proof.

The proof proceeds by repeatedly applying euclidean division and using the fact that the valuation of the remainder is strictly less than that of the dividend. Artin (2011) proves this only for integer matrices, but the same proof works verbatim for arbitrary euclidean domains.□

5393e0

This achieves the ‘nice form’ we were seeking, and since matrix equivalence is an equivalence relation, classifies all matrices in ${\mathcal{M}}_{m,n}(P)$ with smith normal form matrices being canonical representatives of the equivalence classes.

Remark 405.4(Remark).

We now see that $G{L}_n(R)$ is generated by elementary matrices if $R$ is a euclidean domain. However, this is not the case for PIDs. It is possible to produce a Smith normal form for any matrix with entries in a PID, but we will need more than elementary row and column operations.

---

Proposition 405.5(Artin (2011) 14.4.9).

Let $A$ be an $m\times n$ matrix, and let $P$ and $Q$ be invertible integer matrices such that $A^{\prime }=Q^{-1}AP$ has the ‘diagonal from’.

1. The integer solutions of the homogeneous equation $A^{\prime }{X}^{\prime }=0$ are the integer vectors $X^{\prime }$ whose first $k$ coordinates are zero.
2. The integer solutions of the homogeneous equation $AX=0$ are those of the form $X=P{X}^{\prime }$, where $A^{\prime }{X}^{\prime }=0$.
3. The image $W^{\prime }$ of multiplication by $A^{\prime }$ consists of the integer combinations of the vectors $d_1{w}_2,\dots ,d_k{e}_k$. The image of $W$ of multiplication by $A$ consists of the vectors $Y=Q{Y}^{\prime }$, where $Y^{\prime }$ is in $W^{\prime }$

Footnotes

1. We’ve already seen this before! ↩

---

References

Aluffi, P. (2009). Algebra: Chapter 0. American Mathematical Society.

Artin, M. (2011). Algebra (2. ed). Pearson Education, Prentice Hall.