2
$\begingroup$

I have a given $2\times 2$ special linear matrix, for example \begin{equation} m=\begin{pmatrix} 55 & 8469 \\ 1 & 154 \end{pmatrix} \end{equation}

and I would like to get the generating form of it from the s and t matrices which are these:

\begin{equation} t=\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}\qquad\qquad\qquad s=\begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix} \end{equation}

I don't know if exist an algoritmh for this problem or any proceedings which could help me.

$\endgroup$
  • 1
    $\begingroup$ Row reduce and use the Euclidean algorithm. $\endgroup$ – Qiaochu Yuan May 1 '15 at 10:10
  • $\begingroup$ I know the Euclidean algorithm, but can you give me more support to start? Thank you! $\endgroup$ – Alíz May 1 '15 at 10:14
  • 1
    $\begingroup$ So that you can also use column reduction, it is useful to note that $u = \left(\begin{array}{cc}1&0\\1&1\end{array}\right) = st^{-1}s^{-1}$. $\endgroup$ – Derek Holt May 1 '15 at 10:48
2
$\begingroup$

Disclaimer: The ideas for the following answer come from a pdf I found by Keith Conrad at the University of Connecticut.

The idea of the following is to deal with a simple case (one of the entries is $0$) and then reduce to this simple case using the Euclidean algorithm.

Let our arbitrary matrix $m$ be written as $$m=\left(\begin{matrix}a&b\\c&d\end{matrix}\right)$$

Simple Case: First suppose that $c=0$.

As $\det(m)=1$ this means we must have $a=d=\pm1$. If $a=d=1$ we can directly write $m=t^b$, while if $a=d=-1$ we can write $m=s^2t^{-b}$ (note that $s^2=-I$).

General Case: Now suppose $|c|>0$.

We describe an iterative process to reduce this matrix to the simple case. First suppose that $|a|<|c|$. Then let $m'=sm$ (so now $m'$ has $|a'|\ge|c'|$ since we have just switched them up to a sign). Second suppose that $|a|\ge |c|$, and use the Euclidean algorithm to write $a=cq+r$ with $0\le r<c$. Now take $m'=t^{-q}m$. This matrix has $a-cq=r<c$ as the top left entry and $c$ as the bottom left entry.

Applying this process eventually leads to $c=0$ (using the switching operation after the reducing operation always leads to a $c'$ of strictly lesser magnitude than $c$), and from there we fall into our simple case.

$\endgroup$
  • $\begingroup$ Thank you for your answer! :) $\endgroup$ – Alíz May 1 '15 at 10:58
  • $\begingroup$ I tried this algorithm on an arbitrary matrix, and it works for me. $\endgroup$ – Alíz May 1 '15 at 12:21
3
$\begingroup$

The key is that the second matrix rotates by 90 degrees. $$\left( \begin{array}{cc} 1 & 1 \\ 0 & 1 \\ \end{array} \right)^a.\left( \begin{array}{cc} 0 & -1 \\ 1 & 0 \\ \end{array} \right).\left( \begin{array}{cc} 1 & 1 \\ 0 & 1 \\ \end{array} \right)^b $$

Gives the result $$\left( \begin{array}{cc} a & a d-1 \\ 1 & d \\ \end{array} \right)$$

$\endgroup$
  • $\begingroup$ In the product you have a exponent $b$, but in the result you use $d$, you should decide for one. $\endgroup$ – Viktor Glombik May 20 '18 at 13:47
2
$\begingroup$

This rather small example can also be done by hand without any algorithms.

Note that $$ \begin{pmatrix} a & b \\ c & d \end{pmatrix} \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} = \begin{pmatrix} a & a+b \\ c & c+d \end{pmatrix} $$ While $S$ switches the columns and puts a minus sign in.

Then by guesstimating powers, we reduce the size of scalars quite efficiently.

For example: $$ \begin{pmatrix} 55 & 8469 \\ 1 & 154 \end{pmatrix} \begin{pmatrix} 1 & -153 \\ 0 & 1 \end{pmatrix} = \begin{pmatrix} 55 & 54 \\ 1 & 1 \end{pmatrix}. $$ Multiply by $S^3=S^{-1}$:

$$ \begin{pmatrix} 55 & 54 \\ 1 & 1 \end{pmatrix} \begin{pmatrix} 0 & 1 \\ -1 & 0 \end{pmatrix}= \begin{pmatrix} -54 & 55 \\ -1 & 1 \end{pmatrix} $$ This look quite close to a power of $T$. So mulitply it by $T$: $$ \begin{pmatrix} -54 & 55 \\ -1 & 1 \end{pmatrix} \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}= \begin{pmatrix} -54 & 1 \\ -1 & 0 \end{pmatrix} $$ This we recognize as $T^{54}S$. Working backwards, this all means that $$ MT^{-153}ST=T^{54}S. $$ Hence $M=T^{54}ST^{-1}S^{-1}T^{153}$. (this might be simplified though)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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