The Special Linear Group

The extended Euclidean algorithm has uses beyond computing GCDs. Here is an application to linear algebra.

The set of \(2 \times 2\) matrices with integer entries and determinant \(1\) is called the special linear group, denoted

\[\begin{split} \mathrm{SL}(2, \mathbb{Z}) = \left\{\left[\begin{array}{rr} a & b \\ c & d \end{array}\right] : a, b, c, d \in \mathbb{Z}~~\text{and}~~ad - bc = 1 \right\}. \end{split}\]

For example, the matrix

\[\begin{split} A = \left[\begin{array}{rr} 2 & 3 \\ 1 & 2 \end{array}\right] \end{split}\]

is in \(\mathrm{SL}(2, \mathbb{Z})\) because its entries are integers and \(\det(A) = 2 \cdot 2 - 3 \cdot 1 = 1\). Every matrix in \(\mathrm{SL}(2, \mathbb{Z})\) is the standard matrix for a linear transformation that preserves area and orientation.

The top row \(a, b\) of a matrix in \(\mathrm{SL}(2, \mathbb{Z})\) is always relatively prime, since any common divisor of \(a\) and \(b\) also divides \(ad - bc = 1\). The converse is also true: every relatively prime pair \(a, b\) is the top row of some matrix in \(\mathrm{SL}(2, \mathbb{Z})\). Indeed, if \(x\) and \(y\) are integers satisfying \(ax + by=1\), then setting \(d = x\) and \(c = -y\) guarantees that \(ad - bc = 1\).

Problem 4

Write a function named sl2mat() that accepts two relatively prime integers \(a\) and \(b\), that is, \(\operatorname{GCD}(a, b) = 1\). Return a NumPy array

\[\begin{split} A = \left[\begin{array}{rr} a & b \\ c & d \end{array}\right] \end{split}\]

such that \(c\) and \(d\) are integers and \(\det(A) = ad - bc = 1\).

Test Cases

print(sl2mat(1, 7))
print(sl2mat(17, -89))

A = sl2mat(5, 151)
print(np.linalg.det(A))  # Equal to 1, up to floating-point roundoff.
[[1 7]
 [0 1]]
[[ 17 -89]
 [ -4  21]]
1.0000000000000082