Group Elements and Matrices

That concludes the primary train of thought. Normally that would mean it was time for a bunch of random thoughts, but today I have something special for you: a secondary train of thought!

By the way, I really like the whole concept of random thoughts. It's just so natural and so pleasing for an essay to end with some stimulating (or even urticating) tidbits instead of a tedious concluding paragraph. I also really like the analogy I made in Understand, “random thoughts exploding like a firework at the end”. So, imagine that while the first firework is going up, we launch a second, the kind that goes up slowly, leaves a bright trail, and ends with a small ball of light and a loud bang.

To get started, let me show you how to compute the value of a repeating expansion. The technique works for any kind of repeating expansion, but let's look at [2,2,1,1] since that's the first one in the table that we don't already know about. The first step is to assign a name to the unknown value.

z = [2,2,1,1]

Next we unroll the first iteration.

z = [2,2,1,1,2,2,1,1]

Next we make a substitution. The result may look strange, but it makes complete sense if you imagine the continued fraction written out as an actual fraction.

z = [2,2,1,1,z]

We can use the second algorithm to evaluate that expansion.

		2	2	1	1	z
0	1	2	5	7	12	12z + 7
1	0	1	2	3	5	5z + 3

Then we just do a little algebra …

z = (12z + 7)/(5z + 3)
5z² + 3z = 12z + 7
5z² − 9z − 7 = 0

… and we've got a quadratic equation that we can solve in the usual way.

z = (9 ± root 221)/10

It turns out that if we take the minus sign, we always get a negative number, so we should always take the plus sign. And that's the desired value!

The numbers that appear in (12z + 7)/(5z + 3) are lifted from the previous two convergents, where the following old identity applies.

p_n+1q_n − p_nq_n+1 = (−1)ⁿ

As a result, [2,2,1,1,z] and other similar expansions have determinant ±1 and are elements of the continued fraction group! Also, expansions with even length (not counting z) have determinant 1 and are also elements of the modular group. That gives us another way to understand what we just did: [2,2,1,1,z] is the group element that adds the prefix “2,2,1,1” and [2,2,1,1] is the relevant fixed point of that group element.

Now we can easily compute the value of a repeating expansion with a non-repeating prefix. If we want to know the value of, say, [1,2,3,4,2,2,1,1], first we find the fixed point of [2,2,1,1,z], then we add the non-repeating prefix by applying [1,2,3,4,z].

Next, let's see how the math works for the general group element G(z).

z = (az + b)/(cz + d)
cz² + dz = az + b
cz² − (a − d)z − b = 0

Solving the quadratic equation is a bit awkward because the coefficients in a quadratic equation are traditionally called a, b, and c, but I managed to figure it out.

z = (1/2c) [ (a − d) ± root D ]

The discriminant D is traditionally b² − 4ac. Here it has a value that we can immediately rearrange.

D	= (a − d)2 + 4bc
	= a2 − 2ad + d2 + 4bc
	= a2 + 2ad + d2 − 4ad + 4bc
	= (a + d)2 − 4(ad − bc)

Now I'd like to change focus slightly, from the group element G(z) to the associated matrix G. On the right, ad − bc is the determinant of G, and on the left, a + d is the trace of G, that is, the sum of the entries on the main diagonal.

D = (tr G)² − 4 det G

We haven't run into the trace before, but it's a standard property of matrices, nearly as useful as the determinant. In fact, the determinant is the product of the eigenvalues, while the trace is the sum. As a fun result, the discriminant is the squared difference of the eigenvalues. However, I don't think the discriminant generalizes to larger matrices. Also note that eigenvalues and fixed points are different things. For comparison, here are the eigenvalues.

λ = (1/2) [ (a + d) ± root D ]

Now let's consider three cases.

In general, the discriminant can be zero or even slightly negative. For example, S(z) = −1/z has discriminant D = −4 and fixed points z = ±i. Group elements like that have interesting geometric properties that you can read about in [Hua] or wherever.

For the group elements we're concerned with, though, the ones that add prefixes made of positive numbers, the fixed points are always real and irrational, so the discriminant is always positive. (A non-repeating prefix can start with a number that's not positive, but we don't ever need to find the fixed points of group elements that add non-repeating prefixes.)

And, for the group elements we're really concerned with, the ones that add prefixes related to the pattern, we can say a little more. For every solution to the Markov equation, we have (1) an expansion that I'll continue to call expansion(u), (2) a group element that adds the associated prefix, and (3) an associated matrix. Let's call that matrix E(u). Because expansion(u) has even length, E(u) has determinant 1, and because of some pattern magic that I don't understand, E(u) has trace 3u. And that brings us back to the original definition of D!

D = 9u² − 4

To make that a little less abstract, here are the matrices E(u) for u < 500.

	1			2			5			13			34			89			233
2	1		5	2		12	7		31	19		81	50		212	131		555	343
1	1		2	1		5	3		13	8		34	21		89	55		233	144
													194
												467	274
												196	115
										29			169
									74	31		432	179
									31	13		181	75
													433
												1043	611
												437	256

The matrices are arranged to show the tree structure, so the top row consists of E(1), E(2), and the matrices for chain 1. Let's ignore E(1) and look at the rest of the top row. It's fairly obvious that c is equal to u and so is always an odd-indexed Fibonacci number; what's less obvious is that d is always the preceding even-indexed Fibonacci number. There's a simple explanation for most of that, though. The associated expansions consist of a pair of 2s followed by some pairs of 1s, so when we run the second algorithm on [2,2,1,1], the output is exactly the matrices.

		2	2	1	1	1	1	1	1	1	1	1	1
0	1	2	5	7	12	19	31	50	81	131	212	343	555
1	0	1	2	3	5	8	13	21	34	55	89	144	233

The 1s make the later numerators and denominators obey the Fibonacci recurrence relation, so the only question is what the initial conditions are. And, as it turns out, q₀ and q₁ happen to be consecutive Fibonacci numbers, so the rest of the denominators are also Fibonacci numbers. The numbers also happen to line up with u.

Now, we know how to go forward from expansion to group element to matrix. Can we also go backward from matrix to group element to expansion? Of course the first step is trivial. The second step … well, there's probably some clever way to do it, but the only way I've found so far is more like brute force. The key is to remember that we're talking about a group element that adds a prefix. So, we can just pick a nice integer that's valid at the end of a continued fraction expansion, apply the group element to it, and then run the first algorithm to find out what prefix the group element added. Let's see how the whole thing works for E(194). First we turn the matrix into the group element (467z + 274)/(196z + 115), then we apply the group element to, say, z = 3 to get 1675/703, then we run the first algorithm to get the result [2,2,1,1,1,1,2,2,1,1,3].

We could get the same result by adding the prefix “2,2,1,1” and then adding the prefix “2,2,1,1,1,1”. On the one hand, so what? Those are the prefixes associated with 5 and 13, and (194,13,5) is a solution of the Markov equation, so of course the following relationship holds.

prefix(194) = prefix(13) & prefix(5)

On the other hand, now we know about group elements and matrices. If we apply the group element that adds prefix(5) and then apply the group element that adds prefix(13), that's function composition, or, better, matrix multiplication.

E(194) = E(13)E(5)

The same thing is true in general.

E(u) = E(v)E(w)

Bang! A new way to express the pattern! It's nice because matrices are easier to work with than strings of 1s and 2s, but it does also make it hard to see the connection to the Markov constant.

That concludes the secondary train of thought. Does that mean it's time for random thoughts? Not quite. I do have some, but they aren't ripe yet. So, maybe instead it's time to look back and be amazed that thinking about approximation quality leads to such strange and beautiful mathematics.