Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

(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!

share|improve this question
2  
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

1 Answer 1

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} $$

share|improve this answer
    
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. –  Arthur Fischer Dec 7 '13 at 11:55

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.