\documentclass[12pt,a4paper]{article}
\usepackage[utf8]{inputenc}
\usepackage[francais]{babel}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage{amsmath,amsfonts}
\usepackage{amssymb,amsthm}

\usepackage{graphicx}
\usepackage[scale=0.8]{geometry}
\author{Leçons 101, 104, 123, 150, 155, 190 \\ Salim Rostam}
\title{Nombre de matrices diagonalisables dans $\mathcal{M}_n(\mathbb{F}_q)$}

\newtheorem{theoreme}{Théorème}
\newtheorem{lemme}[theoreme]{Lemme}

\theoremstyle{definition}
\newtheorem{definition}[theoreme]{Définition}

\theoremstyle{remark}
\newtheorem{remarque}[theoreme]{Remarque}

\DeclareMathOperator{\orb}{Orb}
\DeclareMathOperator{\stab}{Stab}
\DeclareMathOperator{\diag}{diag}
\DeclareMathOperator{\GL}{GL}
\DeclareMathOperator{\ssi}{\;\underline{ssi}\;}
\DeclareMathOperator{\scal}{Scal}
\DeclareMathOperator{\bb}{b}
\newcommand*{\spb}{\scal^{\bb}}


\begin{document}
\maketitle


Référence : Oraux X-ENS, algèbre, tome 1, exercice 1.10 (donne l'idée de la démonstration).

Soit $n$ un élément de $\mathbb{N}^*$ et soit $q$ une puissance d'un nombre premier. On note $\mathcal{D}_n(q)$ l'ensemble des matrices de $\mathcal{M}_n(q) := \mathcal{M}_n(\mathbb{F}_q)$ diagonalisables sur $\mathbb{F}_q$ ; on s'intéresse au cardinal de $\mathcal{D}_n(q)$. On note $\chi_A(X) := \det(X I_n - A)$ le polynôme caractéristique d'une matrice $A$ de taille $n$, et si $X$ est un ensemble fini on note $| X |$ son cardinal.

\begin{theoreme}
Avec la convention $\mathopen{|}\GL_0(q)| = 1$ on a la formule suivante :
\[
| \mathcal{D}_n(q)| = \sum_{\substack{m_1, \dots, m_q \in \mathbb{N} \\ m_1 + \dots + m_q = n}} \frac{\mathopen{|} \GL_n(q)|}{\prod_{i = 1}^q \mathopen{|} \GL_{m_i}(q)|} 
.\]
\end{theoreme}

Remarquons tout de suite que l'on a une formule explicite pour le cardinal du groupe linéaire.

\begin{lemme}
Pour $m \in \mathbb{N}$ on a
$\mathopen{|}\GL_m(q)| = \prod_{i = 0}^{m - 1} (q^m - q^i) = q^{\frac{m(m - 1)}{2}} \prod_{i = 1}^m (q^i - 1)$.
\end{lemme}

%\begin{proof}
%Pour compter le nombre de matrices inversibles, il suffit de compter le nombre de familles libres $(v_1,\dots,v_m)$ de vecteurs colonne. Ainsi :
%\begin{itemize}
%\item le premier vecteur $v_1$ doit être non nul donc on a $q^m - 1$ choix ;
%\item le deuxième vecteur ne doit pas se trouver dans $\vect(v_1)$ qui a $q$ éléments donc on a $q^m - q$ choix pour $v_2$ ;
%\item pour $i \in \{2,\dots, m - 1\}$, le vecteur $v_{i + 1}$ ne doit pas se trouver dans $\vect(v_1, \dots, v_i)$ qui est de cardinal $q^i$ donc on a $q^m - q^i$ choix pour $v_{i + 1}$.
%\end{itemize}
%Étant donné que la famille ainsi obtenue est libre, on en déduit la formule annoncée. En particulier, la convention $\mathopen{|}\GL_0(q)| = 1$ est compatible avec $\prod_{\emptyset} = 1$.
%\end{proof}

Venons-en à la démonstration du théorème. On va se baser sur le fait suivant :
\begin{equation}
\label{eq:formule_generale}
\mathcal{D}_n(q) = \{PDP^{-1} : D \in \mathcal{M}_n(q) \text{ diagonale et } P \in \GL_n(q)\}.
\end{equation}
Remarquons que $\GL_n(q)$ agit par conjugaison sur $\mathcal{D}_n(q)$ ; pour $M \in \mathcal{D}_n(q)$, on note
 $\orb(M)$ son orbite et $\stab(M)$ son stabilisateur pour l'action de $\GL_n(q)$ sur $\mathcal{D}_n(q)$.
 
\begin{definition}
Soit $\chi$ un polynôme scindé unitaire sur $\mathbb{F}_q$ de degré $n$ ; on écrit $\chi = \prod_{i = 1}^r (X - \lambda_i)^{m_i}$ avec les $\lambda_i \in \mathbb{F}_q$ deux à deux distincts. On lui associe la matrice diagonale $D_{\chi} := \diag(\lambda_i I_{m_i})_{1 \leqslant i \leqslant r}$ et on note $\spb_n(q) := \{D_{\chi} : \chi$ polynôme scindé unitaire sur $\mathbb{F}_q$ de degré $n\}$.
\end{definition}

\begin{remarque}
En réalité, $D_{\chi}$ dépend de l'ordre que l'on choisit pour les racines de $\chi$ mais cela n'est pas grave : la chose importante est que deux éléments distincts de $\spb_n(q)$ ont leur polynôme caractéristique distinct (le polynôme caractéristique de $D_{\chi}$ étant bien sûr $\chi$).
\end{remarque}


%Avant d'énoncer un premier lemme, définissions l'application $\Gamma_D : \GL_n(q) \to \mathcal{M}_n(q)$ par $\Gamma_D(P) := P D P^{-1}$ pour une matrice (diagonale) $D \in \mathcal{M}_n(q)$. Ainsi, $(\ref{eq:formule_generale})$ se réécrit :
%\[
%\mathcal{D}_n(q) = \bigcup_D \Gamma_D(\GL_n(q))
%\]
%où la réunion est prise sur les matrices $D \in \mathcal{M}_n(q)$ diagonales.
% 
%\begin{lemme}
%On a $\mathcal{D}_n(q) = \{PDP^{-1} : D \in \spb_n(q), P \in \GL_n(q)\}$ et plus précisément :
%\[
%\mathcal{D}_n(q) = \bigsqcup_{D \in \spb_n(q)} \Gamma_D(\GL_n(q)).
%\]
%\end{lemme}

\begin{lemme}
$\spb_n(q)$ est un système de représentants des orbites de $\mathcal{D}_n(q)$ sous l'action de $\GL_n(q)$, en particulier :
\[
\mathcal{D}_n(q) = \bigsqcup_{D \in \spb_n(q)} \orb(D).
\]
\end{lemme}

%\begin{proof}
%Soit $D' = \diag(\lambda_i)_{1 \leqslant i \leqslant n} \in \mathcal{M}_n(q)$ une matrice diagonale. Par définition de $\spb_n(q)$, il existe un unique élément $D \in \spb_n(q)$ tel que $D$ et $D'$ aient les mêmes valeurs propres \emph{comptées avec multiplicité} (\textit{i.e.}  $D$ et $D'$ ont le même polynôme caractéristique). Étant donné que $D$ et $D'$ sont diagonales, elles sont donc semblables (via une matrice de permutation par exemple). En écrivant $D' = Q D Q^{-1}$, on a donc $\Gamma_{D'}(\GL_n(q)) = \Gamma_{QDQ^{-1}}(\GL_n(q)) = \{P(QDQ^{-1})P^{-1} : P \in \GL_n(q)\} = \{(PQ)D(PQ)^{-1} : P \in \GL_n(q)\} = \{PDP^{-1} : P \in \GL_n(q)\} = \Gamma_D(\GL_n(q))$ ce qui démontre la première partie du lemme. Pour obtenir la réunion disjointe, on remarque que si $M \in \Gamma_D(\GL_n(q)) \cap \Gamma_{D'}(\GL_n(q))$ avec $D, D' \in \spb_n(q)$ alors on peut écrire $M = PDP^{-1} = Q D' Q^{-1}$ donc $D$ et $D'$ ont le même polynôme caractéristique et comme ce sont deux éléments de $\spb_n(q)$ on a donc $D = D'$.
%\end{proof}

\begin{proof}
Tout d'abord, chaque $D' \in \mathcal{D}_n(q)$ possède au moins un représentant de son orbite dans $\spb_n(q)$, à savoir $D_{\chi_{D'}}$. En effet, $D'$ est semblable à une matrice diagonale et cette matrice diagonale est semblable à $D_{\chi_{D'}}$ (par une matrice de permutation par exemple : il suffit de permuter les vecteurs de la base). Finalement, si $\chi$ et $\psi$ sont deux polynômes scindés unitaires sur $\mathbb{F}_q$ de degré $n$ tels que $D_{\chi} \in \orb(D_{\psi})$ alors $D_{\chi}$ et $D_{\psi}$ sont semblables ; elles ont donc le même polynôme caractéristique d'où $\chi = \psi$.
\end{proof}

Une conséquence immédiate de ce lemme est la chose suivante (formule des classes) :
\begin{equation}
\label{eq_ann:nb_mat_diag_sum_orb}
|\mathcal{D}_n(q)| = \sum_{D \in \spb_n(q)} \mathopen{|}\orb(D)|.
\end{equation}

%\begin{lemme} Pour $D \in \spb_n(q)$ on a :
%\[
%|\Gamma_D(\GL_n(q))| = \frac{\mathopen{|} \GL_n(q)|}{|\mathcal{C}(D)\cap \GL_n(q)|}\]
%où $\mathcal{C}(D) := \{ M \in \mathcal{M}_n(q) : MD = DM\}$ est le commutant de $D$.
%\end{lemme}

\begin{lemme}
Pour $D \in \spb_n(q)$ on a
$\stab(D) = \mathcal{C}(D) \cap \GL_n(q)$ où $\mathcal{C}(D) := \{ M \in \mathcal{M}_n(q) : MD = DM\}$ est le commutant de $D$.
\end{lemme}

%\begin{proof}
%En réalité, on va montrer que $\Gamma_D$ induit une bijection de $\GL_n(q) / (\mathcal{C}(D) \cap \GL_n(q))$ sur son image. Comme $\mathcal{C}(D) \cap \GL_n(q)$ est un sous-groupe de $\GL_n(q)$ on aura bien la formule annoncée.
%
%Soient $P, Q \in \GL_n(q)$ ; si $\Gamma_D(P) = \Gamma_D(Q)$ alors  $P D P^{-1} = Q D Q^{-1}$ donc $D P^{-1}Q = P^{-1} Q D$ d'où $P^{-1}Q \in \mathcal{C}(D)$. Comme $P$ et $Q$ sont inversibles, on a $P^{-1}Q \in \mathcal{C}(D) \cap \GL_n(q)$ ; de plus, on a juste à remonter les calculs pour vérifier la réciproque. Ainsi, l'application induite par $\Gamma_D$ sur $\GL_n(q) / (\mathcal{C}(D) \cap \GL_n(q))$ est bien définie, injective et a même image que $\Gamma_D$ ce qui termine la démonstration.
%\end{proof}

\begin{proof}
Soit $P \in \mathcal{M}_n(q)$ ; on a $P \in \stab(D) \ssi P \in \GL_n(q)$ et $PDP^{-1} = D \ssi P \in \GL_n(q)$ et $PD = DP \ssi P \in \GL_n(q) \cap \mathcal{C}(D)$.
\end{proof}

D'après l'équation $(\ref{eq_ann:nb_mat_diag_sum_orb})$ et la relation orbite--stabilisateur, il reste donc plus qu'à déterminer |$\mathcal{C}(D)\cap \GL_n(q)|$.

\begin{lemme}
Pour $D = \diag {(\lambda_i I_{m_i})}_{1 \leqslant i \leqslant r} \in \spb_n(q)$ (avec les $\lambda_i$ deux à deux distincts) on a la formule suivante :
\[
|\mathcal{C}(D) \cap \GL_n(q) | = \prod_{i = 1}^r \mathopen{|} \GL_{m_i}(q) |.
\]
\end{lemme}

%\begin{proof}
%Soit $D = \diag{(\lambda_i I_{m_i})}_{1 \leqslant i \leqslant r} \in \spb_n(q)$ avec les $\lambda_i$ deux à deux distincts ; soit $R \in \mathcal{M}_n(q)$ que l'on écrit par blocs $R = (R_{ij})_{1 \leqslant i,j \leqslant r}$ avec $R_{ij} \in \mathcal{M}_{m_i, m_j}(q)$ pour $i \leqslant j$ et $R_{ij} \in \mathcal{M}_{m_j, m_i}(q)$ pour $i > j$ (faire un dessin) ; en particulier, $R_{ii} \in \mathcal{M}_{m_i}(q)$. Multiplier à gauche par une matrice diagonale revient à multiplier les lignes donc la ligne $i$ de $DR$ est $(\lambda_i R_{i1} \cdots \lambda_i R_{ir})$ ; de même, multiplier à droite par une matrice diagonale revient à multiplier les colonnes donc la ligne $i$ de $RD$ s'écrit $(\lambda_1 R_{i1} \cdots \lambda_r R_{ir})$. Ainsi, si $R \in \mathcal{C}(D)$ on a $DR = RD$ donc par ce qui précède :
%\[
%\lambda_i R_{ij} = \lambda_j R_{ij}\text{ } \forall i, j \in  \{ 1, \dots, r\}.\]
%Étant donné que les $\lambda_i$ dont deux à deux distincts, on en déduit :
%\[\forall i \neq j, R_{ij} = 0.\] On n'obtient pas de condition sur les blocs diagonaux $R_{ii}$ : si l'on cherche $R$ dans $\GL_n(q)$ on a néanmoins $R_{ii} \in \GL_{m_i}(q)$ (car $\det R = \prod \det R_{ii}$). Réciproquement, on vérifie que les matrices de la forme $\diag(R_{ii})_{1 \leqslant i \leqslant r}$ avec $R_{ii} \in \GL_{m_i}(q)$ sont dans $\mathcal{C}(D) \cap \GL_n(q)$. Ainsi, $\mathcal{C}(D) \cap \GL_n(q)$ est en bijection avec $\prod_{i = 1}^r \GL_{m_i}(q)$ ce qui achève la démonstration.
%\end{proof}

\begin{proof}
Soit $D$ comme dans l'énoncé et soit $P \in \mathcal{C}(D)$. Comme $D$ et $P$ commutent, les sous-espaces propres de $D$ sont stables par $P$, autrement dit $P$ est de la forme $P = {\diag(P_i)}_{1 \leqslant
i \leqslant r}$ avec $P_i \in \mathcal{M}_{m_i}(q)$. Réciproquement, on vérifie que si $P$ est de cette forme alors $P \in \mathcal{C}(D)$. Finalement, pour avoir $P \in \GL_n(q)$ il faut et il suffit de choisir chaque $P_i$ dans $\GL_{m_i}(q)$, ce qui conclut la preuve.
\end{proof}

\begin{proof}[Démonstration du théorème]
Par les lemmes précédents et la relation orbite--stabilisateur on obtient :
\[
|\mathcal{D}_n(q)| = \sum_{D \in \spb_n(q)} \frac{\mathopen{|} \GL_n(q)|}{\prod_{i = 1}^r \mathopen{|} \GL_{m_i}(q)|} 
\]
où l'on écrit les matrices $D \in \spb_n(q)$ sous une forme $D = \diag(\lambda_i I_{m_i})$ avec les $\lambda_i \in \mathbb{F}_q$ deux à deux distincts.
Le but est maintenant de réindexer la somme ; en particulier, la description actuelle n'est pas la plus adaptée car les valeurs propres des matrices $D$ n'interviennent pas. On se souvient que, par construction, $\spb_n(q)$ est en bijection avec l'ensemble des polynômes unitaires scindés sur $\mathbb{F}_q$ de degré $n$ ; or, ce dernier ensemble est lui-même en bijection avec l'ensemble des $q$-uplets $(m_1, \dots, m_q) \in \mathbb{N}^q$ de somme $n$. En effet, en écrivant $\mathbb{F}_q =: \{\mu_1, \dots, \mu_q\}$ l'application qui à un $q$-uplet $(m_1, \dots, m_q)$ de somme $n$ associe le polynôme $\prod_{i = 1}^q (X - \mu_i)^{m_i}$ est une bijection sur les polynômes unitaires scindés sur $\mathbb{F}_q$ de degré $n$. On obtient alors la forme énoncée dans le théorème.
\end{proof}


\begin{remarque}
On peut réécrire le résultat sous la forme :
\[
|\mathcal{D}_n(q)| = \sum_{\substack{m_1 \leqslant \dots \leqslant m_q \in \mathbb{N} \\ m_1 + \dots + m_q = n}} {q \choose \nu_0(m),\dots, \nu_n(m)} \frac{\mathopen{|} \GL_n(q)|}{\prod_{i = 1}^q \mathopen{|} \GL_{m_i}(q)|} 
\]
où :
\begin{itemize}
\item $\nu_i(m) := |\{j \in \{1, \dots, q\} : m_j = i\}|$ ;
\item ${a \choose b_0,\dots, b_n} := \frac{a!}{b_0!\cdots b_n!}$ est le coefficient multinomial.
\end{itemize}

En effet, une fois qu'un $q$-uplet $m = (m_1, \dots, m_q)$ est fixé alors on peut générer directement plusieurs polynômes scindés de degré $n$ (\textit{i.e.} pas seulement $\prod (X - \mu_i)^{m_i}$) ; par exemple avec $q = 3$, le couple $(0, 1, 1)$ peut aussi bien représenter $X(X-1)$ que $X(X - 2)$ ou encore $(X - 1)(X - 2)$. Le nombre de polynômes que l'on peut générer à partir d'un $q$-uplet $m$ est alors ${q \choose \nu_0}{q - \nu_0 \choose \nu_1} \cdots {q - \nu_0 - \dots - \nu_{i - 1} \choose \nu_n} = \frac{q!}{\nu_0! (q - \nu_0)!} \frac{(q - \nu_0)!}{\nu_1! (q - \nu_0 - \nu_1)!} \cdots \frac{(q - \nu_0 - \dots - \nu_{i - 1})!}{\nu_n! 0!} = \frac{q!}{\nu_0 ! \nu_1 ! \cdots \nu_n !}$ qui est bien le coefficient multinomial qui apparaît.
\end{remarque}

\end{document}