# Simultaneous Smith Normalization of a Composable Matrix Sequence

Let $\mathsf{R}$ be a PID and consider a collection of free, finitely generated $\mathsf{R}$-modules $V_1,\ldots,V_n$ along with module maps $m_j:V_j \to V_{j+1}$. That is, we have the following sequence

$$V_1 \stackrel{m_1}{\to} V_2 \stackrel{m_2}{\to} \ldots \stackrel{m_{n-1}}{\to} V_n$$

In particular, if we fix bases of each $V_j$ a priori, we may view each $m_j$ as a matrix with entries in $\mathsf{R}$. Recall that the Smith Normal Form (SNF) of such a matrix is obtained by performing row and column operations - that is, change of bases of $V_j$ and $V_{j+1}$- so that the end result is a canonical matrix with zero off-diagonal entries and where each diagonal entry divides the next.

Start at the end of this sequence and note that we can always put the last matrix $m_{n-1}$ in SNF by performing suitable row and column operations. But now, if we try to do the same with $m_{n-2}$ for instance, we would generically have to change the basis of $V_{n-1}$ and in this new basis $m_{n-1}$ may no longer be in SNF.

Here are the questions:

Under what conditions can one prove the existence of bases of the $V_j$s such that each $m_j$ is in SNF with respect to the chosen basis of $V_j$ and $V_{j+1}$?

And when such conditions hold,

Is there an efficient algorithm for finding these bases?

• I have taken the liberty of changing your tags. – Bruce Westbury Jun 8 '12 at 7:33

## 2 Answers

The Smith Normal Form of a product of matrices is not, in general, the product of the Smith Normal Forms. So most of the time you can't do this.

There are some results in this direction in the book "Integral Matrices" by M. Newman, which I have found useful in the past. However, none of these results are constructive.

EDIT: Let me add one such condition. If $\det(m_1\cdots m_{j-1})$ is relatively prime to $\det(m_j)$ for $j=2,\ldots,n$, then the SNF of $m_1\cdots m_n$ is the product of the Smith normal forms of $m_1,\ldots,m_n$.

• It is not clear to me why solving the simultaneous normalization problem above would be related to asserting that the product of SNFs is the SNF of the product. Could you explain the connection? – Vidit Nanda Jun 8 '12 at 14:03
• Let's say you have a linear transformation $T:V\to W$ where $V$ and $W$ are modules over a PID (for simplicity, lets say of the same rank). Finding the SNF of this transformation is the same as finding a basis $v_1,\ldots,v_n$ for $V$ and $w_1,\ldots,w_n$ for $W$ such that $Tv_i=d_iw_i$, where the $d_i$ are the diagonal entries in the SNF. – David Hill Jun 8 '12 at 14:18
• So now assume you have $T:U\to V$ and $S:V\to W$ and bases for $U,V,W$ such that the matrices for $T$ and $S$ in these bases are both in SNF. Then, evidentally, you have found a basis for $U$ and $W$ putting $ST$ in SNF (i.e. the SNF of the product is the product of the SNF). – David Hill Jun 8 '12 at 14:28

I realise that this does not answer your question as stated. There is a much stronger result which essentially gives a normal form for any sequence of composable linear maps. However this result does assume $R$ is a field.

The first step is to change perspective. Namely you can interpret your matrices as a representation of an algebra. Then there is a normal form if you can classify the indecomposable representations.

The algebra you are considering is known as the quiver algebra of type $A_n$. The indecomposable representations are classified by Gabriel's theorem. In this example they are parametrised by pairs $(i,j)$ with $1\le i\le j\le n$.

• Thanks for the answer, and for changing the tags. However, isn't it true that - over the field of complex numbers, for instance - the indecomposable representations of such a quiver contain matrices that are (Jordan) block-diagonal rather than diagonal? – Vidit Nanda Jun 8 '12 at 14:02
• That's only if there are self-maps. – Allen Knutson Mar 8 '15 at 15:26