Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Hi, I have given a matrix of the following form:

$M = \begin{pmatrix} a_0 & -1 & \cdots & \cdots & -1 \newline -1 & a_1 & -1 & \cdots & -1 \newline \vdots & & \ddots & & \vdots \newline \vdots & & & \ddots & \vdots \newline -1 & \cdots & -1 & \cdots & a_n \end{pmatrix}$ with $a_i \in \mathbb{Z}$, $a_i > 0$.

Is the a an easy way to write down the Smith Normalform of this matrix?

greatz Johannes

share|improve this question
    
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
    
@Andy: the middle $n$'s should be $n+1$'s. It is easy direct calculation(see my answer below). But, I'd like to know the connection to the computation of the critical group of the the complete graph. –  i707107 Mar 5 '13 at 0:12

2 Answers 2

This is a partial answer for the special case when all $a_i$ are distinct. I will work on complex(or algebraic closure of $\mathbb{Q}$) for convenience. Writing $M-\lambda I = D_{\lambda}+E$ where $D_{\lambda}$ is the diagonal matrix with diagonal entries $a_0-\lambda+1, \cdots , a_n-\lambda+1$. With this expression, it is easy to calculate the determinant, which will give the characteristic polynomial of $M$.

If $f(\lambda)=(a_0-\lambda+1)\cdots (a_n-\lambda+1)$, then we have $$ \textrm{det}(M-\lambda I) = f(\lambda)+f'(\lambda).$$ Considering the identity $(f(t)e^t)'=(f(t)+f'(t))e^t$, we can find the roots of characteristic polynomial by looking at the critical points of $f(t)e^t$. Also, by Mean Value theorem, we know that the critical points of $f(t)e^t$ are all distinct.

Therefore, if we let $\lambda_0, \cdots, \lambda_n$ be the critical points of $f(t)e^t$, then we have the following Smith Normal form of the matrix $M-\lambda I$ over the polynomial ring $\mathbb{C}[\lambda]$, (or $\overline{\mathbb{Q}}[\lambda]$): $$ \textrm{Diag}(1,\cdots, 1, (\lambda-\lambda_0) \cdots (\lambda-\lambda_n)).$$ Hence, we obtain the Smith Normal form of $M$ in this case: $$\textrm{Diag}(1,\cdots, 1,\lambda_0 \cdots \lambda_n).$$ There is a natural way of bringing this down to $\mathbb{Z}$, then we have to deal with the irreducible factors of $f(t)+f'(t)$. This is indeed $$\textrm{Diag}(1,\cdots, 1, f(0)+f'(0)).$$ Added) This method also works for the case below:

The cardinality of $\{ j: a_i = a_j \}$ is at most $2$, for any $i=0,\cdots, n$.

Added2) This gives the SNF of $M$ over $\mathbb{Q}$. Over $\mathbb{Z}$ will be certainly more difficult.

share|improve this answer

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!

share|improve this answer
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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