# Graphes et matrices : maths Terminale

Chapitre 24 du programme de mathématiques de Terminale (thème : Maths Expertes). Ressource gratuite OptiTAB.

- Cours : https://www.optitab.net/ressources-gratuites/maths/terminale/graphes-et-matrices/
- Fiche de révision : https://www.optitab.net/ressources-gratuites/maths/terminale/graphes-et-matrices/fiche/
- Exercices corrigés : https://www.optitab.net/ressources-gratuites/maths/terminale/graphes-et-matrices/exercices/

## Cours

**Objectifs : Calculer avec des matrices (produit, inverse, puissances), résoudre un système linéaire et étudier une suite de matrices colonnes ; modéliser une situation par un graphe et compter des chemins avec la matrice d’adjacence ; étudier une chaîne de Markov à deux ou trois états. Programme de Mathématiques expertes.**

## I. Matrices

**Définition : Matrice**
Soient $m$ et $n$ deux entiers naturels non nuls. Une **matrice de taille $m \times n$** est un tableau de nombres réels à $m$ lignes et $n$ colonnes. Le **coefficient** $a_{ij}$ est situé à la ligne $i$ et à la colonne $j$ ; on note $A = (a_{ij})$.

- **Matrice ligne** : une seule ligne (taille $1 \times n$).
- **Matrice colonne** : une seule colonne (taille $m \times 1$).
- **Matrice carrée d’ordre $n$** : $n$ lignes et $n$ colonnes.

**Exemple : $A = \begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{pmatrix}$ est de taille $2 \times 3$ et $a_{23} = 6$ (ligne $2$, colonne $3$). $X = \begin{pmatrix} 1 \\ 0 \\ -1 \end{pmatrix}$ est une matrice colonne de taille $3 \times 1$ et $L = \begin{pmatrix} 1 & 2 & 3 & 4 \end{pmatrix}$ une matrice ligne de taille $1 \times 4$.**

**Définition : Matrices carrées particulières**
- La **matrice nulle** $0_n$ : tous ses coefficients sont nuls.
- La **matrice identité** $I_n$ : des $1$ sur la diagonale, des $0$ ailleurs ; par exemple $I_2 = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$ et $I_3 = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}$.
- Une matrice **diagonale** : ses coefficients hors de la diagonale sont nuls, par exemple $D = \begin{pmatrix} 2 & 0 \\ 0 & 3 \end{pmatrix}$.
**Deux : matrices sont **égales** lorsqu’elles ont la même taille et les mêmes coefficients, place par place.**

## II. Opérations sur les matrices

### Somme et produit par un réel

**Définition : Pour deux matrices $A$ et $B$ de **même taille** et un réel $k$, on calcule coefficient par coefficient :**

$$(A + B)_{ij} = a_{ij} + b_{ij} \qquad \text{et} \qquad (kA)_{ij} = k\,a_{ij}$$

**Exemple : $$\begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{pmatrix} + \begin{pmatrix} 2 & -1 & 0 \\ 3 & 1 & -2 \end{pmatrix} = \begin{pmatrix} 3 & 1 & 3 \\ 7 & 6 & 4 \end{pmatrix}$$**

$$3\begin{pmatrix} 1 & 2 \\ -1 & 4 \end{pmatrix} = \begin{pmatrix} 3 & 6 \\ -3 & 12 \end{pmatrix}$$

### Produit de deux matrices

**Définition : Produit**
Soit $A$ de taille $m \times n$ et $B$ de taille $n \times p$ : le nombre de **colonnes** de $A$ est égal au nombre de **lignes** de $B$. Le produit $AB$ est la matrice de taille $m \times p$ définie par

$$(AB)_{ij} = a_{i1}b_{1j} + a_{i2}b_{2j} + \cdots + a_{in}b_{nj} = \sum_{k=1}^{n} a_{ik}\,b_{kj}$$

**Méthode : Calculer un coefficient de $AB$**
Le coefficient $(AB)_{ij}$ se calcule avec la **ligne $i$ de $A$** et la **colonne $j$ de $B$** : on multiplie leurs termes deux à deux, puis on additionne.

![Produit de matrices : la ligne 2 de A et la colonne 1 de B donnent le coefficient (AB)21 = 11](https://optitab-media.s3.eu-north-1.amazonaws.com/cours_images/v1_n104_co112_1_cours_produit.png)

**Exemple : Avec $A = \begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{pmatrix}$ (taille $2 \times 3$) et $B = \begin{pmatrix} 1 & 0 \\ -1 & 2 \\ 2 & 1 \end{pmatrix}$ (taille $3 \times 2$), le produit $AB$ existe et il est de taille $2 \times 2$ :**

$$
\begin{aligned}
(AB)_{11} &= 1 \times 1 + 2 \times (-1) + 3 \times 2 \\
&= 5 \\
(AB)_{12} &= 1 \times 0 + 2 \times 2 + 3 \times 1 \\
&= 7 \\
(AB)_{21} &= 4 \times 1 + 5 \times (-1) + 6 \times 2 \\
&= 11 \\
(AB)_{22} &= 4 \times 0 + 5 \times 2 + 6 \times 1 \\
&= 16
\end{aligned}
$$

donc $AB = \begin{pmatrix} 5 & 7 \\ 11 & 16 \end{pmatrix}$.

**Propriété : Règles de calcul**
Pour des matrices de tailles compatibles :

- $(AB)C = A(BC)$ (associativité) ;
- $A(B + C) = AB + AC$ et $(A + B)C = AC + BC$ (distributivité) ;
- $AI_n = I_nA = A$ pour toute matrice carrée $A$ d’ordre $n$.

**Attention : Le produit n’est pas commutatif**
En général $AB \neq BA$. Avec $A = \begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix}$ et $B = \begin{pmatrix} 5 & 6 \\ 7 & 8 \end{pmatrix}$ :

$$
AB = \begin{pmatrix} 19 & 22 \\ 43 & 50 \end{pmatrix} \qquad \text{mais} \qquad BA = \begin{pmatrix} 23 & 34 \\ 31 & 46 \end{pmatrix}
$$

De plus, un produit peut être nul sans qu’aucun des facteurs ne le soit : $\begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix}\begin{pmatrix} 1 & -1 \\ -1 & 1 \end{pmatrix} = 0_2$.

## III. Matrice inverse et systèmes linéaires

### Matrice inverse

**Définition : Une matrice carrée $A$ d’ordre $n$ est **inversible** s’il existe une matrice carrée $B$ d’ordre $n$ telle que $AB = BA = I_n$. Cette matrice $B$ est unique : c’est l’**inverse** de $A$, notée $A^{-1}$.**

**Propriété : Une seule égalité suffit (admis)**
Si $A$ et $B$ sont deux matrices carrées d’ordre $n$ telles que $AB = I_n$, alors $A$ est inversible et $A^{-1} = B$.

**Théorème : Inverse d’une matrice d’ordre 2**
Soit $A = \begin{pmatrix} a & b \\ c & d \end{pmatrix}$. Le nombre $\det(A) = ad - bc$ est le **déterminant** de $A$.

- Si $ad - bc \neq 0$, $A$ est inversible et $A^{-1} = \dfrac{1}{ad - bc}\begin{pmatrix} d & -b \\ -c & a \end{pmatrix}$.
- Si $ad - bc = 0$, $A$ n’est pas inversible.

**Démonstration : Posons $B = \begin{pmatrix} d & -b \\ -c & a \end{pmatrix}$. Un calcul direct donne**

$$
\begin{aligned}
AB &= \begin{pmatrix} ad - bc & -ab + ba \\ cd - dc & -cb + da \end{pmatrix} \\
&= (ad - bc)\,I_2
\end{aligned}
$$

- Si $ad - bc \neq 0$ : $A \times \dfrac{1}{ad - bc}B = I_2$, donc $A$ est inversible d’inverse $\dfrac{1}{ad - bc}B$.
- Si $ad - bc = 0$ : $AB = 0_2$. Si $A$ était inversible, on aurait $B = A^{-1}(AB) = 0_2$, donc $a = b = c = d = 0$ et $A = 0_2$, qui n’est pas inversible : c’est absurde.

**Exemple : Pour $A = \begin{pmatrix} 2 & 3 \\ 1 & 4 \end{pmatrix}$ : $\det(A) = 2 \times 4 - 3 \times 1 = 5 \neq 0$, donc**

$$A^{-1} = \frac{1}{5}\begin{pmatrix} 4 & -3 \\ -1 & 2 \end{pmatrix}$$

Contrôle : $\begin{pmatrix} 2 & 3 \\ 1 & 4 \end{pmatrix}\begin{pmatrix} 4 & -3 \\ -1 & 2 \end{pmatrix} = \begin{pmatrix} 5 & 0 \\ 0 & 5 \end{pmatrix} = 5I_2$, donc $AA^{-1} = I_2$.

