Graphes et matrices
Ce chapitre fait partie du programme de Terminale.
Les matrices permettent de ranger des nombres en tableau et de calculer avec ces tableaux comme avec des nombres, à quelques précautions près. Elles servent ici à compter des chemins dans un graphe, à calculer les termes de suites couplées et à prévoir l'évolution d'un système aléatoire, les chaînes de Markov.
Prérequis
- Suites géométriques, suites arithmético-géométriques, limite de $q^n$ selon la valeur de $q$
- Raisonnement par récurrence
- Probabilités conditionnelles, arbres pondérés, formule des probabilités totales
- Résolution d'un système linéaire de deux ou trois équations
- Symbole $\sum$ et manipulation de sommes finies
À la fin du chapitre, on sait
- Calculer une somme, un produit de matrices, et savoir que le produit n'est pas commutatif
- Déterminer si une matrice $2\times 2$ est inversible et calculer son inverse
- Résoudre un système linéaire sous la forme $AX=B$
- Calculer la puissance $n$-ième d'une matrice, en particulier à l'aide d'une écriture $A=PDP^{-1}$
- Exprimer le terme général d'une suite définie par $U_{n+1}=AU_n$ ou $U_{n+1}=AU_n+B$
- Utiliser le vocabulaire des graphes : sommet, arête, arc, degré, ordre, chaîne, chemin, graphe complet, graphe connexe
- Écrire la matrice d'adjacence d'un graphe et compter les chemins de longueur $n$ avec $M^n$
- Modéliser une chaîne de Markov à deux ou trois états, écrire sa matrice de transition et calculer $\pi_n=\pi_0P^n$
- Déterminer une distribution invariante et étudier la convergence de la suite des distributions
1.Matrices et calcul matriciel
Matrice
Soient $n$ et $p$ deux entiers naturels non nuls. Une matrice de taille $n\times p$ est un tableau de nombres réels à $n$ lignes et $p$ colonnes. Le coefficient situé à la ligne $i$ et à la colonne $j$ se note $a_{ij}$, et on écrit $A=(a_{ij})$.
L'ensemble de ces matrices se note $\mathcal{M}_{n,p}(\mathbb{R})$.
- Si $n=p$, la matrice est dite carrée d'ordre $n$ ; l'ensemble se note $\mathcal{M}_n(\mathbb{R})$.
- Si $p=1$, c'est une matrice colonne ; si $n=1$, une matrice ligne.
- La matrice nulle a tous ses coefficients égaux à $0$.
- La matrice identité d'ordre $n$, notée $I_n$, est la matrice carrée qui a des $1$ sur la diagonale et des $0$ ailleurs. Par exemple $I_2=\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$.
- Une matrice carrée est diagonale si tous ses coefficients hors de la diagonale sont nuls.
Somme et produit par un réel
Soient $A=(a_{ij})$ et $B=(b_{ij})$ deux matrices de même taille et $\lambda$ un réel.
- La somme $A+B$ est la matrice de coefficients $a_{ij}+b_{ij}$.
- Le produit $\lambda A$ est la matrice de coefficients $\lambda a_{ij}$.
On ne peut pas additionner deux matrices de tailles différentes.
Produit de deux matrices
Soient $A\in\mathcal{M}_{n,p}(\mathbb{R})$ et $B\in\mathcal{M}_{p,q}(\mathbb{R})$ : le nombre de colonnes de $A$ est égal au nombre de lignes de $B$. Le produit $AB$ est la matrice $C\in\mathcal{M}_{n,q}(\mathbb{R})$ de coefficients $$c_{ij}=\sum_{k=1}^{p}a_{ik}b_{kj}=a_{i1}b_{1j}+a_{i2}b_{2j}+\cdots+a_{ip}b_{pj}.$$ Le coefficient $c_{ij}$ s'obtient en combinant la ligne $i$ de $A$ avec la colonne $j$ de $B$ : on multiplie terme à terme et on additionne.
Produit d'une matrice par une colonne
Soient $A=\begin{pmatrix} 1 & 0 & 2 \\ 3 & -1 & 1 \end{pmatrix}$ (taille $2\times 3$) et $X=\begin{pmatrix} 1 \\ 2 \\ -1 \end{pmatrix}$ (taille $3\times 1$). Le produit $AX$ existe et a la taille $2\times 1$ : $$AX=\begin{pmatrix} 1\times 1+0\times 2+2\times(-1) \\ 3\times 1+(-1)\times 2+1\times(-1) \end{pmatrix}=\begin{pmatrix} -1 \\ 0 \end{pmatrix}.$$ Le produit $XA$ n'existe pas : $X$ a $1$ colonne et $A$ a $2$ lignes.
Calculer un produit de matrices
- Vérifier les formats : $(n\times p)\times(p\times q)$ donne $(n\times q)$. Si les nombres « intérieurs » diffèrent, le produit n'existe pas.
- Pour chaque case $(i,j)$ du résultat, parcourir la ligne $i$ de la matrice de gauche et la colonne $j$ de la matrice de droite en même temps, multiplier terme à terme, additionner.
- Contrôler un ou deux coefficients en refaisant le calcul, ou à la calculatrice.
Règles de calcul
Pour des matrices dont les tailles permettent les opérations et pour tout réel $\lambda$ :
- associativité : $(AB)C=A(BC)$ ;
- distributivité : $A(B+C)=AB+AC$ et $(A+B)C=AC+BC$ ;
- $(\lambda A)B=A(\lambda B)=\lambda(AB)$ ;
- si $A\in\mathcal{M}_n(\mathbb{R})$, $AI_n=I_nA=A$.
Ces propriétés sont admises.
Le produit n'est pas commutatif
Avec $A=\begin{pmatrix} 2 & 1 \\ -1 & 3 \end{pmatrix}$ et $B=\begin{pmatrix} 0 & 2 \\ 1 & -1 \end{pmatrix}$ : $$AB=\begin{pmatrix} 1 & 3 \\ 3 & -5 \end{pmatrix}\qquad BA=\begin{pmatrix} -2 & 6 \\ 3 & -2 \end{pmatrix}.$$ Donc en général $AB\neq BA$. Conséquences :
- $(A+B)^2=A^2+AB+BA+B^2$, et non $A^2+2AB+B^2$ (sauf si $AB=BA$) ;
- l'ordre des facteurs doit toujours être respecté.
De plus, un produit peut être nul sans qu'aucun facteur ne le soit : avec $A=\begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix}$ et $B=\begin{pmatrix} 0 & 0 \\ 0 & 1 \end{pmatrix}$, on a $AB=\begin{pmatrix} 0 & 0 \\ 0 & 0 \end{pmatrix}$.
2.Matrices inverses et systèmes linéaires
Matrice inversible
Une matrice carrée $A$ d'ordre $n$ est inversible s'il existe une matrice $B$ carrée d'ordre $n$ telle que $$AB=BA=I_n.$$ La matrice $B$ est alors appelée inverse de $A$ et notée $A^{-1}$.
Une seule égalité suffit
On admet que, pour des matrices carrées de même ordre, si $AB=I_n$ alors $BA=I_n$. En pratique, pour prouver que $B$ est l'inverse de $A$, il suffit donc de vérifier $AB=I_n$.
Unicité de l'inverse
Si $A$ est inversible, son inverse est unique.
Unicité de l'inverse
Supposons que $B$ et $B'$ vérifient $AB=BA=I_n$ et $AB'=B'A=I_n$. Par associativité : $$B'=B'I_n=B'(AB)=(B'A)B=I_nB=B.$$ L'inverse est donc unique.
Inverse d'un produit
Si $A$ et $B$ sont inversibles de même ordre, alors $AB$ est inversible et $$(AB)^{-1}=B^{-1}A^{-1}.$$ L'ordre des facteurs s'inverse.
Inverse d'un produit
Par associativité : $$(AB)(B^{-1}A^{-1})=A(BB^{-1})A^{-1}=AI_nA^{-1}=AA^{-1}=I_n.$$ D'après la remarque précédente, cela suffit : $B^{-1}A^{-1}$ est l'inverse de $AB$.
Déterminant d'une matrice 2×2
Le déterminant de la matrice $A=\begin{pmatrix} a & b \\ c & d \end{pmatrix}$ est le réel $$\det(A)=ad-bc.$$
Inverse d'une matrice 2×2
La matrice $A=\begin{pmatrix} a & b \\ c & d \end{pmatrix}$ est inversible si et seulement si $ad-bc\neq 0$. Dans ce cas : $$A^{-1}=\frac{1}{ad-bc}\begin{pmatrix} d & -b \\ -c & a \end{pmatrix}.$$
Inverse d'une matrice 2×2
Posons $M=\begin{pmatrix} d & -b \\ -c & a \end{pmatrix}$. On calcule : $$AM=\begin{pmatrix} ad-bc & -ab+ba \\ cd-dc & -cb+da \end{pmatrix}=(ad-bc)I_2.$$
Si $ad-bc\neq 0$ : en divisant par $ad-bc$, on obtient $A\left(\dfrac{1}{ad-bc}M\right)=I_2$. Donc $A$ est inversible et $A^{-1}=\dfrac{1}{ad-bc}M$.
Si $ad-bc=0$ : alors $AM$ est la matrice nulle. Supposons par l'absurde $A$ inversible. En multipliant à gauche par $A^{-1}$, on obtient $M=A^{-1}(AM)$, donc $M$ est nulle, c'est-à-dire $a=b=c=d=0$. Alors $A$ est la matrice nulle, et pour toute matrice $B$, $AB$ est nulle, donc différente de $I_2$ : $A$ n'est pas inversible. C'est une contradiction. Donc $A$ n'est pas inversible.
La double implication est démontrée.
Écriture matricielle d'un système
Un système linéaire de $n$ équations à $n$ inconnues s'écrit $AX=B$, où $A$ est la matrice carrée des coefficients, $X$ la colonne des inconnues et $B$ la colonne des seconds membres.
Si $A$ est inversible, le système admet une unique solution : $$X=A^{-1}B.$$
Solution unique d'un système AX = B
Supposons $A$ inversible.
- Si $X$ vérifie $AX=B$, en multipliant à gauche par $A^{-1}$ : $A^{-1}AX=A^{-1}B$, soit $X=A^{-1}B$. Il y a donc au plus une solution.
- Réciproquement, $A(A^{-1}B)=(AA^{-1})B=B$ : la colonne $A^{-1}B$ est bien solution.
Le système a donc une unique solution, $X=A^{-1}B$.
Résolution d'un système 2×2
On résout $\begin{cases} 2x+3y=7 \\ x-y=1 \end{cases}$.
Il s'écrit $AX=B$ avec $A=\begin{pmatrix} 2 & 3 \\ 1 & -1 \end{pmatrix}$, $X=\begin{pmatrix} x \\ y \end{pmatrix}$, $B=\begin{pmatrix} 7 \\ 1 \end{pmatrix}$.
$\det(A)=2\times(-1)-3\times 1=-5\neq 0$, donc $A$ est inversible et $$A^{-1}=-\frac{1}{5}\begin{pmatrix} -1 & -3 \\ -1 & 2 \end{pmatrix}=\frac{1}{5}\begin{pmatrix} 1 & 3 \\ 1 & -2 \end{pmatrix}.$$ Alors $$X=A^{-1}B=\frac{1}{5}\begin{pmatrix} 7+3 \\ 7-2 \end{pmatrix}=\begin{pmatrix} 2 \\ 1 \end{pmatrix}.$$ Vérification : $2\times 2+3\times 1=7$ et $2-1=1$. La solution est $(x;y)=(2;1)$.
Trouver l'inverse à partir d'une relation entre puissances
Si l'énoncé fournit (ou fait démontrer) une relation du type $A^2=\alpha A+\beta I_n$ avec $\beta\neq 0$ :
- On isole $I_n$ : $A^2-\alpha A=\beta I_n$.
- On factorise par $A$ : $A(A-\alpha I_n)=\beta I_n$.
- On divise par $\beta$ : $A\cdot\dfrac{1}{\beta}(A-\alpha I_n)=I_n$.
- On conclut : $A$ est inversible et $A^{-1}=\dfrac{1}{\beta}(A-\alpha I_n)$.
Cette méthode fonctionne pour toute taille de matrice, en particulier pour les matrices $3\times 3$.
Application de la méthode
Soit $A=\begin{pmatrix} 1 & 1 \\ 0 & 2 \end{pmatrix}$. On calcule $A^2=\begin{pmatrix} 1 & 3 \\ 0 & 4 \end{pmatrix}$ et $3A-2I_2=\begin{pmatrix} 1 & 3 \\ 0 & 4 \end{pmatrix}$, donc $A^2=3A-2I_2$.
Ainsi $A^2-3A=-2I_2$, soit $A(A-3I_2)=-2I_2$, donc $A\cdot\dfrac{1}{2}(3I_2-A)=I_2$. Par conséquent $$A^{-1}=\frac{1}{2}(3I_2-A)=\begin{pmatrix} 1 & -\frac{1}{2} \\ 0 & \frac{1}{2} \end{pmatrix}.$$ On retrouve le résultat de la formule : $\det(A)=2$ et $\dfrac{1}{2}\begin{pmatrix} 2 & -1 \\ 0 & 1 \end{pmatrix}$ donne la même matrice.
Matrices d'ordre 3
Pour une matrice $3\times 3$, aucune formule n'est exigible. On obtient l'inverse à la calculatrice, par une relation entre puissances, ou bien on vérifie par un produit qu'une matrice proposée par l'énoncé est l'inverse cherché.
3.Puissances d'une matrice carrée
Puissance n-ième
Soit $A$ une matrice carrée d'ordre $p$. On pose $A^0=I_p$ et, pour tout entier naturel $n$, $A^{n+1}=A^nA$.
Ainsi $A^n=A\times A\times\cdots\times A$ ($n$ facteurs) pour $n\geqslant 1$. Comme $A$ commute avec elle-même, on a aussi $A^{n+1}=AA^n$ et $A^mA^n=A^{m+n}$.
Puissance d'une matrice et puissance des coefficients
En général, les coefficients de $A^n$ ne sont pas les puissances $n$-ièmes des coefficients de $A$. Par exemple, avec $A=\begin{pmatrix} 1 & 1 \\ 0 & 2 \end{pmatrix}$, on a $A^2=\begin{pmatrix} 1 & 3 \\ 0 & 4 \end{pmatrix}$ et non $\begin{pmatrix} 1 & 1 \\ 0 & 4 \end{pmatrix}$. Le cas des matrices diagonales est une exception.
Puissances d'une matrice diagonale
Si $D=\begin{pmatrix} d_1 & 0 \\ 0 & d_2 \end{pmatrix}$, alors pour tout entier naturel $n$ : $$D^n=\begin{pmatrix} d_1^{\,n} & 0 \\ 0 & d_2^{\,n} \end{pmatrix}.$$ Le résultat est le même pour une matrice diagonale d'ordre $3$.
Puissances d'une matrice diagonale
Par récurrence sur $n$.
Initialisation : $D^0=I_2=\begin{pmatrix} d_1^{\,0} & 0 \\ 0 & d_2^{\,0} \end{pmatrix}$.
Hérédité : supposons la formule vraie au rang $n$. Alors $$D^{n+1}=D^nD=\begin{pmatrix} d_1^{\,n} & 0 \\ 0 & d_2^{\,n} \end{pmatrix}\begin{pmatrix} d_1 & 0 \\ 0 & d_2 \end{pmatrix}=\begin{pmatrix} d_1^{\,n+1} & 0 \\ 0 & d_2^{\,n+1} \end{pmatrix}.$$
Conclusion : la formule est vraie pour tout entier naturel $n$.
Conjecture puis récurrence
Soit $T=\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}$. On calcule $T^2=\begin{pmatrix} 1 & 2 \\ 0 & 1 \end{pmatrix}$, $T^3=\begin{pmatrix} 1 & 3 \\ 0 & 1 \end{pmatrix}$. On conjecture $T^n=\begin{pmatrix} 1 & n \\ 0 & 1 \end{pmatrix}$.
- Initialisation : $T^0=I_2=\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$, la formule est vraie pour $n=0$.
- Hérédité : si $T^n=\begin{pmatrix} 1 & n \\ 0 & 1 \end{pmatrix}$, alors $T^{n+1}=T^nT=\begin{pmatrix} 1 & 1+n \\ 0 & 1 \end{pmatrix}$.
Donc pour tout $n\in\mathbb{N}$, $T^n=\begin{pmatrix} 1 & n \\ 0 & 1 \end{pmatrix}$.
Puissances de A = PDP⁻¹
Soient $A$, $P$, $D$ des matrices carrées de même ordre, $P$ inversible, telles que $A=PDP^{-1}$. Alors pour tout entier naturel $n$ : $$A^n=PD^nP^{-1}.$$ Si $D$ est diagonale, $D^n$ se calcule immédiatement, donc $A^n$ aussi.
Puissances de A = PDP⁻¹
Par récurrence sur $n$.
Initialisation : $PD^0P^{-1}=PI P^{-1}=PP^{-1}=I=A^0$.
Hérédité : supposons $A^n=PD^nP^{-1}$. Alors, par associativité, $$A^{n+1}=A^nA=(PD^nP^{-1})(PDP^{-1})=PD^n(P^{-1}P)DP^{-1}=PD^nDP^{-1}=PD^{n+1}P^{-1}.$$
Conclusion : pour tout $n\in\mathbb{N}$, $A^n=PD^nP^{-1}$.
Calcul de Aⁿ avec une matrice de passage
Soient $A=\begin{pmatrix} 4 & -2 \\ 1 & 1 \end{pmatrix}$, $P=\begin{pmatrix} 1 & 2 \\ 1 & 1 \end{pmatrix}$ et $D=\begin{pmatrix} 2 & 0 \\ 0 & 3 \end{pmatrix}$.
$\det(P)=1-2=-1\neq 0$, donc $P$ est inversible et $P^{-1}=-\begin{pmatrix} 1 & -2 \\ -1 & 1 \end{pmatrix}=\begin{pmatrix} -1 & 2 \\ 1 & -1 \end{pmatrix}$.
On vérifie : $PD=\begin{pmatrix} 2 & 6 \\ 2 & 3 \end{pmatrix}$ puis $PDP^{-1}=\begin{pmatrix} -2+6 & 4-6 \\ -2+3 & 4-3 \end{pmatrix}=\begin{pmatrix} 4 & -2 \\ 1 & 1 \end{pmatrix}=A$.
Donc $A^n=PD^nP^{-1}$ avec $D^n=\begin{pmatrix} 2^n & 0 \\ 0 & 3^n \end{pmatrix}$ : $$PD^n=\begin{pmatrix} 2^n & 2\times 3^n \\ 2^n & 3^n \end{pmatrix},\qquad A^n=\begin{pmatrix} -2^n+2\times 3^n & 2^{n+1}-2\times 3^n \\ -2^n+3^n & 2^{n+1}-3^n \end{pmatrix}.$$ Contrôle pour $n=1$ : on retrouve $\begin{pmatrix} 4 & -2 \\ 1 & 1 \end{pmatrix}$.
Calculer Aⁿ
- Calculer $A^2$, $A^3$ : si une forme apparaît, la conjecturer puis la démontrer par récurrence.
- Si l'énoncé donne $P$ et $D$ (diagonale) : vérifier que $P$ est inversible, calculer $P^{-1}$, vérifier $A=PDP^{-1}$ (ou $P^{-1}AP=D$, ce qui est équivalent).
- Écrire $A^n=PD^nP^{-1}$, calculer d'abord $PD^n$, puis multiplier par $P^{-1}$.
- Contrôler le résultat pour $n=0$ et $n=1$.
Hors programme
La recherche des matrices $P$ et $D$ (diagonalisation) n'est pas au programme : elles sont toujours fournies par l'énoncé. De même, la formule du binôme pour des matrices qui commutent peut être rencontrée en exercice guidé, mais n'est pas exigible.
4.Suites définies par une relation matricielle
Suite de matrices colonnes
Une suite $(U_n)$ de matrices colonnes est définie par la donnée, pour tout $n$, d'une matrice colonne $U_n$. Par exemple, deux suites $(u_n)$ et $(v_n)$ peuvent être regroupées en $U_n=\begin{pmatrix} u_n \\ v_n \end{pmatrix}$.
On dit que $(U_n)$ converge vers la colonne $L$ si chaque coefficient de $U_n$ converge vers le coefficient correspondant de $L$.
Relation U(n+1) = A U(n)
Si pour tout $n\in\mathbb{N}$, $U_{n+1}=AU_n$, alors pour tout $n\in\mathbb{N}$ : $$U_n=A^nU_0.$$
Relation U(n+1) = A U(n)
Par récurrence. Pour $n=0$ : $A^0U_0=IU_0=U_0$. Si $U_n=A^nU_0$, alors $U_{n+1}=AU_n=A(A^nU_0)=A^{n+1}U_0$. La propriété est vraie pour tout $n$.
Deux suites couplées
Soient $(u_n)$ et $(v_n)$ définies par $u_0=1$, $v_0=0$ et, pour tout $n$ : $$\begin{cases} u_{n+1}=4u_n-2v_n \\ v_{n+1}=u_n+v_n \end{cases}$$ Avec $U_n=\begin{pmatrix} u_n \\ v_n \end{pmatrix}$, on a $U_{n+1}=AU_n$ où $A=\begin{pmatrix} 4 & -2 \\ 1 & 1 \end{pmatrix}$ est la matrice de l'exemple précédent. Donc $U_n=A^nU_0$, et comme $U_0=\begin{pmatrix} 1 \\ 0 \end{pmatrix}$, $U_n$ est la première colonne de $A^n$ : $$u_n=2\times 3^n-2^n,\qquad v_n=3^n-2^n.$$ Contrôle : $u_1=4$ et $v_1=1$, ce que donnent aussi les relations de récurrence.
Relation U(n+1) = A U(n) + B
Soit $(U_n)$ telle que $U_{n+1}=AU_n+B$ pour tout $n$. S'il existe une colonne $C$ telle que $C=AC+B$ (colonne fixe), alors pour tout $n\in\mathbb{N}$ : $$U_n=A^n(U_0-C)+C.$$ Si $I-A$ est inversible, une telle colonne existe et vaut $C=(I-A)^{-1}B$.
Relation U(n+1) = A U(n) + B
Existence de $C$ : $C=AC+B\iff C-AC=B\iff(I-A)C=B$. Si $I-A$ est inversible, cette équation a pour unique solution $C=(I-A)^{-1}B$.
Suite auxiliaire : posons $V_n=U_n-C$. En soustrayant $C=AC+B$ à $U_{n+1}=AU_n+B$ : $$V_{n+1}=U_{n+1}-C=AU_n-AC=A(U_n-C)=AV_n.$$ D'après la propriété précédente, $V_n=A^nV_0$, c'est-à-dire $U_n-C=A^n(U_0-C)$, d'où le résultat.
Une suite arithmético-géométrique matricielle
Soient $A=\begin{pmatrix} 0{,}5 & 0{,}25 \\ 0 & 0{,}5 \end{pmatrix}$, $B=\begin{pmatrix} 1 \\ 1 \end{pmatrix}$, $U_0=\begin{pmatrix} 0 \\ 0 \end{pmatrix}$ et $U_{n+1}=AU_n+B$.
- $I-A=\begin{pmatrix} 0{,}5 & -0{,}25 \\ 0 & 0{,}5 \end{pmatrix}$, de déterminant $0{,}25\neq 0$, et $(I-A)^{-1}=\begin{pmatrix} 2 & 1 \\ 0 & 2 \end{pmatrix}$. Donc $C=(I-A)^{-1}B=\begin{pmatrix} 3 \\ 2 \end{pmatrix}$. Contrôle : $AC+B=\begin{pmatrix} 2 \\ 1 \end{pmatrix}+\begin{pmatrix} 1 \\ 1 \end{pmatrix}=C$.
- $A=0{,}5\,T'$ avec $T'=\begin{pmatrix} 1 & 0{,}5 \\ 0 & 1 \end{pmatrix}$ ; comme pour la matrice $T$ ci-dessus, on montre par récurrence $T'^{\,n}=\begin{pmatrix} 1 & 0{,}5n \\ 0 & 1 \end{pmatrix}$, donc $A^n=0{,}5^n\begin{pmatrix} 1 & 0{,}5n \\ 0 & 1 \end{pmatrix}$.
- $U_0-C=\begin{pmatrix} -3 \\ -2 \end{pmatrix}$, donc $A^n(U_0-C)=0{,}5^n\begin{pmatrix} -3-n \\ -2 \end{pmatrix}$ et $$U_n=\begin{pmatrix} 3-(n+3)\times 0{,}5^n \\ 2-2\times 0{,}5^n \end{pmatrix}.$$ Contrôle : $U_1=B=\begin{pmatrix} 1 \\ 1 \end{pmatrix}$ et la formule donne $3-4\times 0{,}5=1$, $2-1=1$.
Comme $0{,}5^n\to 0$ et $n\times 0{,}5^n\to 0$ (croissances comparées), $(U_n)$ converge vers $C=\begin{pmatrix} 3 \\ 2 \end{pmatrix}$.
Étudier une suite U(n+1) = A U(n) + B
- Écrire le système sous forme matricielle et identifier $A$ et $B$.
- Déterminer la colonne fixe $C$ en résolvant $(I-A)C=B$, ou vérifier celle que donne l'énoncé.
- Poser $V_n=U_n-C$ et montrer $V_{n+1}=AV_n$.
- En déduire $U_n=A^n(U_0-C)+C$, puis calculer $A^n$.
- Pour la limite, étudier chaque coefficient : si les coefficients de $A^n$ tendent tous vers $0$, alors $(U_n)$ converge vers $C$.
5.Graphes : vocabulaire
Graphe non orienté
Un graphe non orienté est la donnée d'un ensemble fini de points, les sommets, et d'un ensemble de segments reliant certains de ces sommets, les arêtes. On considère ici des graphes où deux sommets sont reliés par au plus une arête.
- L'ordre du graphe est son nombre de sommets.
- Deux sommets reliés par une arête sont adjacents.
- Le degré d'un sommet est le nombre d'arêtes dont il est une extrémité.
Chaîne, graphe connexe, graphe complet
- Une chaîne est une suite de sommets dans laquelle deux sommets consécutifs sont adjacents. Sa longueur est le nombre d'arêtes parcourues (donc le nombre de sommets moins un). Une chaîne peut repasser par un même sommet ou une même arête.
- Une chaîne est fermée si son premier et son dernier sommet sont égaux.
- Un graphe est connexe si deux sommets quelconques peuvent toujours être reliés par une chaîne.
- Un graphe est complet si deux sommets distincts quelconques sont toujours adjacents.
Somme des degrés
Dans un graphe non orienté, la somme des degrés des sommets est égale au double du nombre d'arêtes.
Somme des degrés
Chaque arête a deux extrémités. En additionnant les degrés de tous les sommets, on compte chaque arête exactement deux fois, une fois pour chacune de ses extrémités. La somme des degrés vaut donc deux fois le nombre d'arêtes.
Conséquence : la somme des degrés est paire, donc le nombre de sommets de degré impair est pair.
Lecture d'un graphe
On considère le graphe d'ordre $4$, de sommets $1,2,3,4$, dont les arêtes sont $\{1,2\}$, $\{1,3\}$, $\{2,3\}$ et $\{3,4\}$.
| Sommet | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| Degré | 2 | 2 | 3 | 1 |
La somme des degrés est $8=2\times 4$ : il y a bien $4$ arêtes. Le graphe est connexe (tout sommet est relié à $3$). Il n'est pas complet : $1$ et $4$ ne sont pas adjacents. La suite $1-3-4$ est une chaîne de longueur $2$ ; la suite $1-2-3-1$ est une chaîne fermée de longueur $3$.
Nombre d'arêtes d'un graphe complet
Un graphe complet d'ordre $n$ possède $\dfrac{n(n-1)}{2}$ arêtes.
En effet, chacun des $n$ sommets a pour degré $n-1$ ; la somme des degrés vaut $n(n-1)$, qui est le double du nombre d'arêtes.
Graphe orienté
Un graphe orienté est formé de sommets et d'arcs : un arc est une flèche allant d'un sommet (origine) vers un sommet (extrémité). Un arc dont l'origine et l'extrémité sont confondues est une boucle.
Un chemin est une suite de sommets telle que, pour deux sommets consécutifs, il existe un arc allant du premier au second. Sa longueur est le nombre d'arcs parcourus. Un chemin est fermé si son origine et son extrémité sont égales.
Graphe pondéré
Un graphe (orienté ou non) est pondéré lorsqu'à chaque arête ou arc est associé un nombre réel, appelé poids (une distance, un coût, une probabilité, etc.).
6.Matrice d'adjacence et nombre de chemins
Matrice d'adjacence
Soit un graphe d'ordre $m$ dont les sommets sont numérotés de $1$ à $m$. Sa matrice d'adjacence est la matrice carrée $M=(m_{ij})$ d'ordre $m$ telle que :
- pour un graphe non orienté, $m_{ij}=1$ si les sommets $i$ et $j$ sont adjacents, $m_{ij}=0$ sinon ;
- pour un graphe orienté, $m_{ij}=1$ s'il existe un arc de $i$ vers $j$, $m_{ij}=0$ sinon.
La matrice dépend de la numérotation choisie pour les sommets.
Cas non orienté
La matrice d'adjacence d'un graphe non orienté est symétrique : $m_{ij}=m_{ji}$ pour tous $i,j$. En l'absence de boucle, sa diagonale est nulle, et la somme des coefficients de la ligne $i$ est le degré du sommet $i$.
Nombre de chemins de longueur n
Soit $M$ la matrice d'adjacence d'un graphe et $n$ un entier naturel non nul. Le coefficient $(i,j)$ de $M^n$ est égal au nombre de chemins (chaînes dans le cas non orienté) de longueur $n$ allant du sommet $i$ au sommet $j$.
Nombre de chemins de longueur n
On note $m_{ij}^{(n)}$ le coefficient $(i,j)$ de $M^n$. On raisonne par récurrence sur $n\geqslant 1$.
Initialisation : un chemin de longueur $1$ de $i$ à $j$ est un arc de $i$ vers $j$. Il en existe $1$ si $m_{ij}=1$ et $0$ sinon. Le nombre de tels chemins est donc $m_{ij}=m_{ij}^{(1)}$.
Hérédité : supposons que, pour tous $i,k$, $m_{ik}^{(n)}$ est le nombre de chemins de longueur $n$ de $i$ à $k$. Un chemin de longueur $n+1$ de $i$ à $j$ se décompose de façon unique en :
- un chemin de longueur $n$ de $i$ vers un sommet $k$ (l'avant-dernier sommet) ;
- suivi d'un arc de $k$ vers $j$.
Pour un $k$ fixé, le nombre de tels chemins est $m_{ik}^{(n)}\times m_{kj}$ : il vaut $m_{ik}^{(n)}$ si l'arc $k\to j$ existe, et $0$ sinon. En additionnant sur toutes les valeurs possibles de $k$, le nombre de chemins de longueur $n+1$ de $i$ à $j$ est $$\sum_{k=1}^{m}m_{ik}^{(n)}m_{kj}.$$ Par définition du produit matriciel, c'est le coefficient $(i,j)$ de $M^nM=M^{n+1}$.
Conclusion : la propriété est vraie pour tout $n\geqslant 1$.
Un graphe orienté à trois sommets
Le graphe orienté de sommets $1,2,3$ a pour arcs $1\to 2$, $1\to 3$, $2\to 3$ et $3\to 1$. Sa matrice d'adjacence est $$M=\begin{pmatrix} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix}.$$ On calcule $$M^2=\begin{pmatrix} 1 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 1 \end{pmatrix},\qquad M^3=\begin{pmatrix} 1 & 1 & 1 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \end{pmatrix}.$$ Le coefficient $(1,1)$ de $M^3$ vaut $1$ : il y a un seul chemin de longueur $3$ de $1$ à $1$, à savoir $1\to 2\to 3\to 1$. Le coefficient $(2,1)$ de $M^3$ vaut $0$ : aucun chemin de longueur $3$ ne va de $2$ à $1$. En effet, depuis $2$, on va forcément en $3$ puis en $1$, et le troisième arc mène en $2$ ou en $3$.
Un graphe non orienté
On reprend le graphe d'ordre $4$ d'arêtes $\{1,2\}$, $\{1,3\}$, $\{2,3\}$, $\{3,4\}$ : $$M=\begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}.$$ Le coefficient $(1,4)$ de $M^2$ s'obtient avec la ligne $1$ et la colonne $4$ de $M$ : $0\times 0+1\times 0+1\times 1+0\times 0=1$. Il y a une seule chaîne de longueur $2$ de $1$ à $4$ : $1-3-4$.
Le coefficient $(3,3)$ de $M^2$ vaut $1+1+0+1=3$, qui est le degré de $3$ : une chaîne fermée de longueur $2$ partant de $3$ consiste à aller vers un voisin puis à revenir.
Compter des chemins avec une matrice
- Numéroter les sommets et écrire la matrice d'adjacence $M$ (ligne = départ, colonne = arrivée).
- Calculer $M^n$, à la main pour $n=2$ ou $3$, à la calculatrice au-delà.
- Lire le coefficient ligne « départ », colonne « arrivée ».
- Attention : la longueur est le nombre d'arcs, pas le nombre de sommets. Un chemin passant par $5$ sommets (en comptant le départ et l'arrivée) a pour longueur $4$.
Connexité et matrice d'adjacence
Dans un graphe non orienté d'ordre $m$, deux sommets distincts reliés par une chaîne le sont par une chaîne de longueur au plus $m-1$. Ainsi, le graphe est connexe si et seulement si tous les coefficients hors diagonale de $M+M^2+\cdots+M^{m-1}$ sont strictement positifs. Ce critère s'utilise en exercice guidé ; il n'est pas exigible.
7.Chaînes de Markov et distribution invariante
Chaîne de Markov
Soit $E=\{1,2,\dots,m\}$ un ensemble fini d'états. Une suite de variables aléatoires $(X_n)_{n\in\mathbb{N}}$ à valeurs dans $E$ est une chaîne de Markov (homogène) si, pour tous états $i$ et $j$, la probabilité de passer de $i$ à $j$ entre les instants $n$ et $n+1$ ne dépend ni de $n$, ni des états occupés avant l'instant $n$. On note $$p_{ij}=P_{(X_n=i)}(X_{n+1}=j).$$ L'avenir ne dépend du passé qu'à travers l'état présent.
Matrice de transition et graphe probabiliste
La matrice de transition de la chaîne est la matrice carrée $P=(p_{ij})$ d'ordre $m$ : la ligne $i$ contient les probabilités de partir de l'état $i$ vers chacun des états.
Chaque coefficient est dans $[0;1]$ et la somme des coefficients de chaque ligne vaut $1$.
Le graphe probabiliste associé est le graphe orienté pondéré dont les sommets sont les états, avec un arc de $i$ vers $j$ de poids $p_{ij}$ lorsque $p_{ij}>0$. La somme des poids des arcs issus d'un sommet vaut $1$.
Distribution
La distribution (ou loi) de $X_n$ est la matrice ligne $$\pi_n=\begin{pmatrix} P(X_n=1) & P(X_n=2) & \cdots & P(X_n=m) \end{pmatrix}.$$ Ses coefficients sont positifs et de somme $1$. $\pi_0$ est la distribution initiale.
Évolution de la distribution
Pour tout entier naturel $n$ : $$\pi_{n+1}=\pi_nP\qquad\text{et donc}\qquad\pi_n=\pi_0P^n.$$
Évolution de la distribution
Soit $j\in E$. Les événements $(X_n=1),\dots,(X_n=m)$ forment un système complet. Par la formule des probabilités totales (les termes où $P(X_n=i)=0$ sont nuls) : $$P(X_{n+1}=j)=\sum_{i=1}^{m}P(X_n=i)\,P_{(X_n=i)}(X_{n+1}=j)=\sum_{i=1}^{m}P(X_n=i)\,p_{ij}.$$ C'est le produit de la ligne $\pi_n$ par la colonne $j$ de $P$ : c'est donc le coefficient $j$ de $\pi_nP$. Ainsi $\pi_{n+1}=\pi_nP$.
Par récurrence : $\pi_0=\pi_0P^0$, et si $\pi_n=\pi_0P^n$, alors $\pi_{n+1}=\pi_nP=\pi_0P^nP=\pi_0P^{n+1}$.
Interprétation de Pⁿ
Le coefficient $(i,j)$ de $P^n$ est la probabilité d'être dans l'état $j$ à l'instant $n$ sachant qu'on part de l'état $i$ à l'instant $0$. C'est l'analogue probabiliste du comptage de chemins : on additionne, sur tous les chemins de longueur $n$ de $i$ à $j$, le produit des poids des arcs.
Ligne ou colonne
Avec la convention du programme ($p_{ij}$ en ligne $i$, colonne $j$), la distribution est une ligne et elle se multiplie à gauche : $\pi_{n+1}=\pi_nP$. Écrire $P\pi_n$ n'a pas de sens (formats incompatibles). Certains énoncés utilisent des colonnes et la transposée de $P$ : lire attentivement la convention choisie.
Une chaîne à deux états
Chaque jour, le temps est beau (état $1$) ou pluvieux (état $2$). S'il fait beau, il fait beau le lendemain avec probabilité $0{,}8$ ; s'il pleut, il fait beau le lendemain avec probabilité $0{,}4$. La matrice de transition est $$P=\begin{pmatrix} 0{,}8 & 0{,}2 \\ 0{,}4 & 0{,}6 \end{pmatrix}.$$ S'il fait beau le jour $0$, $\pi_0=\begin{pmatrix} 1 & 0 \end{pmatrix}$, puis $\pi_1=\pi_0P=\begin{pmatrix} 0{,}8 & 0{,}2 \end{pmatrix}$ et $$\pi_2=\pi_1P=\begin{pmatrix} 0{,}64+0{,}08 & 0{,}16+0{,}12 \end{pmatrix}=\begin{pmatrix} 0{,}72 & 0{,}28 \end{pmatrix}.$$ En notant $p_n=P(X_n=1)$, on a $P(X_n=2)=1-p_n$ et $$p_{n+1}=0{,}8p_n+0{,}4(1-p_n)=0{,}4p_n+0{,}4.$$ Le point fixe vérifie $\ell=0{,}4\ell+0{,}4$, soit $\ell=\frac{2}{3}$. La suite $(p_n-\frac{2}{3})$ est géométrique de raison $0{,}4$, donc $$p_n=\frac{2}{3}+\frac{1}{3}\times 0{,}4^n.$$ Contrôle : $p_1=\frac{2}{3}+\frac{0{,}4}{3}=0{,}8$. Comme $0{,}4^n\to 0$, $(\pi_n)$ converge vers $\begin{pmatrix} \frac{2}{3} & \frac{1}{3} \end{pmatrix}$ : à long terme, il fait beau deux jours sur trois.
Distribution invariante
Une distribution $\pi$ (matrice ligne à coefficients positifs de somme $1$) est invariante (ou stationnaire) pour la chaîne de matrice de transition $P$ si $$\pi P=\pi.$$ Si $\pi_0=\pi$, alors $\pi_n=\pi$ pour tout $n$ : la loi ne change plus.
Chaîne à deux états
Soit une chaîne de Markov à deux états de matrice de transition $$P=\begin{pmatrix} 1-a & a \\ b & 1-b \end{pmatrix}\quad\text{avec }0<a+b<2.$$ Alors :
- la chaîne admet une unique distribution invariante $\pi=\begin{pmatrix} \dfrac{b}{a+b} & \dfrac{a}{a+b} \end{pmatrix}$ ;
- quelle que soit la distribution initiale, la suite $(\pi_n)$ converge vers $\pi$.
La condition $0<a+b<2$ est réalisée en particulier dès que $a$ et $b$ sont dans $]0;1[$.
Chaîne à deux états
Distribution invariante. Soit $\pi=\begin{pmatrix} p & 1-p \end{pmatrix}$ avec $p\in[0;1]$. Le premier coefficient de $\pi P$ vaut $(1-a)p+b(1-p)$ ; le second vaut alors $1$ moins le premier, car les coefficients de $\pi P$ ont pour somme $1$ (chaque ligne de $P$ a pour somme $1$). Donc $$\pi P=\pi\iff(1-a)p+b(1-p)=p\iff b=(a+b)p\iff p=\frac{b}{a+b},$$ puisque $a+b\neq 0$. Ce réel est dans $[0;1]$ car $0\leqslant b\leqslant a+b$. La distribution invariante existe et est unique.
Convergence. Notons $\pi_n=\begin{pmatrix} p_n & 1-p_n \end{pmatrix}$. La relation $\pi_{n+1}=\pi_nP$ donne $$p_{n+1}=(1-a)p_n+b(1-p_n)=(1-a-b)p_n+b.$$ Avec $\ell=\dfrac{b}{a+b}$, on a $\ell=(1-a-b)\ell+b$. Par soustraction, $p_{n+1}-\ell=(1-a-b)(p_n-\ell)$ : la suite $(p_n-\ell)$ est géométrique de raison $q=1-a-b$, donc $$p_n=\ell+(1-a-b)^n(p_0-\ell).$$ Comme $0<a+b<2$, on a $-1<q<1$, donc $q^n\to 0$ et $p_n\to\ell$. Par suite $1-p_n\to 1-\ell=\dfrac{a}{a+b}$, et $(\pi_n)$ converge vers $\pi$.
Chaîne à trois états (admis)
Soit une chaîne de Markov à deux ou trois états de matrice de transition $P$. On admet que, si une puissance $P^k$ de $P$ a tous ses coefficients strictement positifs (en particulier si $P$ n'a aucun coefficient nul), alors :
- la chaîne admet une unique distribution invariante $\pi$ ;
- quelle que soit la distribution initiale $\pi_0$, la suite $(\pi_n)$ converge vers $\pi$.
En exercice, l'énoncé précise les hypothèses à vérifier.
Déterminer une distribution invariante
- Poser $\pi=\begin{pmatrix} x & y & z \end{pmatrix}$ (ou $\begin{pmatrix} x & y \end{pmatrix}$ pour deux états).
- Écrire les équations de $\pi P=\pi$, coefficient par coefficient : la $j$-ième équation utilise la colonne $j$ de $P$.
- Ajouter l'équation $x+y+z=1$. Elle est indispensable : le système $\pi P=\pi$ seul a une équation superflue et une infinité de solutions.
- Résoudre en exprimant toutes les inconnues en fonction de l'une d'elles, puis utiliser la somme égale à $1$.
- Vérifier que les coefficients trouvés sont positifs et que $\pi P=\pi$.
Une marche à trois états
Un pion se déplace sur trois cases $1,2,3$ avec la matrice de transition $$P=\begin{pmatrix} 0{,}5 & 0{,}5 & 0 \\ 0{,}25 & 0{,}5 & 0{,}25 \\ 0 & 0{,}5 & 0{,}5 \end{pmatrix}.$$ On cherche $\pi=\begin{pmatrix} x & y & z \end{pmatrix}$ avec $\pi P=\pi$ et $x+y+z=1$ : $$\begin{cases} 0{,}5x+0{,}25y=x \\ 0{,}5x+0{,}5y+0{,}5z=y \\ 0{,}25y+0{,}5z=z \\ x+y+z=1 \end{cases}$$ La première équation donne $y=2x$, la troisième $y=2z$, donc $z=x$. Alors $x+2x+x=1$, soit $x=\frac{1}{4}$. Donc $$\pi=\begin{pmatrix} \frac{1}{4} & \frac{1}{2} & \frac{1}{4} \end{pmatrix}.$$ La deuxième équation est bien vérifiée : $0{,}5\times\frac{1}{4}+0{,}5\times\frac{1}{2}+0{,}5\times\frac{1}{4}=\frac{1}{2}$.
$P$ contient des zéros, mais $$P^2=\begin{pmatrix} 0{,}375 & 0{,}5 & 0{,}125 \\ 0{,}25 & 0{,}5 & 0{,}25 \\ 0{,}125 & 0{,}5 & 0{,}375 \end{pmatrix}$$ a tous ses coefficients strictement positifs. D'après le théorème admis, $(\pi_n)$ converge vers $\pi$ quelle que soit la case de départ : à long terme, le pion est sur la case centrale avec probabilité $\frac{1}{2}$.