3
$\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$
3
  • 1
    $\begingroup$ Row reduce and use the Euclidean algorithm. $\endgroup$ May 1, 2015 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, 2015 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, 2015 at 10:48

3 Answers 3

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$
1
  • $\begingroup$ In the product you have a exponent $b$, but in the result you use $d$, you should decide for one. $\endgroup$ May 20, 2018 at 13:47
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$
2
  • $\begingroup$ Thank you for your answer! :) $\endgroup$
    – Alíz
    May 1, 2015 at 10:58
  • $\begingroup$ I tried this algorithm on an arbitrary matrix, and it works for me. $\endgroup$
    – Alíz
    May 1, 2015 at 12:21
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$
0

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .