\documentclass{amsart}
%----------Packages----------
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{dsfont}
\usepackage[all]{xy}
\usepackage[mathcal]{eucal}
%----------Commands----------
\DeclareMathOperator{\id}{id}
\DeclareMathOperator{\Fun}{Fun}
\DeclareMathOperator{\Hom}{Hom}
\DeclareMathOperator{\tr}{tr}

\newcommand{\R}{\mathbb{R}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\Sph}{\mathbb{S}}
\newcommand{\D}{\mathbb{D}}
\newcommand{\Hyp}{\mathbb{H}}
\newcommand{\PP}{\mathbb{P}}
\newcommand{\Mob}{\text{M\"ob}}
\newcommand{\im}{\text{Im}}
\newcommand{\re}{\text{Re}}
\newcommand{\IsoD}{\mathcal{D}}
\newcommand{\Map}{\text{Map}^+}
\newcommand{\Aut}{\text{Aut}^+}

\newcommand{\inv}{^{-1}}

\providecommand{\abs}[1]{\left\vert#1\right\vert}
\providecommand{\pmat}[4]{\left(\begin{smallmatrix} #1 & #2 \\ #3 & #4\end{smallmatrix}\right)}
\providecommand{\pmat}[4]{\left[\begin{smallmatrix} #1 & #2 \\ #3 & #4\end{smallmatrix}\right]}
\providecommand{\pvec}[2]{\left(\begin{smallmatrix} #1 \\ #2 \end{smallmatrix}\right)}
\providecommand{\bvec}[2]{\left[\begin{smallmatrix} #1 \\ #2 \end{smallmatrix}\right]}
%----------Theorems----------
\newtheorem{thrm}{Theorem}[section]
\newtheorem{prop}[thrm]{Proposition}
\newtheorem{cor}[thrm]{Corollary}
\newtheorem{lemma}[thrm]{Lemma}
\newtheorem{claim}[thrm]{Claim}

\theoremstyle{definition}
\newtheorem{defn}[thrm]{Definition}

\theoremstyle{remark}
\newtheorem*{exercise}{Exercise}
\newtheorem*{ex}{Example}
\newtheorem*{remark}{Remark}
\newtheorem*{observation}{Observation}
\newtheorem*{note}{Note}
\newtheorem*{question}{Question}
\newtheorem*{answer}{Answer}
%----------Title-------------
\title{University of Chicago REU 2007:\\Groups of $2\times 2$ matrices}
\author{Course by Uri Bader\\July 16-27, 2007\\notes typed by Spencer Dowdall}
%----------Header------------

\begin{document}

\maketitle

\section{Linear Transformations}

Let $K$ be a field (such as $\R$, $\C$, $\dots$), and let $V = K^2 = \{\pvec{s}{t} : s,t\in K\}
= \{se_1 + te_2 : s,t\in K \}$ (where $e_1 = \pvec{1}{0}, e_2 = \pvec{0}{1}$).

\begin{defn} A \emph{linear transformation} is a map $T:V\to V$ such that
\[T(\alpha x + \beta y) = \alpha T(x) + \beta T(y)\]
for all $x,y\in V$ and all $\alpha,\beta\in K$.
\end{defn}


\begin{claim}
 $T$ is determined by the four scalars $\pmat{a}{b}{c}{d}$ where $T(e_1) = ae_1 + ce_2$, $T(e_2) = be_1 + de_2$
\end{claim}
\begin{proof}
 For the vector $\pvec{s}{t} = se_1 + te_2\in V$, we have
\begin{align*}
T\pvec{s}{t} =& T(se_1 + te_2) = sT(e_1) + tT(e_2) = s(ae_1 + ce_2) + t(be_1 + de_2)\\
 =& (as + bt)e_1 + (cs + dt)e_2 = \pvec{as + bt}{cs + dt} =: \pmat{a}{b}{c}{d}\pvec{s}{t}
\end{align*}
\end{proof}

Matrix mutliplication is given by the composition rule: If $T:V\to V$ and $T':V\to V$ are linear transformations corresponding to $\pmat{a}{b}{c}{d}$ and $\pmat{a'}{b'}{c'}{d'}$, then $T\circ T'$ is the linear transformation corresponding to
\[\pmat{aa' + bc'}{ab' + bd'}{ca' + dc'}{cb' + dd'} =: \pmat{a}{b}{c}{d}\pmat{a'}{b'}{c'}{d'}\]
In particular, matrix multiplication is associative and non-commutative. (Why? Because we know this for linear transformations). Also, if $0 = \pmat{0}{0}{0}{0}$ is the zero matrix and $I = \pmat{1}{0}{0}{1}$ is the identity matrix, then
\[\pmat{0}{0}{0}{0}\pmat{a}{b}{c}{d} = \pmat{0}{0}{0}{0} = \pmat{a}{b}{c}{d}\pmat{0}{0}{0}{0}
\quad\text{and}\quad
\pmat{1}{0}{0}{1}\pmat{a}{b}{c}{d} = \pmat{a}{b}{c}{d} = \pmat{a}{b}{c}{d}\pmat{1}{0}{0}{1}\] 

\begin{defn} A matrix $\pmat{a}{b}{c}{d}$ is \emph{invertible} if there exists a matrix $\pmat{a'}{b'}{c'}{d'}$ such that $\pmat{a}{b}{c}{d}\pmat{a'}{b'}{c'}{d'} = I$.
\end{defn}
\begin{claim}
The matrix $\pmat{a}{b}{c}{d}$ is invertible if and only if $\det\pmat{a}{b}{c}{d} = ad-bc\neq 0$
\end{claim}
\begin{proof}
Firstly, if $ad-bc\neq 0$ then one easily checks that $\pmat{a}{b}{c}{d}\inv = \tfrac{1}{ad-bd}\pmat{d}{-b}{-c}{a}$ so that $\pmat{a}{b}{c}{d}$ is indeed invertible. Conversely, if $ad-bc = 0$ then $\pmat{a}{b}{c}{d}\pvec{d}{-c} = \pvec{0}{0}$. Thus, if $\pmat{a}{b}{c}{d}\inv = \pmat{a'}{b'}{c'}{d'}$, then
\[\pvec{d}{-c} = \pmat{1}{0}{0}{1}\pvec{d}{-c} = \pmat{a'}{b'}{c'}{d'}\pmat{a}{b}{c}{d}\pvec{d}{-c} = \pmat{a'}{b'}{c'}{d'}\pvec{0}{0} = \pvec{0}{0} \implies c,d = 0\] 
Similarly, $\pmat{a}{b}{c}{d}\pvec{-b}{a} = \pvec{0}{0} \implies a,b = 0$. This is a contradiction since $\pmat{0}{0}{0}{0}$ is not invertible.
\end{proof}

\begin{exercise} Show that $\pmat{a}{b}{c}{d}$ is invertible as a matrix if and only if the corresponding linear transformation $T:V\to V$ is one-to-one and onto.
\end{exercise}

\begin{defn}
 The above shows that the set of invertible matrices over $K$ forms a group. This group is called the \emph{General Linear Group} and is denoted by $GL_2(K)$.
\end{defn}

\begin{remark}
 $GL_2(\R) \subset \mathcal{M}_{2\times 2}(\R) \simeq\R^4$ ($\mathcal{M}_{2\times 2}(K)$ is the set of $2\times 2$ matrices over $K$). The compliment of this subset is the inverse image of $\{0\}$ under the determinant map $\det:\mathcal{M}_{2\times 2}(\R) \to \R$; so $GL_2(\R) = \det\inv(\R-\{0\})$ which is an open set. Thus $GL_2(\R)$ is not only an algebraic object (group) but is also a topological and geometrical object.
\end{remark}


\section{The Projective Line}
\begin{defn}
Let $\PP(V)$ denote the set of all linear lines in $V$. (A linear line in $V$ is a straight line through the origin, i.e. a linear subspace of dimension $1$; such lines should not be confused with affine lines which need not pass through the origin). Thus
\[\PP(V) = \{\text{all linear lines in } V\} = \{\text{all 1-dimensional linear subspaces of } V\}\]
\end{defn}

To each nonzero vector we may associate the unique line containing it and the origin, thus we have a map $V-\{0\} \to \PP(V)$, $x\mapsto \{\lambda x : \lambda\in K\}$. In this way, two nonzero vectors define the same line iff they are scalar multiplies of eachother; whence $\PP(V) \simeq V-\{0\}/\sim$ where $u\sim v$ if there exists a scalar $\lambda \in K$ such that $\lambda u = v$ (this is obviously an equivalence relation).

\begin{defn}
$\PP^1(K):= \PP(K^2)$ is called the \emph{projective line over $K$}. (It is called a line because it is (in some sense) a one-dimensional object. In higher deminsions we set $\PP^n(K) = \PP(K^{n+1})$).
\end{defn}

If $v\in V-\{0\}$, then let $[v] = \{u\in V-\{0\} : u \sim v\}$ be the equivalence class of all nonzero vectors equivalent to $v$ (i.e., all nonzero vectors on the same linear line as $v$). Then
\[\PP^1(K) = \left\{\bvec{s}{t} : s,t\in K\right\} = \left\{\bvec{1}{t} : t\in K \right\} \cup \left\{\bvec{0}{1}\right\} \cong K \cup \{\infty\} = \hat{K}\]
(think ``one-point compactification'').

\begin{exercise}
 Convince yourself that $\PP^1(\C) = \hat{\C}$ is homeomorphic (that is, topologically equivalent) to the two-sphere $\Sph^2$.
\end{exercise}

Note that the projective line is homogeneous: it looks the same in every direction (the point $\{\infty\}$ is not special). Observe that the action of $GL_2(K)$ on $K^2$ preserves lines (i.e., it sends lines to lines). Therefore this action decsends to an action of $GL_2(K)$ on $\PP^1(K)$.

\begin{claim}\label{claim:3-transitivity}
 The action of $GL_2(K)$ on $\PP^1(K)$ is three-transitive (but not four-transitive), that is, every (ordered) triple of distinct lines can be mapped to any other (ordered) triple of disinct lines by some element of $GL_2(K)$.
\end{claim}
The proof of this is given below, but try to prove it yourself first as an exercise. (Hint: consider the triple $0,1,\infty\in \hat{K} = \PP^1(K)$. Show that every triple of distinct lines can be mapped to it.)

\begin{remark}
 The action of $GL_2(K)$ on $\PP^1(K)$ has a kernel. (If a group $G$ acts on the set $X$, then the \emph{kernel} of the action is the set of those group elements $g\in G$ which act trivially on $X$.) The kernel of this action is exactly the subgroup of scalar matrices:
\[\text{kernel} = \{\pmat{\lambda}{0}{0}{\lambda} : \lambda \in K\} = \text{Scalars}\]
(note that this subgroup is exactly the center of $GL_2(K)$). 

Since the scalar matrices are the kernel of the action of $GL_2(K)$ on $\PP^1(K)$, the action factors through an action of the quotient group $PGL_2(K) := GL_2(K) / \text{Scalars}$ on $\PP^1(K)$ (note that scalar matrices are a normal subgroup of $GL_2(K)$). In fact, $PGL_2(K)$ acts \emph{simply transitively} on the set of distinct ordered triples in $\PP^1(K)$, that is, for every two ordered triples of distinct points in $\PP^1(K)$ there is a unique element in $PGL_2(K)$ that maps the one to the other. 
\end{remark}

\begin{exercise} These remarks are justified below, but you should try to prove them yourself first.
\end{exercise}

\section{M\"obius transformations: another point of view}

Recall that $\PP^1(K) = K\cup \{\infty\}$. In coordinates ($z\leftrightarrow \bvec{z}{1}$, $\infty\leftrightarrow \bvec{1}{0}$) the action of $GL_2(K)$ on $\PP^1(K)$ is given by
\[\pmat{a}{b}{c}{d}\bvec{z}{1} = \bvec{az+b}{cz+d} = \bvec{\frac{az+b}{cz+d}}{1}\]
On $K \subset \PP^1(K)$ this is the mapping $z\mapsto \frac{az+b}{cz+d}$ (such mappings are called \emph{M\"obius transformations}). More precisely, $\pmat{a}{b}{c}{d}\in GL_2(K)$ acts on $\PP^1(K)$ by
\[z\mapsto \begin{cases} 
\infty & cz+d =0 \\ 
\frac{a}{c} & z = \infty, c \neq 0 
\\ \infty & z = \infty, c = 0
\\ \frac{az+b}{cz+d} & \text{else}
\end{cases}\]

\begin{exercise}
 Verify that composition of M\"obius transformations corresponds to matrix multiplication.
\end{exercise}

\begin{remark}
 If $\Mob(K)$ is the group of M\"obious transformations of $K$, then $\Mob(K) \simeq PGL_2(K) \simeq \text{Gal}(K(z),K)$
\end{remark}

We now give a proof the of Claim~\ref{claim:3-transitivity}: 
\begin{proof} (of \ref{claim:3-transitivity})
 We will show that for every triple of lines $L_1,L_2,L_3\in \PP^1(K)$, we can find a $g\in GL_2(K)$ such that $g\pvec{1}{0}\in L_1$, $g\pvec{0}{1}\in L_2$, and $g\pvec{1}{1}\in L_3$. Pick $u_i\in L_i$. $\{u_1,u_2\}$ is a basis, hence $u_3 = \alpha u_1 + \beta u_2$ for some $\alpha,\beta \in K$. Set $v_1 = \alpha u_1$, $v_2 = \beta u_2$, $v_3 = u_3 = \alpha u_1 + \beta u_2 = v_1 + v_2$. Let $g\in GL_2(K)$ be the unique element sending $\pvec{1}{0}\mapsto v_1$ and $\pvec{0}{1}\mapsto v_2$ (if in coordinates $v_i = \pvec{v_{ix}}{v_{iy}}$, then take $g = \pmat{v_{1x}}{v_{2x}}{v_{1y}}{v_{2y}}$). Then $g$ satisfies $\pvec{1}{1}\mapsto v_1 + v_2 = v_3$. Hence it will satisfy $0 \mapsto L_1$, $\infty \mapsto L_2$, and $1\mapsto L_3$. 
\end{proof}

We now justify the remark made earlier that the action of $PGL_2(K)$ on the set of ordered triples of distinct points in $\PP^1(K)$ is simply transitive.

If a group $G$ acts on a set $X$ then the \emph{stabilizer} of a point $x\in X$ is the set $\text{Stab}(x) = \{g\in G : gx = x\}$.
\begin{claim}\label{conjugate-stabilizers}
Suppose that $x,y\in X$ are such that $y = gx$ for some $g\in G$ (such $x$ and $y$ are said to lie in the same \emph{orbit}), Then
\[\text{Stab}(y) = \{ghg\inv : h\in \text{Stab}(x)\} =: \text{Stab}(x)^g\]
\end{claim}
\begin{proof}
If $h\in \text{Stab}(x)$ then $(ghg\inv)y = ghg\inv gx = gx = y$ so that $ghg\inv \in \text{Stab}(y)$. Conversely, if $\gamma\in \text{Stab}(y)$ then $g\inv \gamma g \in \text{Stab}(x)$ so that $ \gamma = g(g\inv \gamma g)g\inv \in \text{Stab}(x)^g$.
\end{proof}
In the action of $GL_2(K)$ on ordered triples of distinct points in $\PP^1(K)$, the stabilizer of $(0,1,\infty)$ is the subgroup of scalar matrices. If $(L_1,L_2,L_3)$ is any ordered triple, then $(L_1,L_2,L_3) = g(0,1,\infty)$ for some $g\in GL_2(K)$. Whence \ref{conjugate-stabilizers} implies that $\text{Stab}(L_1,L_2,L_3) = \{gh g\inv : h\in \text{Scalars}\} = \text{Scalars}$. Since the stabilzer of every triple is exactly the subgroup of scalar matrices, the quotient group $PGL_2(K)$ indeed acts simply transitively. In fact, there is a bijection of sets: $PGL_2(K) \simeq \{\text{(distint, ordered) triples in } \PP^1(K)\}$.

\section{Cross-Ratio}

Observe that the mapping $z\mapsto \frac{(z-z_1)(z_2-z_3)}{(z-z_3)(z_2-z_1)}$ is a M\"obius transformation that sends $(z_1,z_2,z_3)\mapsto (0,1,\infty)$ (in our coordinates $z\leftrightarrow \bvec{z}{1}$ and $\infty\leftrightarrow \bvec{1}{0}$).

\begin{exercise}
 Write this in matrix form
\end{exercise}

\begin{defn} (first definition) For distinct points $w,x,y,z\in \PP^1(K)$, let $g\in GL_2(K)$ be such that $(gw,gx,gy) = (0,1,\infty)$. The \emph{cross-ratio} of $w,x,y,z$ is defined to be the element $(w,x,y,z):=gz\in \PP^1(K)$. Thus the corss-ratio is a mapping $CR:\{\text{distinct 4-tuples in } \PP^1(K)\} \to \PP^1(K)$. Observe that the cross-ratio is $GL_2(K)$-invariant: for $h\in GL_2(K)$, $(hw,hx,hy,hz) = (w,x,y,z)$.
\end{defn}

\begin{defn} (second definition: in coordinates) Representing elements of $\PP^1(K)$ by elements in $K$ (via $z\leftrightarrow \bvec{z}{1}$), we define a \emph{cross-ratio} $CR:\{\text{distinct 4-tuples in }K\} \to K$ by $(z_1,z_2,z_3,z_4)\mapsto z$, where $\left(\bvec{z_1}{1},\bvec{z_2}{1},\bvec{z_3}{1},\bvec{z_4}{1}\right) = \bvec{z}{1}$. This definition leads to an explicit formula:
\[(z_1,z_2,z_3,z_4) = \frac{(z_4-z_1)(z_2-z_3)}{(z_4-z_3)(z_2-z_1)}\]
\end{defn}
\begin{cor}
 The formula is invariant under M\"obius transformations.
\end{cor}
\begin{proof}
 Exercise.
\end{proof}

\begin{thrm}
A self-map of $\PP^1(K)$ that preserves the cross-ratio is from $PGL_2(K)$ (i.e. a M\"obius transformation).
\end{thrm}
\begin{proof}
 Exercise.
\end{proof}

\begin{claim}
 Every M\"obius transformation can be written as a composition of transformations of the following forms:
\[z\mapsto az,\qquad z\mapsto z+b, \qquad z\mapsto \frac{-1}{z}\]
\end{claim}
\begin{proof}
 Consdier $z\mapsto \frac{az+b}{cz+d}$. If $c = 0$, then the map is
\[z\mapsto \tfrac{az+b}{d} = \tfrac{a}{d}z + \tfrac{b}{d}  = (z\mapsto z + \tfrac{b}{d})\circ(z\mapsto \tfrac{a}{d}z)\]
If $c \neq 0$, then
\[\tfrac{az+b}{cz+d} = \tfrac{\tfrac{a}{c}(cz+d) + (b-\tfrac{ad}{c})}{cz+d} = (b-\tfrac{ad}{c})\tfrac{1}{cz+d} + \tfrac{a}{c}\]
Therefore
\[z\mapsto \tfrac{az+b}{cz+d} = (z\mapsto z + \tfrac{a}{c})\circ(z\mapsto(b-\tfrac{ad}{c})z) \circ (z\mapsto \tfrac{1}{z}) \circ (z\mapsto z+d) \circ (z\mapsto cz)\]
\end{proof}

\begin{cor}
This decomposistion of $PGL_2(K)$ can be used to give a decomposition of $GL_2(K)$, known as the \emph{Bruhat decomposition of matrices}.
\end{cor}

When $K = \C$, the complex projective line $\PP^1(\C) = \hat{\C} = \C \cup\{\infty\} \simeq \Sph^2$ is called the \emph{Riemann Sphere}. In this case the transformation $z\mapsto z + b$ is a translation by $b\in \C$, the transformation $z\mapsto \lambda z$ is scaling by $\abs{\lambda}$ and a rotation by $\alpha$ where $\lambda = \abs{\lambda} e^{i\alpha}$, and the transformation $z\mapsto \frac{-1}{z}$ is an inversion and reflection in the unit circle.

\begin{defn}
A \emph{generalized circle} in $\hat{\C}$ is a Euclidean circle or line in $\C$. (Lines in $\C$ are thought of as circles through $\{\infty\}\in \hat{\C}$.) Therefore, any three distinct points in $\hat{\C}$ determine a unique generalized circle.
\end{defn}

\begin{thrm}\label{real-cross-ratio}
Let $w,x,y,z\in \PP^1(\C)$ be distinct. Then for their corss-ratio we have $(w,x,y,z)\in \R$ iff the four points $w,x,y,z$ all lie on a generalized circle (i.e., iff $z$ lies on the generalized circle determined by $w,x,y$).
\end{thrm}
\begin{proof}
 Exercise. (Hint: first prove the case $w,x,y\in \PP^1(\R)$, then generalize by 3-transitivity.)
\end{proof}

\begin{cor}
M\"obius transfromations take generalized circles to generalized circles. Moreover, $\Mob(\C)$ acts transitively on the set of generalized circles.
\end{cor}
\begin{proof}
This follows from 3-transitivity and Thm~\ref{real-cross-ratio} since the cross-ratio is preserved by M\"obius transformations.
\end{proof}

\begin{question}
What is the stabilizer of a circle? (recall that since the action is transitive, the stabilizers of different circles will be conjugate subgroups in $Mob(\C)$; thus it is enough to know the stabilizer of one circle). 
\end{question}

\begin{claim}
 The stabilizer of $\PP^1(\R)\subset\PP^1(\C)$ is exactly $PGL_2(\R)$.
\end{claim}
\begin{proof}
It is clear that $PGL_2(\R)$ stabilizes the circle $\PP^1(\R)\subset \PP^1(\C)$. The fact that this is the whole stabilizer follows from 3-transitivity: if $g\in PGL_2(\C)$ stabilizes $\PP^1(\R)$, then $g(0), g(1), g(\infty) \in \PP^1(\R)$. By 3-transitivity of the action of $PGL_2(\R)$ on $\PP^1(\R)$, there is a unque $h\in PGL_2(\R)$ with $h(0,1,\infty) = (g(0), g(1), g(\infty))$. Since $PGL_2(\C)$ acts \emph{simply} 3-transitively on $\PP^1(C)$, the the fact that $g$ and $h\in PGL_2(\R)\subset PGL_2(\C)$ agree on the three points $0$, $1$, and $\infty$ implies that they agree everywhere, whence $g = h\in PGL_2(\R)$.
\end{proof}

Considering the circle $\PP^1(\R)\subset \PP^1(\C) = \hat{C}\cong \Sph^2$ as the equator, the upper and lower hemispheres are the sets:
\begin{align*}
\text{upper hemisphere} =& U = \{z\in \C : \im{z} > 0\} \\
\text{lower hemisphere} =& L = \{z\in \C : \im{z} < 0\}
\end{align*}
(so the points $\{i\}$ and $\{-i\}$ are the north and south poles).

\begin{cor}
 $PGL_2(\R)$ preserves the decomposition $\PP^1(\C) =  \PP^1(\R)\cup U \cup L$.
\end{cor}

\begin{question}
What is the stabilizer of the upper-hemisphere in $PGL_2(\R)$?
\end{question}
\begin{answer}
By the corollary, it suffices to consider whether the image of $i\in U$ lies in $U$ or $L$. If $\pmat{a}{b}{c}{d}\in PGL_2(\R)$, then 
\[\im\left(\pmat{a}{b}{c}{d}i\right) = \im\left(\tfrac{ai+b}{ci+d}\right) = \im\left(\tfrac{(ai+b)(d-ci)}{c^2 + d^2}\right) = \tfrac{\det\pmat{a}{b}{c}{d}}{c^2 + d^2} \in U \iff \det\pmat{a}{b}{c}{d} > 0\]
Whence $\pmat{a}{b}{c}{d}\in PGL_2(\R)$ stabilizes the upper-hemisphere iff $\det\pmat{a}{b}{c}{d} > 0$.
\end{answer}

\begin{defn}
Let $GL_2^+(\R) := \{g\in GL_2(\R) : \det g > 0\}$ be the subgroup of invertible matrices with positve determinant. This is an index-2 subgroup of $GL_2(\R)$. The \emph{Special Linear group} (over $\R$) is the subgroup $SL_2(\R) := \{\pmat{a}{b}{c}{d}\in GL_2(\R) : \det\pmat{a}{b}{c}{d} = 1\}$ of invertible matrices with determinant equal to 1. Whence we have the inclusion of subgroups $SL_2(\R) \leqslant GL_2^+(\R) \leqslant GL_2(\R)$. The images of these subgroups under the natural quotient map $GL_2(\R) \to PGL_2(\R)$ are denoted by $PSL_2(\R)$ and $PGL_2^+(\R)$.
\end{defn}
\begin{exercise}
Show that $PSL_2(\R) = PGL_2^+(\R)$ and that $PGL_2^+(\R)$ is an index-2 subgroup of $PGL_2(\R)$. Whence we have the diagram
\[\xymatrix{
SL_2(\R) \ar[d]^q & \leqslant & GL_2^+(\R) \ar[d]^q& \stackrel{\text{index-2}}{\leqslant} & GL_2(\R) \ar[d]^q\\
PSL_2(\R) & = & PGL_2^+(\R) & \stackrel{\text{index-2}}{\leqslant} & PGL_2(\R)}
\]
\end{exercise}


Observations about the action of $PSL_2(\R)$:
\begin{enumerate}
 \item[(i)] $PSL_2(\R)$ acts on the upper hemisphere $\{z : \text{Im}(z) > 0\}$ and on the circle $\PP^1(\R)$.

 \item[(ii)] The action of $PSL_2(\R)$ is 2-transitive on $\PP^1(\R)$. (For two lines $L_1,L_2\in \PP^1(\R)$, choose two nonzero vectors $v_i\in L_i$. Rescale $v_1$ so that the matrix having $v_1$ and $v_2$ as its columns has determinant 1. Then this matrix sends $e_i$ to $v_i$ and hence $\infty\mapsto L_1$, $0 \mapsto L_2$.

\item[(iii)] The action of $PSL_2(\R)$ is not 3-transitive on $\PP^1(\R)$. Rather, the action on (distinct, ordered) triples has two orbits. (Given three points $x,y,z\in \PP^1(\R)$, one may map $x$ and $y$ to $0$ and $\infty$ by 2-transitivity. An easy calculation shows that the stabilizer of the pair $(0,\infty)$ is diagonal matrices, i.e. matrices of the form $\pmat{\lambda}{0}{0}{\lambda\inv}$. Such matrices act on the third point $z$ by $\pmat{\lambda}{0}{0}{\lambda\inv}\bvec{z}{1} = \bvec{\lambda z}{\lambda\inv } = \bvec{\lambda^2 z}{1}$. Whence the third point $z$ can be scaled by any positive real number, but its sign cannot be changed. Therefore the orbits of the tirples $(0,\infty,1)$ and $(0,\infty,-1)$ are distinct.)

\item[(iv)] The action of $PSL_2(\R)$ on the upper hemisphere $U = \{z : \text{Im}(z) > 0 \}$ is transitive. (By choosing the appropriate $a,b\in \R$, the matrix $\pmat{a}{ba\inv}{0}{a\inv}$ will map the point $\bvec{i}{1}\leftrightarrow i\in U$ to any desired point in $U$.)

\item[(v)] The stabilizer of $i$ is $\left\{\pmat{\cos \theta}{\sin\theta}{-\sin\theta}{\cos\theta} : \theta\in \R\right\} = SO_2(\R)$ (exercise: verify this by a calculation). Identifying $i\in \hat{\C} \simeq \Sph^2$ with the north pole and $\PP^1(\R)\subset \hat{\C}$ with the equator, such matrices rotate the sphere an angle of $\theta$ about the axis through $i$ and $-i$. Be careful! This action of $SO_2(\R)$ on $\hat{\C}$ by M\"obius transformations is not linear and should not be confused with the usual (linear) action of $SO_2(\R)$ on $\R^2\simeq \C$ by rotation.
\end{enumerate}

Observations about the action of $\Mob(\C)$:
\begin{enumerate}
\item[(i)] The subgroup of $\Mob(\C)$ that fixes the origin and the unit circle is $\{z \mapsto e^{2\pi i \alpha}z : \alpha\in [0,1]\}$. (Clearly such maps fix the origin and unit circle. Use 3-transitivity to show that all such maps are of this form.)

\item[(ii)] The action of the M\"obius group is conformal (i.e. it preserves angles). (This follows from the complex-differentiability of M\"obius transformations: the action of the differential is by scalar multiplication, which is conformal).
\end{enumerate}

\section{Hyperbolic Space}

\begin{defn}
Consider the unit disk $\D = \{z\in \hat{\C} : \abs{z} < 1\}$. A \emph{hyperbolic line} in $\D$ is a (generalized) circle that intersects the unit circle $\Sph^1 = \partial \D$ in right angles.
\end{defn}

By 3-transitivity, there is an element $g\in \Mob(\C)$ sending the circle $\PP^1(\R)$ to the unit circle $\partial \D$ and the upper-hemisphere $\{\im z > 0\}$ to the unit disk $\D$. It follows that the conjugate subgroup $\IsoD = g (PSL_2(\R)) g\inv$ is the subgroup of $\Mob(\C)$ which preserves $\D$. The action of $\IsoD$ on $\D$ is therefore conformal, 2-transitive on $\partial \D$, 1-transitive on $\D$, and sends hyperbolic-lines to hyperbolic lines.

\begin{claim}
For every two (distinct) points in $\overline{\D}$, there is a unique hyperbolic line containing them. 
\end{claim}
\begin{proof}
This is immediate for a pair of antipodal points on $\partial \D$ as diameters are clearly hyperbolic lines. The claim thus follows for arbitrary pairs on $\partial \D$ by the 2-transitivity of the confomal action of $\IsoD$ on $\partial \D$. Similarly, the claim is clear for pairs of the form $(0,y)$ with $y\in \overline{\D}$ as the diameter containing $y$ again suffices. Therefore, the result holds for abitrary pairs by the 1-transitivity of the action of $\IsoD$ on $\D$.
\end{proof}

\begin{claim}
The stabilizer of $\partial \D$ in $\Mob(\C)$ acts transitively on the set of hyperbolic lines.
\end{claim}
\begin{proof}
This follows from the 3-transitivity of the action of $\Mob(\C)$ on the unit circle and the bijective correspondence between hyperbolic lines and pairs of points on the unit circle.
\end{proof}

We now adjust our ordering convention for the cross ratio: For $z_0,z_1,z_2,z_3\in \hat{\C}$, set their cross ratio to be $(z_0,z_1,z_2,z_3) = \tfrac{(z_2-z_0)(z_3-z_1)}{(z_1-z_0)(z_3-z_2)}$. (Note: this is the standard convention for the cross-ratio; it is a permutation of the definition given earlier).

\begin{defn}
For $x,y\in \D$, let $L$ be the unique hyberbolic line through $x$ and $y$, and let $s,t$ be the intersections of $L$ with the unit circle $\partial \D$ (labeled so that the points appear in the order $(s,x,y,t)$ on $L$). Define a metric on $\D$ by setting
\[d(x,y) = \tfrac{1}{2}\abs{\log(s,x,y,t)}\]
(recall that by Thm~\ref{real-cross-ratio} the cross-ratio of four points on the same circle is a real number).
\end{defn}

Note that there are some symetries in the cross-ratio $(s,x,y,t)$ obtained by permuting the vaiables. Exercise: Find all of the possibilities for the cross-ratio of four distinct points. 

\begin{remark}
 $d$ is invariant under the subgroup $\IsoD$ of $\Mob(\C)$ preserving $\D$.
\end{remark}

\begin{observation}
Let $z_0,z_1,\dots,z_4$ be any 5 points on the same circle. Then
\begin{align*}
 (z_0,z_1,z_3,z_4) =& \frac{(z_3-z_0)(z_4-z_1)}{(z_1-z_0)(z_4-z_3)} = \frac{(z_2-z_0)(z_4-z_1)}{(z_1-z_0)(z_4-z_2)}\cdot\frac{(z_3-z_0)(z_4-z_2)}{(z_2-z_0)(z_4-z_3)}\\
=& (z_0,z_1,z_2,z_4)\cdot(z_0,z_2,z_3,z_4)
\end{align*}

\end{observation}

\begin{cor}
 Hyperbolic lines are geodesics in the metric space $(\D,d)$. (A \emph{geodesic} is an isometric embedding (copy) of $\R$ into a metric space.)
\end{cor}

\begin{thrm}
 $d$ is a metric on $\D$.
\end{thrm}
\begin{proof}
The only non-trivial thing to check is the triangle inequality. We sketch a proof of this: Let $x,y,z\in \D$ and consider the (hyperbolic) triangle $\Delta\subset \D$ having these points as vertices. Let $a,b,c$ denote the lengths of these sides so that $d(x,z) = a$, $d(x,y) = b$, and $d(y,z) = c$, and let $A$, $B$, $C$ be the cooresponding hyperbolic lines comprising the sides of $\Delta$. We must show $a \leq b + c$.

Let $P$ be the hyperbolic line through $y$ and perpendicular to $A$. and let $w$ be the intersection point of $A$ and $P$. If $a' = d(x,w)$ and $a'' = d(w,z)$, then, by the above observation, we have $a = a' + a''$. Thus it suffices to prove $a' \leq b$ and $a'' \leq c$, so we have reduced to the case of a right triangle.

By applying a M\"obius transformation, we may assume that $x = 0$ so that the hyperbolic lines $A$ and $B$ connconnecting $x$ to $w$ and $y$ are diameters (i.e. straight Euclidian lines). Therefore, if $\tilde{a}$ and $\tilde{b}$ are the Euclidean distances from $x$ to $w$ and $y$, it suffices to check that $\tilde{a}\leq \tilde{b}$. The hyperbolic line $P$ from $w$ to $y$ is now a circular arc perpendicular to the diameter $A$. Draw the striaght Euclidean line $E$ through $w$ perpendicular to $A$ (so $E$ is tangent to $P$ at $w$). Since (looking at things Euclideanly) the line $P$ is curving away from the origin $x$, we see that $E$ intersects $B$ closer to $x$ than does $P$; call this Euclidean distnace $\tilde{b}'$ so that $\tilde{b}' \leq \tilde{b}$. Finally, the lines $A$, $B$, $E$ form a Euclidean right triangle with hypotenuse  of length $\tilde{b}'$. As $\tilde{a}$ is the length of one leg of this triangle, Euclidean geometry implies that $\tilde{a} \leq \tilde{b}' \leq \tilde{b}$ as desired.
\end{proof}

\begin{cor}
$(\D,d)$ is a metric space and the subgroup $\IsoD \leqslant PGL_2(\C)$ preserving $\D$ acts on it by isometries. Indeed, the same holds for any other circle in $\hat{\C}$, in particular, for the upper half plane $\{z : \im(z) > 0\}$ on which $PSL_2(\R)$ acts by isometries.
\end{cor}

\begin{exercise}
Show that $PSL_2(\R) \leqslant \text{Isom}(\text{Upper half-plane})$ is an index-2 subgroup.
\end{exercise}

\begin{defn}
The metric space $(\D,d)$ is called the \emph{hyperbolic plane}, and is denoted by $\Hyp^2$ (sometimes $\Hyp^2(\R)$).
\end{defn}

\section{The group $PSL_2(\Z)$}
The goal in this section is to look at images of $PSL_2(\Z)$ in $PSL_2(\R)$ and understand the corresponding actions on $\Hyp^2$. To this end, we study the space of unimodular lattices.

What are all of the basis of $\C$? Each such is given by a map (of abelian groups) $\Z^2 \stackrel{\varphi}{\to}\C$ such that $\varphi\pvec{1}{0}$ and $\varphi\pvec{0}{1}$ are not on the same line. Considering $\C$ as a 2-dimensional vector space, all such maps are linear, so we may set $\Map(\Z^2,\C) = \{\varphi:\Z^2\to\C : \det(\varphi) >0\}$ to be the space of all such maps with positive determinant.

We will now mod out by some obvious equivalences on this space: There is an obvious left-action of $\C^*$ on $\Map(\Z^2,\C)$ by post-multiplication by a scalar: $\lambda\cdot \varphi = \lambda \varphi$. Similarly, there is a right-action of $\Aut(\Z^2) = SL_2(\Z)$ on $\Map(\Z^2,\C)$ by pre-composition: $\varphi\cdot \alpha = \varphi\circ \alpha$. Since these two actions correspond to post- and pre-composition respectively ($\lambda\cdot \varphi \cdot \alpha = \Z^2 \stackrel{\alpha}{\to}\Z^2 \stackrel{\varphi}{\to} \C \stackrel{\lambda}{\to}\C$), the associativity of composition of maps implies that the two actions commute with each other 

(Note: For $R$ a ring,
\begin{align*}
GL_2(R) =& \{2\times 2 \text{ invertible matrices over } R\} = \{\pmat{a}{b}{c}{d} : ad-bc \in R^*\}
\end{align*} 
(where $R^*$ denotes the set of units of $R$). Therefore $GL_2(\Z) \neq \mathcal{M}_{2\times 2}\cap GL_2(\R)$; but rather $GL_2(\Z) = \mathcal{M}_{2\times 2} \cap \{\det = \pm 1\}$. Whence $SL_2(\Z)$ is an index-2 subgroup of $GL_2(\Z)$.)

There is a natural correspondence: $\Map(\Z^2,\C)/C^* \to \Hyp^2$ (in upper half-plan model) given by $\varphi\mapsto \varphi\pvec{0}{1}\varphi\pvec{1}{0}\inv$; this is clearly a bijection becaues for every $z\in \Hyp^2$, there is a $\varphi\in\Map(\Z^2,\C)$ with $\varphi\pvec{0}{1} = z$ and $\varphi\pvec{1}{0}=1$. Since the actions of $SL_2(\Z$ and $\C^*$ on $\Map(\Z^2,\C)$ commute, we get an induced action of $SL_2(\Z)$ on the quotient $\Map(\Z^2,C)/C^*\cong \Hyp^2$. We also have the natural action of $SL_2(\Z)$ on $\Hyp^2$ by M\"obius transformations. These two actions are related very simply:

\begin{claim}
The action of $SL_2(\Z)$ on the quotient $\Map(\Z^2,\C)/C^*\cong\Hyp^2$ agrees with the usual action on $\Hyp^2$ by M\"obius transformations; i.e. the correspondence $\Map(\Z^2,\C)/C^* \to \Hyp^2$ is an an $SL_2(\Z)$-equivariant bijection.
\end{claim}

\begin{remark}
$_{GL_2(\Z)} \setminus^{\Map(\Z^2,C)} \cong _{SL_2(\Z)} \setminus^{\Map(\Z^2,\C)}$ can be identified with the space of lattices in $\C$, or with the space of ``torus group quotients'' of $\C$. In fact the quotient
\[ MV = _{PSL_2(\Z)}\setminus^{\Map(\Z^2,\C)}/_{\C^*}\]
is the space of ``complex structures on the torus''; also called the \emph{modular variety}. Accordingly, $PSL_2(\Z)$ is also called the \emph{modular group}.
\end{remark}

\begin{question}
What does the space $MV$ look like? 
\end{question}

To answer this, we will study/find a \emph{fundamental domain} for the action of $PSL_2(\Z)$ on $\Hyp^2$ (a \emph{fundamental domain} is a subset of $\Hyp^2$ that meets each (generic) orbit in exactly one point). (Note: Although $PSL_2(\R)$ acts transitively on $\Hyp^2$, the subgroup $PSL_2(\Z) \leqslant PSL_2(\R)$ is discrete and therefore cannot act transitively.)


\begin{claim}
Let $F = \{z\in \Hyp^2 : \abs{z} \geq 1\} \cap \{z\in \Hyp^2 : -\tfrac{1}{2} \leq \im(z) \leq \tfrac{1}{2}\}$. Then $F$ is a fundamental domain for the action of $PSL_2(\Z)$ on $\Hyp^2$; more precisely, every orbit of $PSL_2(\Z)$ in $\Hyp^2$ meets $F$ in exactly one interior point, exactly two boundary points, or the point $i$.
\end{claim}
\begin{proof} (sketch)
Consider a lattice $\Lambda = \varphi(\Z^2)$ for $\varphi\in \Map(\Z^2,\C)$. Up to the action of $\C^*$, we may assume that $\varphi\pvec{1}{0}=1$. Up to the $SL_2(\Z)$ action, we may assume that (i) $\varphi\pvec{1}{0}$ is of shortest length in $\varphi(\Z^2)$ and that (ii) $\abs{\re(\varphi\pvec{0}{1})} \leq \frac{1}{2}$; whence $x=\varphi\pvec{0}{1}\in F$. Since $\{\varphi\pvec{1}{0},\varphi\pvec{0}{1}\}$ forms a basis of $\varphi(\Z^2)$, it follows that (iii) $\im(x)$ is minimal in $\varphi(\Z^2)$. (Note that facts (i)-(iii) uniquely determine a vector $v$ such that $\{1,v\}$ is a basis.) Therefore, to the lattice $\Lambda$ we associate the unique point $x = \varphi\pvec{0}{1}\in\Lambda$ such that $x\in F$ and $\im(x)$ is minimal in $\Lambda$. Conversely, given an interior point $y\in F$ we associate the lattice with basis $\{1,y\}$. Thus we have a bijection:
\[\xymatrix{
\text{lattices} \ar@(ur,ul)[rrr]^{\text{the above argument}}  &&& \ar@(dl,dr)[lll]^{\text{lattice generated by } \{1,x\} }\text{(interior) points } x\in F 
}\]

However, this is not a bijection on $\partial F$ where we have the identifications $z \leftrightarrow z+1$ for $z\in F \cap \{\re(z) = -\frac{1}{2}\}$ (corresonding to the action by the group element $\pmat{1}{1}{0}{1}\in PSL_2(\Z)$), and $z\leftrightarrow -\frac{1}{z}$ for $z\in F\cap \{\abs{z} = 1\}$ (corresponding to the action by the group element $\pmat{0}{-1}{1}{0}\in PSL_2(\Z)$). Making these identifications, we see that the modular variety (recall that $MV = \text{the quotient space } _{PSL_2(\Z)}\setminus^{\Map(\Z^2,\C)}/_{\C^*}$) is shaped like a ``triangular pillowcase'' with cusps at $i$, $(\frac{1}{2},\frac{\sqrt{3}}{2})$, and $\infty$. 
\end{proof}

This picture of the modular variety should help us understand the algebraic structure of $PSL_2(\Z)$.

\section{The Structure of $PSL_2(\Z)$}
Consider the elements $S= \pmat{0}{-1}{1}{0}, T = \pmat{1}{1}{0}{1}\in PSL_2(\Z)$ corresponding to the M\"obius transformations $S(z) = -\frac{1}{z}$, and $T(z) = z+1$.

\begin{claim}
The elements $S$ and $T$ generate $PSL_2(\Z)$.
\end{claim}
\begin{proof} (sketch)
Observe that the stabilizer of $2i\in F$ is trivial in $PSL_2(\Z)$. (Exercise: show this. Idea: if $\frac{a(2i) + b}{c(2i) + d} = 2i$ with $a,b,c,c\in \Z$, then conclude $\pmat{a}{b}{c}{d} = \pmat{\pm 1}{0}{0}{\pm 1}$.) Now, consider $g\in PSL_2(\Z)$ and let $y = g(2i)$. The goal is to use $S$ and $T$ to send $y$ into $F$, i.e. to find a word $w$ in $S$ and $T$ such that $w y \in F$. Since $\text{Orbit}_{2i}\cap F = \{2i\}$, we have that $2i = w y = (wg)2i$ which implies that $g = w\inv$ is a word in $S$ and $T$ since the stabilizer of $2i$ is trivial.

We now describe the algorithm to construct the word $w$:
\begin{enumerate}
\item[(i)] If $\im(y) > 1$, then $T^n y \in F$ for some $n\in \Z$
\item[(ii)] If $\im(y) < 1$, then we apply $T^n$ to get either into $F$ or into the open hemisphere $\{\abs{z} < 1\}$. In the first case we are done, in the second, apply $S$ to increase $\im(y)$.
\item[(iii)] Repeat.
\end{enumerate}
We need only check that $\im(y)$ increases by a sufficient amount each time so that we always eventually obtain $\im(y) > 1$ (i.e., so that the algorithm terminates). This is made more precise by the following compactness arbument: If I start at $y = a + bi$, then when I apply $S$ and $T$ as in the above algorithm, I always end up in $\{z : \abs{z} \leq \frac{1}{b}\}\cap\{z : \im(z) \geq b\}$, which is a compact set. This compact set can only intersect finitely many copies of the fundamental domain (in the tiling of $\Hyp^2$ by the images of $F$ under $S$ and $T$), so the algorithm must terminate.
\end{proof}

\begin{cor}
Set $U = ST$. Then $PSL_2(\Z)$ is generated by $S$ and $U$.
\end{cor}

Observe that $S(z) = -\frac{1}{z} \leftrightarrow \pmat{0}{1}{-1}{0}$ and $U(z) = \frac{-1}{z+1} \leftrightarrow \pmat{0}{-1}{1}{1}$. One easily checks that $S^2 = 1 = U^3$.

Consider the group $G$ given by the presentation $G = \langle \tilde{S}, \tilde{U} : \tilde{S}^2 = \tilde{U}^3 = 1\rangle$. Thus $G$ is the (universal) group generated by the two elements $\tilde{S}$, $\tilde{U}$ under the relations $\tilde{S} =  1 =\tilde{U}^3$. (Note that this is the same as the free product: $G = C_2 \ast C_3$, where $C_n$ is the cyclic group of order $n$.)

Such a group can be constructed as follows: Take the free group $F(\tilde{S},\tilde{U})$ on the two symbols $\tilde{S}$ and $\tilde{U}$. That is
\[F(\tilde{S},\tilde{U}) = \{\text{all reduced words in } \tilde{S}, \tilde{U}, \tilde{S}\inv, \tilde{U}\inv\}\]
(\emph{reduced} means that we cancel all terms $\tilde{S}\tilde{S}\inv, \tilde{S}\inv \tilde{S}, \tilde{U}\tilde{U}\inv, \tilde{U}\inv \tilde{U}$). Note that this $F$ is a functor from the category of sets to the category of groups. It is left adjoint to the forgetful functor $U$ from the category of groups to the category of sets.

Let $N$ be the minimal normal subgroup of $F(\tilde{S},\tilde{U})$ containing the elements $\tilde{S}^2$ and $\tilde{U}^3$ (e.g, take $N$ to be the intersection of all such subgroups). The presentation $\langle \tilde{S},\tilde{U} | \tilde{S}^2 = \tilde{U}^3 = 1\rangle$ is defined to be the quotient by $N$:
\[G = \langle \tilde{S},\tilde{U} | \tilde{S}^2 = \tilde{U}^3 = 1\rangle := F(\tilde{S},\tilde{U})/N\]
The groups $F(\tilde{S},\tilde{U})$ and $G$ satisfy the following ``universal'' properties:
\begin{enumerate}
\item[(i)] For every group $\Gamma$, and any two elements $s,u\in \Gamma$, there exists a unique homomorphism $\Theta:F(\tilde{S},\tilde{U})\to \Gamma$ such that $\tilde{S}\mapsto s$ and $\tilde{U}\mapsto u$. Moreover, this map is onto iff $\Gamma$ is generated by $s$ and $u$.

\item[(ii)] If in $\Gamma$ we have $s^2 = u^3 = 1$, then $\Theta$ factors through the quotient group $G$:
\[\xymatrix{
F(\tilde{S},\tilde{U}) \ar[d] \ar[rrd]^{\Theta} & \\
G = F(\tilde{S},\tilde{U})/N \ar@{-->}[rr]^{\exists !\theta} && \Gamma}\]
and gives a unique map $\theta:G\to \Gamma$ such that $\tilde{S}\mapsto s$ and $\tilde{U}\mapsto u$.
\end{enumerate}

\begin{cor} There is a unique (surjective) map $\Psi:G = \langle \tilde{S},\tilde{U} | \tilde{S}^2 = \tilde{U}^3 =1 \rangle \to PSL_2(\Z)$ such that $\Psi(\tilde{S}) = S$ and $\Psi(\tilde{U}) = U$.
\end{cor}


\begin{thrm}
The natrual map $\Psi:G\to PSL_2(\Z)$ is an isomorphism.
\end{thrm}
\begin{proof}
It remains to prove that $\Psi$ is injective.

First, let's consider the action of $PLS_2(\Z)$ on $\PP^1(\R)$. Consder $\Sph^1 \cong \PP^1(\R)\subset \PP^1(\C)\cong \Sph^2$. If we let $0,\infty\in \PP^1(\C)$ be the south and north poles of $\Sph^2$ respectively, then $\PP^1(\R)$ is a great meridian of the sphere. Then $\PP^1(\R) -\{0,\infty\} = L'\cup R'$ where $L'$ and $R'$ are the two (open) circular arcs from $0$ to $\infty$, labelled such that $-1\in L'$ and $1\in R'$ (i.e. the left and right halfs of the circle $\PP^1(\R)$). Let $L = \overline{L'} = L\cup\{0,\infty\}$ and, similarly, $R = \overline{R'} = R'\cup\{0,\infty\}$. We now consider the images of $L$ and $R$ under the maps $S$, $U$, and $U^2$:

$S(z) = -\frac{1}{z}$. Thus $S$ maps $0\mapsto \infty$, $\infty \mapsto 0$, $1\mapsto -1$, and $-1\mapsto 1$; whence $S(L)\subset R$. $U(z) = \frac{-1}{z+1}$. Thus $U$ maps $0\mapsto -1$, $\infty \mapsto 0$, $1\mapsto -\frac{1}{2}$, and $-1\mapsto \infty$; whence $U(R)\subset L$. Finally, $U^2(z) = \frac{z+1}{-z}$. Thus $U^2$ maps $0\mapsto \infty$, $\infty \mapsto -1$, $1\mapsto -2$, and $-1\mapsto 0$; whence $U^2(R) \subset L$ as well.

The point is that $S$ sends the left half to the right half, whereas $U$ and $U^2$ send the right half to the left half. Therefore, in their action on $\PP^1(\R)$, we may imgine that $S$ is playing ping-pong against the $U$'s.

We now prove the claim: If $\Psi$ is not injective, then there is an element $w\in G$ with $\Psi(w) = 1\in PSL_2(\Z)$. As $w\in \langle \tilde{S},\tilde{U} | \tilde{S}^2 = \tilde{U}^3 =1 \rangle$, $w$ can be written as a reduced word in $\tilde{S}$, $\tilde{U}$, and $\tilde{U}^2 = \tilde{U}\inv$ in which no two $\tilde{U}$ terms next appear to each other. As $\Psi(g w g\inv) = 1$ for all $g\in G$, by conjugating by an appropriate $g\in G$, we may assume that $w$ starts and ends with $\tilde{U}$ and $\tilde{U}\inv$ (i.e. that $\tilde{S}$ is neither the first nor last letter in $w$), hence $w = \tilde{U}^{\varepsilon_1} \tilde{S} \tilde{U}^{\varepsilon_2} \tilde{S}\cdots \tilde{S} \tilde{U}^{\varepsilon_n}$ for some $n$ with $\varepsilon_i = \pm 1$ for each $i$. Then $U^{\varepsilon_1} S U^{\varepsilon_2} S\cdots S U^{\varepsilon_n} = \Psi(w)=1$ acts as the identity on $\PP^1(\R)$. However, this contradicts the ping-pong game that $S$ and the $U$'s are playing against each other: since there are $n$ $U$ letters and $n-1$ $S$ letters, we see that $\Psi(w)$ maps $R$ into $L$. In particular have $1 = \text{Id}_{\PP^1(\R)}(1) =  (\Psi(w))(1) \in L$, which is a contradiction. Therefore, there is no such $w\in G$ and $\Psi$ must be injective.
\end{proof}

\begin{remark}
People take this ping-pong idea to great extents; there is even a whole abstract formulation and a ``ping-pong lemma'' and such. Indeed, by utilizing the ping-pong lemma, Jacques Tits proved the following:
\end{remark}

\begin{thrm} (Tit's Alternative)
Over any filed $K$, for any dimension $n$, and any group $\Gamma < GL_n(K)$, either $\Gamma$ contains a copy of $\mathbb{F}_2$ (the free group on 2 generators), or $\Gamma$ is virtualy solvable (i.e. contains a solvable subgroup of finite index).
\end{thrm}

\begin{exercise}
Prove, using the same techniques, that $SL_2(\Z) \cong \langle a, b | a^4 = b^6 = 1 \rangle$.
\end{exercise}

\end{document}