Modular Inverse of a Matrix
The inverse of a matrix mod \(n\) of a matrix \(A\) is a matrix \(A^{-1}\) such that, when multiplied by \(A\), the result is congruent to the identity matrix \(I\) modulo \(n\), meaning $$ AA^{-1} \equiv I \mod n $$
Every element of the product matrix is congruent to the corresponding element in the identity matrix, modulo n.
How to Calculate the Inverse Matrix Mod n
Let's consider a 2x2 square matrix modulo n
$$ A = \begin{pmatrix} a & b \\ c & d \end{pmatrix} $$
To calculate the inverse matrix A-1 modulo n of a matrix A with integer elements, compute the determinant modulo n.
$$ det(A) $$
It's necessary for the determinant and n to be coprime, meaning their greatest common divisor must be 1; otherwise, matrix A is not invertible modulo n.
If the determinant and n are coprime, the calculation can proceed.
$$ GCD(\ \det(A) \ , \ n \ ) = 1 $$
Find the multiplicative inverse of the determinant modulo n, denoted as det(A)−1 mod n
In other words, find a number det(A)−1 such that, when multiplied by det(A), it yields 1 mod n.
$$ \det(A) \cdot \det(A)^{-1} \equiv 1 \mod 9 $$
Now, the inverse matrix A-1 modulo n can be obtained using this formula:
$$ A^{-1} = det(A)^{-1} \cdot \begin{pmatrix} d & -b \\ -c & a \end{pmatrix} \ \mod n $$
Finally, adjust each element of the resulting inverse matrix to ensure it falls within the 0 to n−1 range.
A Practical Example
Consider a 2x2 square matrix with modulus n=9.
$$ B = \begin{pmatrix} 2 & 3 \\ 1 & 4 \end{pmatrix} $$
Calculate the determinant of matrix B modulo 9.
$$ \det(B) = 2 \cdot 4 - 3 \cdot 1 = 5 \ \mod 9 $$
Check that det(B)=5 and n=9 are coprime, meaning their greatest common divisor equals 1 modulo 9.
$$ GCD(5,9) = 1 \ \mod 9 $$
In this case, they are coprime, so matrix B is invertible and we can proceed.
Note. Otherwise, matrix B is not invertible. If det(B) and n are not coprime, matrix B does not have an inverse, and the calculation ends here.
The multiplicative inverse of 5 modulo 9 is 2, because
$$ 5 \cdot 2 \equiv 10 \equiv 1 \mod 9 $$
Apply the formula for the inverse of a 2x2 matrix with operations modulo 9
$$ B^{-1} \mod 9 = 2 \cdot \begin{pmatrix} 4 & -3 \\ -1 & 2 \end{pmatrix} \mod 9 $$
$$ B^{-1} \mod 9 = \begin{pmatrix} 2 \cdot 4 & 2 \cdot (-3) \\ 2 \cdot (-1) & 2 \cdot 2 \end{pmatrix} \mod 9 $$
$$ B^{-1} \mod 9 = \begin{pmatrix} 8 & -6 \\ -2 & 4 \end{pmatrix} \mod 9 $$
Adjust the values in the matrix to ensure they are within the 1 to 9 range.
For instance, here we have two congruences -6≡3 mod 9 and -2≡7 mod 9.
Therefore, the inverse modulo 9 of matrix B is:
$$ B^{-1} \mod 9 = \begin{pmatrix} 8 & 3 \\ 7 & 4 \end{pmatrix} \mod 9 $$
This example illustrates how to calculate the inverse modulo n of a 2x2 matrix when the determinant and n are coprime.
Verification. Multiply matrix A by its inverse matrix A-1 modulo 9.
$$ B \cdot B^{-1} \mod 9 = \begin{pmatrix} 2 & 3 \\ 1 & 4 \end{pmatrix} \cdot \begin{pmatrix} 8 & 3 \\ 7 & 4 \end{pmatrix} \mod 9$$
$$ B \cdot B^{-1} \mod 9 = \begin{pmatrix} 2 \cdot 8 + 3 \cdot 7 & 2 \cdot 3 + 3 \cdot 4 \\ 1 \cdot 8 + 4 \cdot 7 & 1 \cdot 3 + 4 \cdot 4 \end{pmatrix} \mod 9$$
$$ B \cdot B^{-1} \mod 9 = \begin{pmatrix} 37 & 18 \\ 36 & 19 \end{pmatrix} \mod 9$$
Finally, adjust the values with modulo 9.
For example, 37≡1 mod 9, 18≡0 mod 9, 36≡0 mod 9, 19≡1 mod 9
$$ B \cdot B^{-1} \mod 9 = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} \mod 9$$
The final result is the identity matrix modulo 9.
And so on.
