Suppose we have an $N$-letter alphabet and want to send digraphs as our message units. As we have seen here, we can let each digraph correspond to an integer considered modulo $N^2$, i.e. to an element of $\mathbb{Z}/N^2\mathbb{Z}$. An alternate possibility is to let each digraph correspond to a vector $\begin{pmatrix}
x\\
y
\end{pmatrix}$ with $x,y\in\mathbb{Z}/N\mathbb{Z}$. For example, if we are using the 26-letter alphabet A- Z with numerical equivalents 0-25, respectively, then the digraph NO corresponds to the vector $\begin{pmatrix}
13\\
14
\end{pmatrix}$. We consider the $xy$-plane as the finite lattice $\mathbb{Z}/N\mathbb{Z}\times\mathbb{Z}/N\mathbb{Z}=(\mathbb{Z}/N\mathbb{Z})^2$.

Let $M_2(\mathbb{Z}/N\mathbb{Z})$ denote the set of all $2\times 2$ matrices with entries in $\mathbb{Z}/N\mathbb{Z}$. Let $A=\begin{pmatrix}
a & b\\
c & d \end{pmatrix}\in M_2(\mathbb{Z}/N\mathbb{Z})$ and suppose that $D=\det(A)=ad-bc\in(\mathbb{Z}/N\mathbb{Z})^*$. Let $D^{-1}$ denote the multiplicative inverse of $D$ in $\mathbb{Z}/N\mathbb{Z}$. Then \begin{align*}
\begin{pmatrix}
D^{-1}d & -D^{-1}b\\
-D^{-1}c & D^{-1}a
\end{pmatrix}\begin{pmatrix}
a & b\\
c & d
\end{pmatrix}&=\begin{pmatrix}
D^{-1}(da-bc) & 0\\
0 & D^{-1}(-cb+ad)
\end{pmatrix}\\
&=\begin{pmatrix}
1 & 0\\
0 & 1
\end{pmatrix}
\end{align*}
Similarly,
$$\begin{pmatrix}
a & b\\
c & d
\end{pmatrix}\begin{pmatrix}
D^{-1}d & -D^{-1}b\\
-D^{-1}c & D^{-1}a
\end{pmatrix}=\begin{pmatrix}
1 & 0\\
0 & 1
\end{pmatrix}$$
Thus, we see that
\begin{equation}
\label{eq:invmat}
A^{-1}=\begin{pmatrix}
D^{-1}d & -D^{-1}b\\
-D^{-1}c & D^{-1}a
\end{pmatrix}
\end{equation}

Example. Find the inverse of $A=\begin{pmatrix}
2 & 3\\
7 & 8
\end{pmatrix}\in M_2(\mathbb{Z}/26\mathbb{Z})$.

Solution. $D=16-21=-5\equiv 21\mod 26$. Since $(21,26)=1$, there exists $21^{-1}\in\mathbb{Z}/26\mathbb{Z}$. Remember that finding $21^{-1}\in\mathbb{Z}/26\mathbb{Z}$ is equivalent to solving the diophantine equation $21x+26y=1$.
\begin{align*} 26&=21\cdot 1+5\\ 21&=5\cdot 4+1 \end{align*}
and
\begin{align*} 1&=21-5\cdot 4\\ &=21-(26-21)4\\ &=5\cdot 21+26(-4) \end{align*}
Thus, we find $21^{-1}\equiv 5\mod 26$.
\begin{align*} A^{-1}&=\begin{pmatrix} 5\cdot 8 & -5\cdot 3\\ -5\cdot 7 & 5\cdot 2 \end{pmatrix}\\ &=\begin{pmatrix} 40 & -15\\ -35 & 10 \end{pmatrix}\\ &\equiv\begin{pmatrix} 14 & 11\\ 17 & 10 \end{pmatrix}\mod 26 \end{align*}

Let $A=\begin{pmatrix}
a & b\\
c & d
\end{pmatrix}\in M_2(\mathbb{Z}/N\mathbb{Z})$. Then
$$\begin{pmatrix}
x’\\
y’
\end{pmatrix}=A\begin{pmatrix}
x\\
y
\end{pmatrix}=\begin{pmatrix}
a & b\\
c & d
\end{pmatrix}\begin{pmatrix}
x\\
y
\end{pmatrix}=\begin{pmatrix}
ax+by\\
cx+dy
\end{pmatrix}$$
This gives a linear map or a linear transformation from vectors to vectors.

We introduce the following theorem without proof.

Theorem. Let $A=\begin{pmatrix}
a & b\\
c & d
\end{pmatrix}\in M_2(\mathbb{Z}/N\mathbb{Z})$ and set $D=ad-bc$ as before. Then the following are equivalent:

