Cours et exercices corrigés de terminale : Calcul matriciel, graphes et chaînes de Markov

1. Produit matriciel et matrice inverse

• Le produit matriciel $A \times B$ n'est possible que si le nombre de colonnes de $A$ égale le nombre de lignes de $B$. En général, $AB \neq BA$ (non-commutativité).
• Inverse d'une matrice $2 \times 2$ : pour $A = \begin{pmatrix} a & b \\ c & d \end{pmatrix}$, si $\det(A) = ad - bc \neq 0$, alors :

$$A^{-1} = \frac{1}{ad - bc} \begin{pmatrix} d & -b \\ -c & a \end{pmatrix}$$

2. Chaînes de Markov et distribution stationnaire

• Soit $P$ la matrice de transition d'un graphe probabiliste. Si $\pi_n$ désigne la matrice ligne des probabilités des états au rang $n$, alors $\pi_{n+1} = \pi_n P$ et $\pi_n = \pi_0 P^n$.
• Un état stable (ou distribution stationnaire) est une matrice ligne $\pi = (x \quad y)$ telle que $\pi P = \pi$ avec $x + y = 1$.

3. Graphes et matrice d'adjacence

• Un graphe est formé de sommets reliés par des arêtes (orientées ou non). L'ordre est le nombre de sommets ; le degré d'un sommet est le nombre d'arêtes dont il est une extrémité (pour un graphe non orienté).
• Une chaîne (ou chemin) de longueur $n$ est une suite de $n$ arêtes consécutives ; un graphe est connexe si deux sommets quelconques sont reliés par une chaîne ; il est complet si tous ses sommets sont adjacents deux à deux.
• La matrice d'adjacence $A$ d'un graphe d'ordre $p$ est la matrice carrée dont le coefficient $a_{ij}$ est le nombre d'arêtes allant du sommet $i$ au sommet $j$.
• Théorème : le coefficient $(i, j)$ de $A^n$ est le nombre de chemins de longueur $n$ allant de $i$ à $j$.

4. Chaînes de Markov

• Une chaîne de Markov sur un ensemble fini d'états est une suite de variables aléatoires $(X_n)$ telle que la probabilité de passer de l'état $i$ à l'état $j$, $p_{ij} = P_{\{X_n = i\}}(X_{n+1} = j)$, ne dépend ni de $n$ ni des états antérieurs.
• La matrice de transition $P = (p_{ij})$ est stochastique : coefficients positifs, somme de chaque ligne égale à $1$.
• Si $\pi_n$ est la matrice ligne de la loi de $X_n$, alors $\pi_{n+1} = \pi_n P$ et $\pi_n = \pi_0 P^n$.
• Cas de deux états : si $P = \begin{pmatrix} 1 - a & a \\ b & 1 - b \end{pmatrix}$ avec $0 < a + b < 2$, la suite $(\pi_n)$ converge vers l'unique distribution invariante $\pi = \left(\dfrac{b}{a + b} \quad \dfrac{a}{a + b}\right)$, quelle que soit la loi initiale.

5. Suites de matrices

• Si $U_{n+1} = AU_n$ (avec $U_n$ matrice colonne), alors $U_n = A^n U_0$ par récurrence.
• Si $U_{n+1} = AU_n + B$ et si $C$ vérifie $C = AC + B$, alors $V_n = U_n - C$ vérifie $V_{n+1} = AV_n$, donc $U_n = A^n(U_0 - C) + C$.
• Puissances d'une matrice diagonale : $\begin{pmatrix} a & 0 \\ 0 & b \end{pmatrix}^n = \begin{pmatrix} a^n & 0 \\ 0 & b^n \end{pmatrix}$. Si $A = QDQ^{-1}$ avec $D$ diagonale, alors $A^n = QD^nQ^{-1}$.

6. Démonstration : nombre de chemins de longueur $n$

On note $a_{ij}^{(n)}$ le coefficient $(i, j)$ de $A^n$ et on raisonne par récurrence sur $n \ge 1$.

• Initialisation : pour $n = 1$, $a_{ij}$ est le nombre d'arêtes, c'est-à-dire de chemins de longueur $1$, de $i$ à $j$.
• Hérédité : supposons la propriété vraie au rang $n$. Un chemin de longueur $n + 1$ de $i$ à $j$ se décompose de façon unique en un chemin de longueur $n$ de $i$ à un sommet $k$, suivi d'une arête de $k$ à $j$. Pour $k$ fixé, il y en a $a_{ik}^{(n)} \times a_{kj}$ (principe multiplicatif) ; en additionnant sur tous les sommets $k$ (cas disjoints), le nombre de chemins est

$$\sum_{k=1}^{p} a_{ik}^{(n)}\, a_{kj}$$
C'est exactement le coefficient $(i, j)$ du produit $A^n \times A = A^{n+1}$.

• Conclusion : pour tout $n \ge 1$, le coefficient $(i, j)$ de $A^n$ est le nombre de chemins de longueur $n$ de $i$ à $j$.

7. Démonstration : distribution après $n$ transitions d'une chaîne de Markov

• Une transition : d'après la formule des probabilités totales, pour chaque état $j$,

$$P(X_{n+1} = j) = \sum_{i} P(X_n = i) \times p_{ij}$$
ce qui s'écrit matriciellement $\pi_{n+1} = \pi_n P$.

• Récurrence : $\pi_0 = \pi_0 P^0$ et, si $\pi_n = \pi_0 P^n$, alors $\pi_{n+1} = \pi_n P = \pi_0 P^{n+1}$. Donc $\pi_n = \pi_0 P^n$ pour tout $n \in \mathbb{N}$.
• Interprétation de $P^n$ : si l'on part de l'état $i$ (distribution initiale avec un $1$ en position $i$ et des $0$ ailleurs), $\pi_n$ est la ligne $i$ de $P^n$. Le coefficient $(i, j)$ de $P^n$ est donc la probabilité de passer de l'état $i$ à l'état $j$ en $n$ transitions.

8. Matrices et transformations du plan

Une transformation du plan qui s'écrit $\begin{pmatrix} x' \\ y' \end{pmatrix} = A\begin{pmatrix} x \\ y \end{pmatrix}$ est représentée par la matrice $A$. Exemples :

• rotation de centre $O$ et d'angle $\theta$ : $A = \begin{pmatrix} \cos\theta & -\sin\theta \\ \sin\theta & \cos\theta \end{pmatrix}$ ; pour $\theta = \frac{\pi}{2}$, le point $(1 ; 0)$ a pour image $(0 ; 1)$ ;
• homothétie de centre $O$ et de rapport $k$ : $A = \begin{pmatrix} k & 0 \\ 0 & k \end{pmatrix}$ ;
• symétrie par rapport à l'axe des abscisses : $A = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}$.

Appliquer la transformation de matrice $A$, puis celle de matrice $B$, revient à appliquer la transformation de matrice $BA$.