0
$\begingroup$

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.

$\endgroup$
3

1 Answer 1

5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.