Factorising a unimodular matrix

This program expresses a unimodular matrix A = [p,q;r,s] ≠ I<sub>2</sub> or U0 = [0,1;1,0], with non-negative coefficients, as a product of the type P, U0P, PU0, or U0PU0, where P is a product of matrices of the form Uc = [c,1;1,0], c > 0.
The representation is unique. (See Kjell Kolden, Continued fractions and linear substitutions, Arch. Math. Naturvid. 50 (1949), 141-196.)

While r > 0 and s > 0, we repeatedly use the identity

where d = min([p/r],[q/s]).

The process eventually stops, either because r = 0, in which case we reach UqU0,
or because s=0, in which case we reach Up.

This is a BCMATH translation of a BC program.

Enter p (≥ 0):
Enter q (≥ 0):
Enter r (≥ 0):
Enter s (≥ 0):

Last modified 24th June 2010
Return to main page