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.
 A: 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.
