Dénombrement d'endomorphismes sur un corps fini

Soit $\mathbb{K}$ un corps fini de cardinal $q$ . On considère $E$ un $\mathbb{K}$ -espace vectoriel de dimension $n \in \mathbb{N}^*$ . On note $\mathcal{L}(E)$ l'ensemble des endomorphismes de $E$ .

Déterminer le cardinal du groupe des automorphismes de $E$ , noté $GL(E)$ . Dans la suite, on posera $w_n = |GL(E)| = \prod_{k=0}^{n-1} (q^n - q^k)$ pour $n \geq 1$ , et $w_0 = 1$ .
Soit $u \in \mathcal{L}(E)$ $u \in L (E)$ .
1. Montrer qu'il existe une unique décomposition $E = F \oplus G$ telle que $F$ et $G$ soient stables par $u$ , la restriction $u_{|F}$ soit un automorphisme de $F$ et la restriction $u_{|G}$ soit un endomorphisme nilpotent de $G$ .
2. Pour $0 \leq r \leq n$ , déterminer le nombre de couples $(F, G)$ de sous-espaces de $E$ tels que $E = F \oplus G$ avec $\dim F = r$ .
On note $\nu_n$ $ν_{n}$ le nombre d'endomorphismes nilpotents de $E$ $E$ .
1. En utilisant la décomposition de la question 2, établir la relation : $q^{n^2} = \sum_{r=0}^n \frac{w_n}{w_r} \nu_{n-r}$
2. À l'aide d'un raisonnement par récurrence, en déduire que pour tout $n \in \mathbb{N}^*$ : $\nu_n = q^{n^2-n}$

1.

Pour dénombrer $GL(E)$ , dénombrer les bases de $E$ en choisissant les vecteurs les uns après les autres.

2.

Pour la décomposition (lemme de Fitting), considérer les suites $\ker(u^k)$ et $\text{im}(u^k)$ . Elles stationnent dès l'indice $n$ .

3.

Pour le dénombrement des décompositions $E=F \oplus G$ , compter les bases de $E$ dont les $r$ premiers vecteurs engendrent $F$ et les $n-r$ suivants engendrent $G$ .

4.

Pour la relation combinatoire, classer les endomorphismes selon la dimension de leur "partie inversible".

Idées clés

•

Dénombrement de bases dans un espace vectoriel sur un corps fini.

•

Lemme de Fitting : décomposition d'un endomorphisme en parties inversible et nilpotente.

•

Relation de récurrence sur les cardinaux.

Résolution.

