## The Only LFTs You’ll Ever Need

Let us consider linear fractional transformations $\frac{az+b}{cz+d}$ where the coefficients are all integers and $ad-bc=1$. Since multiplying all of the coefficients by a constant doesn’t change the transformation, we may multiply everything by -1 whenever we want (for instance, to make a chosen coefficient positive). Recall, also, that writing the transformation as a matrix, $\left(\begin{smallmatrix}a&b\\ c&d\end{smallmatrix}\right)$ is not an entirely unreasonable thing to do, as composites of transformations are correctly determined by matrix multiplication. I’ll be talking about sequence of these matrices, so let my original matrix be $\left(\begin{smallmatrix}a_0&b_0\\ c_0&d_0\end{smallmatrix}\right)$

If $c_0=0$, then the requirement $a_0d_0-b_0c_0=1$ means that $a_0=d_0=\pm 1$, and we may choose $a_0=d_0=1$. Then our transformation is simply $\left(\begin{smallmatrix}1 & b_0 \\ 0 & 1\end{smallmatrix}\right)$. Since $b_0$ is an integer, we could write this as $\left(\begin{smallmatrix}1 & 1\\ 0 & 1\end{smallmatrix}\right)^{b_0}$.

If $c_0\neq 0$, then there is a $q_0\in \mathbb{Z}$ so that $0\leq a_0-q_0c_0. I’ll leave you to check the following:

$L_0 = \begin{pmatrix}1 & q_0\\ 0 & 1\end{pmatrix}\begin{pmatrix}0 & 1\\ 1 & 0\end{pmatrix}\begin{pmatrix}c_0 & d_0 \\ a_0-q_0c_0 & b_0-q_0d_0\end{pmatrix}$

Writing this right-most matrix as $L_1=\left(\begin{smallmatrix}a_1 & b_1\\ c_1 & d_1\end{smallmatrix}\right)$, we are looking at another matrix with integer coefficients whose determinant is 1. So we may repeat the process, finding integers $q_k$ and LFTs $L_k$ with $L_k=\left(\begin{smallmatrix}1&q_k\\ 0&1\end{smallmatrix}\right)\left(\begin{smallmatrix}0&1\\ 1&0\end{smallmatrix}\right)L_{k+1}$. The process must stop eventually, because $c_0>c_1>c_2>\cdots$ are all non-negative integers. Eventually, one of them will be 0, and we already dealt with transformations like that in the previous paragraph.

Let $T=\left(\begin{smallmatrix}1&1\\ 0&1\end{smallmatrix}\right)$, and note that $T^b=\left(\begin{smallmatrix}1&b\\ 0&1\end{smallmatrix}\right)$, which we’ve used before. Also, let $\overline{S}=\left(\begin{smallmatrix}0&1\\1&0\end{smallmatrix}\right)$ (you might note that $\overline{S}^2$ is the identity matrix). Then our relation above is $L_k=T^{q_k}\overline{S}L_{k+1}$. That is,

$\begin{array}{rcl}\begin{pmatrix}a&b\\ c&d\end{pmatrix}=L_0 &=& T^{q_0}\overline{S}L_1 \\ &=&T^{q_0}\overline{S}T^{q_1}\overline{S}L_2\\ &=&\cdots=T^{q_0}\overline{S}T^{q_1}\overline{S}\cdots T^{q_k}.\end{array}$

The collection of matrices that we have been working with, 2×2 matrices with integer coefficients whose determinant is 1, tend to get called the modular group and we have just shown that $T$ and $\overline{S}$ can be multiplied together to give you any element of the group. More officially, they “generate” the group. You might fuss and say that technically these matrices are really the special linear group $SL_2(\mathbb{Z})$, and note that the modular group is really the quotient of this group where you say two matrices are the same if one is -1 times the other.

One interesting thing about this process is that it is really just the process you go through to find the greatest common divisor of $a_0$ and $c_0$. The standard algorithm (Euclid’s) is to note that, if $c_0\neq 0$, there is an integer $q_0$ such that $a_0=q_0c_0+c_1$ where $0\leq c_1. The next step is to repeat the process, writing $c_0=q_1c_1+c_2$, with $0\leq c_2. Iterating, you find $q_k$ so that $c_{k-1}=q_kc_k+c_{k+1}$, and eventually a $c_n$ is 0, and the process stops.

