Matrices That Represent Continued Fractions

In fact, we can answer the second question in complete generality. If a matrix represents a continued fraction, then we immediately know that the determinant is ±1 and that the denominators (q_n−1,q_n−2) in the second row satisfy q_n−1 > q_n−2 > 0, with some exceptions of course. It turns out that those conditions are not just necessary but also sufficient. Let's start the proof by disposing of the exceptions.

• (0,1). Only a length 0 expansion can have these denominators, so we need to ask whether the matrix is the identity matrix. If so, then depending on the situation we might say that it represents a continued fraction. If not, then it definitely doesn't represent a continued fraction.
• (1,0). Only a length 1 expansion can have these denominators, so we need to require that the determinant is −1, then the matrix must be P(a) for some a. That is, it's the proper form of an integer.
• (1,1). Only a length 2 expansion can have these denominators, so we need to require that the determinant is 1, then the matrix must be P(a,1) for some a. That is, it's the improper form of an integer.

What about the non-exception case? We want to prove that the matrix represents a continued fraction, and the best way to do that is to produce the continued fraction that it represents. So, remember this old equation?

q_n−1 = a_n−1q_n−2 + q_n−3

What it means here is that if we divide q_n−1 by q_n−2, the quotient is the coefficient a_n−1 and the remainder is the previous denominator q_n−3. Then we can divide q_n−2 by q_n−3, and so on. We can regard the entire process either as the Euclidean algorithm applied to q_n−1 and q_n−2 or as the first algorithm applied to the rational number q_n−1/q_n−2. But, we already know the result of the latter from Triangles and The Discriminant.

q_n−1 / q_n−2 = [a_n−1, a_n−2, a_n−3, … , a₃, a₂, a₁]

The first algorithm only produces proper forms, but the expansion above can be proper or improper. How do we know which form to choose? And how do we determine a₀? Let's resolve those two questions by looking at some examples.

Suppose we have the following matrix.

229	99
37	16

When we divide 37 by 16, we can compute not just the previous denominator but also the previous numerator, like so.

229	− 2 × 99 =	31
37	− 2 × 16 =	5

In that way we can run the second algorithm backward all the way to the start. That demonstrates that the matrix really does represent a continued fraction.

		6	5	3	2
0	1	6	31	99	229
1	0	1	5	16	37

The only complication is that when the denominator becomes zero, we can't divide by it, so instead we have to get the coefficient a₀ = 6 from the numerator immediately below.

Now let's look at a different matrix with the same denominators.

252	109
37	16

When we run the second algorithm backward, we get into trouble. When the denominator becomes zero, the numerator becomes −1 instead of 1.

				5	3	2
		−1	7	34	109	252
		0	1	5	16	37

Fortunately, all we have to do to get out of trouble is choose the improper form of q_n−1/q_n−2, that is, [2,3,4,1] instead of [2,3,5].

		6	1	4	3	2
0	1	6	7	34	109	252
1	0	1	1	5	16	37

Is it suspicious that the second example is the same-denominator form of the first? No. The only other way to get the same denominators is to change a₀, not an interesting change.

Can we get into trouble in any other ways? No.

1. Every 2×2 block of numerators and denominators has determinant ±1. We've proved that before starting from the identity matrix on the left, but we can also prove it starting from the original matrix on the right, so it's true even if we get into trouble.
2. So, the original two denominators are relatively prime (because any divisor is also a divisor of the determinant).
3. So, the output of the Euclidean algorithm ends with a 1 followed by a 0.
4. So, when the denominator becomes zero, the numerator can only become ±1.