Two matrices that generate the tree

The rung below ended on a determinant. Two fractions $\tfrac{p}{q}$ and $\tfrac{r}{s}$ are neighbours when $rq - ps = 1$, the starting pair is, the property passes to every mediant, and that single fact is why nothing in the tree ever needs cancelling.

A determinant is a property of a matrix, and there is a matrix here waiting to be written down.

The matrix a node really is #

A node of the tree is usually described by its value, and its value is not enough to grow the tree from — the next step needs to know what the node lies between. So a node is a pair of fractions, and a pair of fractions is four numbers, and four numbers arranged two by two is a matrix:

$$M = \begin{pmatrix} p & r \\ q & s \end{pmatrix}, \qquad \text{value} = \frac{p+r}{q+s}.$$

The root is $\begin{pmatrix} 0 & 1 \\ 1 & 0\end{pmatrix}$, whose columns are $\tfrac01$ and $\tfrac10$ — the two boundary symbols the rung below had to introduce, sitting quietly as the columns of the identity’s cousin.

A left turn keeps the left bound and replaces the right one by the mediant. A right turn does the reverse. Both are matrix multiplications on the right:

$$L = \begin{pmatrix} 1 & 0 \\ 1 & 1\end{pmatrix}, \qquad R = \begin{pmatrix} 1 & 1 \\ 0 & 1\end{pmatrix}.$$

Multiplying $M$ by $L$ replaces the second column by the sum of the two, which is the mediant; multiplying by $R$ replaces the first. The tree’s two moves are those two matrices, and a path down the tree is a word in them.

Why the determinant does everything #

The neighbour condition $rq - ps = 1$ is exactly $\det M = -1$ with the sign convention above, or $+1$ with the columns the other way round. Either way it is a determinant, and the reason it propagates is now one line rather than a computation.

$\det L = 1$ and $\det R = 1$. And a determinant multiplies: the determinant of a product is the product of the determinants. So every word in $L$ and $R$ has determinant $1$, and the root’s matrix has determinant $-1$, so every node’s matrix has determinant $-1$.

That is the rung below’s inductive argument replaced by an algebraic identity. The induction there checked $(p+r)q - p(q+s) = rq - ps$ by expanding; here nothing is expanded, because multiplicativity is a theorem about all matrices and this is an instance of it.

And lowest terms follow immediately. A common factor $d$ of the mediant’s parts would divide any integer combination of them, including the determinant, which is $\pm 1$. So $d = 1$.

Read the other way, the same line says something stronger than lowest terms and worth having on its own. A determinant of $\pm 1$ means the equation $px + qy = 1$ has a whole-number solution, exhibited by the matrix’s other column — so the matrix carries not only the fact that $p$ and $q$ are coprime but a certificate of it. Every node of the tree comes with the Bézout coefficients for its own fraction, computed for free by the multiplication that built it.

That is the practical value of the reading. Establishing that two numbers are coprime is a computation; the tree hands over the coprimality and the witness together, because the witness is the column the construction was carrying anyway. A proof that produces its own certificate is worth more than one that produces a verdict, and here the certificate was never separately computed.

What the two matrices generate #

The natural next question is which matrices are reachable, and the answer is a named object.

$L$ and $R$ generate, as a monoid — products with no inverses allowed — exactly the two-by-two matrices with non-negative whole-number entries and determinant one. Every such matrix is a word in $L$ and $R$, and the word is unique, which is the statement that the tree never rejoins. The figures check the uniqueness on the words they draw by requiring no two to produce the same matrix.

Allow inverses and the two generate the modular group $\mathrm{SL}(2,\mathbb{Z})$ — all integer matrices of determinant one — which is one of the most-studied groups there is. It acts on the upper half-plane by fractional linear transformations, its quotient is the modular curve, and the theory of modular forms is built on it.

So the tree is a picture of a monoid inside a famous group, and the picture came from adding numerators and denominators.

That is worth registering as a fact about how objects arrive. Nobody set out to construct $\mathrm{SL}(2,\mathbb{Z})$ from a schoolroom error; the error turned out to be one of the group’s two generators, acting on pairs of fractions, and the tree is its orbit.

The uniqueness of the word is the half worth dwelling on, because it is what “free” means and it is a strong statement. In a general group two different products of generators can be equal — that is what a relation is — and a monoid in which they never are has no relations at all, so it is as large as two generators can make it.

