Smith normal form of a Matrix with -1 outside the diagonal

I am given a matrix of the following form: $$M = \begin{pmatrix} a_0 & -1 & \cdots & \cdots & -1 \newline -1 & a_1 & \ddots & & \vdots \newline \vdots & \ddots & \ddots & \ddots & \vdots \newline \vdots & & \ddots & \ddots & -1 \newline -1 & \cdots & \cdots & -1 & a_n \end{pmatrix}$$ with $a_i \in \mathbb{Z}$, $a_i > 0$.

Is there an easy way to write down the Smith normal form of this matrix?

greatz Johannes

• the two by two case has a really nice SNF; the three-by-three version is already beginning to look not that nice. Perhaps the fact that $M+E$ (where $E=11^T$) is diagonal can be exploited... – Suvrit Sep 30 '12 at 14:41
• My guess is that the answer depends subtly on the gcd of the ai (or worse, subsets of the ai) try various cases where the ai are all distinct primes. – Andy B Sep 30 '12 at 19:20
• Also, when all the $a_i = n$ this becomes the computation of the critical group of the the complete graph. The SNF in this case is $(1,n,\dots,n,0)$. – Andy B Sep 30 '12 at 19:22
• I think the 3x3 should work nicely, because there is a formula for the determinant of a matrix of this kind. greatz – Johannes Oct 4 '12 at 17:01
• @AndyB According to en.wikipedia.org/wiki/Kirchhoff%27s_theorem, we have $a_i=n-1$ for the complete graph. Then the matrix $M$ is singular and the SNF in this case is $(1,n,\ldots, n , 0)$ as you commented. – Sungjin Kim Nov 13 '16 at 22:26

According to http://www-math.mit.edu/~rstan/transparencies/snf.pdf, the Smith Normal form for a nonsingular matrix $M$ is $$\textrm{Diag}(e_1,\ldots, e_n),$$ where $e_1\cdots e_i = \gcd \big( i\times i\textrm{ minors of }M \big)$.

There are infinitely many $a_1,\ldots, a_n$ such that $M$ is nonsingular, so we assume that $M$ is nonsingular for convenience. The singular case may be treated separately.

Case 1 : $M$ is nonsingular

Since the matrix has $-1$ in most of the entries, the $i\times i$ minors are relatively easy to find.

From this, the $1\times 1$ entry $e_1$ is easily seen to be $1$.

The $2\times 2$ entry $e_2$ can be obtained from $$e_2=e_1e_2=\gcd\big( \{a_i+1 | i=1,\ldots,n\}, \{a_ia_j-1 | 1\leq i<j\leq n\}\big).$$ Since $a_ia_j-1=(a_i+1)(a_j+1)-(a_i+1)-(a_j+1)$, we have $$e_2=\gcd\big( \{a_i+1 | i=1,\ldots,n\}\big).$$ The $3\times 3$ entry $e_3$ is obtained from \begin{align} e_1e_2e_3&=\gcd\big( \{(a_i+1)(a_j+1) | 1\leq i<j\leq n\}, \{(a_i+1)(a_j+1)(a_k+1) -(a_i+1)(a_j+1) - (a_j+1)(a_i+1) - (a_k+1)(a_i+1)|1\leq i<j<k\leq n\}\big)\\ &=\gcd\big( \{(a_i+1)(a_j+1) | 1\leq i<j\leq n\} \big) \end{align}

In general, for $2\leq i\leq n-1$, $$e_1\cdots e_i = \gcd\big( \{\prod_{k=1}^{i-1} (a_{j_k}+1) | 1\leq j_1< \cdots <j_{i-1}\leq n\}\big).$$ Then $e_n$ is obtained from $$e_n=\frac{\det M}{e_1\cdots e_{n-1}}.$$

Case 2: $M$ is singular

This case, we have $$1 = \sum_{i=1}^n \frac1{a_i+1}.$$ Since $1\neq \sum_{i=1}^{n-1}\frac1{a_i+1}$, the rank of $M$ is $n-1$ and we can proceed the same method as in Case 1, after putting all zeros on the last column and the last row by row/column operations.

While I believe the full answer to your question is 'no,' I was pleasantly surprised that I can predict the first two diagonal entries of the SNF.

Permute the rows so that there is a 1 in entry $(1,1)$. Then after a first round of row and column operations, we produce a matrix:

$$\left[ \begin{array}{c|c} 1 & \mathbf{0}^T \\ \hline \mathbf{0} & M' \end{array}\right]$$

First observation: $1$ is the first diagonal entry.

Second observation: If every $a_i$ is equivalent to $-1$ modulo $k$ for some $k$, then $k$ divides the next diagonal entry of the SNF... and if $k$ is the largest such number, then it is the next. This is because $M'$ contains only entries such as $0$, $\pm(1 + a_i)$ or $1 - a_ia_j$.

Hope this helps!

• I would write that as $k=gcd(a_0+1,a_1+1,...,a_n+1)$. In the three-by-three case we know that the determinant is $a_0a_1a_2 - (a_0+a_1+a_2)-2$, so we can get the last entry. I suspect things get significantly more difficult already for $n=3$. – Will Sawin Sep 30 '12 at 15:37