Background

The Hill cipher works by:

1. defining a letter-to-number substitution table/list/pattern/etc.;


2. encoding a cypher-word into a column vector $u$ whose components are determined by the said list;


3. multiplying $u$ with a random “key” matrix $K$ of corresponding dimension, rendering another column vector $z$;


4. converting $z$ into a cypher-word.

Decryption works by:

1. considering the number of characters in the list to be $m$;


2. multiplying $z$ by $K^{-1}$ to give another column vector $w$;


3. attaining $u$ via the relationship $uequiv wpmod m$ where all components of $u$ are in the list; and


4. 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}mapstotext{bc}$$

The original word is obtained by

$$K^{-1}z=pmatrix{1&-1/2\-1&1}pmatrix{1\2}=pmatrix{0\1}mapstotext{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?

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.