For $L$ and $R$ the argument is short and is the tree’s ordering read backwards. Any non-negative unimodular matrix other than the root has one column entrywise at least the other; subtracting the smaller from the larger undoes exactly one letter, and which letter is determined by which column was larger. So the last letter is forced, and by induction the whole word is. The construction is reversible one step at a time, which is why nothing in the tree is ever reached twice — the rung below’s assertion that no fraction appears twice, arriving as a statement about subtraction.

That subtraction is Euclid’s algorithm again, running on the two columns. Every reading on this ladder keeps arriving at it, and this is the sharpest form: descending the tree is repeated addition of a pair, and reading a node’s address is repeated subtraction of the same pair.

Reading a word #

The correspondence makes the rung below’s continued-fraction observation into arithmetic.

A path is a word like $R\,L\,R\,R$, and grouping it into runs — one $R$, one $L$, two $R$s — gives the continued fraction $[1; 1, 2]$. In matrix terms a run of $k$ identical letters is $L^k$ or $R^k$, and

$$L^k = \begin{pmatrix} 1 & 0 \\ k & 1\end{pmatrix}, \qquad R^k = \begin{pmatrix} 1 & k \\ 0 & 1\end{pmatrix},$$

so a run is a single matrix with the run length in it. The continued fraction’s quotients are the exponents in the word, and computing a fraction from its continued fraction is multiplying out a handful of matrices rather than descending a tree one step at a time.

That is the whole reason Euclid’s algorithm reaches $\tfrac{355}{113}$ in five steps where the tree takes two hundred and ninety-two: the algorithm computes the exponents and the tree walks the letters. Reading the same fact in the other direction, the algorithm’s step count is the number of runs and not the number of turns, which is why it is logarithmic where a walk is linear.

What being unimodular buys elsewhere #

A matrix of determinant one with whole-number entries is called unimodular, and the word is worth having because the property has the same consequence everywhere it appears.

Its inverse is also a whole-number matrix. The inverse of $\begin{pmatrix} a & b \\ c & d\end{pmatrix}$ is $\frac{1}{ad-bc}\begin{pmatrix} d & -b \\ -c & a\end{pmatrix}$, and dividing by one leaves whole numbers. So a unimodular matrix is invertible over the integers, which almost no integer matrix is — $\begin{pmatrix} 2 & 0 \\ 0 & 1\end{pmatrix}$ has an inverse and it is not a whole-number matrix.

It takes the integer lattice onto itself. A determinant is the factor by which area is multiplied, so a determinant of one means area is preserved; combined with whole-number entries and a whole-number inverse it means the lattice of integer points goes exactly onto itself, with nothing lost and nothing gained.

That is the property the tree is really using. Each node’s matrix is a change of basis of the lattice, and the two bounding fractions are the two basis vectors; the mediant is their sum, which is another lattice point, and the condition that the pair remains a basis is the determinant staying at one.

So the tree is a walk through the bases of the integer lattice, and the fractions are the slopes of the basis vectors. That reading connects it directly to how close a fraction can get, where the question of good approximation becomes a question about lattice points near a line — and the two subjects are the same subject with the same matrices in them.

Where the matrices act #

There is a second reading of $L$ and $R$ that explains why they behave like turns, and it is worth having because it connects the tree to a picture rather than to an arrangement.

A matrix $\begin{pmatrix} a & b \\ c & d\end{pmatrix}$ acts on a number $x$ by $x \mapsto \dfrac{ax+b}{cx+d}$. Under that action $R$ sends $x$ to $x + 1$ and $L$ sends $x$ to $\dfrac{x}{x+1}$, which is $1/(1/x + 1)$ — so $R$ adds one and $L$ inverts, adds one, and inverts again.

Those are exactly the two moves of the continued-fraction algorithm read backwards, and the node’s value is the image of $1$ under the word. A path down the tree is a composition of two simple maps applied to a single starting number, which is a considerably more mechanical description than “take mediants”.

The action also explains the ordering. $R$ increases and $L$ decreases, both strictly, and both preserve the interval a node is confined to — so reading the tree left to right reads the values in order, which the rung below observed and did not explain.

There is a further payoff worth stating, because it makes the tree into an algorithm. Descending towards a target number means, at each step, asking whether the current node is above or below it and turning accordingly. Under the map reading, that is: subtract one if the number exceeds one, otherwise invert — and record which. The descent is the continued-fraction algorithm with its steps written out one at a time, and the word it produces is the algorithm’s trace.

That equivalence is why the tree can answer the clockmaker’s question the rung below described. Finding the simplest fraction in an interval is descending until the current node lands inside; under the map reading it is running the algorithm on the interval’s two ends and stopping where they first disagree, which is five operations rather than hundreds. The two procedures are the same procedure at two granularities, and the coarse one is the useful one.

