Difficult to understand question involving Matrices and Prime numbers.

Question

This question was asked in the entrance of an engineering University. Apparently, this is the most difficult question they have ever asked.

Answer 1

For the first sub-question,

Let us first assume that $A$ is symmetric. Then $c = b$ and the determinant of $A$ is $a^2−b^2$ which factors as $(a+b)(a−b)$. Since p is a prime, if it divides $a^2 − b^2$, it has to divide either $a + b$ or $a − b$. Since $a$ and $b$ lie between $0$ and $p − 1$, the second possibility means $a = b$ while the first one can hold only if $a + b = 0$ or $p.a = b$ has $p$ solutions. As for $a + b = 0$, the only solution is $a = 0$, $b = 0$ which is already counted. For $a + b = p$, $a$ can take any value from $1$ to $p − 1$ and then $b$ is uniquely determined. Also note that $a + b = p$ and $a = b$ cannot hold simultaneously since $p$ is odd. Hence in all there are $p + (p − 1)$ i.e. $2p − 1$ possibilities, each of which gives exactly one symmetric matrix $A ∈ T_p$ with determinant divisible by $p$.

Now assume $A$ is skew symmetric. Then $a = 0$ and $c = −b$. Then $det(A) = b^2$ which is divisible by $p$ only when $b = 0$. But in that case $A$ is the zero matrix which is already counted as a symmetric matrix. Finally, the only matrix which is both symmetric and skew symmetric is the zero matrix which is already counted. So the net count remains at $2p − 1$.

For the second sub-question,

The trace is $2a$ which is divisible by $p$ if and only if $a = 0$. So we assume $a\ne 0$. For each such fixed $a$ we now need to determine all ordered pairs $(b, c)$ for which $a^2 − bc$ is divisible by $p$. Note that even though $1 ≤ a ≤ p − 1$, $a^2$ may be bigger than $p$. Let $r$ be the remainder when $a^2$ is divided by $p$. Then $r \ne 0$ (as otherwise $p$ would divide $a$) and so $1 ≤ r ≤ p − 1$. The condition that $a^2 − bc$ is divisible by $p$ is equivalent to saying that the integer $bc$ also leaves the remainder $r$ when divided by $p$. This rules out the possibility that $b = 0$. For every $b$ with $1 ≤ b ≤ p − 1$, we claim that there is precisely one $c$ with $1 ≤ c ≤ p − 1$ such that $bc$ leaves the remainder $r$ when divided by $p$. To see this consider the remainders when the multiples $b, 2b, 3b, . . . ,(p − 1)b$ are divided by $p$. None of these remainders is $0$ as otherwise $p$ would divide $b$. We claim these remainders are all distinct. For, suppose $ib$ and $jb$ leave the same remainder for some $i, j$ with $1 ≤ i < j ≤ p − 1$. Then $p$ divides $(j − i)b$ which would mean that either $p$ divides $j − i$ or it divides $b$, both of which are impossible since $j − i$ and $b$ both lie between $1$ and $p − 1$. Since the remainders left by $b, 2b, . . . ,(p − 1)b$ are all distinct, and there are $p − 1$ possible values for the remainder, we conclude that the remainder $r$ occurs precisely once in this list. Put differently, for each $b ∈ {1, 2, . . . , p − 1}$, there is precisely one $c$ such that $bc$ leaves the same remainder as $a^2$ does, which is equivalent to saying that $a^2 −bc$ is divisible by $p$. So, for each fixed $a ∈ {1, 2, . . . , p−1}$ there are $p−1$ matrices of the desired type. Since $a$ itself takes $p − 1$ distinct values, the total number of desired matrices is $(p − 1)^2$.

For the third sub-question,

The very format of the question suggests that complementary counting is the right tool. Since every matrix in $T_p$ is determined by three mutually independent parameters $a, b, c$ each taking $p$ possible values, in all there are $p^3$ matrices in the set $T_p$. We are interested in counting how many of these have a determinant not divisible by $p$. So let us count how many matrices in $T_p$ have determinants divisible by $p$. In the last question we did this count when the trace was not divisible by $p$ and that count was $(p − 1)^2$. Let us now add to this the number of matrices with both the trace and the determinant being divisible by $p$. The trace $2a$ is divisible precisely when $a$ is divisible by $p$, i.e. when $a = 0$. In this case, the determinant is simply $−bc$ which is divisible by $p$ if and only if $b$ or $c$ (or both) is $0$. There are $2p − 1$ ways this can happen. Thus the number of matrices with determinant divisible by $p$ is $(p−1)^2 + 2p−1$ which is simply $p^2$. So, the number of desired matrices is $p^3 − p^2$.