Centralizer of a Matrix over a Finite Field This question in stackExchange remained unanswered. 
Let $\mathbb F$  be a finite field. Denote by $M_n(\mathbb F)$  the set of matrices of order $n$  over $\mathbb F$ . For a matrix $A∈M_n(\mathbb F)$  what is the cardinality of $C_{M_n(\mathbb F)} (A)$ , the centralizer of $A$  in $M_n(\mathbb F)$? There are papers about it? 
 A: Treat $F^n$ as an $F[t]$-module $M^A$, where $t$ acts by the matrix $A$. Then the centralizer can be thought of as $\mathrm{End}_{F[t]} M^A$. Now, $M^A$ has a primary decomposition
$ M^A = \bigoplus_{p \in \mathrm{Irr}(F[t])} M_p$
where $M_p$ consists of vectors in $M^A$ which are annihilated by some power of $p(A)$. Likewise, 
$C_{M_n(F)}(A)= \mathrm{End}_{F[t]} M^A = \bigoplus_p \mathrm{End}_{F[t]} M_p$
So the problem is reduced to the primary case, where the characteristic polynomial of $A$ is a power of some irreducible polynomial $p$.
Now, there exists a unique partition $\lambda=(\lambda_1,\dotsc,\lambda_l)$ such that
$M_p = \bigoplus_{i=1}^l F[t]/(p(t))^{\lambda_i}$.
As a vector space (and even as an $F[t]$-module), the endomorphism algebra of this module is the sum
$\bigoplus_{i,j} \mathrm{Hom}_{F[t]} (F[t]/(p(t))^{\lambda_i},F[t]/(p(t))^{\lambda_j})$.
The $(i,j)$th summand has dimension $(\deg p)\min\{\lambda_i,\lambda_j\}$. Therefore, the endomorphism algebra of this primary part is of dimension
$ (\deg p)\sum_{i,j} \min\{\lambda_i,\lambda_j\}$
To get the centralizer of the original matrix, you would add these numbers over all primary parts.
Finally, raising $q$ to this number is the cardinality that you want.
These centralizers are discussed in great detail in Pooja Singla's PhD thesis http://www.hbni.ac.in/phdthesis/allthesis/MATH10200604007_PSingla.pdf
and a related paper in J. Algebra 2010 (available on the arXiv at http://arxiv.org/abs/1001.5304v1).
A: Let me add some cases in which one has a clear answer:
[R.A. Horn, C.R. Johnson, Topics in Matrix Analysis, Cambridge University Press, Cambridge, 1991., Corollary 4.4.18]. Let $F$ be a field and $n$ is a natural number. If
$A\in  M_n(F)$ is a cyclic matrix, then $C_{M_n(F)}(A)$ is the set of all matrices which are
polynomial in $A$ with coefficients in $F$.
Recall that a cyclic matrix in $M_n(F)$ is a matrix whose minimal and characteristic polynomials are the same.
[Lemma 3 of S. Akbari et al. / Linear Algebra and its Applications 390 (2004) 345–355] Let $F$ be a field and $n\geq 2$. If $A$ is a non-scalar matrix in $M_n(F)$ and
$C_{M_n(F)}(A)$ has maximum dimension over $F$, then $\dim_F C_{M_n(F)}(A) = n^2 − 2n + 2$
and $A$ is similar to either $aI_1 \oplus bI_{n−1}$ or $aI_n + bE_{12}$, for some $a, b \in F$. 
See for the notation the latter mentioned paper.
I suggest you to look for papers on the commuting graphs of rings, you may find some other cases which are treated in the proofs. 
One paper is quoted above and the another is
S. Akbari, P. Raja / Linear Algebra and its Applications 416 (2006) 1038–1047
A: You asked this on Math Stack Exchange too.  One messy case is when $A$ is unipotent. Some cases of tat are dealt with in a famous paper of P. Hall and G. Higman on "Reduction Theorems for Burnside's Problem" (Proceedings of London Mathematical Society, 1956). The centralizer of a semisimple matrix is relatively easy to understand. Therefore, the essence of the question does reside in the structure of the centralizer of a nilpotent matrix.
A: I've recently come across this question about the size of the centralizer (I assume that you mean the subgroup of $\text{GL}_n(F)$ which commute with the matrix).  It seems to be hard to find.  I wonder why it's been omitted from every Algebra book (even Bourbaki!) that I've consulted.  There is a derivation of it in Dickson's "Linear Groups with an Exposition of the Galois Field Theory" p. 235 (Dover edition) dating from 1900.   A more modern way of seeing this is to let $R = F[x]$, and construct the $R$-module on a vector space $V$ of dimension $n$ (if $A$ is $n \times n$) by having $x v = A v$.  Then the centralizer is $\text{Aut}_R(V)$.  In MacDonald's book "Symmetric Functions and Hall Polynomials" p. 87 (1979 edition) he derives the formula in terms of the theory of finitely generated modules over a commutative discrete valuation ring.  This, incidentally, also gives the formula for the number of automorphisms of a finite abelian group.
A: This is just elementary comment, but may be too long for comment, probably you know it, but just for completeness.
I happened to ask almost (but not exactly) the same question some days ago: 
Conjugcy classes in GL(F_2) ? GL(F_q)
It sounds a little different - size of conjugacy classes in GL(F_q).
But conjugacy class of element "C" is size of GL(F_q)/ size of centralizer of element "C".
Because size of any orbit is |G|/|Stabilizer| and here we have action by conjugation and stabilizer
is centralizer.
So if you know the size of centralizer - you know size of conjugacy class.
The difference is, of course, that you asked about Mat(F_q) while setup above is about non-degenerate matrices GL(F_q).

Let me also write down some elementary facts for completeness.
If you consider element $C$ such that its characteristic polynomial is irreducible, (then it automatically minimal), then size of centralizer in Mat_n(F_q) is q^n (if I understand correctly)
and q^n-1 in GL_n(F_q).
One has good way to think about this centralizer: let consiser p(x) - char.pol. of "C".
F_q[x]/p(x) is a field F_q^n.
To any element of the field "a" in F_q^n one can correspond a matrix M(a) - the matrix of multiplication by "a":F_q^n -> F_q^n.
Map "a->M(a)" is clearly homomorphism of algebras so in particular all matrices M(a) commute among themselves. They provide a centralizer of a matrix M(x). 
