Smith normalform of a Matrix with -1 outside the diagonal - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T12:39:47Z http://mathoverflow.net/feeds/question/108419 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/108419/smith-normalform-of-a-matrix-with-1-outside-the-diagonal Smith normalform of a Matrix with -1 outside the diagonal Johannes 2012-09-29T19:16:22Z 2013-03-05T17:58:31Z <p>Hi, I have given a matrix of the following form:</p> <p>$M = \begin{pmatrix} a_0 &amp; -1 &amp; \cdots &amp; \cdots &amp; -1 \newline -1 &amp; a_1 &amp; -1 &amp; \cdots &amp; -1 \newline \vdots &amp; &amp; \ddots &amp; &amp; \vdots \newline \vdots &amp; &amp; &amp; \ddots &amp; \vdots \newline -1 &amp; \cdots &amp; -1 &amp; \cdots &amp; a_n \end{pmatrix}$ with $a_i \in \mathbb{Z}$, $a_i > 0$.</p> <p>Is the a an easy way to write down the Smith Normalform of this matrix?</p> <p>greatz Johannes</p> http://mathoverflow.net/questions/108419/smith-normalform-of-a-matrix-with-1-outside-the-diagonal/108473#108473 Answer by Shaun Ault for Smith normalform of a Matrix with -1 outside the diagonal Shaun Ault 2012-09-30T14:25:39Z 2012-09-30T14:25:39Z <p>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.</p> <p>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:</p> <p>$$\left[ \begin{array}{c|c} 1 &amp; \mathbf{0}^T \\ \hline \mathbf{0} &amp; M' \end{array}\right]$$</p> <p>First observation: $1$ is the first diagonal entry.</p> <p>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 <em>is</em> the next. This is because $M'$ contains only entries such as $0$, $\pm(1 + a_i)$ or $1 - a_ia_j$.</p> <p>Hope this helps!</p> http://mathoverflow.net/questions/108419/smith-normalform-of-a-matrix-with-1-outside-the-diagonal/123498#123498 Answer by i707107 for Smith normalform of a Matrix with -1 outside the diagonal i707107 2013-03-04T01:39:50Z 2013-03-05T17:58:31Z <p>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$. </p> <p>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. </p> <p>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:</p> <p>The cardinality of $\{ j: a_i = a_j \}$ is at most $2$, for any $i=0,\cdots, n$. </p> <p>Added2) This gives the SNF of $M$ over $\mathbb{Q}$. Over $\mathbb{Z}$ will be certainly more difficult. </p>