Where it needs care #

The matrix is not the value. Two different nodes can have the same value in the sense of being equal as fractions only if they are the same node — the tree never repeats — but a matrix carries more than the fraction it evaluates to, and reconstructing the matrix from the value requires the whole path.

The determinant’s sign depends on the convention. With the columns as written the root’s determinant is $-1$ and every node’s is $-1$; ordering the columns the other way makes them all $+1$. Nothing depends on which, and every source picks one silently.

The monoid is free and the group is not. $L$ and $R$ generate a free monoid, so a word determines a matrix and conversely. With inverses allowed the relations of $\mathrm{SL}(2,\mathbb{Z})$ appear and words are no longer unique — the group has a presentation with two generators of orders four and six, which is a completely different structure from the tree’s.

And the identity is not in the tree. The root’s matrix is not the identity, and the word for a node has to be read against that root. A presentation starting from the identity draws a different tree with the same shape.

The action is on the projective line, not on numbers. The map $x \mapsto (ax+b)/(cx+d)$ sends some number to infinity and brings infinity back to a finite value, which is why $\tfrac10$ has to be admitted as a symbol and why it behaves properly under the two letters. A treatment that refuses it has to special-case the right-hand edge of every level, and the rung below said so; the matrix reading explains it, since $\tfrac10$ is an honest column and infinity is an honest point of the projective line.

Two matrices differing by an overall sign act identically, so what really acts is $\mathrm{SL}(2,\mathbb{Z})$ with $\pm$ identified — the group written $\mathrm{PSL}(2,\mathbb{Z})$. Nothing in the tree notices, because every matrix reached from the root has non-negative entries and the sign never arises; but a statement about “the group generated by $L$ and $R$” is ambiguous between the two, and which is meant depends on whether matrices or maps are the subject.

Two names, one construction #

The matrix reading is not in Stern’s paper or in Brocot’s. Stern was doing number theory in 1858 and Brocot was building clocks in 1861, and neither had a reason to write a pair of fractions as a matrix — the notation was available and the habit of using it for this was not.

It arrives with Klein and the study of the modular group in the 1880s, from the other direction entirely: somebody investigating $\mathrm{SL}(2,\mathbb{Z})$ found that its non-negative part is a free monoid on two generators, and the tree is what that statement looks like when the matrices are written as pairs of fractions.

So the two descriptions were developed independently and are the same object, which is the recurring situation on this ladder — the tree, the Farey sequences, the Ford circles and the continued fractions were four subjects before they were one.

That the merge took decades is worth a comment. The obstacle was not difficulty; it was that a mediant is an operation on pairs and a matrix is a natural home for a pair, and nobody put the two together because pairs of fractions had no notation. A construction waits for a notation as often as for an idea.

What the pictures cannot show #

The table shows six words and the tree is infinite. What it can show is the correspondence — word, matrix, columns, value — for enough cases that the pattern is checkable, and the assertion that no two words agree is made on those six rather than on all of them.

The infinitude is the important absence. That every non-negative determinant-one matrix is a word in $L$ and $R$ is a theorem about infinitely many matrices, and six rows are six instances of one direction of it.

And the group is entirely undrawn. $\mathrm{SL}(2,\mathbb{Z})$ acting on the upper half-plane has a picture — the modular tessellation — and it is not on this page, because the tree is its non-negative corner and the rest of it is a different subject.

The ladder from here #

Rungs above: the sequence that lists every rational without a tree, where the same enumeration is flattened into one recursion. The descent towards an irrational, where the path’s stops are the best approximations there are. The modular group’s action on the upper half-plane and the tessellation it produces. Continued fractions of quadratic irrationals, which are eventually periodic exactly when the matrix word is, by Lagrange’s theorem. And the Minkowski question-mark function, which maps the tree onto the binary expansions and turns quadratic irrationals into rationals.

A pair, given a notation #

The habit is the one the history above names: when a construction operates on a pair, look for the object whose notation holds a pair.

The mediant takes two fractions and returns a third, and describing a node by its value throws away the pair the next step needs. Every account of the tree that describes a node by its value has to carry the two bounds separately, in prose, as bookkeeping — and the moment they are written as columns, the bookkeeping becomes multiplication and the invariant becomes a determinant.

Nothing was discovered by that change and a great deal became easy, which is the usual return on a notation. The determinant’s multiplicativity was already a theorem; what the matrix supplies is the observation that the tree’s invariant is an instance of it.

The general test is whether the new notation makes a previously-checked property automatic. Here it makes two: lowest terms and the ordering. If it had made neither, it would be a rewriting rather than a reading.