Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Dear mathoverflow,

Let $ \left( \begin{array}{cc} a & b \newline c & d \end{array} \right) $ be a matrix with $a, b, c, d \in \mathbb{Z}$, $\gcd(a,b,c,d) = 1$ and $ad - bc = \pm N$, with $N > 0$. Does there exist $e, f, g, h, t, u, v, w \in \mathbb{Z}$ such that $$ \left( \begin{array}{cc} N & 0 \newline 0 & 1 \end{array} \right) \cdot \left( \begin{array}{cc} e & f \newline g & h \end{array} \right) = \left( \begin{array}{cc} t & u \newline v & w \end{array} \right) \cdot \left( \begin{array}{cc} a & b \newline c & d \end{array} \right) $$ where $eh - gf = \pm 1$ and $tw - uv = \pm 1$?

In other words, are matrices $ \left( \begin{array}{cc} a & b \newline c & d \end{array} \right) $ and $ \left( \begin{array}{cc} N & 0 \newline 0 & 1 \end{array} \right) $ equivalent with respect to elementary operations?

I would like to have an algorithm to calculate $e,f,g,h,t,u,v$ and $w$.

Thank you.

share|improve this question
    
You're looking for orthogonal matrices with integer entries? –  J. M. May 17 '11 at 12:52
3  
en.wikipedia.org/wiki/Smith_normal_form should provide more information than you need. –  Will Orrick May 17 '11 at 13:31
    
Will, please turn your comment into an answer. –  S. Carnahan May 17 '11 at 15:19
add comment

1 Answer

At Scott's request, here's my comment in answer form:

The stated conditions imply imply that your two matrices are equivalent. Up to permutation of rows and columns, your diagonal matrix is the Smith normal form of your original matrix. Specifically, that $\gcd(a,b,c,d)$ is 1 implies that one of the invariant factors is 1, which means that the other must be $N$.

The Wikipedia article describes an algorithm for computing the Smith normal form of an $m\times n$ matrix. Essentially it involves repeatedly clearing successive rows and columns using the Euclidean algorithm until the matrix reaches diagonal form. (Think about why this must terminate.) The definition of Smith normal form imposes divisibility requirements on the invariant factors, so some additional operations on the diagonal elements may need to be performed to bring the matrix to final form.

share|improve this answer
add comment

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.