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
For example, the matrix
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
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