1
$\begingroup$

I'm trying to find the inverse of the matrix $\begin{bmatrix} 4 &8 \\ 5 &7 \end{bmatrix} \mod 26$. However the determinant of this matrix is 14 so I cannot use Cramer's rule and each time I try to solve simply by elimination, I end up with non-invertible elements in the resulting matrix.

For example, multiplying the second row by 15: $$\left.\begin{matrix} 4&8 \\ 23&1 \end{matrix}\right| \begin{matrix} 1&0 \\ 0&15 \end{matrix}$$

Then adding the second row the first: $$\left.\begin{matrix} 1&9 \\ 23&1 \end{matrix}\right| \begin{matrix} 1&15 \\ 0&15 \end{matrix}$$ Adding 3 times the first row to the second: $$\left.\begin{matrix} 1&9 \\ 0&2 \end{matrix}\right| \begin{matrix} 1&15 \\ 3&8 \end{matrix}$$

At this point, 2 doesn't have an inverse mod 26 and $2x\equiv9 \pmod{26}$ has no solution. I've tried a number of different combinations of row operations. How can I find the inverse of this matrix?

$\endgroup$
1
  • 5
    $\begingroup$ If the determinant is not invertible, then the matrix is not invertible. $\endgroup$ Mar 10 '13 at 2:36
5
$\begingroup$

The multiplication formula $$\det(AB)=\det(A)\det(B)$$ is true whenever $A,B$ have elements from a commutative ring. If $A$ is invertible with inverse $A^{-1}$ then $$1=\det(AA^{-1}) = \det(A)\det(A^{-1})$$ so $\det(A)$ is invertible with inverse $\det(A^{-1}).$ So for $A$ to be invertible it is necessary that $\det(A)$ be invertible, which is not the case here. A stronger result is that $A$ is invertible if and only if $\det(A)$ is invertible.

$\endgroup$
0
$\begingroup$

Hint $\rm\: mod\,\ 26\!:\ \left[\begin{array}{c} 4 & 8\\ 5 & 7\end{array}\right]\left[\begin{array}{c}x\\ \rm y\end{array}\right] = \left[\begin{array}{c}0\\ \rm 0\end{array}\right]\ $ has solution $\:\left[\begin{array}{c}13\\ \rm 13\end{array}\right]\: $so the matrix is not invertible.

Indeed, if it it were invertible then multiplying by the inverse shows $\ \smash[t]{\rm \left[\begin{array}{c}x\\ \rm y\end{array}\right] = \left[\begin{array}{c}0\\ \rm 0\end{array}\right]}$

$\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.