Number of matrices on $\mathbb Z_{p}$ with a given characteristic polynomial How can I find the number of n×n matrices on $\mathbb Z_{p}$ with a given characteristic polynomial?
for example:
If $p$ is a prime number s.t. $p \equiv 3 \pmod 4$, then number of $2\times 2$ matrices on $\mathbb Z_{p}$ that their characteristic polynomial is $x^2+1$ would be equal to $p(p-1)$.
I don't have the proof of above example.
 A: $\newcommand{\Size}[1]{\left\lvert #1 \right\rvert}$For your special case, with characteristic polynomial $x^{2} + 1$ and $p \equiv 3 \pmod{4}$, the matrix is conjugate to its rational canonical form
$$
R =
\begin{bmatrix}
0 & 1\\
-1 & 0\\
\end{bmatrix}.
$$
So it is just a matter to see how many conjugates $R$ has. Alternatively, one may compute the centralizer of $R$, and discover that it is
$$
a I + b R
$$
with $a, b$ not both zero. So the centralizer has order $p^2 - 1$, hence $R$ has
$$\dfrac{\Size{\operatorname{GL}(2,p)}}{p^2 - 1}
=
\dfrac{(p^{2} - 1)(p^{2} - p)}{p^2 - 1}
= p(p-1)$$
conjugates.

When $p \equiv 1 \pmod{p}$, then the matrix can be put in the form
$$
R =
\begin{bmatrix}
a & 0\\
0 & -a\\
\end{bmatrix}.
$$
where $a$ is a primitive fourth root of unity. This time the centralizer has order $(p-1)^{2}$, as it consists of the diagonal matrices, hence $R$ has
$$\dfrac{\Size{\operatorname{GL}(2,p)}}{(p - 1)^{2}}
=
\dfrac{(p^{2} - 1)(p^{2} - p)}{(p - 1)^{2}}
= p(p+1)$$
conjugates.
A: For the characteristic polynomial $x^2-1$:
Observe that the matrices must have the form $\begin{pmatrix}a&b\\c&-a\end{pmatrix}$ where
$$a^2=1-bc.$$
Hence, given $b$ and $c$ we can find zero, one or two $a$'s that will work. To count the number of solutions, we consider the following cases:


*

*If $1-bc=0$. In this case there's only one $a$ (namely $a=0$) that will work. Give a non-zero $c$, and there's only one $b$, namely $b=1/c$ (and of course, $c=0$ doesn't work). Conclusion: there are $p-1$ such matrices with $bc=1$.

*If $1-bc=1$, i.e., $bc=0$. In this case there are two $a$'s that will work (except if $p=2$). Now, to have $bc=0$ we consider the number of possible pairs $(b,c)$:


*

*$b=0,c\neq0$: there are $p-1$ pairs ($p-1$ possible $c$'s),

*dually, $b\neq0,c=0$ yields $p-1$ pairs,

*$b=0,c=0$: only one possibility


Hence this case yields $2p-1$ pairs hence we'll have $4p-2$ corresponding matrices if $p\neq2$ (and $2p-1=3$ if $p=2$).

*If $1-bc\not\in\{0,1\}$ (case only valid if $p\neq2$): we know that there are $(p-1)/2$ quadratic residues modulo $p$; we already considered one (namely, $1$) so there are $(p-3)/2$ quadratic residues left. For each of them, say $q\neq1$, there are $(p-1)$ pairs $(b,c)$ such that $1-bc=q$, namely $c\neq0$ and $b=(1-q)/c$: that's only one $b$ for each non-zero $c$, hence $(p-1)$ number of pairs $(b,c)$. There are exactly two $a$'s in this case. Hence there are exactly $(p-3)(p-1)$ such matrices with $1-bc\not\in\{0,1\}$.


Conclusion: if $p=2$ we have $4$ such matrices and if $p\neq2$ there are
$$p-1+4p-2+(p-3)(p-1)=p(p+1)$$
such matrices. Moreover, the proof is constructive.

For the characteristic polynomial $x^2+1$: notice that the previous proof can be adapted as follows: the equation characterizing the matrices is $a^2=-1-bc$. The case $p=2$ is similar to the previous one, so we exclude it.


*

*If $-1-bc=0$: $p-1$ matrices,

*If $-1-bc=-1$: $2p-1$ pairs $(b,c)$, but $-1$ is a quadratic residue if and only if $p=1\pmod4$. This amounts for $4p-2$ matrices if $p=1\pmod4$ and $0$ otherwise;

*If $-1-bc\not\in\{0,-1\}$: $(p-1)$ pairs $(b,c)$ for a given $-1-bc$; there are $(p-1)/2$ quadratic residues, one was already considered in the previous case when $p=1\ (\text{mod}4)$. There are $2$ corresponding $a$'s. This amounts to $(p-3)(p-1)$ matrices if $p=1\ (\text{mod}4)$ and $(p-1)^2$ if $p=3\pmod4$.


Conclusion: there are that many such matrices:
$$\begin{cases}
p(p-1)&\text{if $p=3\pmod4$}\\
p(p+1)&\text{if $p=1\pmod4$}.
\end{cases}$$
