# [Matrices over Z] - An algorithm for calculating the diagonal with elementary operations

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.

-
You're looking for orthogonal matrices with integer entries? –  J. M. May 17 '11 at 12:52
en.wikipedia.org/wiki/Smith_normal_form should provide more information than you need. –  Will Orrick May 17 '11 at 13:31
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.