**Méthode : Inverse d’une matrice d’ordre 3**
On obtient l’inverse à la calculatrice (ou avec un logiciel), puis on le **contrôle** par un produit. Par exemple, pour $T = \begin{pmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{pmatrix}$ et $T' = \begin{pmatrix} 1 & -1 & 1 \\ 0 & 1 & -1 \\ 0 & 0 & 1 \end{pmatrix}$, on vérifie que $TT' = I_3$ : donc $T^{-1} = T'$.

**Attention : On ne divise jamais par une matrice : l’écriture $\dfrac{1}{A}$ n’a pas de sens. On multiplie par $A^{-1}$, du bon côté. Si $A$ et $B$ sont inversibles, $(AB)^{-1} = B^{-1}A^{-1}$ : l’ordre s’inverse.**

**Remarque : Pour aller plus loin (hors programme) : déterminant d’ordre 3**
Pour $A = \begin{pmatrix} a & b & c \\ d & e & f \\ g & h & i \end{pmatrix}$, on définit

$$
\begin{aligned}
\det(A) = {} & aei + bfg + cdh \\
& - ceg - afh - bdi
\end{aligned}
$$

La **règle de Sarrus** permet de retrouver cette formule : on recopie les deux premières colonnes à droite du tableau, on additionne les produits des trois diagonales descendantes et on retranche ceux des trois diagonales montantes. Comme à l’ordre 2, $A$ est inversible si et seulement si $\det(A) \neq 0$.

![Règle de Sarrus : trois diagonales descendantes comptées avec le signe plus, trois diagonales montantes avec le signe moins](https://optitab-media.s3.eu-north-1.amazonaws.com/cours_images/v1_n104_co112_2_cours_sarrus.png)

### Écriture matricielle d’un système linéaire

**Définition : Un système de $n$ équations linéaires à $n$ inconnues s’écrit $AX = Y$, où $A$ est la matrice carrée des coefficients, $X$ la matrice colonne des inconnues et $Y$ la matrice colonne des seconds membres.**

**Théorème : Si $A$ est inversible, le système $AX = Y$ admet une **unique** solution :**

$$X = A^{-1}Y$$

**Démonstration : Si $AX = Y$, en multipliant à gauche par $A^{-1}$ : $A^{-1}AX = A^{-1}Y$, c’est-à-dire $X = A^{-1}Y$. Réciproquement, $X = A^{-1}Y$ vérifie $AX = AA^{-1}Y = Y$.**

**Exemple : Le système $\begin{cases} 2x + 3y = 5 \\ x + 4y = 6 \end{cases}$ s’écrit $AX = Y$ avec $A = \begin{pmatrix} 2 & 3 \\ 1 & 4 \end{pmatrix}$, $X = \begin{pmatrix} x \\ y \end{pmatrix}$ et $Y = \begin{pmatrix} 5 \\ 6 \end{pmatrix}$. On a vu que $A^{-1} = \dfrac{1}{5}\begin{pmatrix} 4 & -3 \\ -1 & 2 \end{pmatrix}$, donc**

$$
\begin{aligned}
X = A^{-1}Y &= \frac{1}{5}\begin{pmatrix} 4 \times 5 + (-3) \times 6 \\ (-1) \times 5 + 2 \times 6 \end{pmatrix} \\
&= \frac{1}{5}\begin{pmatrix} 2 \\ 7 \end{pmatrix}
\end{aligned}
$$

L’unique solution est $x = \dfrac{2}{5}$ et $y = \dfrac{7}{5}$.

**Exemple : Un système de trois équations**
Le système $\begin{cases} x + y = 3 \\ y + z = 5 \\ z = 2 \end{cases}$ s’écrit $TX = \begin{pmatrix} 3 \\ 5 \\ 2 \end{pmatrix}$ avec la matrice $T$ ci-dessus. Donc

$$X = T^{-1}\begin{pmatrix} 3 \\ 5 \\ 2 \end{pmatrix} = \begin{pmatrix} 3 - 5 + 2 \\ 5 - 2 \\ 2 \end{pmatrix} = \begin{pmatrix} 0 \\ 3 \\ 2 \end{pmatrix}$$

**Attention : Si $A$ n’est pas inversible, le système a soit aucune solution, soit une infinité de solutions : on le résout alors par combinaison ou par substitution.**

## IV. Puissances de matrices et suites

### Puissances d’une matrice carrée

**Définition : Pour une matrice carrée $A$ d’ordre $p$ et un entier $n \geq 1$, $A^n = A \times A \times \cdots \times A$ ($n$ facteurs), avec la convention $A^0 = I_p$. Pour tout $n$, $A^{n+1} = A^n \times A = A \times A^n$.**

**Propriété : Matrice diagonale**
Pour $D = \begin{pmatrix} a & 0 \\ 0 & b \end{pmatrix}$ et tout entier $n \geq 0$, $D^n = \begin{pmatrix} a^n & 0 \\ 0 & b^n \end{pmatrix}$ (de même à l’ordre 3).

**Attention : Sauf pour une matrice diagonale, on n’obtient **pas** $A^n$ en élevant chaque coefficient à la puissance $n$.**

**Méthode : Calculer $A^n$**
1. Calculer $A^2$, $A^3$, $A^4$ (à la main ou à la calculatrice).
2. Conjecturer une formule pour $A^n$.
3. La démontrer par récurrence, en utilisant $A^{n+1} = A^n \times A$.

**Exemple : Soit $A = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}$. On trouve $A^2 = \begin{pmatrix} 1 & 2 \\ 0 & 1 \end{pmatrix}$ et $A^3 = \begin{pmatrix} 1 & 3 \\ 0 & 1 \end{pmatrix}$ : on conjecture que $A^n = \begin{pmatrix} 1 & n \\ 0 & 1 \end{pmatrix}$ pour tout entier $n \geq 0$.**

- **Initialisation** : $A^0 = I_2 = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$, la formule est vraie pour $n = 0$.
- **Hérédité** : si $A^n = \begin{pmatrix} 1 & n \\ 0 & 1 \end{pmatrix}$, alors $A^{n+1} = A^nA = \begin{pmatrix} 1 & n \\ 0 & 1 \end{pmatrix}\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} = \begin{pmatrix} 1 & n + 1 \\ 0 & 1 \end{pmatrix}$.

### Suites de matrices colonnes

**Théorème : Soit $A$ une matrice carrée et $(U_n)$ une suite de matrices colonnes telle que $U_{n+1} = AU_n$ pour tout entier $n$. Alors, pour tout entier $n \geq 0$ :**

$$U_n = A^nU_0$$

**Démonstration : Par récurrence : $U_0 = I\,U_0 = A^0U_0$ ; si $U_n = A^nU_0$, alors $U_{n+1} = AU_n = A\,A^nU_0 = A^{n+1}U_0$.**

**Exemple : Écrire une suite récurrente sous forme matricielle**
La suite définie par $u_0 = 0$, $u_1 = 1$ et $u_{n+2} = u_{n+1} + 2u_n$ s’étudie avec $U_n = \begin{pmatrix} u_{n+1} \\ u_n \end{pmatrix}$ :

$$U_{n+1} = \begin{pmatrix} u_{n+2} \\ u_{n+1} \end{pmatrix} = \begin{pmatrix} 1 & 2 \\ 1 & 0 \end{pmatrix}\begin{pmatrix} u_{n+1} \\ u_n \end{pmatrix}$$

donc $U_n = \begin{pmatrix} 1 & 2 \\ 1 & 0 \end{pmatrix}^n U_0$ avec $U_0 = \begin{pmatrix} 1 \\ 0 \end{pmatrix}$.

**Méthode : Suite $U_{n+1} = AU_n + C$**
1. Chercher une matrice colonne constante $L$ telle que $L = AL + C$, c’est-à-dire $(I - A)L = C$ ; si $I - A$ est inversible, $L = (I - A)^{-1}C$.
2. Poser $V_n = U_n - L$ : alors $V_{n+1} = AU_n + C - (AL + C) = AV_n$, donc $V_n = A^nV_0$.
3. Conclure : $U_n = A^n(U_0 - L) + L$.

**Exemple : $A = \begin{pmatrix} 0{,}5 & 0 \\ 0 & 0{,}25 \end{pmatrix}$, $C = \begin{pmatrix} 1 \\ 3 \end{pmatrix}$ et $U_0 = \begin{pmatrix} 0 \\ 0 \end{pmatrix}$. L’équation $(I_2 - A)L = C$ s’écrit $0{,}5\,\ell_1 = 1$ et $0{,}75\,\ell_2 = 3$, donc $L = \begin{pmatrix} 2 \\ 4 \end{pmatrix}$. Alors**

$$U_n = A^n(U_0 - L) + L = \begin{pmatrix} 2 - 2 \times 0{,}5^n \\ 4 - 4 \times 0{,}25^n \end{pmatrix}$$

Comme $0{,}5^n$ et $0{,}25^n$ tendent vers $0$, les coordonnées de $U_n$ tendent vers $2$ et $4$.

## V. Transformations géométriques du plan

**Propriété : Dans un repère orthonormé d’origine $O$, chacune des transformations ci-dessous envoie le point $M(x\,;y)$ sur le point $M'(x'\,;y')$ tel que $\begin{pmatrix} x' \\ y' \end{pmatrix} = A\begin{pmatrix} x \\ y \end{pmatrix}$.**

| Transformation | Matrice $A$ |
|---|---|
| Rotation de centre $O$ et d’angle $\theta$ | $\begin{pmatrix} \cos\theta & -\sin\theta \\ \sin\theta & \cos\theta \end{pmatrix}$ |
| Symétrie d’axe $(Ox)$ | $\begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}$ |
| Symétrie d’axe $(Oy)$ | $\begin{pmatrix} -1 & 0 \\ 0 & 1 \end{pmatrix}$ |
| Homothétie de centre $O$ et de rapport $k$ | $\begin{pmatrix} k & 0 \\ 0 & k \end{pmatrix}$ |