Un endomorphisme de $E$ $E$ est inversible si et seulement si l'image d'une base est une base. Le nombre d'automorphismes est donc le nombre de bases $(e_1, \dots, e_n)$ $(e_{1}, \dots, e_{n})$ de $E$ $E$ . Pour construire une base :
- Le vecteur $e_1$ peut être n'importe quel vecteur non nul : $q^n - 1$ choix.
- Le vecteur $e_2$ doit être hors de $\text{Vect}(e_1)$ , qui contient $q$ vecteurs : $q^n - q$ choix.
- De manière générale, $e_k$ doit être choisi hors de $\text{Vect}(e_1, \dots, e_{k-1})$ , espace de dimension $k-1$ contenant $q^{k-1}$ vecteurs : $q^n - q^{k-1}$ choix.
En multipliant ces choix indépendants, on obtient :
$\boxed{w_n = |GL(E)| = \prod_{k=0}^{n-1} (q^n - q^k)}$
1. Existence : Considérons les suites de sous-espaces $K_k = \ker(u^k)$ et $I_k = \text{im}(u^k)$ . La suite $(K_k)$ est croissante au sens de l'inclusion et $(I_k)$ est décroissante. Comme $\dim E = n$ , ces suites stationnent au plus tard à l'indice $n$ . D'après le lemme de Fitting, on a $E = \ker(u^n) \oplus \text{im}(u^n)$ . Posons $G = \ker(u^n)$ et $F = \text{im}(u^n)$ . Ces espaces sont stables par $u$ . $u_{|G}$ est nilpotent car $(u_{|G})^n = 0$ . $u_{|F}$ est un endomorphisme de $F$ qui est surjectif (car $u(I_n) = I_{n+1} = I_n$ ), donc c'est un automorphisme. Unicité : Si $E = F \oplus G$ convient, alors pour tout $k \geq n$ , $G \subset \ker(u^k) = \ker(u^n)$ et $F = \text{im}(u^k) = \text{im}(u^n)$ par les propriétés de nilpotence et d'inversibilité des restrictions. D'où $G = \ker(u^n)$ et $F = \text{im}(u^n)$ .
2. Pour fixer une décomposition $E = F \oplus G$ avec $\dim F = r$ , on peut compter le nombre de bases $(e_1, \dots, e_n)$ dont les $r$ premiers vecteurs forment une base de $F$ et les $n-r$ suivants une base de $G$ . Il y a $w_n$ bases de $E$ . Pour un couple $(F, G)$ fixé, il y a $w_r$ bases de $F$ et $w_{n-r}$ bases de $G$ . Le nombre de couples $(F, G)$ est donc : $\boxed{N_{r, n-r} = \frac{w_n}{w_r w_{n-r}}}$
1. Tout endomorphisme $u \in \mathcal{L}(E)$ $u \in L (E)$ est uniquement déterminé par :
  - Le choix d'une décomposition $E = F \oplus G$ (soit $r = \dim F$ ).
  - Le choix d'un automorphisme $u_{|F} \in GL(F)$ .
  - Le choix d'un endomorphisme nilpotent $u_{|G} \in Nilp(G)$ .
  Le nombre total d'endomorphismes est $|\mathcal{L}(E)| = q^{n^2}$ $∣ L (E) ∣ = q^{n^{2}}$ . En sommant sur les dimensions possibles de $F$ $F$ :
  $q^{n^2} = \sum_{r=0}^n N_{r, n-r} \times w_r \times \nu_{n-r}$
  En remplaçant $N_{r, n-r}$ $N_{r, n - r}$ par sa valeur :
  $\boxed{q^{n^2} = \sum_{r=0}^n \frac{w_n}{w_r w_{n-r}} w_r \nu_{n-r} = \sum_{r=0}^n \frac{w_n}{w_{n-r}} \nu_{n-r}}$
  Ce qui se réécrit, par changement d'indice $j = n-r$ $j = n - r$ :
  $q^{n^2} = \sum_{j=0}^n \frac{w_n}{w_j} \nu_j$
2. On procède par récurrence sur $n$ . Pour $n=1$ , $q^1 = \frac{w_1}{w_0} \nu_0 + \frac{w_1}{w_1} \nu_1 = (q-1) \cdot 1 + 1 \cdot \nu_1$ , donc $\nu_1 = 1 = q^{1^2-1}$ . Supposons $\nu_k = q^{k^2-k}$ pour tout $k < n$ . La relation devient : $q^{n^2} = \nu_n + \sum_{j=0}^{n-1} \frac{w_n}{w_j} q^{j^2-j}$ Remarquons que $\frac{w_n}{w_j} = \frac{w_n}{w_{n-1}} \cdot \frac{w_{n-1}}{w_j} = q^{n-1}(q^n-1) \frac{w_{n-1}}{w_j}$ . Alors : $\sum_{j=0}^{n-1} \frac{w_n}{w_j} q^{j^2-j} = q^{n-1}(q^n-1) \sum_{j=0}^{n-1} \frac{w_{n-1}}{w_j} \nu_j$ D'après la relation au rang $n-1$ , cette somme vaut $q^{(n-1)^2}$ . Ainsi : $q^{n^2} = \nu_n + q^{n-1}(q^n-1) q^{n^2-2n+1} = \nu_n + (q^n-1) q^{n^2-n} = \nu_n + q^{n^2} - q^{n^2-n}$ Après simplification, on obtient bien : $\boxed{\nu_n = q^{n^2-n}}$

Attention à l'unicité dans le lemme de Fitting : les sous-espaces $F$ et $G$ sont uniques pour un endomorphisme $u$ donné, ce qui permet de sommer sur les décompositions sans double comptage.