MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 11 down vote accepted

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$.

share|cite|improve this answer
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. – Nikita Sidorov Nov 22 '10 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.

share|cite|improve this answer
Kevin, thanks! I have modified my question. – Nikita Sidorov Nov 21 '10 at 20:43
OK! I don't understand the modified question, so don't expect any more from me :-) – Kevin Buzzard Nov 21 '10 at 20:49
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... – Kevin Buzzard Nov 21 '10 at 20:51
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. – Sándor Kovács Nov 21 '10 at 21:12
@Sandor: yes I know my first para is logically superfluous---it was an attempt to answer the question "any relevant references will be appreciated". – Kevin Buzzard Nov 21 '10 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).

share|cite|improve this answer
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! – Kevin Buzzard Nov 21 '10 at 20:43
Mark, thanks! I have modified my question. – Nikita Sidorov Nov 21 '10 at 20:43
@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). – Mark Sapir Nov 21 '10 at 21:06
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. – Kevin Buzzard Nov 21 '10 at 21:43
Mark, thanks again! I didn't know about the Sanov subgroup. – Nikita Sidorov Nov 21 '10 at 22:24

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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