#### Factorization of a 2x2 non-singular non-negative matrix in the style of Perron, Band 1

Input: a matrix A = , p, q, r, s ≥ 0 with p ≥ q or r ≥ s and Δ= ps – qr ≠ 0.

We express A uniquely as BC, where
- B=[b
_{ij}] is unimodular and b_{11} ≥ b_{12} and b_{21} ≥ b_{22},
- C=[c
_{ij}] is upper triangular with (a) c_{11} > 0, c_{22} > 0 and
(b) -c_{22} ≤ c_{12} ≤ c_{11}.

This factorization was Lemma 3 in K.R. Matthews and R.F.C. Walters, *Some properties of the continued fraction expansion of (m/n)e *^{1/q}, Proc. Camb. Phil. Soc. 67 (1970) 67-74 and is a version of Satz 4.1. of *Die Lehre von den Kettenbrüchen*, Band 1, S. 111.

(Lemma 3 of that paper stated that -c_{22} < c_{12} ≤ c_{11}, which is true if q > 0 or s > 0.)
Here c_{11} = gcd(p, r), b_{11} = p/gcd(p, r), b_{21} = r/gcd(p, r), c_{11}c_{22}=|Δ|.

If b_{21} > 1 and p/r = [a_{0}, ..., a_{n}] = A_{n}/B_{n}, a_{n} > 1, then b_{12}/b_{22} = A_{n - 1}/B_{n - 1} or (A_{n} – A_{n - 1})/(B_{n} – B_{n - 1}).

If b_{21} = 1, then b_{22} = 0 and b_{12} = 1 if Δ < 0, whereas b_{22} = 1 and b_{12} = b_{11} – 1 if Δ > 0.

Finally, c_{12} is determined by q = b_{11}c_{12} + b_{12}c_{22}.

*Last modified 22nd June 2010*

Return to main page