You might be a little worried (justifiably) that this process only seems to look at $a_0$ and $c_0$, leaving $b_0$ and $d_0$ out of the picture. If you look at what we did with the matrices, our process took $\left(\begin{smallmatrix}a_0&b_0\\ c_0&d_0\end{smallmatrix}\right)$ and wrote it as $T^{q_0}\overline{S}\left(\begin{smallmatrix}a_1 & b_1\\ c_1 & d_1\end{smallmatrix}\right)$, and the $b_1$ and $d_1$ depended on $b_0$ and $d_0$. In the final step of the process, where the $c$-coefficient is 0, we ended up with a $d$-coefficient of 1, but the $b$-coefficient will be a function of the values $b_0$ and $d_0$, so those values do show up and get used, eventually. Of course, since $a_0d_0-b_0c_0=1$, knowing one of $b_0$ or $d_0$ is enough to determine the other (assuming you know $a_0$ and $c_0$). You should be thinking that the $b_i$ and $d_i$ are the extra variables that run around in Euclid’s alrgorithm when you do the “extended” version.

We’ve been talking about all of this in terms of matrices, but remember that the matrices represent linear fractional transformations. The matrix $T$ is the transformation $z+1$, and the power $T^b$ is then $z+b$. These are just horizontal translations. The matrix $\overline{S}$ is the transformation $1/z$. With our relations among the $L_i$ above, we see that we could write

$\begin{array}{rcl}\dfrac{a_0z+b_0}{c_0z+d_0} &=& T^{q_0}\overline{S}L_1 = q_0 + \frac{1}{L_1} \\ &=& q_0+\frac{1}{T^{q_1}\overline{S}L_2}=q_0+\cfrac{1}{q_1+\cfrac{1}{L_2}} \\ &=& q_0+\cfrac{1}{q_1+\cfrac{1}{\ddots+\cfrac{1}{q_k+z}}}\end{array}$

Hurray for continued fractions! Of course, I feel like I set something up backwards. Plugging in $z=0$ will give me a continued fraction for $b_0/d_0$, but I was saying that the $q_k$ come from thinking about the greatest common divisor of $a_0$ and $c_0$. Ah well.

[Update 20091203: The error I’m concerned about above stems from some loose dealings with the end of the iterative procedure. Letting $L_i=\left(\begin{smallmatrix}a_i & b_i\\ c_i & d_i\end{smallmatrix}\right)$, we will get to something like $L_n=T^{q_n}\overline{S}L_{n+1}$ where $L_{n+1}=\left(\begin{smallmatrix}1 & b_{n+1} \\ 0 & 1\end{smallmatrix}\right)$, i.e. $L_{n+1}=T^{b_{n+1}}$. So we end up saying $L_0=T^{q_0}\overline{S}T^{q_1}\overline{S}\cdots T^{q_n}\overline{S}T^{b_{n+1}}$. And that $b_{n+1}$ does depend on the initial $b_0$, presumably in a manner such that plugging in $z=0$ makes the fraction make sense.]

What I’ve said is that every 2×2 matrix with coefficients in $\mathbb{Z}$ and determinant 1 can be written in terms of $T$ and $\overline{S}$. However, you might want to use $S=\left(\begin{smallmatrix}0&-1\\ 1&0\end{smallmatrix}\right)=-1/z$ instead of $\overline{S}$. Going through essentially the same process as before, with some minus signs sprinkled in appropriately, one can determine that $T$ and $S$ can be used, instead of $T$ and $\overline{S}$, to generate any of the matrices we are considering. What is the advantage of $S$ over $\overline{S}$? One way to state the advantage, for our story, is that applying $S$ to points in the upper half plane leaves them in the upper half plane (and similaly for the lower half), whereas $\overline{S}$ flips points in upper half plane to the lower half plane. We should think of this an advantage, because all of our Ford circles lie in the upper half plane. If you go back to yesterday’s discussion, you’ll note that I used $S$ in the factorization.

So, anyway, $T$ and $S$ are the only LFTs you need. You can quickly check that $S^2=1$ and also (not quite as quickly) that $(TS)^3=1$. If you write $U=TS$, then I guess you get to say that the modular group is generated by $S$ and $U$, and can establish an isomorphism between the modular group and the free product of the cyclic group of order 2 with the cyclic group of order 3. That’s something.