1
$\begingroup$

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.

1 Answers 1

0

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.

  • 0
    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)$?2011-10-23
  • 0
    Oops! They should still be $x+1$, as the edited version now shows.2011-10-23