Théorème d'Interclassement

Théorème (Cauchy Interlacing)

Soit $A \in \mathcal{M}_N(\mathbb{C})$ hermitienne, et $B$ une sous-matrice principale de taille $(N-1)\times(N-1)$ obtenue en supprimant la $N$-ième ligne et colonne. Notons $\lambda_1(A) \le \lambda_2(A) \le \cdots \le \lambda_N(A)$ et $\lambda_1(B) \le \cdots \le \lambda_{N-1}(B)$ leurs valeurs propres. Alors :

\lambda_1(A) \;\le\; \lambda_1(B) \;\le\; \lambda_2(A) \;\le\; \lambda_2(B) \;\le\; \cdots \;\le\; \lambda_{N-1}(B) \;\le\; \lambda_N(A)

Les valeurs propres de $B$ s'intercalent entre celles de $A$.

VISUALISATION

L'interclassement en action

Matrice $2\times 2$ hermitienne

Ajuste les paramètres et observe comment $\lambda_1(B)$ s'intercale entre $\lambda_1(A)$ et $\lambda_2(A)$.

$a_{11}$ 2.0

$a_{22}$ 4.0

$|a_{12}|$ 1.0

ÉTAPE 01

Setup : la formule min-max

L'outil central est la formule de Courant-Fischer. Pour $A$ hermitienne de taille $N$ :

\lambda_k(A) = \min_{\substack{S \subset \mathbb{C}^N \\ \dim S = k}} \;\max_{\substack{x \in S \\ x \ne 0}} \frac{x^* A x}{x^* x}

En particulier, pour $k=1$ : $\lambda_1(A) = \min_{x \ne 0} \dfrac{x^* A x}{x^*x}$ est le minimum global du quotient de Rayleigh.

Pourquoi c'est l'outil adapté $B$ est la restriction de $A$ à un sous-espace $E \cong \mathbb{C}^{N-1}$. La formule min-max relie directement les valeurs propres à des optimisations sur des sous-espaces — elle va nous permettre de comparer $A$ et $B$ via leurs espaces respectifs.

On identifie $E = \{x \in \mathbb{C}^N : x_N = 0\}$, de dimension $N-1$. Le quotient de Rayleigh de $B$ vaut $\frac{x^* A x}{x^*x}$ pour $x \in E$ (car $B = A|_E$).

ÉTAPE 02

Inégalité gauche : $\lambda_k(A) \le \lambda_k(B)$

Par la formule min-max :

