Finding the key matrix of a 2x2 Hill Cipher I'm trying to find the Hill Cipher key from the following given info:
(1,3)^T is encrypted as (-9, -2)^T, and (7, 2)^T is encrypted as (-2, 9)^T.
However I don't seem to end up with the correct answer as the encryption is invalid when I try to use the key. Below is my solution, did I make a mistake somewhere?
So
$$\begin{bmatrix} a & b\\ c & d\end{bmatrix}\begin{bmatrix}1\\3 \end{bmatrix}= \begin{bmatrix}-9\\-2 \end{bmatrix}$$
and
$$\begin{bmatrix} a & b\\ c & d\end{bmatrix}\begin{bmatrix}7\\2 \end{bmatrix}= \begin{bmatrix}-2\\9 \end{bmatrix}$$
or in one matrix notation:
$$\begin{bmatrix} a & b\\ c & d\end{bmatrix} \begin{bmatrix} 1 & 7\\ 3 & 2\end{bmatrix} = \begin{bmatrix} -9 & -2\\ -2 & 9\end{bmatrix}$$
which allows us to find the encryption matrix by
$$\begin{bmatrix} a & b\\ c & d\end{bmatrix} = \begin{bmatrix} -9 & -2\\ -2 & 9\end{bmatrix} {\begin{bmatrix} 1 & 7\\ 3 & 2\end{bmatrix}}^{-1}$$
The determinant of $\begin{bmatrix} 1 & 7\\ 3 & 2\end{bmatrix}$ is $1\cdot 2 - 3\cdot 7 = 7 \pmod{26}$, so the inverse exists and equals
$$\begin{bmatrix} 2 & -7\\ -3 & 1\end{bmatrix}$$
This allows us to compute the encryption matrix
$$\begin{bmatrix} a & b\\ c & d\end{bmatrix} = \begin{bmatrix} -9 & -2\\ -2 & 9\end{bmatrix} {\begin{bmatrix} 2 & -7\\ -3 & 1\end{bmatrix}}$$
$$
\begin{bmatrix} 
-9*2+-2*-3=14 & -9*-7+-2*1=9\\ 
-2*2+9*-3=21 & -2*-7+9*1=23\end{bmatrix}
=
\begin{bmatrix} 14 & 9\\ 21 & 23\end{bmatrix}
$$
Then $$\begin{bmatrix} 14 & 9\\ 21 & 23\end{bmatrix}\begin{bmatrix}1\\3 \end{bmatrix}= \begin{bmatrix}15\\12 \end{bmatrix}$$ which does not match the given info as it should have been equal to
$$\begin{bmatrix}-9\\-2 \end{bmatrix}$$
 A: I fully agree with
$$\begin{bmatrix} a & b\\ c & d\end{bmatrix} = \begin{bmatrix} -9 & -2\\ -2 & 9\end{bmatrix} {\begin{bmatrix} 1 & 7\\ 3 & 2\end{bmatrix}}^{-1}$$
and indeed the determinant of the right hand side matrix equals $$2- 21 \pmod{26} = -19 = 7 \pmod{26}$$ which is relatively prime to $26$ so has an inverse.
The general formula for an 2-by-2 inverse is:
$$A^{-1} = \begin{bmatrix}a & b\\c & d\end{bmatrix}^{-1} = \frac{1}{\det A}
\begin{bmatrix}d &-b\\-c & a\end{bmatrix}$$ so your inverse is wrong and all entries need to be multiplies by the invesre (modulo $26$) of the determinant $7$.
This inverse can be found by applying the extended Euclidean algorithm to $7$ and $26$ and we get the Bézout identity
$$1 = -11 \cdot 7 + 3\cdot 26$$
from which it follows that $$-11 \cdot 7 = 1 \pmod{26}$$
so that the inverse of $7$ is $-11 \equiv 15$.
So we multiply all elements of $$\begin{bmatrix} 2 & -7\\ -3 & 1\end{bmatrix}$$ by $15$ to get the inverse matrix we're looking for (of course all modulo $26$)
and we get $$\begin{bmatrix} 4 & 18\\ 7 & 15\end{bmatrix}$$
and now you can do the multiplication from the first equation modulo 26:
$$\begin{bmatrix} -9 & -2\\ -2 & 9\end{bmatrix} \begin{bmatrix} 4 & 18\\ 7 & 15\end{bmatrix}$$ to find the encryption matrix $E$. I leave that final bit to you.
takeaway: division is multiplying by the inverse. The inverse is found by the extended Euclidean algorithm. For $n=26$ you could also find the table of inverses once (program or trial and error) and use them all the time.
