# How can I get this to Smith Normal Form?

As part of a larger problem, I want to compute the Smith Normal Form of $xI-A$ over $\mathbb{Q}[x]$ where $$A=\begin{pmatrix} 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0\end{pmatrix}.$$

I've gone through about 12 steps and I finally get the matrix to the form $$\begin{pmatrix} x+1 & 0 & 0 & 0 \\ 0 & x+1 & 0 & 0 \\ 0 & 0 & x+1 & 0 \\ 0 & 0 & x & x-3\end{pmatrix}.$$ I can't figure out how to get this in a diagonal form. Is there a way to fix it? I can include my reduction steps also if that's helpful. Thanks.

-

what you want to do is use the GCD of the entries in a non-reduced column. Specifically, in a column containing entries $f$ and $g$, let $h = gcd(f, g)$. We can always find elements (polynomials) $p, q$ such that $h = pf + gq$. Then there is a series of row operations that will reduce $f$ to $d$ and $g$ to $0$. Here's how it works in your matrix. It suffices to look at the lower $2 \times 2$ submatrix (but I'll label rows as $R_3$ and $R_4$ to stay consistent with your matrix.

$$\left[\begin{array}{cc} x+1 & 0 \\ x & x-3 \end{array}\right]$$ $(-1)R_4 + R_3 \mapsto R_3$

$$\left[\begin{array}{cc} 1 & -x+3 \\ x & x-3 \end{array}\right]$$ $(-x)R_3 + R_4 \mapsto R_4$ $$\left[\begin{array}{cc} 1 & -x+3 \\ 0 & x^2 - 2x-3 \end{array}\right]$$

Then, a column operation gets rid of the upper-right entry.

$(x-3)C_3 + C_4 \mapsto C_4$ $$\left[\begin{array}{cc} 1 & 0 \\ 0 & x^2 - 2x-3 \end{array}\right]$$ Note now that $x^2 - 2x - 3 = (x-3)(x+1)$, a multiple of $x+1$. Reording the rows and columns obtains the SNF of the whole $4 \times 4$ matrix: $$\left[\begin{array}{cccc} 1 & 0 & 0 & 0\\ 0 & x+1 & 0 & 0\\ 0 & 0 & x+1 & 0 \\ 0 & 0 & 0 & (x-3)(x+1)\end{array}\right]$$

Hope this helps!

You may also view http://en.wikipedia.org/wiki/Smith_normal_form though I find it to be a bit unclear in places.

-
I see, I didn't think to multiply rows and columns by polynomials! In the final form, why did the $x+1$s change to $x-3s$? Would it be fine to have a diagonal $1, x+1,x+1,(x-3)(x+1)$? – Buble Oct 23 '11 at 1:08
Oops! They should still be $x+1$, as the edited version now shows. – Shaun Ault Oct 23 '11 at 3:13