Trigonalisation stricte par permutation

Résolution.

Nous allons démontrer ce résultat par récurrence sur l'entier $n \ge 1$.

Initialisation : Pour $n=1$, la matrice $M$ est réduite à un seul coefficient $(m_{1,1})$. L'hypothèse appliquée à $I=\{1\}$ impose que la matrice $(m_{1,1})$ est non inversible, donc $m_{1,1} = 0$. La matrice est bien strictement triangulaire supérieure.

Hérédité : Soit $n > 1$. Supposons que la propriété soit vraie pour toute matrice de taille $n-1$. Considérons $M \in \mathcal{M}_n(\mathbb{K})$ vérifiant les hypothèses.

Montrons d'abord qu'il existe au moins une ligne de $M$ qui est nulle. Supposons par l'absurde que chaque ligne de $M$ contienne au moins un coefficient non nul.

1. Pour chaque $i \in \{1, \dots, n\}$, il existe un indice $j \in \{1, \dots, n\}$ tel que $m_{i,j} \neq 0$. Remarquons que pour tout $i$, $m_{i,i}=0$ d'après l'hypothèse appliquée à $I=\{i\}$ (sous-matrice de taille 1). Ainsi, pour tout $i$, il existe $j \neq i$ tel que $m_{i,j} \neq 0$.

2. On peut donc construire une suite d'indices $(i_k)_{k \in \mathbb{N}}$ telle que pour tout $k$, $m_{i_k, i_{k+1}} \neq 0$. Comme l'ensemble des indices est fini, cette suite finit par boucler, créant ainsi un cycle dans le graphe de la matrice.

3. Soit $\gamma = (j_1, j_2, \dots, j_k, j_1)$ un cycle de longueur **minimale** $k$ dans ce graphe (avec $k \ge 2$ car les $m_{i,i}$ sont nuls). Par minimalité du cycle, pour tous indices distincts $a, b \in \{1, \dots, k\}$, le coefficient $m_{j_a, j_b}$ est non nul **si et seulement si** $b$ est le successeur de $a$ dans le cycle ($b \equiv a+1 \pmod k$).

4. En effet, s'il existait une "corde" dans le cycle (un $m_{j_a, j_b} \neq 0$ avec $b$ non successeur de $a$), on pourrait extraire un cycle plus court, ce qui contredirait la minimalité de $k$.

5. Considérons alors la sous-matrice principale $M_I$ associée à l'ensemble d'indices $I = \{j_1, \dots, j_k\}$. Quitte à renuméroter, cette matrice est de la forme :
   $$M_I = \begin{pmatrix} 0 & m_{j_1, j_2} & 0 & \dots & 0$$
   0 & 0 & m_{j_2, j_3} & \dots & 0
   \vdots & \vdots & \ddots & \ddots & \vdots
   0 & 0 & \dots & 0 & m_{j_{k-1}, j_k}
   m_{j_k, j_1} & 0 & \dots & 0 & 0 \end{pmatrix}

6. Le déterminant de cette matrice se calcule aisément (par exemple par développement selon la première colonne ou via la formule de Leibniz) :
   $$\det(M_I) = (-1)^{k+1} \prod_{a=1}^k m_{j_a, j_{a+1}}$$
   Comme chaque facteur du produit est non nul, on en déduit :
   $$\boxed{\det(M_I) \neq 0}$$
   Ceci contredit l'hypothèse stipulant que toute sous-matrice principale est non inversible.

Il existe donc un indice $i_0 \in \{1, \dots, n\}$ tel que la $i_0$-ème ligne de $M$ soit nulle.

Soit $\tau \in \mathcal{S}_n$ une permutation qui échange $i_0$ et $n$. La matrice $M' = P_{\tau} M P_{\tau}^{-1}$ possède sa dernière ligne nulle. Elle est de la forme :

où $A \in \mathcal{M}_{n-1}(\mathbb{K})$ est une sous-matrice principale de $M'$ (et donc de $M$).

Toute sous-matrice principale de $A$ est aussi une sous-matrice principale de $M$, donc elle est non inversible. Par hypothèse de récurrence, il existe $\sigma' \in \mathcal{S}_{n-1}$ telle que $P_{\sigma'} A P_{\sigma'}^{-1}$ soit strictement triangulaire supérieure.

En posant $\sigma$ la permutation de $\{1, \dots, n\}$ qui agit comme $\sigma'$ sur $\{1, \dots, n-1\}$ et fixe $n$, la matrice $P_{\sigma} M' P_{\sigma}^{-1}$ est strictement triangulaire supérieure. Par composition des permutations, on obtient le résultat souhaité.