Why are there $736$ matrices $M\in \mathcal M_2(\mathbb{Z}_{26})$ for which it holds that $M=M^{-1}$?

I'm currently trying to introduce myself to cryptography.

I'm reading about the Hill Cipher currently in the book Applied Abstract Algebra. The Hill Cipher uses an invertible matrix $M$ for encryption and the inverse matrix $M^{-1}$ for decryption. The book recommends to use a matrix $M$ for which it holds that $M=M^{-1}$, since we then have the same key for encryption and decryption.

In the book, they use a $2 \times 2$ matrix $M$ over $\mathbb{Z}_{26}$ as example, and state that for there are 736 $2 \times 2$ matrices for which it hold that $M=M^{-1}$.

I'm trying to pick up on as much as possible when reading things, since I find it counter-productive for learning to skip something, when you don't get the theory behind it. Can someone enlighten to me, as to why it is that there are 736 possible $2 \times 2$ $M=M^{-1}$ matrices and how to find them?

Solution 1:

Indeed there turns out to be a more systematic answer. Computing the number $a_n$ of self-inverse matrices over $\mathbb Z_n$ for some $n$ leads to OEIS sequences A066907 and A066947. It turns out that $a_n$ is multiplicative and given by

$$ a_n=c_m\prod_i\left(2+p_i^{2k_i-1}(p_i+1)\right) $$

for $n=2^m\prod_ip_i^{k_i}$, where the $p_i$ are the odd prime factors of $n$ and

$$ c_m= \begin{cases} 1&m=0\;,\\ 4&m=1\;,\\ 28&m=2\;,\\ 9\cdot4^{m-1}+32&m\gt2\;. \end{cases} $$

In the present case $26=2^1\cdot13^1$, so $a_{26}=4(2+13\cdot14)=736$.

Unfortunately the links in the entry are all broken and the author's email address is obsolete, so the question remains how to derive this.

Solution 2:

There may be a more systematic way of doing this; here's a semi-systematic way.

Your condition is equivalent to $M^2=I$. For $\displaystyle M=\pmatrix{a&b\\c&d}$ that yields four equations:

$$ \begin{align} a^2+bc&\equiv1\;,\\ ab+bd&\equiv0\;,\\ ca+dc&\equiv0\;,\\ cb+d^2&\equiv1\;. \end{align} $$

The first and last of these have solutions for $a$ and $d$, respectively, if and only if $1-bc$ is a quadratic residue. If so, $a^2\equiv d^2$, and thus $a\equiv\pm d$.

The second and third equation are $(a+d)b\equiv0$ and $(a+d)c\equiv0$. These are fulfilled for $a\equiv-d$, so we have one solution for every pair $b,c$ with $1-bc\equiv0$ or $1-bc\equiv13$ and two solutions for every pair $b,c$ with $1-bc$ a quadratic residue other than $0$ and $13$. I don't know a systematic way of counting these; this code counts $728$.

That leaves the alternative $a\equiv+d$, excluding $a=d=0$ and $a=d=13$ since these have already been counted under $a\equiv-d$. In this case $a+d$ is even and not divisble by $13$, so $(a+d)b\equiv0$ and $(a+d)c\equiv0$ if and only if $b$ and $c$ are both $0$ or $13$. That's $4$ combinations, and for each of them there are two square roots of $1-bc$ that $a=d$ can be, so that makes $8$ additional possibilities, for a total of $728+8=736$.

Solution 3:

Let $A,B,C$ range over the nonzero elements of ${\mathbb Z}/13$.

Then over ${\mathbb Z}/13$ I get the following self-inverse matrices:

$$\hbox{12 of type} \pmatrix{0&B\cr 1/B&0\cr}$$ $$\hbox{144 of type} \pmatrix{A&B\cr{1-A^2\over B}&-A\cr}$$ $$\hbox{4 of type} \pmatrix{\pm 1&0\cr 0&\pm 1\cr}$$ $$\hbox{12 each of types} \pmatrix{1&0\cr C&-1\cr}, \pmatrix{-1&0\cr C&1\cr},\pmatrix{1&B\cr 0&-1\cr},\pmatrix{-1&B\cr 0&1\cr}$$

That's a total of 208 over ${\mathbb Z}/13$. If I multiply this by 4 (the number of self-inverse matrices over ${\mathbb Z}/2$), I get 832, not 736. Where's my mistake?