Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 0 down vote accepted

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.

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

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.