2
$\begingroup$

I've been checking the following discrete mathematics exercise:

How many 2x2 matrices with module 27 inputs exist with the condition being invertible?

Checking many information in the internet I found that one answer proposed is $526178$, another one is $314928$ but through different calculations I've been unable to find those numbers.

Any help will be really appreciated

$\endgroup$
1
  • $\begingroup$ For a similar question see here. $\endgroup$ – Dietrich Burde Oct 13 '18 at 18:41
3
$\begingroup$

Let the matrix have rows $a, b$ and $c, d$.

If the matrix is invertible mod $27$, then no row or column can be a vector multiple of $3$. There are two cases:

Case 1: If $3\mid a$ then neither $b$ or $c$ can be a multiple of $3.$ There are $9$ choices for $a$ and $18$ for each of $b$ and $c$. For a given choice of $a, b,$ and $c$, we need to exclude any values for $d$ that makes $ad-bc$ divisible by $3$. But $bc$ is not divisible by $3$ while $a$ is. So the congruence $ad\equiv bc \pmod{3}$ has no solutions. Therefore $d$ can be any of the $27$ numbers. We have $9\cdot 18\cdot 18\cdot 27 = 78732$ possibilities for Case 1.

Case 2: If $3\nmid a$, then $b$ and $c$ can be anything. So we have $18$ choices for $a$ and $27$ each for $b$ and $c$. Since $3\nmid a$, the congruence $ax=cd \pmod{3}$ has a unique solution which lifts to $9$ solutions $\pmod{27}.$ These must be excluded, so there are $18$ choices for $d$. We have $18\cdot 27 \cdot 27\cdot18 = 236196$ possibilities for Case 2.

We add the two cases and get $314928$ for the final answer.

$\endgroup$
0
$\begingroup$

Idea: The number of all $2\times 2$ matrices is $27^4$. Calculate the number of matrices that are not invertibile, so $$27\mid ad-bc$$ if $a,b,c,d\in \mathbb{Z}_{27}$ and

$$ M= \left[ \begin{matrix} a&b\\ c&d\\ \end{matrix} \right] $$

Divide it on cases

If $3\nmid d$ then $a$ is uniqely determined with $b,c,d$ with formula $a= bcd^{-1}{\mod 27}$

If $3\mid d$ and $9\nmid d$ ...

If $9\mid d$ and $27\nmid d$ ...

If $27\mid d$ ...

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