# Find the number of n by n matrices conjugate to a diagonal matrix

(a) Find the number of matrices of size $n$ by $n$ over the field of two elements which are conjugate to a diagonal matrix. What is the answer for $n = 4$?

(b) What is the number of $n$ by $n$ matrices conjugate to a diagonal matrix over any finite field $F_q$?

Any help or approaches to this problem would be very much appreciated!

-
This paper provides a formula for the number of $n\times n$ diagonalizable matrices over a finite field $\mathbb{F}_q$ (which we denote as $d_n$). The formula given is $$d_n=\sum_{n_1 + n_2 + \cdots + n_q = n}\frac{\gamma_n}{\gamma_{n_1}\gamma_{n_2}\cdots\gamma_{n_q}}$$ where $\gamma_n$ denotes the order of $\mathrm{GL}_n(q)$. The proof given in the paper looks to be a bit involved, but it is given under a broad context. You may be able to simplify it for this particular problem. – EuYu Oct 22 '13 at 3:15
Incidentally, a proof (the same proof from what I can tell) is also given in Stanley's Enumerative Combinatorics Volume I under section 1.10. – EuYu Oct 22 '13 at 3:53
Is there any slightly simpler method to solve this problem? – Nikhil Ghosh Oct 22 '13 at 6:00
If $F_q=\{x_1,x_2,\ldots,x_q\}$ then the matrices conjugate to the diagonal matrix with $a_i$ entries equal to $x_i$ (so obviously $\sum_i a_i=n$) is equal to the number of ways of decomposing $F_q^n$ as a direct sum of subspaces $V_i$ of dimensions $a_i$. Note that ordering matters, so if $a_i=a_j$ for $i\neq j$, then interchanging the subspaces $V_i$ and $V_j$ counts as a different decomposition. The idea is that a matrix is conjugate to a prescribed diagonal matrix, iff it acts on a direct sum of subspaces by the prescribed eigenvalues with the prescribed multiplicities. – Jyrki Lahtonen Oct 22 '13 at 6:44
@JyrkiLahtonen Thank you, I now understand that I have to compute the number of ways to decompose the space as as a direct sum of subspaces. How would I go about about computing this number? An example for the field of two elements would be very helpful. – Nikhil Ghosh Oct 23 '13 at 4:30

Let $X(q,n,r)$ denote the set of all uples of independent vectors $(v_1,v_2, \ldots,v_r)\in V^r$, where $V$ is an $n$-dimensional vector space over ${\mathbb F}_q$.

By an easy induction,

$$|X(n,q,r)|=(q^n-1)(q^n-q)(q^n-q^2) \ldots (q^n-q^{r-1}) \tag{1}$$

In particular, if we denote by ${\cal B}(V)$ the set of all bases of $V$, then ${\cal B}(V)=X(q,n,n)$ so

$$|{\cal B}(V)|=(q^n-1)(q^n-q)(q^n-q^2) \ldots (q^n-q^{n-1}), \ \text{with} \ n={\sf dim}(V) \tag{2}$$

Then, if we denote by ${\cal S_1}(q,n,a)$ the set of all subspaces $W$ of dimensionality $a$ in $V$, then

$$|{\cal S_1}(q,n,a)|=\frac{|X(n,q,a)|}{|{\cal B}(W)|}= \frac{(q^n-1)(q^n-q)(q^n-q^2) \ldots (q^n-q^{a-1})}{(q^a-1)(q^a-q)(q^a-q^2) \ldots (q^a-q^{a-1})} \tag{3}$$

More generally, if we denote by ${\cal S_s}(q,n,a_1,a_2, \ldots,a_s)$ the set of all uples $(W_1,W_2,\ldots,W_s)$ such that the sum $\sum_{W_j}$ is a direct sum and ${\sf dim}(W_i)=a_i$, we have

$$|{\cal S_s}(q,n,a_1,a_2, \ldots,a_s|=\frac{|X(n,q,a_1+a_2+\ldots +a_s)|}{\prod_{j}|{\cal B}(W_j)|}= \frac{(q^n-1)(q^n-q)(q^n-q^2) \ldots (q^n-q^{a_1+a_2+a_3+\ldots a_s-1})}{\prod_{j}(q^a_j-1)(q^a_j-q)(q^a_j-q^2) \ldots (q^a_j-q^{a_j-1})} \tag{3}$$

Given a partition $\pi=[p_1+\ldots+p_s]$ of $[n]$, the number of diagonalizable $n\times n$ matrices of type $\pi$ is $L(\pi) \times M(\pi)$, where $L(\pi)$ is the number of choices for the eigenvalues and $M(\pi)$ is the number of space decompositions. We compute $L(\pi)$ by direct counting and we compute $M(\pi)$ by (3).

Here are some examples :

$$\begin{array}{|l|l|l|l|} \hline n & \pi & L(\pi) & M(\pi) & N(\pi)=L(\pi)M(\pi) \\ \hline 2 & [2] & q & 1 & q \\ \hline 2 & [1+1] & q(q-1) & q(q+1) & q^2(q^2-1) \\ \hline 3 & [3] & q & 1 & q \\ \hline 3 & [2+1] & q(q-1) & q^2+q+1 & q(q-1)(q^2+q+1) \\ \hline 3 & [1+1+1] & q(q-1)(q-2) & q^3(q+1)(q^2+q+1) & (q-2)(q-1)q^4(q+1)(q^2+q+1) \\ \hline 4 & [4] & q & 1 & q \\ \hline 4 & [3+1] & q(q-1) & q^3(q+1)(q^2+1) & (q-1)q^4(q+1)(q^2+1) \\ \hline 4 & [2+2] & q(q-1) & q^4(q^2+1)(q^2+q+1) & (q-1)q^5(q^2+1)(q^2+q+1) \\ \hline 4 & [2+1+1] & q(q-1)(q-2) & q^5(q+1)(q^2+q+1)(q^2+q+1) & (q-2)(q-1)q^6(q+1)(q^2+q+1)(q^2+q+1) \\ \hline 4 & [1+1+1+1] & q(q-1)(q-2) & q^6(q+1)^2(q^2+q+1)(q^2+q+1) & (q-2)(q-1)q^7(q+1)^2(q^2+q+1)(q^2+q+1) \\ \hline \end{array}$$

Adding those results together, one can deduce the number $d_n$ of diagonlizable matrices of size $n\times n$ :

$$\begin{array}{|l|l|l|l|} \hline n & d_n & d_n \ \text{when} \ q=2 \\ \hline 2 & q(q^3-q+1) & 14 \\ \hline 3 & q(q^8 - q^7 - 2q^6 + q^4 + 2q^3 - q^2 + 1) & 58 \\ \hline 4 & q(q^{15} - 3q^{14} - 2q^{13} + 4q^{12} + 5q^{11} + 8q^{10} + q^9 - 4q^8 - 4q^7 - 6q^6 + 2q^5 - q^4 - q^3 + 1)& 1362\\ \hline \end{array}$$

-
Ewan, it's your call, but you may want to consider temporarily taking down your answer. This looks like a contest problem: meta.math.stackexchange.com/questions/11034/… I may be wrong though, so I leave it up to you. – Alex Youcis Oct 27 '13 at 10:40
@AlexYoucis You’re right. Deleted now, thanks for warning me. – Ewan Delanoy Oct 27 '13 at 11:36
The deadline has passed for this contest; feel free to undelete. – arjafi Dec 7 '13 at 11:55