Similar Matrices in a field Let $p$ be a odd prime integer. And $A$ and $B$ be matrices from the set  $GL(l,p)$. Further, suppose that $A$ and $B$ are similar. That is, there exists an invertible matrix $H$ such that $B = HAH^{-1}$. Finally let 
$$ S = \{ H \in  GL(l,p):  B = HAH^{-1}\bmod~p \}.$$
I am trying to determine the number of elements of the set $S$. 
My approach is to solve $B = HAH^{-1}$ for the unknown elements of $H$. Notice that will result in having a homogeneous linear system with $l^2$ unknowns, where $l$ is the number of rows and columns of $H$.  Experimentally, I observed that the number of free variables when solving this system is $l$. Would this imply that the number elements of the set $S$ is $(p-1)^l$?
Any help with this will be highly appreciated. You may contact me directly at  j1 dot feeb "@" G mail  dot   com.  Thanks in advance.
 A: EDIT 1. First part. We consider the orbit $O_A=\{HAH^{-1}|H\in G\}$ where $G=GL_l(p)$.
Assume that $p$ is a large integer and let $\chi_A$ be the characteristic polynomial of $A\in M_l(p)$ and $K=\mathbb{Z}/p\mathbb{Z}$. If $A$ is a random matrix, then, with a probability close to $1-\dfrac{1}{p}$, one has $discrim(\chi_A(x))\in K\setminus \{0\}$ and the eigenvalues of $A$ are distinct in $\overline{K}$.
Case 1. The eigenvalues are in $K$. Thus we may assume that $A$ is diagonal. We consider the stabilizer $G_A=\{H\in G|HA=AH\}=\{H|H\;diagonal,h_{i,i}\not= 0\}$. Then $card(G_A)=(p-1)^l$.
Case 2. The eigenvalues are not all in $K$. It is much more difficult! We seek the matrices $H=Q(A)=a_0I+a_1A+\cdots+a_{l-1}A^{l-1}$ (where $Q\in K_{l-1}[x]$) s.t. $\det(H)\not= 0$. We give two examples where $l=3,p=101$.
Example 1. $A=\begin{pmatrix}23&43&35\\98&20&64\\78&66&97\end{pmatrix}$ has $3$ distinct eigenvalues in $\overline{K}$ including one in $K$. $card(G_A)=101^3-10301=(p-1)^l+20000$.
Example 2. $A=\begin{pmatrix}98&40&79\\21&85&16\\44&4&91\end{pmatrix}$ has $3$ distinct eigenvalues in $\overline{K}$ and none in $K$. $card(G_A)=101^3-1$ ($\det(H)=0$ implies that $a_0=a_1=a_2=0$).
EDIT 2. Let $\chi_A$ be the characteristic polynomial of $A$. Using the Sedran's idea, we prove the following
Proposition 1. If $\chi_A$ is irreducible over $K$, then $card(G_A)=p^l-1$.
Proof. The eigenvalues of $A$ are distinct and algebraic of degree $l$ over $K$ and, consequently, are not roots of a polynomial of degree $l-1$. Thus $H$ cannot have a zero eigenvalue, except if the $(a_i)$ are zero.
Proposition 2. If $l\geq 3$ and $\chi_A(x)=(x-a)p_{l-1}(x)$ where $a\in K$ and $p_{l-1}$ is irreducible, then $card(G_A)=p^l-(p^{l-1}+p-1)$.
Proof. The eigenvalues of $A$ are distinct and, except $a$, are algebraic of degree $l-1$. If $H=Q(A)$ and $\det(H)=0$, then one studies two cases:
Case 1. $Q(a)=0$ that is $Q(x)=(x-a)q_{l-2}(x)$ where $q_{l-2}$ is an arbitrary polynomial of degree $l-2$; there are $p^{l-1}$ such polynomials.
Case 2. $Q(x)=\alpha p_{l-1}(x)$ where $\alpha\in K\setminus \{0\}$. There are $p-1$ such polynomials.   $\square$
Finally $card(O_A)=card(G)/card(G_A)=\dfrac{(p^l-1)(p^l-p)\cdots(p^l-p^{l-1})}{card(G_A)}$.
Second part. Now I answer your question; you fix two similar matrices $A,B$. In fact, $card(S)=card(G_A)$. Indeed, if $U$ is a fixed matrix s.t. $UAU^{-1}=B$, then $S=\{UH|H\in G_A\}$.
A: This is a follow up to the answer provided by @loup blanc. 
Note: I hope I am following the proper procedure in doing so.  Any pointers on how to properly post a follow up will be appreciated. 
Lemma: 
 Let $A\in M_l(K)$ that has $l$ distinct eigenvalues in $\overline{K}$ and 
