Continued Fractions and Matrices

Matrices are very useful when analyzing continued fractions. In previous blogs, I wrote about the continued fractions approximation function and the continued fractions basic properties. Today, I will show how matrices can be used to reason with continued fractions.

Today's blog is based on H. M. Stark's An Introduction to Number Theory. If you are not familiar with Continued Fractions, start here. If you are not familiar with the Continued Fraction approximation algorithm, start here.

A continued fraction breaks a real number into a series of integers such as a₀, a₁, ... a_n. It makes sense that we can use matrices to reason about them.

In today's blog, I will focus on the simplest properties of matrices. For example, I will only deal with two types of matrices:

1 x 2 matrices such as (5,6)

2 x 2 matrices

For those who would need a review of simple matrices, matrix products, determinants, inverses, or some basic lemmas, start here.

To represent, continued fractions as matrices, we define the following:

(a) A_n



NOTE: a_n is taken directly from the continued fraction. See here for details on how this is generated.

(b) M_n



NOTE: p_n, q_n are generated based on the continued fraction approximation function. See here for details on how these two values are generated.

(c) γ_n

γ_n = q_n-2 + α_nq_n-1

NOTE: α_n is generated based on the continued fraction for α (see here). q_n is generated based on the continued fraction approximation algorithm (see here).

Using these definitions, I will go through some lemmas that will be useful in solving Pell's equation.

Lemma 1: M_n+1 = A_nM_n

(1) A_nM_n =



NOTE: By the definitions above.



NOTE: By carrying out the matrix product [see here for review if needed]



NOTE: By applying the definitions of p_n and q_n [see here for details]

= M_n+1 [By the definition above]

QED

Lemma 2: γ_n(1,α) = (1,α_n)M_n

(1) (1,α_n)M_n =



= (q_n-2 + α_nq_n-1 , p_n-2 + α_np_n-1) [See here to review matrix products]

= (q_n-2 + α_nq_n-1)(1,α) [Since α * (q_n-2 + α_nq_n-1) = p_n-2 + α_np_n-1; see here]

= γ_n(1,α)

QED

Lemma 3: α is irrational → γ_n ≠ 0

(1) Since α is irrational, α_n is irrational. (See here for proof; only rational numbers give way to rational α_n)

(2) Assume γ_n = 0.

(3) Then, q_n-2 + α_nq_n-1 = 0.

(4) Then q_n-2=0 and q_n-1 = 0. [See here for proof]

(5) q_-1 = q₁ - q₀a₁ = a₁ - a₁(1) = 0
q_-2 = q₀ - q_-1a₀ = 1 - 0*a₀ = 1

NOTE: See here for review of q_n

(6) We also know for all values n ≥ 1, that q_n ≥ 1 (see here).

(7) So (#4) is impossible and we reject our assumption.

QED

Lemma 4: det(M_n) = (-1)ⁿ

(1) det(M_n) = p_n-1q_n-2 - p_n-2q_n-1 (See here for a review of determinants)

(2) So, det(M_n) = (-1)ⁿ by a previous result. (See here)

QED

Lemma 5: M_n+1 = A_nA_n-1...A₁A₀

(1) M_n+1 = A_nM_n (From Lemma 1 above)

(2) Applying Lemma 1 again gives us:

M_n+1 = A_nA_n-1M_n-1

(3) Since n is an integer greater than 0, we can keep on doing this until eventually we get:

M_n+1 = A_nA_n-1...A₁A₀

NOTE:

(a) p_-1 = p₁ - p₀a₁ = a₀a₁ + 1 - a₀a₁ = 1.

(b) q_-1 = 0 (see Lemma 3 above)

(c)


QED

Lemma 6: M_n^-1 is a 2 x 2 matrix of integers.

M_n^-1 =



NOTE: det(M_n) = (-1)ⁿ from Lemma 4 above.

QED