[Math] Inverse of a modular matrix

matricesmodular arithmetic

I have the matrix$$
\begin{pmatrix}
1 & 5\\
3 & 4
\end{pmatrix} \pmod{26}
$$
and I need to find its inverse. I do it according to this website.

I find the modular multiplicative inverse (of the matrix determinant, which is $1×4-3×5=-11$) with the extended Euclid algorithm (it is $-7 \equiv 19 \pmod{26}$). Then I have $$\frac{1}{19}×\begin{pmatrix}4 & -5\\-3 & 1\end{pmatrix}.$$ I calculate that$$-5 \equiv 21 \pmod{26},\ -3 \equiv 23 \pmod{26}.$$

No matter what I do I am not able to get the solution they have on the website, which is$$\begin{pmatrix}2 & 17\\5 & 7\end{pmatrix}.$$

Can someone help me with this? What am I doing wrong?

Best Answer

The determinant is $-11$, as you mentioned.

The Euclidean algorithm will tell you that the inverse is $7$ or $-19$, since $-11 \times 7 = -77 \equiv 1 \mod 26$.

Now the usual $2 \times 2$ inverse is $\begin{pmatrix}4 & -5 \\ -3 & 1\end{pmatrix}$, and this times $7$ is $\begin{pmatrix}28 & -35 \\ -21 & 7\end{pmatrix}$,which simplifies $\mod 26$ to $\begin{pmatrix} 2 & 17 \\ 5 & 7\end{pmatrix}$.

Reiterate procedure, for your help. Given a matrix $A$, which you want to invert $\mod m$ (where the inverse of $A$ exists $\mod m$),

  • First, compute the determinant of the matrix,$\det A$. If $\det A$ is coprime to $m$, then you can be sure that $A$ is invertible $\mod m$.

  • Find the inverse of $\det A$ modulo $m$. This we denote by $(\det A)^{-1}$ and will be the unique integer between $0$ and $m$ which satisfies $(\det A) \times (\det A)^{-1} \equiv 1 \mod m$.

  • Next, compute the matrix of cofactors of $A$, call this $B$. So, this is the matrix which would have been the usual inverse of $A$, without division by the determinant.

  • The matrix $(\det A)^{-1} \times B$ is an inverse to $A$ modulo $m$. You can ensure that all the entries of the above matrix are between $0$ and $m$ for completeness, by division by $26$ and taking the consequent remainder of each entry.

Related Question