and let $r\in \{0,1, \cdots  l-1\}$ be the number of its eigenvalues in $K$. Then $$card(G_A)=p^l-1,  \mbox{ when }r=0.$$
Proof:
Consider $H=a_{l-1}A^{l-1}+ \cdots a_1A+ a_0I$ s.t. $\det(H)\not\equiv 0 \pmod{p}$. And let $\lambda_{k}~~(0 \leq k \leq l-1) $ be the eigenvalues of $A$. Since none of these eigenavlues are in $K$, it follows that the eigenvalues of $H$
$$a_0+a_1\>{\lambda_{k}}+\cdots+a_{l-1}{\lambda_{k}}^{l-1} \not\equiv 0 \pmod{p},$$
except for $a_0 = a_1\> = \cdots a_{l-1} = 0.$ Hence, 
$$card(G_A)=p^l-1.$$        
A: Here is another attempt at this question. Given a prime $p$,  $l\times l$ matrices $A$, $B$, and $H \in  GL(l,p)$ such that $$ B \equiv H.A.H^{-1} \pmod{p},$$ we seek to find the number of all $\hat{H} \in GL(l,p)$ such that $$ \hat{H}.A.{\hat{H}}^{-1} \equiv  H.A.H^{-1} \equiv B \pmod{p}.$$
Consider $$ \hat{H}.A.{\hat{H}}^{-1} \equiv  H.A.H^{-1} \pmod{p}.$$
This implies that $ H^{-1}.\hat{H}.A \equiv  A.H^{-1}.\hat{H} \pmod{p}\Rightarrow H^{-1}.\hat{H} \in Cen_{{{M}}_l(Z_p)}(A)$.
It is well known that the  centralizer of  $A$ is 
$$Cen_{{{M}}_l(Z_p)}(A) = \{f(A)\> | \> f(t)\mbox{ is a polynomial over } Z_p\}$$
provided that  the minimum polynomial and characteristic polynomial of $A$ coincide. This condition is satisfied if $A$ has distinct eigenvalues. 
Assuming that this is the case, then $$H^{-1}.\hat{H} \in Cen_{{{M}}_k(Z_p)}(A) \iff \hat{H} \equiv 
H.(\alpha_{l-1}\>A^{l-1}+\alpha_{l-2}\>A^{l-2} + \ldots \alpha_{0}\>I)   \pmod{p}, $$
where $ 0 <  \alpha_k \leq  p-1,$  for $ 0 < k \leq  l-1$.
Therefor, there are $(p-1)^l$ possible $\hat{H}$'s.
Agree/Disagree/Not even close/Maybe? $~$ :-)
A: This will depend on the similarity class of $A$. Let $C_A = \{ B \in M_l (\mathbb{F}_p)| AB=BA\}$ and $G_A=\{ H\in GL_l(\mathbb{F}_p) | AH=HA\}$. Denote by $C_A^{(0)} = C_A \cap \{B\in M_l(\mathbb{F}_p)|\det B=0\}$. Then 
$$
|G_A|=|C_A|-|C_A^{(0)}|.
$$
Clearly, $C_A$ is finite dimensional over $\mathbb{F}_p$. Let $m=\dim_{\mathbb{F}_p} C_A$. Then $m\geq l$ and $m=l$ if and only if the minimal and characteristic polynomial for $A$ coincide. For the proof of this, see this answer. 
Let $\{I=B_1,\ldots, B_m\}$ be a basis for $C_A$ over $\mathbb{F}_p$.  Consider $$
\det(c_1B_1+\cdots + c_mB_m)=0. \ \ \ (*)
$$
For any given $c_2, \ldots, c_m$, the equation $(*)$ is a polynomial equation in $c_1$ of degree $l$. Thus, the number of solutions to $(*)$ is at most $l p^{m-1}$. This gives
$$
|C_A^{(0)}|\leq lp^{m-1}.
$$
Then, it follows that 
$$
|C_A|-lp^{\dim C_A -1}\leq |G_A|\leq |C_A|.
$$
In the special case that the minimal and the characteristic polynomial of $A$ coincide, we have $m=l$. Thus, 
$$
p^l-lp^{l-1}\leq |G_A|\leq p^l.
$$
This bound will be useful only when $p$ is  larger than $l$. An article 'The Order of the Conjugacy Classes of $GL(n,F)$', Advances in Mathematics 129, p. 73-84, written by Eugene Spiegel, provides an exact formula for $|G_A|$. 
A: The following is taken from http://www.westminster.edu/staff/offnerde/CountingEigenvalues.pdf.
For any matrix $A\in M_{l}(\mathbb{F})$, let $S(A)  \subseteq M_{l}(\mathbb{F})$ be the set of matrices similar to $A$, and let $C(A)$ denote the subgroup of $GL_l(\mathbb{F})$ of matrices $P$ such that $PA = AP$.
Lemma: For Any $J \in M_{l}(\mathbb{F})$, $|S(J)|\ = \frac{|G_{l}(\mathbb{F})|}{|C(J)|}$.
Proof: Fix a matrix $J \in M_{l}(\mathbb{F})$. We wish to find the cardinality of 
$$ S(J) = \{{AJA^{-1}: A \in G_{l}(\mathbb{F})}\}.$$
For any matrix $A$, $B$ $\in G_{l}(\mathbb{F})$, $AJA^{-1} = BJB^{-1}$ if and only if 
$B^{-1}AJ = JB^{-1}A$, i.e. if $B^{-1}A \in C(J)$. Now $B^{-1}A \in C(J)$ if and only if $A$ and $B$ are in the same coset of $C(J)$ in $G_{l}(\mathbb{F})$ and thus $S(J)$ has the same cardinality as the number of cosets of $C(J)$ in $G_{l}(\mathbb{F})$, which is equal to $|G_{l}(\mathbb{F})|/|C(J)|$ by Lagrange's Theorem.
