Is the subgroup of $GL(2,\mathbb Z)$ generated by the matrices $$ \left( \begin{array}{cc} 1 & 1 \\\ 1 & 0 \end{array} \right) \ \ \text{and} \ \ \left( \begin{array}{cc} 2 & 1 \\\ 1 & 0 \end{array} \right) $$ free of exponential growth? More generally, how does one find all the relations between two matrices?

I am sure this is well known, so any relevant references will be appreciated.

My motivation comes from dynamical systems where these matrices specify two automorphisms of the 2-torus; I am interested in studying the orbits of their joint action.


3 Answers 3


I interpret the question "how does one find all the relations between the matrices" as "find a set of defining relations for the group generated by the two matrices".

To do that we need a presentation of $GL(2,\mathbb{Z})$. I found one in the paper:

T. Brady, Automatic structures on Aut$F_2)$, Arch. Math. 63, 97-102 (1994).

$\langle p,s,u \mid p^2=s^2=(sp)^4=(upsp)^2=(ups)^3=(us)^2=1 \rangle$

where $p= \left(\begin{array}{cc}0&1\\1&0\end{array}\right)$, $s= \left(\begin{array}{cc}-1&0\\0&1\end{array}\right)$, $u= \left(\begin{array}{cc}1&1\\0&1\end{array}\right)$.

Denoting your two matrices by

$a= \left(\begin{array}{cc}1&1\\1&0\end{array}\right)$, $b= \left(\begin{array}{cc}2&1\\1&0\end{array}\right)$

we have $a=up$, $b=u^2p$.

Putting $H = \langle a,b \rangle$ and using coset enumeration in Magma, it turns out that $H={\rm GL}(2,\mathbb{Z})$. So your two matrices actually generate all of GL$(2,\mathbb{Z})$.

In fact, denoting $a^{-1}$ and $b^{-1}$ by $A$ and $B$, we have

$p=aBa$, $u=a^2Ba$, $s=abaBAbabA$.

Using the modified coset enumeration algorithm, we can compute a presentation of $H$, which came out as the not particularly enlightening

$H = \langle a,b \mid (aBa)^2, (AbaBA)^2, aBabABAbAbABAbAbABAbAbAB, (abABabaB)^3 \rangle$.

  • $\begingroup$ Derek, thanks a lot! This is precisely what I need. I didn't expect $H$ to be all of $GL(2,\mathbb Z)$ but in fact it suits me perfectly. $\endgroup$ Nov 22, 2010 at 12:38

A subgroup of $SL(2,\mathbf{Z}$) is free iff it's torsion-free; this is a useful trick (and it's not an immediately obvious fact: it's because $SL(2,\mathbf{Z})$ acts on a tree with finite stabilisers). This is a useful trick in situations like this.

However, if your matrices are denoted $a$ and $b$, then random mucking about gives me that $ba^{-2}$ has order 2, so the subgroup you're asking about cannot possibly be free.

EDIT: this was an answer to the original question "is the group free" and goes nowhere towards answering the revised question.

  • $\begingroup$ Kevin, thanks! I have modified my question. $\endgroup$ Nov 21, 2010 at 20:43
  • $\begingroup$ OK! I don't understand the modified question, so don't expect any more from me :-) $\endgroup$ Nov 21, 2010 at 20:49
  • 1
    $\begingroup$ I will perhaps remark that I spotted $ba^{−2}ba^{−2}=1$ and Mark spotted $[a,b]^6=1$, and these look to me like "distinct relations", if that has any meaning... $\endgroup$ Nov 21, 2010 at 20:51
  • $\begingroup$ Kevin, I guess the meaning is simply that the subgroup of relations (in the $F_2$ that maps onto this group) is not generated by a single element. Probably not too surprising. Also, even though the statement you mention in the first paragraph is interesting, it is not really needed here. I mean you are using the easy direction, that is, that if there is a non-trivial relation then the group is not free. $\endgroup$ Nov 21, 2010 at 21:12
  • $\begingroup$ @Sandor: yes I know my first para is logically superfluous---it was an attempt to answer the question "any relevant references will be appreciated". $\endgroup$ Nov 21, 2010 at 21:17

No, the subgroup is not free. You can check that if $A$ is your first matrix, $B$ is the second matrix, then $[A,B]^6=1$, where $[A,B]=ABA^{-1}B^{-1}$.

Update 1. There is a paper by Klimenko and Kopteva which might be useful: All discrete ${\scr{RP}}$ groups whose generators have real traces. Internat. J. Algebra Comput. 15 (2005), no. 3, 577–618. It might be in the arXiv, I did not check.

Update 2. The subgroup does have exponential growth. The matrices $B^2$ and $A^6$ belong to the Sanov subgroup. This is a free subgroup of $SL(2,Z)$ consisting of matrices of the form $$\left\[\begin{array}{ll} 4k+1 & 2n \\\ 2m & 4l+1\end{array}\right\].$$ Since $A^6$ and $B^2$ do not commute, they generate a free subgroup of rank 2. The definition of Sanov subgroup can be found in the standard group theory book by Kargapolov and Merzlyakov, 14.2.1 and the Exercise 14.2.3 (I refer to the third edition).

  • $\begingroup$ Mark---how did you come to this answer? I am sure you know a lot more about this sort of thing than me. I just computed the char polys of $a^mb^n$ for some small values of $m$ and $n$ until I got lucky. I am sure there are far better ways to go about it! $\endgroup$ Nov 21, 2010 at 20:43
  • $\begingroup$ Mark, thanks! I have modified my question. $\endgroup$ Nov 21, 2010 at 20:43
  • 2
    $\begingroup$ @Kevin: I looked at the traces too. These are 1 and 2 - too small to generate a free group. I had done some computation with such groups in the past, and I usually look at the commutator and see if it is torsion first. I think that this is how Klimenko and Kopteva ruled out some cases in their paper as well (it might be even that I was the editor handling their paper in IJAC). $\endgroup$
    – user6976
    Nov 21, 2010 at 21:06
  • $\begingroup$ I see! The elements I was trying could also be used as part of a 2-element generating set for the group: the commutator is somehow "genuinely deeper in" so I can see the logic in your approach. $\endgroup$ Nov 21, 2010 at 21:43
  • $\begingroup$ Mark, thanks again! I didn't know about the Sanov subgroup. $\endgroup$ Nov 21, 2010 at 22:24

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.