THE HILL CIPHER (CONTINUED): COMPUTING THE INVERSE OF A MATRIX

MATH 195

Recall that given a commutative ring R, we consider the k × k square matrices with entries in R, denoted M(k, R). We have a map det : M(k, R) → R called the determinant. We also have the following rule of thumb: All usual rules for computing determinants avoiding divisions are valid over any commutative ring R.

Now we would like to compute inverses of a matrix. Suppose A is a (k × k)- matrix over a commutative ring R, say A = (a_{ij})_{1≤i,j≤k}, a_{ij} ∈ R. Define A^{∗} = (a_{ij}^{∗})_{1≤i,j≤k} ∈ M(k, R) by

a_{ij}^{∗} = (−1)^{i+j} det(A_{ji}) ∈ R

where A_{ji} is the (k − 1) × (k − 1) matrix obtained from A by deleting the jth row and the ith column.

(It is important to transpose i and j: the text is wrong on this point.)

For example, if

A = (\begin{matrix}a & b \\ c & d \end{matrix}) ,

then a_{11}^{∗} = a^{∗} = (−1)^{2}d = d, a_{22}^{∗} = d^{∗} = a, and a_{12}^{∗} = b^{∗} = (−1)^{1+2}b = −b, a_{21}^{∗} = c^{∗} = −c, so

A^{∗} = (\begin{matrix}d & −b \\ −c & a \end{matrix}) .

Note that given a ring R, the set R^{∗} = {a ∈ R : ∃b ∈ R, ab = 1} of units of R is much different than the adjoint matrix A^{∗} of a matrix A ∈ M(k, R)!

Then we have the following amazing fact:

AA^{∗} = A^{∗}A = det(A)I = (\begin{matrix}det(A) & 0 & … & 0 \\ 0 & det(A) & … & 0 \\ ⋮ & ⋮ & ... & ⋮ \\ 0 & 0 & … & det(A) \end{matrix}) .

For example, for the 2 × 2 matrix above, we have

(\begin{matrix}a & b \\ c & d \end{matrix}) (\begin{matrix}d & −b \\ −c & a \end{matrix}) = (\begin{matrix}ad − bc & 0 \\ 0 & ad − bc \end{matrix}) = (det A) (\begin{matrix}1 & 0 \\ 0 & 1 \end{matrix}) .

Fact. A is invertible (i.e. belongs to GL(k, R)) if and only if det(A) ∈ R^{∗}.

(Note that the text makes an error: the determinant needs to be not only nonzero but invertible!)

This is some of the material covered February 12, in Math 195: Cryptography, taught by Hendrik Lenstra, prepared by John Voight jvoight@math.berkeley.edu.

Proof. If A is invertible, there exists a B such that AB = I, hence

det(AB) = det(A) det(B) = det(I) = 1

so det(A) ∈ R^{∗} (the inverse is det(B)). In the other direction, suppose det A ∈ R^{∗}, then A((det A)^{−1}A^{∗}) = I, so A^{−1} = (det A)^{−1}A^{∗}. □

Example. Let R = ℤ/26ℤ, k = 3. Let

K = (\begin{matrix}−9 & −9 & 5 \\ −5 & −8 & −5 \\ 2 & 2 & −7 \end{matrix}) .

Then

K^{∗} = (\begin{matrix}(−8)(−7) − (−5)2 \\ & −((−9)(−5) − 5(−5)) \end{matrix}) ≡ (\begin{matrix}−12 & −1 & 7 \\ 7 & 1 & 8 \\ 6 & 0 & 1 \end{matrix}) (mod 26)

and indeed

(\begin{matrix}−9 & −9 & 5 \\ −5 & −8 & −5 \\ 2 & 2 & −7 \end{matrix}) (\begin{matrix}−12 & −1 & 7 \\ 7 & 1 & 8 \\ 6 & 0 & 1 \end{matrix}) = (\begin{matrix}3 & 0 & 0 \\ 0 & 3 & 0 \\ 0 & 0 & 3 \end{matrix}) .

Here is the “usual algorithm” for finding the inverse of a matrix over a field F. Say for example F = ℤ/7ℤ, and

A = (\begin{matrix}3 & 3 & −2 \\ 0 & −3 & 0 \\ 2 & 2 & −2 \end{matrix}) .

We write down

(\begin{matrix}3 & 3 & −2 & 1 & 0 & 0 \\ 0 & −3 & 0 & 0 & 1 & 0 \\ 2 & 2 & −2 & 0 & 0 & 1 \end{matrix}) .

Now we multiply the first row by the inverse 3^{−1} = −2 (mod 7) to get:

(\begin{matrix}1 & 1 & −3 & −2 & 0 & 0 \\ 0 & −3 & 0 & 0 & 1 & 0 \\ 2 & 2 & −2 & 0 & 0 & 1 \end{matrix}) .

Now multiply the first row by 2 and subtract it from the last row:

(\begin{matrix}1 & 1 & −3 & −2 & 0 & 0 \\ 0 & −3 & 0 & 0 & 1 & 0 \\ 0 & 0 & −3 & −3 & 0 & 1 \end{matrix}) .

Now invert (−3)^{−1} = 2 and scale the middle and bottom rows:

(\begin{matrix}1 & 1 & −3 & −2 & 0 & 0 \\ 0 & 1 & 0 & 0 & 2 & 0 \\ 0 & 0 & 1 & 1 & 0 & 2 \end{matrix}) .

Now subtract the second row from the first and add three times the last to the first:

(\begin{matrix}1 & 0 & 0 & 1 & −2 & −1 \\ 0 & 1 & 0 & 0 & 2 & 0 \\ 0 & 0 & 1 & 1 & 0 & 2 \end{matrix}) .

Recall inside the matrices M(k, R), we have the invertible matrices GL(k, R) called the general linear group. Inside GL(k, R) we have SL(k, R) = {A ∈ M(k, R) : det A = 1}, called the special linear group. Inside SL(k, R) we have the elementary subgroup E(k, R), those matrices that can be obtained as the product of elementary matrices. If R is a field or ℤ or ℤ/nℤ, E(k, R) = SL(k, R). But it is not true for every commutative ring R: this is a fascinating field of mathematics known as K-theory.