📂Topological Data Analysis

Smith Normal Form of a Matrix

Definition ^{1 2}

Given a PID, or Principal Ideal Domain $R$, if there exist $d_{1} , \cdots , d_{r} \in R$ and invertible matrices $P \in R^{m \times m}$, $Q \in R^{n \times n}$ that satisfy the following for a matrix $A \in R^{m \times n}$, then $PAQ \in R^{m \times n}$ is called the Smith Normal Form of $A$. $$PAQ = \begin{bmatrix} d_{1} & 0 & 0 & 0 & \cdots & 0 \\ 0 & \ddots & 0 & 0 & \cdots & 0 \\ 0 & 0 & d_{r} & 0 & \cdots & 0 \\ 0 & 0 & 0 & 0 & \cdots & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & 0 & \cdots & 0 \end{bmatrix} \in R^{m \times n}$$ Here, $d_{1} , \cdots , d_{r}$ must not be $0$ in $R$, and it must be $d_{1} \mid \cdots \mid d_{r}$. In other words, $d_{k} \ne 0$ must be a [Divisor] of $d_{k+1}$.

Example

The inverse matrix might seem complicated, but it can actually be obtained through the Gaussian elimination method. While it’s not an official expression, to make the example easier to read, I will indicate on the right side of the matrix which operations are applied. $r-$ is row, $c-$ is column, $-x$ is exchange, $-e$ is elimination, and $-+$ is the operation of multiplying by a coefficient and adding.

Of course, computing it through Gaussian elimination might not be smart in terms of computation. It’s just something to note that it can also be solved this way when calulating by hand.

Ring of Integers $\mathbb{Z}$

$$\begin{align*} \begin{bmatrix} 2 & 3 & 1 \\ 4 &-1 &-1 \end{bmatrix} \sim & & \begin{bmatrix} 1 & 3 & 2 \\ -1 &-1 & 4 \end{bmatrix} & \qquad cx(1,3) \\ \sim & & \begin{bmatrix} 1 & 0 & 0 \\ -1 & 2 & 6 \end{bmatrix} & \qquad ce(1 \to 2,3) \\ \sim & & \begin{bmatrix} 1 & 0 & 0 \\ 0 & 2 & 6 \end{bmatrix} & \qquad re(1 \to 2) \\ \sim & & \begin{bmatrix} 1 & 0 & 0 \\ 0 & 2 & 0 \end{bmatrix} & \qquad ce(2 \to 3) \end{align*}$$

Here, note that $1 \mid 2$.

Ring of Polynomials $\mathbb{Q} [x]$

$$\begin{align*} \begin{bmatrix} x & 2 & 0 \\ 0 & 1 & 2x \\ -1 & 0 & x+1 \end{bmatrix} \sim & \begin{bmatrix} x & 2 & x \\ 0 & 1 & 2x \\ -1 & 0 & x \end{bmatrix} & \qquad c+(1 \to 3, 1) \\ \sim & \begin{bmatrix} x+1 & 2 & 0 \\ 2 & 1 & 0 \\ -1 & 0 & x \end{bmatrix} & \qquad re(3 \to 1, 2) \\ \sim & \begin{bmatrix} 2 & 1 & 0 \\ x+1 & 2 & 0 \\ -1 & 0 & x \end{bmatrix} & \qquad rx(1,2) \\ \sim & \begin{bmatrix} 1 & 2 & 0 \\ 2 & x+1 & 0 \\ 0 & -1 & x \end{bmatrix} & \qquad cx(1,2) \\ \sim & \begin{bmatrix} 1 & 2 & 0 \\ 0 & x-3 & 0 \\ 0 & -1 & x \end{bmatrix} & \qquad re(1 \to 2) \\ \sim & \begin{bmatrix} 1 & 0 & 0 \\ 0 & x-3 & 0 \\ 0 & -1 & x \end{bmatrix} & \qquad ce(1 \to 2) \\ \sim & \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & -x \\ 0 & x-3 & 0 \end{bmatrix} & \qquad rx(2,3) \\ \sim & \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & x-3 & x(x-3) \end{bmatrix} & \qquad c+(2 \to 3, x) \\ \sim & \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & x(x-3) \end{bmatrix} & \qquad r+(2 \to 3, -(x-3)) \end{align*}$$

Explanation

It’s important to note that the given Principal Ideal Domain $R$ does not guarantee to be a Field, which means division is generally not permitted, and elimination must be performed using PID being a Bézout Domain.

Conclusion

Existence and Uniqueness

When $R$ is a Principal Ideal Domain, a Smith Normal Form uniquely exists for all matrices $A \in R^{m \times n}$. The uniqueness here disregards the multiplication of $d_{k}$ by units.

Proof

It is shown through an algorithm that specifically computes the Smith Normal Form.

■

See Also

• Normal Forms of Vector Fields