1. $(D,N)=1$.
2. $A$ has an inverse matrix.
3. if $x$ and $y$ are not both $0$ in $\mathbb{Z}/N\mathbb{Z}$, then $A\begin{pmatrix}x\\y \end{pmatrix}\ne\begin{pmatrix}0\\0\end{pmatrix}$.
4. $A$ gives a one-to-one correspondence of $(\mathbb{Z}/N\mathbb{Z})^2$ with itself.

Example. Solve the following systems of simultaneous congruences.

1. \begin{align*}2x+3y&\equiv 1\mod 26\\ 7x+8y&\equiv 2\mod 26 \end{align*}
2. \begin{align*} x+3y&\equiv 1\mod 26\\ 7x+9y&\equiv 2\mod 26 \end{align*}
3. \begin{align*} x+3y&\equiv 1\mod 26\\ 7x+9y&\equiv 1\mod 26 \end{align*}

Solution.

1. The system of simultaneous congruences can be written as the matrix congruence $AX\equiv B\mod 26$ or as the matrix equation $AX=B$ in $\mathbb{Z}/26\mathbb{Z}$, where $$A=\begin{pmatrix}2 & 3\\7 & 8\end{pmatrix},\ X=\begin{pmatrix}x\\y\end{pmatrix},\ B=\begin{pmatrix}1\\2\end{pmatrix}$$ $D=16-21=-5$ and $(-5,26)=1$, so by above Theorem, we see that $A^{-1}$ exists. In fact, we have already found $A^{-1}$ in the previous example. The solution $X$ is given by \begin{align*} X&\equiv A^{-1}B\mod 26\\&\equiv\begin{pmatrix} 14 & 11\\ 17 & 10 \end{pmatrix}\begin{pmatrix} 1\\ 2 \end{pmatrix}\mod 26\\ &\equiv\begin{pmatrix} 10\\ 11 \end{pmatrix}\mod 26 \end{align*}
2. The matrix in parts 2 and 3 does not have an inverse matrix in $\mathbb{Z}/26\mathbb{Z}$ because $D=9-21=-12$ and $(-12,26)=2\ne 1$. However, it does have an inverse matrix in $\mathbb{Z}/13\mathbb{Z}$ and the solution is given by \begin{align*} \begin{pmatrix} x\\ y \end{pmatrix}&\equiv\begin{pmatrix} 9 & 10\\ 6 & 1 \end{pmatrix}\begin{pmatrix} 1\\ 2 \end{pmatrix}\mod 13\\ &\equiv\begin{pmatrix} 3\\ 8 \end{pmatrix}\mod 13 \end{align*} We now examine the possibilities of having solutions in $\mathbb{Z}/26\mathbb{Z}$. Since $x\equiv 3\mod 13$ and $y\equiv 8\mod 13$, $x$ and $y$ can be written as $x=3+13k_1$ and $y=8+13k_2$ for some $k_1,k_2\in\mathbb{Z}$. \begin{align*} x+3y&\equiv 1+13(k_1+k_2)\mod 26\\ &\equiv 1\mod 26 \end{align*} if and only if $k_1+k_2$ is even. Suppose that $k_1+k_2$ is even, so that $x+3y\equiv 1\mod 26$. \begin{align*} 7x+9y&\equiv 15+13(k_1+k_2)\mod 26\\ &\equiv 15\mod 26\\ &\not\equiv 2\mod 26 \end{align*} since $k_1+k_2$ is even. Hence, there are no solutions for part 2.
3. Similarly to part 2, the solution in $\mathbb{Z}/13\mathbb{Z}$ is given by \begin{align*} \begin{pmatrix} x\\ y \end{pmatrix}&\equiv\begin{pmatrix} 9 & 10\\ 6 & 1 \end{pmatrix}\begin{pmatrix} 1\\ 1 \end{pmatrix}\mod 13\\ &\equiv\begin{pmatrix} 6\\ 7 \end{pmatrix}\mod 13 \end{align*} We test the possibilities of solutions in $\mathbb{Z}/26\mathbb{Z}$. Since $x\equiv 6\mod 13$ and $y\equiv 7\mod 13$, $x$ and $y$ can be written as $x=6+13k_1$ and $y=7+13k_2$ for some $k_1,k_2\in\mathbb{Z}$. \begin{align*} x+3y&\equiv 1+13(k_1+k_2)\mod 26\\ &\equiv 1\mod 26 \end{align*} if and only if $k_1+k_2$ is even. Now we assume that $k_1+k_2$ is even, so that we have $x+3y\equiv 1\mod 26$. \begin{align*} 7x+9y&\equiv 1+13(k_1+k_2)\mod 26\\ &\equiv 1\mod 26 \end{align*} since $k_1+k_2$ is even. Hence, there are solutions for part 3. Let $0\leq x,y\leq 25$. Then $k_1, k_2=0,1$. Since $k_1+k_2$ is even, we have either $k_1=k_2=0$ or $k_1=k_2=1$. Therefore, the solutions are \begin{align*} \begin{pmatrix} x\\ y \end{pmatrix}&\equiv\begin{pmatrix} 6\\ 7 \end{pmatrix}\mod 26\\ &\mbox{or}\\ \begin{pmatrix} x\\ y \end{pmatrix}&\equiv\begin{pmatrix} 19\\ 20 \end{pmatrix}\mod 26 \end{align*}

