Modular Inverse of a Matrix

1. Introduction

In order to decrypt messages that have been encrypted using the matrix multiplication based hill cipher cryptosystem, you need to be able to find the multiplicative inverse of a matrix modulo \(n\). As you know from linear algebra, a matrix \(A\) is only invertible, iff the determinant \(\det A\) of \(A\) is not \(0\). On top of that, the elements \(a_{ij}\) inside the matrix potentially need to have multiplicative inverse modulo \(n\) which means the greatest common divisor \(gcd(a,n)\) needs to be \(1\). In this case, we say that \(a\) and \(n\) are coprime. This is definetely assured if \(n\) is a prime number, so for the following algorithm we assume that the amount of elements in the alphabet is prime.
Why does the matrix used as the key in the hill cipher cryptosystem even needs to have an inverse? Well, if it doesn't, you can encrypt messages but even with the knowledge of how to derive the decryption function out of the encryption function, it wouldn't be possible to decrypt the message, since the matrix is not invertible. In terms of security it would be beneficial, but it's not suitable for the practical usage.

2. The algorithm

Let's do an example. Given the following \((2\times 2)-\)matrix $$ \left( \begin{matrix} 1 & 2\\ -1 & 0 \end{matrix} \right) $$ Let's assume we operate in \(\mathbb{Z}/29\mathbb{Z}\) (mod \(29\)). First of all, we simply invert the matrix as known from linear algebra without any modular arithmetic. For that, we write the matrix and the \(2\times 2\) identity matrix side by side and convert the matrix on the left-hand side into the identity matrix. Every single operation we apply to the left-hand side is similiary applied to the right-hand side.
To start, let's add the first row to the second row:
After that, subtract the second row from the first row:
Finally, you could divide the second row by \(2\):
As a result, you get the matrix $$ \left( \begin{matrix} 0 & -1\\ 1/2 & 1/2 \end{matrix} \right) $$ Now you apply the modulo operation for each element in the matrix. But what happens with the two \(\frac{1}{2}\)s in the second row?

3. Fractions mod n

Remember, that you can rewrite $$ \frac{1}{a} $$ to $$ a^{-1} $$ for \(a\neq 0\). Similiary you can rewrite $$ \frac{b}{a} $$ to $$ b\cdot a^{-1} $$ \(a^{-1}\) can be interpreted as the multiplicative inverse of the integer \(a\) mod \(n\). If we rewrite the elements in our inverse matrix with that knowledge, we get $$ \left( \begin{matrix} 0 & -1\\ 2^{-1} & 2^{-1} \end{matrix} \right) $$ What you need to do now is to find the multiplicative inverse of \(2\) modulo \(29\). How do you do that? Well, by using the extended euclidean algorithm.
First you need to apply the euclidean algorithm to find the greatest common divisor of \(29\) and \(2\): $$ \begin{array}{l} 29 = 14\cdot 2+1\\ 2 = 2\cdot 1 + 0 \end{array} $$ The greatest common divisor of \(29\) and \(2\) is \(1\). These two elements are coprime, so the inverse of \(2\) modulo \(29\) exists (but we already knew that, since \(29\) is a prime number). The extended euclidean algorithm gives you a linear combination $$ gcd(29,2)=s\cdot 29+t\cdot 2 $$ of the two numbers \(29\) and \(2\). The factor \(t\) will be the multiplicative inverse of \(2\) modulo \(29\). Simply subtract \(14\cdot 2\) from \(29\) and you'll get: $$ gcd(29,1)=1=\underbrace{1}_{s}\cdot 29\underbrace{-14}_{t}\cdot 2 $$ So the multiplicative inverse of \(2\) modulo \(29\) is \(-14\). You can check this result by simply calculating $$ 2\cdot (-14)\mod 29 $$ which gives you \(1\), so this is the correct answer!
Now you simply replace \(2^{-1}\) by the calculated multiplicative inverse of \(2\) modulo \(29\) and you're done: $$ \left( \begin{matrix} 0 & -1\\ -14 & -14 \end{matrix} \right) $$