\lambda_k(A) = \min_{\dim S = k,\; S \subset \mathbb{C}^N} \max_{x \in S \setminus\{0\}} \frac{x^* A x}{x^*x}$$ $$\lambda_k(B) = \min_{\dim S' = k,\; S' \subset E} \max_{x \in S' \setminus\{0\}} \frac{x^* A x}{x^*x}

Dans $\lambda_k(B)$, le minimum est pris sur un ensemble strictement plus petit : seulement les sous-espaces de $E$, pas tous ceux de $\mathbb{C}^N$.

Principe général Restreindre le domaine d'un minimum ne peut qu'augmenter sa valeur (moins de candidats, donc le meilleur est moins bon ou pareil). Formellement : si $\mathcal{F}_1 \supset \mathcal{F}_2$, alors $\min_{\mathcal{F}_1} f \le \min_{\mathcal{F}_2} f$.

Ici : $\{S' \subset E, \dim S'=k\} \subset \{S \subset \mathbb{C}^N, \dim S=k\}$, donc :

\lambda_k(A) \;\le\; \lambda_k(B) \qquad \checkmark

ÉTAPE 03

L'argument clé : comptage de dimensions

Pour l'inégalité droite $\lambda_k(B) \le \lambda_{k+1}(A)$, on a besoin d'un fait géométrique crucial sur les intersections de sous-espaces.

Formule de Grassmann Pour deux sous-espaces $S, E \subset \mathbb{C}^N$ : $$\dim(S \cap E) \ge \dim S + \dim E - N$$

Hover sur les cercles pour explorer — $S$ de dimension $k+1$, $E$ de dimension $N-1$, dans $\mathbb{C}^N$

Application avec $\dim S = k+1$ et $\dim E = N-1$ :

\dim(S \cap E) \;\ge\; (k+1) + (N-1) - N \;=\; k

Donc pour tout sous-espace $S$ de dimension $k+1$ dans $\mathbb{C}^N$, l'intersection $S \cap E$ contient un sous-espace de dimension au moins $k$. En particulier, il existe un sous-espace $S' \subset S \cap E$ avec $\dim S' = k$.

ÉTAPE 04

Inégalité droite : $\lambda_k(B) \le \lambda_{k+1}(A)$

Soit $S$ un sous-espace quelconque de $\mathbb{C}^N$ avec $\dim S = k+1$. Par l'étape précédente, il existe $S' \subset S \cap E$ avec $\dim S' = k$. On chaîne trois inégalités :

\max_{x \in S \setminus\{0\}} \frac{x^* A x}{x^*x} \;\overset{\scriptsize(i)}{\ge}\; \max_{x \in S' \setminus\{0\}} \frac{x^*Ax}{x^*x} \;\overset{\scriptsize(ii)}{\ge}\; \min_{\substack{S'' \subset E \\ \dim S''=k}} \max_{x \in S'' \setminus\{0\}} \frac{x^*Ax}{x^*x} \;=\; \lambda_k(B)

Justification des inégalités

(i)

$S' \subset S$, donc le max sur $S'$ est $\le$ le max sur $S$ — restreindre le domaine d'un maximum le diminue.

(ii)

$S' \subset E$ avec $\dim S' = k$, donc $S'$ est un candidat parmi tous les $S'' \subset E$ de dimension $k$. Le minimum sur tous ces candidats est $\le$ la valeur pour ce candidat particulier.

On vient de montrer que pour tout $S$ de dimension $k+1$, $\max_{x \in S}\frac{x^*Ax}{x^*x} \ge \lambda_k(B)$.

En prenant le minimum sur tous ces $S$ :

\lambda_{k+1}(A) = \min_{\dim S = k+1} \max_{x \in S} \frac{x^*Ax}{x^*x} \;\ge\; \lambda_k(B) \qquad \checkmark

ÉTAPE 05

Conclusion

En combinant les deux inégalités pour tout $k = 1, \ldots, N-1$ :

\lambda_k(A) \;\le\; \lambda_k(B) \;\le\; \lambda_{k+1}(A)

Ce qui donne la chaîne complète :

\lambda_1(A) \le \lambda_1(B) \le \lambda_2(A) \le \lambda_2(B) \le \cdots \le \lambda_{N-1}(B) \le \lambda_N(A)

Intuition géométrique finale Supprimer une dimension force les valeurs propres à se "tasser" : $B$ perd un degré de liberté, donc ses valeurs propres ne peuvent pas toutes être extrêmes — elles doivent s'intercaler entre celles de $A$. C'est une contrainte de compatibilité géométrique entre les espaces propres.

RÉCAPITULATIF

Structure de la preuve

Outil

Formule min-max de Courant-Fischer : $\lambda_k(A) = \min_{\dim S=k}\max_{x\in S}\frac{x^*Ax}{x^*x}$

Clé géom.

Tout $S$ de dim $k+1$ rencontre $E$ de dim $N-1$ en un sous-espace de dim $\ge k$ (formule de Grassmann)

$\lambda_k(A) \le \lambda_k(B)$

Restreindre le domaine d'un min $\nearrow$ la valeur : moins de candidats $\Rightarrow$ min plus grand

$\lambda_k(B) \le \lambda_{k+1}(A)$

Pour tout $S$ de dim $k+1$, il existe $S'\subset S\cap E$ de dim $k$, donc le max sur $S$ domine $\lambda_k(B)$ — prendre le min donne $\lambda_{k+1}(A) \ge \lambda_k(B)$