Propriétés des matrices stochastiques

Résolution.

1. Structure de $S$
   1. Soit $U = \begin{pmatrix} 1$
      \vdots
      1 \end{pmatrix} \in \mathcal{M}_{n,1}(\mathbb{R}). Pour toute matrice $A \in S$, le $i$-ème coefficient du produit $AU$ est donné par :
      $$(AU)_i = \sum_{j=1}^n a_{i,j} \cdot 1 = 1$$
      On en déduit immédiatement que $AU = U$.
      $$\boxed{ \text{Toutes les matrices de } S \text{ admettent } 1 \text{ comme valeur propre pour le vecteur propre commun } U. }$$

   2. Soient $A, B \in S$ et $t \in [0, 1]$. Posons $C = tA + (1-t)B$. Puisque $t \ge 0$, $1-t \ge 0$ et que les coefficients de $A$ et $B$ sont positifs, on a $c_{i,j} = t a_{i,j} + (1-t) b_{i,j} \ge 0$. De plus, pour tout $i \in \llbracket 1, n \rrbracket$ :
      $$\sum_{j=1}^n c_{i,j} = t \sum_{j=1}^n a_{i,j} + (1-t) \sum_{j=1}^n b_{i,j} = t(1) + (1-t)(1) = 1$$
      \boxed{ S \text{ est donc un ensemble convexe.} }

   3. Soient $A, B \in S$. Posons $C = AB$. Les coefficients de $C$ sont $c_{i,j} = \sum_{k=1}^n a_{i,k} b_{k,j}$. Comme sommes et produits de réels positifs, on a $c_{i,j} \ge 0$. Vérifions la somme des lignes :
      $$\sum_{j=1}^n c_{i,j} = \sum_{j=1}^n \sum_{k=1}^n a_{i,k} b_{k,j} = \sum_{k=1}^n a_{i,k} \left( \sum_{j=1}^n b_{k,j} \right) = \sum_{k=1}^n a_{i,k} \cdot 1 = 1$$
      \boxed{ S \text{ est stable par produit.} }

2. Localisation du spectre
   1. Soit $X = (x_1, \dots, x_n)^T \in \mathbb{C}^n$ un vecteur propre non nul associé à $\lambda$. Soit $i_0 \in \llbracket 1, n \rrbracket$ tel que $|x_{i_0}| = \max_{j} |x_j|$. Comme $X \neq 0$, on a $|x_{i_0}| > 0$. L'égalité $AX = \lambda X$ donne à la ligne $i_0$ : $\lambda x_{i_0} = \sum_{j=1}^n a_{i_0,j} x_j$. En passant au module et en utilisant l'inégalité triangulaire :
      $$|\lambda| |x_{i_0}| \le \sum_{j=1}^n a_{i_0,j} |x_j| \le \left( \sum_{j=1}^n a_{i_0,j} \right) |x_{i_0}| = 1 \cdot |x_{i_0}|$$
      En simplifiant par $|x_{i_0}| > 0$, on obtient :
      $$\boxed{ |\lambda| \le 1 }$$

   2. Le déterminant est le produit des valeurs propres comptées avec multiplicité dans $\mathbb{C}$. Puisque pour chaque valeur propre $\lambda_i$, on a $|\lambda_i| \le 1$, alors :
      $$|\det(A)| = \left| \prod_{i=1}^n \lambda_i \right| = \prod_{i=1}^n |\lambda_i| \le 1^n$$
      $$\boxed{ |\det(A)| \le 1 }$$

