MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
You're looking for orthogonal matrices with integer entries? – J. M. May 17 '11 at 12:52
3 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

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

Your Answer


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.