Background
The Hill cipher works by:
- defining a letter-to-number substitution table/list/pattern/etc.;
- encoding a cypher-word into a column vector $u$ whose components are determined by the said list;
- multiplying $u$ with a random “key” matrix $K$ of corresponding dimension, rendering another column vector $z$;
- converting $z$ into a cypher-word.
Decryption works by:
- considering the number of characters in the list to be $m$;
- multiplying $z$ by $K^{-1}$ to give another column vector $w$;
- attaining $u$ via the relationship $u\equiv w\pmod m$ where all components of $u$ are in the list; and
- obtaining the original word using the list.
There is a caveat: In addition to $K$ needing to be invertible, the determinant of the key $\det K$ must share no common factors with the modulus $m$.
Personal investigation
In order to understand why this condition is required, I created my own example in which I use the pattern
$$\begin{array}{ccccccccc} \text{a} & \text b & \text c & \text d & \text e & \text f & \text g & \cdots & \text z \\ 0 & 1 & 2 & 3 & 4 & 5 & 6 & \cdots & 25 \end{array}$$
and the key $$K = \pmatrix{2&1\\2&2}$$ to encrypt the word $$\text{ab}\mapsto \pmatrix{0\\1}=u$$ (like the muscle), in which I know $\det K=2$ shares a factor with the modulus $26$.
The cipher-word is attained by
$$z=Ku=\pmatrix{2&1\\2&2}\pmatrix{0\\1}=\pmatrix{1\\2}\mapsto\text{bc}$$
The original word is obtained by
$$K^{-1}z=\pmatrix{1&-1/2\\-1&1}\pmatrix{1\\2}=\pmatrix{0\\1}\mapsto\text{ab}$$
as originally planned. . . .
Question
At first I thought there was a possibility that my cipher working was due to the matrix components being small numbers, but after working out several additional examples, it seems that no matter what key I choose, it works flawlessly if the key matrix is invertible.
Is it even necessary that the key matrix not share factors with the modulus? If so, why?
Best Answer
The matrix $K^{-1}$ that you propose is only the inverse over the rational numbers, not in the ring $\mathbb{Z}_{26}$ that you are working over (the characters are $0$ to $25$). The determinant is not coprime with $n$ so has no inverse in the ring. This means that you don't always get the right result with your "pseudoinverse"
To see where things go wrong concretely in your example:
$an$ is encrypted to $na$ but applying your inverse you'd get $nn$ as the decrypt. In fact anyone receiving $na$ as a ciphertext cannot tell whether to decrypt it to $an$ or $nn$. Both plaintexts give that same ciphertext. Encryption is thus not 1-1 and hence cannot be invertible.
Other such cases (it goes wrong in half of the $26^2$ pairs):
$ao \rightarrow oc \rightarrow no$ (Last step is your pseudo inverse)
$es \rightarrow as \rightarrow rs$
$do \rightarrow ui \rightarrow qo$ etc. Write a program to generate all such pairs (I did).
You can see that the requirement is truly essential.