1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ You multiply by the reciprocal of $-11$ (which is $7$) not divide by it. $\endgroup$ – Lord Shark the Unknown Mar 11 '18 at 8:46
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

The determinant is $-11 \pmod{26}$.

$$(-7)(-11)=77=26\cdot 3-1\equiv -1 \pmod{26}$$

Hence the inverse is suppose to be $7$ rather than $-7$.

$$7 \begin{bmatrix} 4 & -5 \\ -3 & 4\end{bmatrix} \equiv \begin{bmatrix} 2 & 17 \\ 5 & 3\end{bmatrix} \pmod{26}$$

$\endgroup$
0
$\begingroup$

Doing aritmetic modulo $\;26\;$ all the time, we get that

$$\det A=\begin{vmatrix}1&5\\3&4\end{vmatrix}=4-15=-11=15\implies$$

$$\implies A^{-1}=\frac1{15}\begin{pmatrix}4&-5\\-3&1\end{pmatrix}=7\begin{pmatrix}4&21\\23&1\end{pmatrix}=\begin{pmatrix}2&17\\5&7\end{pmatrix}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.