Exo Maths X MP #8 - Propriétés des matrices stochastiques

Exos Maths X MP

Publié

Révisé

October 16, 2020

Il y a 4 années

Exercice d'oral de maths de Polytechnique filière MP tombé en 2018.

On dit qu'une matrice carrée réelle $P$ est stochastique si ses coefficients sont positifs et si la somme des coefficients de chaque colonne vaut $1$ .

1. Montrer que $1$ est valeur propre de $P$ , puis que son spectre est inclus dans le disque de centre $min_{1 \leq i \leq n} p_{i i}$ et de rayon $1 - min_{1 \leq i \leq n} p_{i i}$ .

2. On suppose que $min_{1 \leq i \leq n} p_{i i} > 0$ et que $1$ est valeur propre simple. Montrer que $(P^{k})_{k}$ converge vers une matrice stochastique.

Correction

Bravo à Fabien Pourre (MP, Pierre-de-Fermat) et à Jean Wallard (MP*, Louis-le-Grand) d'avoir réussi à résoudre cet exercice de l'X et merci à eux d'avoir rédigé leur correction !

Rejoins le groupe Facebook Exos Maths X MP pour te préparer à l'X.

Remarque préliminaire. Dire que la somme des coefficients de chaque colonne d'une matrice $A$ vaut $1$ équivaut à dire que $A^{T} 1_{n} = 1_{n}$ où $1_{n} = (1, . . ., 1)^{T} \in R^{n}$ .

Question 1

D'après la remarque préliminaire, $P^{T} 1_{n} = 1_{n}$ . Donc $1_{n}$ est valeur propre de $P^{T}$ , et ainsi valeur propre de $P$ .

Soit $λ \in C$ une valeur propre de $P$ , donc de $P^{T}$ . Soit $X = (x_{1}, . . ., x_{n})^{T} \in C^{n}$ un vecteur propre non nul associé à $λ$ . Pour tout $j \in [[1, n]]$ , $\sum_{i = 1}^{n} p_{i j} x_{i} = λ x_{j}$ . Donc :

(λ - p_{j j}) x_{j} = i ∣ i \neq = j \sum p_{i j} x_{i}

On choisit $j$ tel que $∣ x_{j} ∣$ soit maximal, et donc non nul car $X \neq = 0$ . En passant au module et en utilisant l'inégalité triangulaire :

∣ λ - p_{j j} ∣ ∣ x_{j} ∣ \leq i ∣ i \neq = j \sum ∣ p_{i j} ∣ ∣ x_{i} ∣ \leq ⎝ ⎜ ⎛ i ∣ i \neq = j \sum p_{i j} ⎠ ⎟ ⎞ ∣ x_{j} ∣ = (1 - p_{j j}) ∣ x_{j} ∣

Comme $∣ x_{j} ∣ \neq = 0$ , $∣ λ - p_{j j} ∣ \leq (1 - p_{j j})$ . Soit $k$ tel que $p_{k k}$ soit minimal. Alors, en sachant que $p_{j j} - p_{k k} \geq 0$ :

∣ λ - p_{k k} ∣ \leq ∣ λ - p_{j j} ∣ + ∣ p_{j j} - p_{j_{0} j_{0}} ∣ \leq (1 - p_{j j}) + (p_{j j} - p_{j_{0} j_{0}}) = (1 - p_{j_{0} j_{0}})

Donc $λ$ appartient au disque de centre $p_{k k}$ et de rayon $1 - p_{k k}$ et ce pour toute valeur propre complexe $λ$ de $P$ .

Question 2

Supposons que pour tout $i$ , $p_{i i} > 0$ et que $1$ est valeur propre simple de $P$ .

Étape 1 : Si $(P_{k})_{k}$ converge, alors la limite est une matrice stochastique.

Le produit de deux matrices $A$ et $B$ stochastiques est stochastique car $A B$ est à coefficients positifs et $(A B)^{T} 1_{n} = B^{T} A^{T} 1_{n} = 1_{n}$ . Par récurrence, $P^{k}$ est stochastique pour tout $k \in N^{*}$ .

L'ensemble des matrices stochastiques $S$ est fermé car il est l'intersection :

de l'ensemble des matrices à coefficients positifs, fermé,
de $f^{- 1} ({1_{n}})$ avec $f : P \in M_{n} (R) \mapsto P^{T} 1_{n}$ , fermé aussi, car préimage du fermé ${1_{n}}$ par une application continue (linéaire en dimension finie).

Ainsi, $(P_{k})_{k}$ est une suite qui vit dans $S$ , fermé. Donc si $(P_{k})_{k}$ converge, alors sa limite est une matrice stochastique.

Étape 2 : $(P^{k})_{k}$ converge.

Si $λ$ est une valeur propre de $P$ , alors $λ = 1$ ou $∣ λ ∣ < 1$ , car en notant $r = min_{1 \leq i \leq n} p_{i i}$ et en utilisant la question 1 :

$∣ λ - r ∣ \leq 1 - r$ . Par l'inégalité triangulaire, on en déduit que $∣ λ ∣ - r \leq 1 - r$ et donc que $∣ λ ∣ \leq 1$ .
Si $∣ λ ∣ = 1$ , alors $∣ λ - r ∣^{2} - (1 - r)^{2} \leq 0$ équivaut à $2 r (1 - Re (λ)) \leq 0$ équivaut à $Re (λ) = 1$ puisque $r > 0$ par hypothèse. Donc $λ = 1$ .

On en déduit que $(λ^{n})_{n}$ converge soit vers $1$ ou $0$ .

D'après le lemme des noyaux appliqué au polynôme minimal de $P$ :

C^{n} = i = 1 ⨁ p E_{i} Ker (P - λ_{i} I_{n})^{a_{i}}

Comme $1$ est valeur propre simple de $P$ , on peut supposer sans perdre en généralité que $λ_{1} = 1$ , $a_{1} = 1$ et $∣ λ_{i} ∣ < 1$ pour $i > 1$ .

Pour tout $i \in [[1, p]]$ , $P$ est stable sur $E_{i}$ car il commute avec $(P - λ_{i} I_{n})^{a_{i}}$ . On peut donc considérer sa resctriction à $E_{i}$ , notée $P_{∣ i}$ .

Dans le cas $i = 1$ , $P_{∣ 1} = I_{1}$ , donc $(P_{∣ 1}^{k})_{k}$ converge.

Dans le cas $i > 1$ , $P_{∣ i}$ n'a que $λ_{i}$ comme valeur propre. Elle est donc semblable à $λ_{i} I + N$ avec $N$ une matrice triangulaire supérieure stricte donc nilpotente (notons $m$ son ordre). Ainsi :

k \to \infty lim (λ_{i} I + N)^{k} = k \to \infty lim j = 0 \sum m (j k) λ_{i}^{k - j} N^{j} = j = 0 \sum m (k \to \infty lim (j k) λ_{i}^{k - j}) N^{j}

Comme $(j k) \leq k^{j}$ et $∣ λ_{i} ∣ < 1$ , $lim_{k \to \infty} (j k) λ_{i}^{k - j} = 0$ . Donc $((λ_{i} I + N)^{k})_{k}$ converge vers la matrice nulle. Donc $(P_{∣ i}^{k})_{k}$ converge.

Donc $(P^{k})_{k}$ converge.

Exos Maths X MP

Prépare-toi aux oraux de maths de Polytechnique filière MP en résolvant les exercices tombés les années précédentes.