**Exemple : La rotation de centre $O$ et d’angle $\dfrac{\pi}{2}$ a pour matrice $R = \begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix}$, car $\cos\dfrac{\pi}{2} = 0$ et $\sin\dfrac{\pi}{2} = 1$. L’image de $M(2\,;1)$ est $M'(-1\,;2)$, car $\begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix}\begin{pmatrix} 2 \\ 1 \end{pmatrix} = \begin{pmatrix} -1 \\ 2 \end{pmatrix}$.**

![Rotation de centre O et d'angle pi sur 2 : le point M(2 ; 1) a pour image M'(-1 ; 2)](https://optitab-media.s3.eu-north-1.amazonaws.com/cours_images/v1_n104_co112_3_cours_rotation.png)

**Attention : Composer deux transformations**
Appliquer d’abord la transformation de matrice $A$, puis celle de matrice $B$, revient à appliquer la matrice $BA$ (et non $AB$) : $X'' = B(AX) = (BA)X$.

## VI. Graphes

### Vocabulaire

**Définition : Graphe**
Un **graphe** (non orienté) est formé de **sommets** et d’**arêtes** ; chaque arête relie deux sommets distincts, et deux sommets sont reliés par au plus une arête. Deux sommets reliés par une arête sont **adjacents**.

- L’**ordre** du graphe est son nombre de sommets.
- Le **degré** d’un sommet est le nombre d’arêtes dont il est une extrémité.
- Un graphe est **complet** si deux sommets distincts quelconques sont toujours adjacents.

![Graphe non orienté G à cinq sommets A, B, C, D, E et sept arêtes](https://optitab-media.s3.eu-north-1.amazonaws.com/cours_images/v1_n104_co112_4_cours_graphe.png)

**Exemple : Le graphe $G$ est d’ordre $5$ et possède $7$ arêtes. $A$ et $B$ sont adjacents ; $A$ et $C$ ne le sont pas, donc $G$ n’est pas complet.**

| Sommet | $A$ | $B$ | $C$ | $D$ | $E$ |
|---|---|---|---|---|---|
| Degré | $2$ | $3$ | $3$ | $4$ | $2$ |

**Propriété : La somme des degrés des sommets d’un graphe est égale au **double du nombre d’arêtes**.**

**Démonstration : Chaque arête a deux extrémités : elle est comptée une fois dans le degré de chacune d’elles, donc deux fois dans la somme des degrés. Pour $G$ : $2 + 3 + 3 + 4 + 2 = 14 = 2 \times 7$.**

**Propriété : Graphe complet**
Dans le graphe complet $K_n$ à $n$ sommets, chaque sommet est de degré $n - 1$ ; la somme des degrés vaut $n(n - 1)$, donc $K_n$ possède $\dfrac{n(n - 1)}{2}$ arêtes.

![Graphes complets K4 (6 arêtes) et K5 (10 arêtes)](https://optitab-media.s3.eu-north-1.amazonaws.com/cours_images/v1_n104_co112_5_cours_complets.png)

### Chaînes et connexité

**Définition : - 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. Les sommets et les arêtes peuvent se répéter.**
- Une chaîne est **fermée** si son premier et son dernier sommet sont égaux ; un **cycle** est une chaîne fermée dont les arêtes sont toutes distinctes.
- Un graphe est **connexe** si deux sommets quelconques peuvent toujours être reliés par une chaîne.

**Exemple : Dans $G$, $A - B - C - E$ est une chaîne de longueur $3$ et $B - C - D - B$ est un cycle de longueur $3$. Le graphe $G$ est connexe ; si on lui retire les arêtes $C - E$ et $D - E$, le sommet $E$ est isolé et le graphe obtenu n’est plus connexe.**

![Le graphe G est connexe ; sans les arêtes C-E et D-E, le sommet E est isolé et le graphe n'est plus connexe](https://optitab-media.s3.eu-north-1.amazonaws.com/cours_images/v1_n104_co112_6_cours_connexe.png)

### Graphes orientés, graphes pondérés

**Définition : - Dans un **graphe orienté**, les arêtes ont un sens : ce sont des **arcs**. Un **chemin** est une suite de sommets dans laquelle chaque sommet est relié au suivant par un arc ; sa longueur est son nombre d’arcs.**
- Dans un **graphe pondéré**, chaque arête (ou arc) porte un nombre, son **poids** : distance, durée, coût, probabilité…

**Exemple : Le graphe pondéré ci-dessous donne les durées de trajet, en minutes, entre cinq villages. La chaîne $A - B - D - E$ a pour poids $3 + 9 + 12 = 24$ et la chaîne $A - D - E$ a pour poids $7 + 12 = 19$ : elle est plus rapide.**

![Graphe pondéré : durées de trajet en minutes entre les villages A, B, C, D et E](https://optitab-media.s3.eu-north-1.amazonaws.com/cours_images/v1_n104_co112_7_cours_pondere.png)

## VII. Matrice d’adjacence et nombre de chemins

**Définition : Soit un graphe d’ordre $p$ dont les sommets sont numérotés de $1$ à $p$. Sa **matrice d’adjacence** est la matrice carrée $M$ d’ordre $p$ dont le coefficient $m_{ij}$ vaut $1$ si une arête relie $i$ et $j$ (si un arc va de $i$ vers $j$, pour un graphe orienté), et $0$ sinon.**

**Propriété : - Pour un graphe non orienté, $M$ est **symétrique** ($m_{ij} = m_{ji}$) et la somme de la ligne $i$ est le degré du sommet $i$.**
- Pour un graphe orienté, la somme de la ligne $i$ est le nombre d’arcs qui partent du sommet $i$.
- Sans boucle, la diagonale de $M$ ne contient que des $0$.

**Exemple : Graphe non orienté**
Dans l’ordre $A$, $B$, $C$, $D$, $E$, la matrice d’adjacence du graphe $G$ est

$$M_G = \begin{pmatrix} 0 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 & 0 \end{pmatrix}$$

Elle est symétrique ; la ligne de $D$ contient quatre $1$ : $D$ est de degré $4$.

![Graphe orienté H : arcs A vers B, B vers C, C vers A, A vers D, C vers D et D vers B](https://optitab-media.s3.eu-north-1.amazonaws.com/cours_images/v1_n104_co112_8_cours_oriente.png)

**Exemple : Graphe orienté**
Le graphe orienté $H$ a pour arcs $A \to B$, $B \to C$, $C \to A$, $A \to D$, $C \to D$ et $D \to B$. Dans l’ordre $A$, $B$, $C$, $D$ :

$$M = \begin{pmatrix} 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \end{pmatrix}$$

Elle n’est pas symétrique : il y a un arc $A \to B$ mais pas d’arc $B \to A$.

**Théorème : Nombre de chemins de longueur $n$**
Soit $M$ la matrice d’adjacence d’un graphe et $n \geq 1$ un entier. Le coefficient $(M^n)_{ij}$ est égal au **nombre de chemins de longueur $n$** (de chaînes de longueur $n$ pour un graphe non orienté) qui vont du sommet $i$ au sommet $j$.

**Démonstration : Par récurrence sur $n$. Pour $n = 1$, c’est la définition de $M$.**

Supposons la propriété vraie pour un entier $n \geq 1$. Un chemin de longueur $n + 1$ de $i$ à $j$ est formé d’un chemin de longueur $n$ de $i$ à un sommet $k$ (son avant-dernier sommet), suivi d’un arc de $k$ vers $j$. Pour $k$ fixé, il y a $(M^n)_{ik}$ chemins de $i$ à $k$, et chacun se prolonge de $m_{kj}$ façons ($1$ si l’arc $k \to j$ existe, $0$ sinon) : cela fait $(M^n)_{ik}\,m_{kj}$ chemins. Les cas $k = 1, \dots, p$ ne se recouvrent pas, donc le nombre total est

$$\sum_{k=1}^{p} (M^n)_{ik}\,m_{kj} = (M^nM)_{ij} = (M^{n+1})_{ij}$$

**Exemple : Interpréter $M^2$**
Pour le graphe orienté $H$ :

$$M^2 = \begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 0 & 2 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}$$

Le coefficient ligne $C$, colonne $B$ vaut $2$ : il y a deux chemins de longueur $2$ de $C$ vers $B$, $C \to A \to B$ et $C \to D \to B$. Le coefficient ligne $B$, colonne $B$ est nul : aucun chemin de longueur $2$ ne part de $B$ pour y revenir.

![Les deux chemins de longueur 2 de C vers B, en vert : C-A-B et C-D-B](https://optitab-media.s3.eu-north-1.amazonaws.com/cours_images/v1_n104_co112_9_cours_chemins.png)

**Méthode : Calculer rapidement une ligne de $M^2$**
La ligne $i$ de $M^2$ est la **somme des lignes de $M$ des sommets atteints depuis $i$ par un arc**. Dans $H$, de $C$ partent les arcs $C \to A$ et $C \to D$ : la ligne $C$ de $M^2$ est la somme des lignes $A$ et $D$ de $M$, soit $\begin{pmatrix} 0 & 1 & 0 & 1 \end{pmatrix} + \begin{pmatrix} 0 & 1 & 0 & 0 \end{pmatrix} = \begin{pmatrix} 0 & 2 & 0 & 1 \end{pmatrix}$.

**Remarque : Pour aller plus loin : connexité et matrice**
Un graphe d’ordre $p$ est connexe si et seulement si tous les coefficients de $I_p + M + M^2 + \cdots + M^{p-1}$ sont strictement positifs : deux sommets reliés par une chaîne le sont par une chaîne de longueur au plus $p - 1$. Pour un graphe orienté, cette condition signifie que l’on peut aller de tout sommet à tout autre par un chemin : on dit que le graphe est **fortement connexe**.

**Attention : - Les coefficients de $M^n$ comptent les chemins de longueur **exactement** $n$, sommets répétés compris.**
- On fixe l’ordre des sommets avant d’écrire $M$ : ligne $=$ départ, colonne $=$ arrivée.
- Les puissances de la matrice des poids d’un graphe pondéré ne comptent pas les chemins.

## VIII. Chaînes de Markov

### Matrice de transition et graphe

**Définition : Un système peut se trouver dans deux ou trois **états** ; on note $X_n$ son état à l’étape $n$ ($n = 0, 1, 2, \dots$). La suite $(X_n)$ est une **chaîne de Markov** si la probabilité de passer de l’état $i$ à l’état $j$ ne dépend que de $i$ et de $j$ (ni de $n$, ni des états antérieurs). On note**

$$p_{ij} = P_{(X_n = i)}(X_{n+1} = j)$$

La **matrice de transition** est $P = (p_{ij})$ : la ligne $i$ correspond à l’état de départ, la colonne $j$ à l’état d’arrivée. Le **graphe pondéré associé** a un sommet par état et un arc $i \to j$ de poids $p_{ij}$ lorsque $p_{ij} \neq 0$ (une boucle si $i = j$).

**Propriété : Les coefficients de $P$ sont positifs ou nuls et la **somme des coefficients de chaque ligne vaut $1$** : sur le graphe, les poids des arcs qui partent d’un sommet, boucle comprise, ont pour somme $1$.**

**Exemple : Deux états**
Chaque semaine, un abonné utilise l’une de deux plateformes $A$ et $B$. S’il est sur $A$, il y reste la semaine suivante avec la probabilité $0{,}8$ ; s’il est sur $B$, il passe sur $A$ avec la probabilité $0{,}3$. Dans l’ordre $A$, $B$ :

$$P = \begin{pmatrix} 0{,}8 & 0{,}2 \\ 0{,}3 & 0{,}7 \end{pmatrix}$$

![Graphe probabiliste à deux états A et B avec les probabilités de transition 0,8 ; 0,2 ; 0,3 ; 0,7](https://optitab-media.s3.eu-north-1.amazonaws.com/cours_images/v1_n104_co112_10_cours_markov2.png)

### Distribution après $n$ transitions

**Définition : La **distribution** à l’étape $n$ est la matrice ligne $\pi_n$ des probabilités des états ; pour deux états, $\pi_n = \begin{pmatrix} P(X_n = A) & P(X_n = B) \end{pmatrix}$. La matrice $\pi_0$ est la **distribution initiale**.**

**Théorème : Pour tout entier $n \geq 0$ :**

- $\pi_{n+1} = \pi_nP$, donc $\pi_n = \pi_0P^n$ ;
- le coefficient $(P^n)_{ij}$ est la probabilité de passer de l’état $i$ à l’état $j$ en $n$ transitions : $(P^n)_{ij} = P_{(X_0 = i)}(X_n = j)$.

**Démonstration : Les événements $(X_n = k)$, pour les différents états $k$, forment une partition. D’après la formule des probabilités totales, $P(X_{n+1} = j)$ est la somme, sur tous les états $k$, des produits $P(X_n = k) \times P_{(X_n = k)}(X_{n+1} = j)$. Comme $P_{(X_n = k)}(X_{n+1} = j) = p_{kj}$ :**

$$P(X_{n+1} = j) = \sum_{k} P(X_n = k)\,p_{kj}$$

C’est le coefficient $j$ de la matrice ligne $\pi_nP$ : donc $\pi_{n+1} = \pi_nP$, et par récurrence $\pi_n = \pi_0P^n$.

Si la chaîne part de l’état $i$ avec certitude, $\pi_0$ a un $1$ en position $i$ et des $0$ ailleurs : $\pi_n = \pi_0P^n$ est alors la ligne $i$ de $P^n$, et son coefficient $j$ est $(P^n)_{ij}$.

**Exemple : L’abonné est sur $A$ au départ : $\pi_0 = \begin{pmatrix} 1 & 0 \end{pmatrix}$. Alors**

$$\pi_1 = \pi_0P = \begin{pmatrix} 0{,}8 & 0{,}2 \end{pmatrix}$$

Pour $\pi_2 = \pi_1P$, on calcule ses deux coefficients :

$$
\begin{aligned}
0{,}8 \times 0{,}8 + 0{,}2 \times 0{,}3 &= 0{,}7 \\
0{,}8 \times 0{,}2 + 0{,}2 \times 0{,}7 &= 0{,}3
\end{aligned}
$$

donc $\pi_2 = \begin{pmatrix} 0{,}7 & 0{,}3 \end{pmatrix}$.

La probabilité qu’il soit sur $A$ deux semaines plus tard est $0{,}7$ : c’est aussi le coefficient $(P^2)_{AA}$, car $P^2 = \begin{pmatrix} 0{,}7 & 0{,}3 \\ 0{,}45 & 0{,}55 \end{pmatrix}$.

**Attention : La distribution est une matrice **ligne**, placée **à gauche** de $P$ : $\pi_{n+1} = \pi_nP$, et non $P\pi_n$.**

### Distribution invariante

**Définition : Une distribution $\pi$ (matrice ligne à coefficients positifs ou nuls, de somme $1$) est **invariante** si $\pi P = \pi$ : si la chaîne a la distribution $\pi$ à une étape, elle la garde à toutes les étapes suivantes.**

**Méthode : Déterminer une distribution invariante**
On pose $\pi = \begin{pmatrix} p & q \end{pmatrix}$ (ou $\pi = \begin{pmatrix} a & b & c \end{pmatrix}$ pour trois états), on écrit le système $\pi P = \pi$ et on lui ajoute l’équation $p + q = 1$ (ou $a + b + c = 1$).

**Exemple : Pour $P = \begin{pmatrix} 0{,}8 & 0{,}2 \\ 0{,}3 & 0{,}7 \end{pmatrix}$, la première équation de $\pi P = \pi$ est $0{,}8p + 0{,}3q = p$, soit $0{,}3q = 0{,}2p$, c’est-à-dire $q = \dfrac{2}{3}p$ (la seconde équation donne la même condition). Avec $p + q = 1$ : $\dfrac{5}{3}p = 1$, donc $p = 0{,}6$ et $q = 0{,}4$. La distribution invariante est $\pi = \begin{pmatrix} 0{,}6 & 0{,}4 \end{pmatrix}$.**

**Exemple : Évolution à long terme**
Avec $a_n = P(X_n = A)$, on a $P(X_n = B) = 1 - a_n$, donc

$$
\begin{aligned}
a_{n+1} &= 0{,}8a_n + 0{,}3(1 - a_n) \\
&= 0{,}5a_n + 0{,}3
\end{aligned}
$$

Ainsi $a_{n+1} - 0{,}6 = 0{,}5(a_n - 0{,}6)$ : la suite $(a_n - 0{,}6)$ est géométrique de raison $0{,}5$ et $a_n = 0{,}6 + (a_0 - 0{,}6) \times 0{,}5^n$. Comme $0{,}5^n$ tend vers $0$, $a_n$ tend vers $0{,}6$ : quelle que soit la distribution initiale, $\pi_n$ se rapproche de la distribution invariante $\begin{pmatrix} 0{,}6 & 0{,}4 \end{pmatrix}$.

![Probabilités a_n d'être en A : depuis A ou depuis B, elles se rapprochent de 0,6](https://optitab-media.s3.eu-north-1.amazonaws.com/cours_images/v1_n104_co112_11_cours_convergence.png)

**Exemple : Trois états**
Un pion se déplace sur trois cases alignées $A$, $B$, $C$. Depuis $A$ (ou depuis $C$), il reste sur place ou va en $B$, avec la probabilité $0{,}5$ chaque fois ; depuis $B$, il reste en $B$ avec la probabilité $0{,}5$ et va en $A$ ou en $C$ avec la probabilité $0{,}25$ chaque fois. Dans l’ordre $A$, $B$, $C$ :

$$P = \begin{pmatrix} 0{,}5 & 0{,}5 & 0 \\ 0{,}25 & 0{,}5 & 0{,}25 \\ 0 & 0{,}5 & 0{,}5 \end{pmatrix}$$

Avec $\pi = \begin{pmatrix} a & b & c \end{pmatrix}$, le système $\pi P = \pi$ s’écrit

$$\begin{cases} 0{,}5a + 0{,}25b = a \\ 0{,}5a + 0{,}5b + 0{,}5c = b \\ 0{,}25b + 0{,}5c = c \end{cases}$$

La première équation donne $b = 2a$, la troisième $b = 2c$. Avec $a + b + c = 1$ : $a + 2a + a = 1$, donc $a = c = 0{,}25$ et $b = 0{,}5$ (la deuxième équation est alors vérifiée). La distribution invariante est $\begin{pmatrix} 0{,}25 & 0{,}5 & 0{,}25 \end{pmatrix}$.

![Graphe probabiliste à trois états A, B, C alignés, avec boucles et probabilités 0,5 et 0,25](https://optitab-media.s3.eu-north-1.amazonaws.com/cours_images/v1_n104_co112_12_cours_markov3.png)

### Calcul avec Python

Le programme suivant calcule $\pi_n = \pi_0P^n$ en appliquant $n$ fois la relation $\pi_{k+1} = \pi_kP$ (les listes représentent les matrices ligne par ligne).

```python
def distrib(pi, P, n):
    k = len(P)
    for _ in range(n):
        pi = [sum(pi[i] * P[i][j]
              for i in range(k))
              for j in range(k)]
    return pi

P = [[0.8, 0.2],
     [0.3, 0.7]]
pi = distrib([1, 0], P, 2)
print([round(p, 4)
       for p in pi])
# affiche [0.7, 0.3]
```

Avec $n = 20$, le programme affiche `[0.6, 0.4]` : on retrouve la distribution invariante.

## IX. L’essentiel

**À retenir : - $(AB)_{ij}$ : ligne $i$ de $A$ par colonne $j$ de $B$ ; en général $AB \neq BA$.**
- Si $ad - bc \neq 0$, $\begin{pmatrix} a & b \\ c & d \end{pmatrix}^{-1} = \dfrac{1}{ad - bc}\begin{pmatrix} d & -b \\ -c & a \end{pmatrix}$ ; si $A$ est inversible, $AX = Y \iff X = A^{-1}Y$.
- $U_{n+1} = AU_n$ donne $U_n = A^nU_0$ ; pour $U_{n+1} = AU_n + C$, on cherche $L = AL + C$, puis $U_n = A^n(U_0 - L) + L$.
- $(M^n)_{ij}$ est le nombre de chemins de longueur $n$ de $i$ à $j$.
- Chaîne de Markov : $\pi_n = \pi_0P^n$ ; distribution invariante : $\pi P = \pi$, avec des coefficients de somme $1$.

**Attention : Erreurs fréquentes**
- Multiplier des matrices de tailles incompatibles, ou dans le mauvais ordre.
- Écrire $\dfrac{1}{A}$ ou « diviser » par une matrice.
- Calculer $A^n$ en élevant chaque coefficient à la puissance $n$ (faux, sauf pour une matrice diagonale).
- Inverser lignes et colonnes dans une matrice d’adjacence ou de transition : ligne $=$ départ.
- Oublier une boucle dans un graphe de Markov : les poids qui partent de chaque sommet ont pour somme $1$.

## Fiche de révision

**Objectifs : Retenir l’essentiel de « Graphes et matrices » : calcul matriciel, systèmes, suites, graphes et chaînes de Markov. Programme de Mathématiques expertes.**

## I. Calcul matriciel

**Formule : $(AB)_{ij} = \displaystyle\sum_{k} a_{ik}\,b_{kj}$ : ligne $i$ de $A$ par colonne $j$ de $B$**

1. $AB$ existe si le nombre de colonnes de $A$ est égal au nombre de lignes de $B$ ; en général $AB \neq BA$.
2. $A$ est inversible si $AA^{-1} = A^{-1}A = I_n$. Ordre 2 : si $ad - bc \neq 0$, $\begin{pmatrix} a & b \\ c & d \end{pmatrix}^{-1} = \dfrac{1}{ad - bc}\begin{pmatrix} d & -b \\ -c & a \end{pmatrix}$.
3. Système $AX = Y$ avec $A$ inversible : $X = A^{-1}Y$.
4. Rotation de centre $O$ et d’angle $\theta$ : $\begin{pmatrix} \cos\theta & -\sin\theta \\ \sin\theta & \cos\theta \end{pmatrix}$ ; homothétie de rapport $k$ : $kI_2$.

## II. Puissances et suites

1. $A^0 = I$ et $A^{n+1} = A^nA$ ; pour une matrice diagonale, on élève les coefficients diagonaux à la puissance $n$.
2. Méthode : calculer $A^2$, $A^3$, conjecturer $A^n$, puis démontrer par récurrence.
3. $U_{n+1} = AU_n$ donne $U_n = A^nU_0$.
4. $U_{n+1} = AU_n + C$ : on cherche $L$ tel que $L = AL + C$ ; alors $U_n = A^n(U_0 - L) + L$.

## III. Graphes

![Graphe non orienté G à cinq sommets A, B, C, D, E et sept arêtes](https://optitab-media.s3.eu-north-1.amazonaws.com/synthesis_images/v1_n104_fi49_1_cours_graphe.png)

1. Ordre : nombre de sommets ; degré d’un sommet : nombre d’arêtes issues de ce sommet ; somme des degrés $= 2 \times$ nombre d’arêtes.
2. Graphe complet $K_n$ : $\dfrac{n(n - 1)}{2}$ arêtes. Graphe connexe : deux sommets quelconques sont reliés par une chaîne.
3. Matrice d’adjacence : $m_{ij} = 1$ s’il y a une arête (un arc) de $i$ vers $j$, $0$ sinon ; elle est symétrique pour un graphe non orienté.

**Théorème : $(M^n)_{ij}$ est le nombre de chemins (de chaînes) de longueur $n$ qui vont du sommet $i$ au sommet $j$.**

## IV. Chaînes de Markov

![Graphe probabiliste à deux états A et B avec les probabilités de transition 0,8 ; 0,2 ; 0,3 ; 0,7](https://optitab-media.s3.eu-north-1.amazonaws.com/synthesis_images/v1_n104_fi49_2_cours_markov2.png)

1. $p_{ij}$ : probabilité de passer de l’état $i$ à l’état $j$ ; chaque ligne de $P$ a pour somme $1$.
2. $\pi_{n+1} = \pi_nP$ et $\pi_n = \pi_0P^n$ ; $(P^n)_{ij}$ est la probabilité d’aller de $i$ à $j$ en $n$ étapes.
3. Distribution invariante : $\pi P = \pi$, coefficients positifs de somme $1$. Pour $P = \begin{pmatrix} 0{,}8 & 0{,}2 \\ 0{,}3 & 0{,}7 \end{pmatrix}$, on trouve $\pi = \begin{pmatrix} 0{,}6 & 0{,}4 \end{pmatrix}$.

## V. Les pièges à éviter

**Attention : Les 5 erreurs classiques**
1. Calculer $BA$ au lieu de $AB$, ou un produit de tailles incompatibles.
2. « Diviser » par une matrice : on multiplie par $A^{-1}$, du bon côté.
3. Calculer $A^n$ coefficient par coefficient (juste seulement pour une matrice diagonale).
4. Confondre lignes et colonnes : ligne $=$ départ, colonne $=$ arrivée.
5. Écrire $P\pi_n$ au lieu de $\pi_nP$.

**Remarque : Réflexe**
Graphe → matrice d’adjacence → puissances pour compter les chemins. Chaîne de Markov → matrice de transition → $\pi_0P^n$ et $\pi P = \pi$.

## Exercices corrigés

### Exercice 1 : Marche aléatoire et état stable

Un randonneur passe chaque nuit dans l'un des trois refuges $A$, $B$, $C$ d'un massif ; les refuges $A$ et $C$ ne sont reliés que par l'intermédiaire de $B$. Chaque matin, il choisit sa prochaine étape ainsi :

- s'il est en $A$, il y reste avec la probabilité $0{,}7$, sinon il va en $B$ ;
- s'il est en $B$, il va en $A$ avec la probabilité $0{,}2$, reste en $B$ avec la probabilité $0{,}3$, sinon il va en $C$ ;
- s'il est en $C$, il y reste avec la probabilité $0{,}7$, sinon il va en $B$.

On note $X_n$ le refuge de la nuit $n$ et $\pi_n = \begin{pmatrix} P(X_n = A) & P(X_n = B) & P(X_n = C) \end{pmatrix}$. La nuit $0$, le randonneur dort en $A$.

1. Représenter la situation par un graphe probabiliste, puis écrire la matrice de transition $P$ (états rangés dans l'ordre $A$, $B$, $C$).
2. Donner $\pi_0$, puis calculer $\pi_1$ et $\pi_2$.
3. Quelle est la probabilité que le randonneur dorme en $C$ la nuit $2$ ? Quel coefficient de $P^2$ cette probabilité représente-t-elle ?
4. Montrer que, pour tout entier $n \geq 1$, $P(X_n = B) = 0{,}3$.
5. Déterminer la distribution invariante $\pi = \begin{pmatrix} a & b & c \end{pmatrix}$ de cette chaîne de Markov.
6. On admet que $\pi_n$ converge vers $\pi$. Interpréter ce résultat.

#### Correction détaillée

## Question 1 : Graphe probabiliste et matrice de transition

**Méthode : Un sommet par état ; un arc $i \to j$ portant la probabilité $p_{ij}$ de passer de $i$ à $j$ (une boucle pour rester sur place). La ligne $i$ de $P$ contient les probabilités des arcs qui partent de $i$.**

**Etape : Le graphe**
Depuis $A$ : boucle $0{,}7$ et arc vers $B$ de poids $1 - 0{,}7 = 0{,}3$. Depuis $B$ : arcs vers $A$ ($0{,}2$), vers $C$ ($1 - 0{,}2 - 0{,}3 = 0{,}5$) et boucle $0{,}3$. Depuis $C$ : boucle $0{,}7$ et arc vers $B$ de poids $0{,}3$.

![Graphe probabiliste des refuges A, B, C : boucles 0,7 en A, 0,3 en B, 0,7 en C ; arcs A vers B 0,3, B vers A 0,2, B vers C 0,5, C vers B 0,3](https://optitab-media.s3.eu-north-1.amazonaws.com/exercice_images/v1_n104_ex1140_1_ex1140_graphe.png)

**Etape : La matrice de transition**
$$P = \begin{pmatrix} 0{,}7 & 0{,}3 & 0 \\ 0{,}2 & 0{,}3 & 0{,}5 \\ 0 & 0{,}3 & 0{,}7 \end{pmatrix}$$
Contrôle : la somme de chaque ligne vaut $1$ ($0{,}7 + 0{,}3$ ; $0{,}2 + 0{,}3 + 0{,}5$ ; $0{,}3 + 0{,}7$).

**Resultat : $$P = \begin{pmatrix} 0{,}7 & 0{,}3 & 0 \\ 0{,}2 & 0{,}3 & 0{,}5 \\ 0 & 0{,}3 & 0{,}7 \end{pmatrix}$$**

## Question 2 : $\pi_0$, $\pi_1$ et $\pi_2$

**Méthode : $\pi_{n+1} = \pi_nP$ : la distribution est une matrice **ligne**, placée à gauche de $P$.**

**Etape : Distribution initiale et $\pi_1$**
Le randonneur est en $A$ la nuit $0$ : $\pi_0 = \begin{pmatrix} 1 & 0 & 0 \end{pmatrix}$. Alors $\pi_1 = \pi_0P$ est la première ligne de $P$ :
$$\pi_1 = \begin{pmatrix} 0{,}7 & 0{,}3 & 0 \end{pmatrix}$$

**Etape : Calcul de $\pi_2 = \pi_1P$, coefficient par coefficient**
$$
\begin{aligned}
0{,}7 \times 0{,}7 + 0{,}3 \times 0{,}2 + 0 \times 0 &= 0{,}55 \\
0{,}7 \times 0{,}3 + 0{,}3 \times 0{,}3 + 0 \times 0{,}3 &= 0{,}3 \\
0{,}7 \times 0 + 0{,}3 \times 0{,}5 + 0 \times 0{,}7 &= 0{,}15
\end{aligned}
$$
Contrôle : $0{,}55 + 0{,}3 + 0{,}15 = 1$.

**Resultat : $\pi_0 = \begin{pmatrix} 1 & 0 & 0 \end{pmatrix}$, $\pi_1 = \begin{pmatrix} 0{,}7 & 0{,}3 & 0 \end{pmatrix}$ et $\pi_2 = \begin{pmatrix} 0{,}55 & 0{,}3 & 0{,}15 \end{pmatrix}$.**

**Attention : Erreur fréquente**
Écrire $P\pi_n$ au lieu de $\pi_nP$ : avec des lignes de $P$ correspondant aux états de départ, la distribution se multiplie **à gauche**.

## Question 3 : Probabilité d'être en $C$ la nuit $2$

**Etape : Lecture de $\pi_2$**
$P(X_2 = C)$ est le troisième coefficient de $\pi_2$ : $0{,}15$.

**Etape : Lien avec $P^2$**
$\pi_2 = \pi_0P^2$ et $\pi_0 = \begin{pmatrix} 1 & 0 & 0 \end{pmatrix}$ : $\pi_2$ est la première ligne de $P^2$. Donc $0{,}15 = (P^2)_{AC}$, la probabilité de passer de $A$ à $C$ en deux transitions.

**Point : Vérification sur le graphe**
Le seul chemin de longueur $2$ de $A$ à $C$ est $A \to B \to C$ (il n'y a pas d'arc $A \to C$) : sa probabilité est $0{,}3 \times 0{,}5 = 0{,}15$.

**Resultat : $P(X_2 = C) = 0{,}15$ : c'est le coefficient $(P^2)_{AC}$, ligne $A$ et colonne $C$ de $P^2$.**

## Question 4 : $P(X_n = B) = 0{,}3$ pour $n \geq 1$

**Méthode : Écrire le deuxième coefficient de $\pi_{n+1} = \pi_nP$ et remarquer que la colonne $B$ de $P$ est constante.**

**Etape : Deuxième coefficient de $\pi_{n+1}$**
Avec $\pi_n = \begin{pmatrix} a_n & b_n & c_n \end{pmatrix}$ :
$$
\begin{aligned}
b_{n+1} &= 0{,}3a_n + 0{,}3b_n + 0{,}3c_n \\
&= 0{,}3\left(a_n + b_n + c_n\right)
\end{aligned}
$$

**Etape : Conclure**
$a_n + b_n + c_n = 1$ (les trois états forment une partition), donc $b_{n+1} = 0{,}3$ pour tout entier $n \geq 0$.

**Resultat : Pour tout entier $n \geq 1$, $P(X_n = B) = 0{,}3$ : quel que soit le refuge de la veille, il va en $B$ avec la probabilité $0{,}3$.**

## Question 5 : Distribution invariante

**Méthode : Écrire le système $\pi P = \pi$, puis ajouter la condition $a + b + c = 1$.**

**Etape : Le système $\pi P = \pi$**
$$\begin{cases} 0{,}7a + 0{,}2b = a \\ 0{,}3a + 0{,}3b + 0{,}3c = b \\ 0{,}5b + 0{,}7c = c \end{cases}$$

**Etape : Résolution avec $a + b + c = 1$**
- Deuxième équation : $0{,}3(a + b + c) = b$, donc $b = 0{,}3$.
- Première équation : $0{,}2b = 0{,}3a$, donc $a = \dfrac{0{,}2 \times 0{,}3}{0{,}3} = 0{,}2$.
- Troisième équation : $0{,}5b = 0{,}3c$, donc $c = \dfrac{0{,}5 \times 0{,}3}{0{,}3} = 0{,}5$.

**Point : Vérification**
$0{,}2 + 0{,}3 + 0{,}5 = 1$. Première équation : $0{,}7 \times 0{,}2 + 0{,}2 \times 0{,}3 = 0{,}2$, c'est bien $a$.

**Resultat : La distribution invariante est $\pi = \begin{pmatrix} 0{,}2 & 0{,}3 & 0{,}5 \end{pmatrix}$.**

## Question 6 : Interprétation

**Etape : État stable**
Lorsque $n$ devient grand, $P(X_n = A)$, $P(X_n = B)$ et $P(X_n = C)$ se rapprochent de $0{,}2$, $0{,}3$ et $0{,}5$ : c'est l'état stable de la marche.

![Probabilités d'être en A, B et C la nuit n pour un départ en A : elles se rapprochent de 0,2, 0,3 et 0,5](https://optitab-media.s3.eu-north-1.amazonaws.com/exercice_images/v1_n104_ex1140_2_ex1140_convergence.png)

**Resultat : À long terme, le randonneur dort en $C$ une nuit sur deux en moyenne, en $B$ $30\,\%$ des nuits et en $A$ $20\,\%$ des nuits, quel que soit son refuge de départ.**

#### Réponses

1. $P = \begin{pmatrix} 0{,}7 & 0{,}3 & 0 \\ 0{,}2 & 0{,}3 & 0{,}5 \\ 0 & 0{,}3 & 0{,}7 \end{pmatrix}$ ; graphe : boucles $0{,}7$ ($A$), $0{,}3$ ($B$), $0{,}7$ ($C$) ; arcs $A \to B$ ($0{,}3$), $B \to A$ ($0{,}2$), $B \to C$ ($0{,}5$), $C \to B$ ($0{,}3$).
2. $\pi_0 = \begin{pmatrix} 1 & 0 & 0 \end{pmatrix}$, $\pi_1 = \begin{pmatrix} 0{,}7 & 0{,}3 & 0 \end{pmatrix}$, $\pi_2 = \begin{pmatrix} 0{,}55 & 0{,}3 & 0{,}15 \end{pmatrix}$.
3. $P(X_2 = C) = 0{,}15 = (P^2)_{AC}$.
4. $b_{n+1} = 0{,}3(a_n + b_n + c_n) = 0{,}3$.
5. $\pi = \begin{pmatrix} 0{,}2 & 0{,}3 & 0{,}5 \end{pmatrix}$.
6. À long terme : $20\,\%$ des nuits en $A$, $30\,\%$ en $B$, $50\,\%$ en $C$.

### Exercice 2 : Graphe orienté et nombre de chemins

On considère le graphe orienté ci-dessous, de sommets $A$, $B$, $C$, $D$, dont les arcs sont $A \to B$, $A \to C$, $B \to C$, $B \to D$, $C \to A$, $C \to D$ et $D \to A$.

![Graphe orienté à quatre sommets A, B, C, D avec les arcs A-B, A-C, B-C, B-D, C-A, C-D et D-A](https://optitab-media.s3.eu-north-1.amazonaws.com/exercice_images/v1_n104_ex1142_1_ex1142_graphe.png)

1. Écrire la matrice d’adjacence $M$ de ce graphe (sommets rangés dans l’ordre $A$, $B$, $C$, $D$).
2. Calculer $M^2$ et interpréter ses coefficients.
3. Calculer $M^3$ et interpréter le coefficient situé ligne $A$, colonne $A$.
4. Déterminer le nombre de chemins de longueur $2$ de $A$ vers $D$, puis les citer.
5. Un graphe orienté est dit **fortement connexe** si, pour tous sommets distincts $X$ et $Y$, il existe un chemin de $X$ vers $Y$. Ce graphe est-il fortement connexe ?

#### Correction détaillée

## Question 1 : Matrice d’adjacence

**Méthode : $m_{ij} = 1$ s’il existe un arc du sommet $i$ vers le sommet $j$, $0$ sinon ; la ligne correspond au départ, la colonne à l’arrivée.**

**Etape : Lire les arcs sommet par sommet**
- Depuis $A$ : $A \to B$ et $A \to C$, donc ligne $A$ : $\begin{pmatrix} 0 & 1 & 1 & 0 \end{pmatrix}$.
- Depuis $B$ : $B \to C$ et $B \to D$, donc ligne $B$ : $\begin{pmatrix} 0 & 0 & 1 & 1 \end{pmatrix}$.
- Depuis $C$ : $C \to A$ et $C \to D$, donc ligne $C$ : $\begin{pmatrix} 1 & 0 & 0 & 1 \end{pmatrix}$.
- Depuis $D$ : $D \to A$, donc ligne $D$ : $\begin{pmatrix} 1 & 0 & 0 & 0 \end{pmatrix}$.

**Resultat : $$M = \begin{pmatrix} 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \end{pmatrix}$$**

## Question 2 : Calcul et interprétation de $M^2$

**Méthode : Dans $M^2 = M \times M$, la ligne d’un sommet $X$ est la somme des lignes de $M$ des sommets atteints depuis $X$ par un arc (c’est le calcul « ligne par colonne » regroupé).**

**Etape : Vérifier la méthode sur un coefficient**
$(M^2)_{AD} = 0 \times 0 + 1 \times 1 + 1 \times 1 + 0 \times 0 = 2$ (ligne $A$ de $M$ par colonne $D$ de $M$).

**Etape : Calculer les quatre lignes**
- Ligne $A$ (arcs vers $B$ et $C$) : $\begin{pmatrix} 0 & 0 & 1 & 1 \end{pmatrix} + \begin{pmatrix} 1 & 0 & 0 & 1 \end{pmatrix} = \begin{pmatrix} 1 & 0 & 1 & 2 \end{pmatrix}$.
- Ligne $B$ (arcs vers $C$ et $D$) : $\begin{pmatrix} 1 & 0 & 0 & 1 \end{pmatrix} + \begin{pmatrix} 1 & 0 & 0 & 0 \end{pmatrix} = \begin{pmatrix} 2 & 0 & 0 & 1 \end{pmatrix}$.
- Ligne $C$ (arcs vers $A$ et $D$) : $\begin{pmatrix} 0 & 1 & 1 & 0 \end{pmatrix} + \begin{pmatrix} 1 & 0 & 0 & 0 \end{pmatrix} = \begin{pmatrix} 1 & 1 & 1 & 0 \end{pmatrix}$.
- Ligne $D$ (arc vers $A$) : $\begin{pmatrix} 0 & 1 & 1 & 0 \end{pmatrix}$.

**Resultat : $$M^2 = \begin{pmatrix} 1 & 0 & 1 & 2 \\ 2 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 0 \end{pmatrix}$$**

**Point : Interprétation**
$(M^2)_{XY}$ est le nombre de chemins de longueur $2$ de $X$ vers $Y$. Par exemple :

- $(M^2)_{AA} = 1$ : un seul chemin, $A \to C \to A$ ;
- $(M^2)_{BA} = 2$ : $B \to C \to A$ et $B \to D \to A$ ;
- $(M^2)_{CB} = 1$ : $C \to A \to B$ ;
- $(M^2)_{BB} = 0$ : aucun chemin de longueur $2$ ne part de $B$ pour revenir en $B$.

## Question 3 : Calcul de $M^3$

**Méthode : $M^3 = M \times M^2$ : la ligne d’un sommet $X$ est la somme des lignes de $M^2$ des sommets atteints depuis $X$ par un arc.**

**Etape : Calculer les quatre lignes**
- Ligne $A$ (vers $B$, $C$) : $\begin{pmatrix} 2 & 0 & 0 & 1 \end{pmatrix} + \begin{pmatrix} 1 & 1 & 1 & 0 \end{pmatrix} = \begin{pmatrix} 3 & 1 & 1 & 1 \end{pmatrix}$.
- Ligne $B$ (vers $C$, $D$) : $\begin{pmatrix} 1 & 1 & 1 & 0 \end{pmatrix} + \begin{pmatrix} 0 & 1 & 1 & 0 \end{pmatrix} = \begin{pmatrix} 1 & 2 & 2 & 0 \end{pmatrix}$.
- Ligne $C$ (vers $A$, $D$) : $\begin{pmatrix} 1 & 0 & 1 & 2 \end{pmatrix} + \begin{pmatrix} 0 & 1 & 1 & 0 \end{pmatrix} = \begin{pmatrix} 1 & 1 & 2 & 2 \end{pmatrix}$.
- Ligne $D$ (vers $A$) : $\begin{pmatrix} 1 & 0 & 1 & 2 \end{pmatrix}$.

**Resultat : $$M^3 = \begin{pmatrix} 3 & 1 & 1 & 1 \\ 1 & 2 & 2 & 0 \\ 1 & 1 & 2 & 2 \\ 1 & 0 & 1 & 2 \end{pmatrix}$$**

**Point : Interprétation de $(M^3)_{AA} = 3$**
Il y a trois chemins de longueur $3$ qui partent de $A$ et y reviennent : $A \to B \to C \to A$, $A \to B \to D \to A$ et $A \to C \to D \to A$.

## Question 4 : Chemins de longueur 2 de $A$ vers $D$

**Etape : Lire le coefficient**
Le nombre cherché est $(M^2)_{AD}$, ligne $A$ et colonne $D$ de $M^2$ : il vaut $2$.

**Etape : Citer les chemins**
Un chemin de longueur $2$ de $A$ vers $D$ passe par un sommet intermédiaire $X$ avec $A \to X$ et $X \to D$. Depuis $A$, on peut aller en $B$ ou en $C$, et les deux arcs $B \to D$ et $C \to D$ existent.

![Les deux chemins de longueur 2 de A vers D, en vert : A-B-D et A-C-D](https://optitab-media.s3.eu-north-1.amazonaws.com/exercice_images/v1_n104_ex1142_2_ex1142_chemins.png)

**Resultat : Il y a $2$ chemins de longueur $2$ de $A$ vers $D$ : $A \to B \to D$ et $A \to C \to D$.**

## Question 5 : Le graphe est-il fortement connexe ?

**Méthode : Chercher un circuit (chemin fermé) qui passe par tous les sommets : en le suivant, on va de n’importe quel sommet à n’importe quel autre.**

**Etape : Trouver un circuit passant par tous les sommets**
Les arcs $A \to B$, $B \to C$, $C \to D$ et $D \to A$ existent : $A \to B \to C \to D \to A$ est un circuit qui passe par les quatre sommets.

**Etape : Conclure**
Pour aller d’un sommet $X$ à un sommet $Y$, il suffit de suivre ce circuit depuis $X$ jusqu’à $Y$. Le graphe est donc fortement connexe.

**Remarque : Contrôle matriciel**
Tous les coefficients de $I_4 + M + M^2 + M^3 = \begin{pmatrix} 5 & 2 & 3 & 3 \\ 3 & 3 & 3 & 2 \\ 3 & 2 & 4 & 3 \\ 2 & 1 & 2 & 3 \end{pmatrix}$ sont non nuls : chaque sommet en atteint chaque autre par un chemin de longueur au plus $3$.

**Resultat : Le graphe est fortement connexe.**

#### Réponses

1. $M = \begin{pmatrix} 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \end{pmatrix}$
2. $M^2 = \begin{pmatrix} 1 & 0 & 1 & 2 \\ 2 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 0 \end{pmatrix}$ : $(M^2)_{XY}$ est le nombre de chemins de longueur $2$ de $X$ vers $Y$.
3. $M^3 = \begin{pmatrix} 3 & 1 & 1 & 1 \\ 1 & 2 & 2 & 0 \\ 1 & 1 & 2 & 2 \\ 1 & 0 & 1 & 2 \end{pmatrix}$ ; $(M^3)_{AA} = 3$ : trois chemins de longueur $3$ de $A$ à $A$.
4. $2$ chemins : $A \to B \to D$ et $A \to C \to D$.
5. Oui : le circuit $A \to B \to C \to D \to A$ passe par tous les sommets.

### Exercice 3 : Puissances d'une matrice et suite de matrices

On considère la matrice $A = \begin{pmatrix} 2 & 1 \\ 0 & 2 \end{pmatrix}$ et la suite de matrices colonnes $(M_n)$ définie par $M_0 = \begin{pmatrix} 1 \\ 1 \end{pmatrix}$ et, pour tout entier naturel $n$, $M_{n+1} = A \times M_n$.

1. Calculer $A^2$, $A^3$ et $A^4$.
2. Conjecturer une formule pour $A^n$, $n \geq 1$.
3. Démontrer par récurrence la formule conjecturée.
4. Calculer $M_1$, $M_2$, $M_3$ et $M_4$.
5. Exprimer $M_n$ en fonction de $n$.

#### Correction détaillée

## Question 1 : Calcul de $A^2$, $A^3$, $A^4$

**Etape : Calculer $A^2$**
$$
\begin{aligned}
A^2 &= \begin{pmatrix} 2 & 1 \\ 0 & 2 \end{pmatrix}\begin{pmatrix} 2 & 1 \\ 0 & 2 \end{pmatrix} \\
&= \begin{pmatrix} 2 \times 2 + 1 \times 0 & 2 \times 1 + 1 \times 2 \\ 0 \times 2 + 2 \times 0 & 0 \times 1 + 2 \times 2 \end{pmatrix} \\
&= \begin{pmatrix} 4 & 4 \\ 0 & 4 \end{pmatrix}
\end{aligned}
$$

**Etape : Calculer $A^3 = A^2 \times A$**
$$
\begin{aligned}
A^3 &= \begin{pmatrix} 4 & 4 \\ 0 & 4 \end{pmatrix}\begin{pmatrix} 2 & 1 \\ 0 & 2 \end{pmatrix} \\
&= \begin{pmatrix} 8 & 4 + 8 \\ 0 & 8 \end{pmatrix} \\
&= \begin{pmatrix} 8 & 12 \\ 0 & 8 \end{pmatrix}
\end{aligned}
$$

**Etape : Calculer $A^4 = A^3 \times A$**
$$
\begin{aligned}
A^4 &= \begin{pmatrix} 8 & 12 \\ 0 & 8 \end{pmatrix}\begin{pmatrix} 2 & 1 \\ 0 & 2 \end{pmatrix} \\
&= \begin{pmatrix} 16 & 8 + 24 \\ 0 & 16 \end{pmatrix} \\
&= \begin{pmatrix} 16 & 32 \\ 0 & 16 \end{pmatrix}
\end{aligned}
$$

**Resultat : $A^2 = \begin{pmatrix} 4 & 4 \\ 0 & 4 \end{pmatrix}$, $A^3 = \begin{pmatrix} 8 & 12 \\ 0 & 8 \end{pmatrix}$ et $A^4 = \begin{pmatrix} 16 & 32 \\ 0 & 16 \end{pmatrix}$.**

## Question 2 : Conjecture

**Etape : Coefficients diagonaux**
On lit $2^n$ sur la diagonale : $2, 4, 8, 16$.

**Etape : Coefficient en haut à droite**
| $n$ | $1$ | $2$ | $3$ | $4$ |
|---|---|---|---|---|
| Coefficient | $1$ | $4$ | $12$ | $32$ |
| $n \times 2^{n-1}$ | $1 \times 1$ | $2 \times 2$ | $3 \times 4$ | $4 \times 8$ |

**Resultat : Conjecture : pour tout entier $n \geq 1$, $A^n = \begin{pmatrix} 2^n & n \times 2^{n-1} \\ 0 & 2^n \end{pmatrix}$.**

## Question 3 : Démonstration par récurrence

**Etape : Énoncer la propriété**
Pour $n \geq 1$, on note $\mathcal{P}(n)$ : « $A^n = \begin{pmatrix} 2^n & n \times 2^{n-1} \\ 0 & 2^n \end{pmatrix}$ ».

**Etape : Initialisation**
Pour $n = 1$ : $\begin{pmatrix} 2^1 & 1 \times 2^0 \\ 0 & 2^1 \end{pmatrix} = \begin{pmatrix} 2 & 1 \\ 0 & 2 \end{pmatrix} = A$. Donc $\mathcal{P}(1)$ est vraie.

**Etape : Hérédité**
Soit $k \geq 1$ tel que $\mathcal{P}(k)$ est vraie. Alors $A^{k+1} = A^k \times A = \begin{pmatrix} 2^k & k \times 2^{k-1} \\ 0 & 2^k \end{pmatrix}\begin{pmatrix} 2 & 1 \\ 0 & 2 \end{pmatrix}$, d’où

$$
\begin{aligned}
(A^{k+1})_{11} &= 2^k \times 2 + k \times 2^{k-1} \times 0 = 2^{k+1} \\
(A^{k+1})_{12} &= 2^k \times 1 + k \times 2^{k-1} \times 2 \\
&=  2^k + k \times 2^k \\
&= (k + 1) \times 2^k \\
(A^{k+1})_{21} &= 0 \times 2 + 2^k \times 0 = 0 \\
(A^{k+1})_{22} &= 0 \times 1 + 2^k \times 2 = 2^{k+1}
\end{aligned}
$$

C’est la formule au rang $k + 1$ : $\mathcal{P}(k + 1)$ est vraie.

**Resultat : Par récurrence, pour tout entier $n \geq 1$, $A^n = \begin{pmatrix} 2^n & n \times 2^{n-1} \\ 0 & 2^n \end{pmatrix}$.**

## Question 4 : Calcul de $M_1$ à $M_4$

**Etape : Appliquer $M_{n+1} = AM_n$**
$$
\begin{aligned}
M_1 &= \begin{pmatrix} 2 & 1 \\ 0 & 2 \end{pmatrix}\begin{pmatrix} 1 \\ 1 \end{pmatrix} = \begin{pmatrix} 2 + 1 \\ 2 \end{pmatrix} = \begin{pmatrix} 3 \\ 2 \end{pmatrix} \\
M_2 &= \begin{pmatrix} 2 & 1 \\ 0 & 2 \end{pmatrix}\begin{pmatrix} 3 \\ 2 \end{pmatrix} = \begin{pmatrix} 6 + 2 \\ 4 \end{pmatrix} = \begin{pmatrix} 8 \\ 4 \end{pmatrix} \\
M_3 &= \begin{pmatrix} 2 & 1 \\ 0 & 2 \end{pmatrix}\begin{pmatrix} 8 \\ 4 \end{pmatrix} \\
&=  \begin{pmatrix} 16 + 4 \\ 8 \end{pmatrix} \\
&= \begin{pmatrix} 20 \\ 8 \end{pmatrix} \\
M_4 &= \begin{pmatrix} 2 & 1 \\ 0 & 2 \end{pmatrix}\begin{pmatrix} 20 \\ 8 \end{pmatrix} \\
&=  \begin{pmatrix} 40 + 8 \\ 16 \end{pmatrix} \\
&= \begin{pmatrix} 48 \\ 16 \end{pmatrix}
\end{aligned}
$$

**Resultat : $M_1 = \begin{pmatrix} 3 \\ 2 \end{pmatrix}$, $M_2 = \begin{pmatrix} 8 \\ 4 \end{pmatrix}$, $M_3 = \begin{pmatrix} 20 \\ 8 \end{pmatrix}$ et $M_4 = \begin{pmatrix} 48 \\ 16 \end{pmatrix}$.**

## Question 5 : Expression de $M_n$

**Méthode : Comme $M_{n+1} = AM_n$, on a $M_n = A^nM_0$ pour tout entier $n$ ; on utilise la formule de $A^n$.**

**Etape : Calculer le produit**
$$
\begin{aligned}
M_n = A^nM_0 &= \begin{pmatrix} 2^n & n \times 2^{n-1} \\ 0 & 2^n \end{pmatrix}\begin{pmatrix} 1 \\ 1 \end{pmatrix} \\
&= \begin{pmatrix} 2^n + n \times 2^{n-1} \\ 2^n \end{pmatrix} \\
&= \begin{pmatrix} (n + 2) \times 2^{n-1} \\ 2^n \end{pmatrix}
\end{aligned}
$$

car $2^n = 2 \times 2^{n-1}$.

**Point : Vérification**
Pour $n = 4$ : $6 \times 2^3 = 48$ et $2^4 = 16$, on retrouve $M_4$.

**Resultat : Pour tout entier $n \geq 1$ : $M_n = \begin{pmatrix} (n + 2) \times 2^{n-1} \\ 2^n \end{pmatrix}$.**

#### Réponses

1. $A^2 = \begin{pmatrix} 4 & 4 \\ 0 & 4 \end{pmatrix}$, $A^3 = \begin{pmatrix} 8 & 12 \\ 0 & 8 \end{pmatrix}$, $A^4 = \begin{pmatrix} 16 & 32 \\ 0 & 16 \end{pmatrix}$
2. Conjecture : $A^n = \begin{pmatrix} 2^n & n \times 2^{n-1} \\ 0 & 2^n \end{pmatrix}$
3. Initialisation pour $n = 1$, hérédité par le calcul de $A^k \times A$.
4. $M_1 = \begin{pmatrix} 3 \\ 2 \end{pmatrix}$, $M_2 = \begin{pmatrix} 8 \\ 4 \end{pmatrix}$, $M_3 = \begin{pmatrix} 20 \\ 8 \end{pmatrix}$, $M_4 = \begin{pmatrix} 48 \\ 16 \end{pmatrix}$
5. $M_n = \begin{pmatrix} (n + 2) \times 2^{n-1} \\ 2^n \end{pmatrix}$