3. Cas des coefficients strictement positifs
   1. Supposons $|\lambda| = 1$. Reprenons l'inégalité de la question 2(a) avec $|x_{i_0}|=1$ :
      $$1 = |\lambda x_{i_0}| = \left| \sum_{j=1}^n a_{i_0,j} x_j \right| \le \sum_{j=1}^n a_{i_0,j} |x_j| \le \sum_{j=1}^n a_{i_0,j} = 1$$
      Toutes les inégalités sont des égalités. En particulier, $\sum a_{i_0,j} |x_j| = \sum a_{i_0,j}$. Comme $a_{i_0,j} > 0$, cela impose $|x_j| = 1$ pour tout $j$. Ensuite, le cas d'égalité dans l'inégalité triangulaire $\left| \sum a_{i_0,j} x_j \right| = \sum a_{i_0,j} |x_j|$ avec $a_{i_0,j} > 0$ implique que tous les nombres complexes $x_j$ ont le même argument. Comme ils ont tous le même module ($|x_j|=1$) et le même argument, ils sont tous égaux : $x_1 = x_2 = \dots = x_n = x_{i_0}$. Alors $X = x_{i_0} U$, d'où $AX = x_{i_0} AU = x_{i_0} U = X$. Ainsi $\lambda X = X$, et comme $X \neq 0$, on en conclut :
      $$\boxed{ \lambda = 1 }$$

   2. Nous venons de montrer que si $AX = X$, alors $X \in \text{Vect}(U)$. Le sous-espace propre $E_1(A) = \text{Ker}(A - I_n)$ est donc la droite vectorielle engendrée par $U$.
      $$\boxed{ \dim(\text{Ker}(A - I_n)) = 1 }$$

4. Cas d'égalité du déterminant
   1. Si $|\det A|=1$, alors toutes les valeurs propres complexes de $A$ sont de module 1. L'ensemble $S$ est fermé (défini par des inégalités larges et des égalités) et borné (coefficients entre 0 et 1), donc $S$ est un compact de $\mathcal{M}_n(\mathbb{R})$. Puisque $S$ est stable par produit, pour tout $k \in \mathbb{N}$, $A^k \in S$. La suite $(A^k)_{k \in \mathbb{N}}$ est donc bornée. Si $A$ avait une valeur propre $\lambda$ (de module 1) dont le bloc de Jordan associé était de taille $>1$, la suite $(A^k)$ ne serait pas bornée (croissance polynomiale en $k$). Ainsi $A$ est diagonalisable dans $\mathbb{C}$. Par ailleurs, $|\det A| \neq 0$ implique que pour chaque ligne $i$, il existe au moins un $j$ tel que $a_{i,j} > 0$. L'argument de la source suggère l'existence d'une permutation $\sigma$ telle que $a_{i,\sigma(i)} > 0$. En supposant quitte à permuter que $a_{i,i} > 0$, l'étude du cas d'égalité précédent montre que les valeurs propres de module 1 sont nécessairement 1 si la matrice est "assez remplie". Plus rigoureusement, une matrice stochastique de déterminant 1 ou -1 est une matrice de permutation. En effet, chaque ligne est un vecteur du simplexe. Pour que le produit des modules des valeurs propres soit 1 alors que la trace est bornée, les lignes doivent être des vecteurs de la base canonique (points extrémaux) et la matrice doit être inversible.
      $$\boxed{ A \text{ est une matrice de permutation.} }$$

   2. Oui. Une matrice de permutation $P_\sigma$ a pour déterminant $\varepsilon(\sigma) \in \{-1, 1\}$.
      $$\boxed{ |\det(P_\sigma)| = 1 }$$

5. Étude géométrique de $S$
   1. Si $a_{i,j} \in \{0, 1\}$, la condition $\sum_{j=1}^n a_{i,j} = 1$ impose que sur chaque ligne $i$, il y a exactement un coefficient égal à $1$ et tous les autres sont nuls.
      $$\boxed{ \text{Ce sont les matrices possédant un unique 1 par ligne.} }$$

   2. Soit $A$ une matrice telle que chaque ligne possède un unique 1. Supposons $A = \frac{1}{2}(B+C)$ avec $B, C \in S$. Pour chaque ligne $i$, soit $j_0$ tel que $a_{i,j_0} = 1$. Alors $1 = \frac{1}{2}(b_{i,j_0} + c_{i,j_0})$. Comme $b_{i,j_0} \le 1$ et $c_{i,j_0} \le 1$, on a nécessairement $b_{i,j_0} = 1$ et $c_{i,j_0} = 1$. Comme la somme des coefficients d'une ligne vaut 1, tous les autres coefficients des lignes $i$ de $B$ et $C$ sont nuls. Donc $B = C = A$. $A$ est un point extrémal. Réciproquement, si une ligne $i$ de $A$ possède au moins deux coefficients strictement positifs $a_{i,j_1}$ et $a_{i,j_2}$, on peut construire de petites perturbations conservant la somme égale à 1, prouvant que $A$ n'est pas extrémal.
      $$\boxed{ \text{Les points extrémaux sont les matrices ayant un seul 1 par ligne.} }$$