Let $A=\begin{pmatrix}
a & b\\
c & d
\end{pmatrix}
\in M_2(\mathbb{Z}/N\mathbb{Z})$ with $(D,N)=1$ where $D=ad-bc$ be an enciphering matrix. Then it defines the enciphering transformation $C=AP$ where $P=\begin{pmatrix} x\\ y
\end{pmatrix}$ and $C=\begin{pmatrix}
x’\\
y’
\end{pmatrix}$ are plaintext message unit and ciphertext, respectively. That is,
$$\begin{pmatrix}
x’\\
y’
\end{pmatrix}=\begin{pmatrix}
a & b\\
c & d
\end{pmatrix}\begin{pmatrix} x\\ y
\end{pmatrix}$$
The deciphering transformation is then given by $P=A^{-1}C$, i.e.
$$\begin{pmatrix} x\\ y
\end{pmatrix}=\begin{pmatrix}
D^{-1}d & -D^{-1}b\\
-D^{-1}c & D^{-1}a
\end{pmatrix}\begin{pmatrix} x’\\ y’
\end{pmatrix}$$

Example. Wokring in the 26-letter alphabet, use the matrix $A=\begin{pmatrix} 2 & 3\\ 7 & 8 \end{pmatrix}\in M_2(\mathbb{Z}/26\mathbb{Z})$ to encipher the message unit “NO”. $$AP=\begin{pmatrix} 2 & 3\\ 7 & 8 \end{pmatrix}\begin{pmatrix} 13\\ 14 \end{pmatrix}=\begin{pmatrix} 68\\ 103 \end{pmatrix}\equiv\begin{pmatrix} 16\\ 21 \end{pmatrix}\mod 26 $$ Thus the ciphertext $C=AP$ is “QV”.

Remark. To encipher a plaintext sequence of $k$ digraphs $P=P_1P_1P_3\cdots P_k$, we can write the $k$ vectors as columns of a $2\times k$ matrix and then multiply $A$ by the $2\times k$ matrix $P$ to get a $2\times k$ matrix $C=AP$ of coded digraph vectors.

Example. Encipher “NOANSWER”.

Solution. The numerical equivalence of “NOANSWER” is $$\begin{pmatrix} 13\\ 14 \end{pmatrix}\begin{pmatrix} 0\\ 13 \end{pmatrix}\begin{pmatrix} 18\\ 22 \end{pmatrix}\begin{pmatrix} 4\\ 17 \end{pmatrix}$$ \begin{align*} C&=AP\\ &=\begin{pmatrix} 2 & 3\\ 7 & 8 \end{pmatrix}\begin{pmatrix} 13 & 0 & 18 & 4\\ 14 & 13 & 22 & 17 \end{pmatrix}\\ &=\begin{pmatrix} 68 & 39 & 102 & 59\\ 203 & 104 & 302 & 164 \end{pmatrix}\\ &\equiv\begin{pmatrix} 16 & 13 & 24 & 7\\ 21 & 0 & 16 & 8 \end{pmatrix}\mod 26 \end{align*} i.e. the coded message is “QVNAYQHI”.

Example. In the situation of previous example, decipher the ciphertext “FWMDIQ”.

Solution.
\begin{align*} P&=A^{-1}C\\ &=\begin{pmatrix} 14 & 11\\ 17 & 10 \end{pmatrix}\begin{pmatrix} 5 & 12 & 8\\ 22 & 3 & 16 \end{pmatrix}\\ &=\begin{pmatrix} 312 & 201 & 288\\ 305 & 234 & 296 \end{pmatrix}\\ &\equiv\begin{pmatrix} 0 & 19 & 2\\ 19 & 0 & 10 \end{pmatrix}\mod 26 \end{align*}
Hence, the deciphered plaintext is “ATTACK”.