8
$\begingroup$

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

$\endgroup$
5
  • 1
    $\begingroup$ 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... $\endgroup$
    – Suvrit
    Sep 30, 2012 at 14:41
  • $\begingroup$ 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. $\endgroup$
    – Andy B
    Sep 30, 2012 at 19:20
  • 1
    $\begingroup$ 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)$. $\endgroup$
    – Andy B
    Sep 30, 2012 at 19:22
  • $\begingroup$ I think the 3x3 should work nicely, because there is a formula for the determinant of a matrix of this kind. greatz $\endgroup$
    – Johannes
    Oct 4, 2012 at 17:01
  • $\begingroup$ @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. $\endgroup$ Nov 13, 2016 at 22:26

2 Answers 2

6
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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!

$\endgroup$
1
  • 2
    $\begingroup$ 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$. $\endgroup$
    – Will Sawin
    Sep 30, 2012 at 15:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.