Mathématiques du lycée · Grades 10–12

30Matrices et graphes

Une matrice est un tableau rectangulaire de nombres, additionné et multiplié selon des règles conçues pour que l’algèbre matricielle représente la composition des applications linéaires. Les matrices résolvent les systèmes linéaires, pilotent les suites récurrentes couplées, et comptent les chemins dans les réseaux — les mathématiques derrière les moteurs de recherche et les algorithmes de plus court chemin.

30.1 Algèbre matricielle

Définition 30.1 (Matrice)

Une matrice $m \times n$ est un tableau de nombres réels à $m$ lignes et $n$ colonnes : $A = (a_{ij})$ , où $a_{ij}$ est l’entrée de la ligne $i$ , colonne $j$ . Deux matrices de même taille s’additionnent entrée par entrée, et $\lambda A = (\lambda a_{ij})$ .

Définition 30.2 (Produit matriciel)

Soit $A$ de taille $m \times n$ et $B$ de taille $n \times p$ . Le produit $AB$ est la matrice $m \times p$ dont l’entrée $(i,j)$ est

(AB)_{ij} = \sum_{k=1}^{n} a_{ik} b_{kj}

(la règle « ligne $i$ de $A$ multipliée par colonne $j$ de $B$ »).

Exemple 30.3

$\begin{pmatrix} 1 & 2\\ 3 & 4\end{pmatrix} \begin{pmatrix} 0 & 1\\ 1 & 1\end{pmatrix} = \begin{pmatrix} 2 & 3\\ 4 & 7\end{pmatrix}$ , tandis que $\begin{pmatrix} 0 & 1\\ 1 & 1\end{pmatrix} \begin{pmatrix} 1 & 2\\ 3 & 4\end{pmatrix} = \begin{pmatrix} 3 & 4\\ 4 & 6\end{pmatrix}$ : la multiplication matricielle n’est pas commutative.

Proposition 30.4 (Règles de l’algèbre matricielle)

Dès que les tailles rendent les produits significatifs :

(AB)C = A(BC), \qquad A(B + C) = AB + AC, \qquad (A+B)C = AC + BC,

et la matrice identité $I_n$ (uns sur la diagonale, zéros ailleurs) satisfait $I_m A = A I_n = A$ pour $A$ de taille $m \times n$ .

Démonstration. Toutes se vérifient entrée par entrée à partir de Définition 30.2 ; l’associativité, la seule non triviale, revient à échanger deux sommes finies : $\bigl((AB)C\bigr)_{ij} = \sum_l \left(\sum_k a_{ik}b_{kl}\right) c_{lj} = \sum_k a_{ik} \left(\sum_l b_{kl} c_{lj}\right) = \bigl(A(BC)\bigr)_{ij}$ . ∎

Définition 30.5 (Inverse)

Une matrice carrée $A$ de taille $n$ est inversible s’il existe une matrice $B$ avec $AB = BA = I_n$ ; $B$ est alors unique, notée $A^{-1}$ .

Proposition 30.6 (Inverse d’une matrice $2\times2$ )

Soit $A = \begin{pmatrix} a & b\\ c & d\end{pmatrix}$ et $\det A = ad - bc$ (le déterminant). Alors $A$ est inversible si et seulement si $\det A \neq 0$ , auquel cas

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

Démonstration. Un calcul donne $A \begin{pmatrix} d & -b\\ -c & a\end{pmatrix} = \begin{pmatrix} d & -b\\ -c & a\end{pmatrix} A = (ad - bc) I_2$ ; si $ad - bc \neq 0$ , diviser. Réciproquement, si $ad - bc = 0$ , les colonnes de $A$ sont proportionnelles, et de même les colonnes de $AB$ pour toute $B$ ; mais les colonnes de $I_2$ ne le sont pas, donc aucune $B$ ne peut vérifier $AB = I_2$ . ∎

Méthode 30.7 (Systèmes linéaires)

Le système $\begin{cases} ax + by = e\\ cx + dy = f \end{cases}$ est l’équation matricielle $AX = Y$ avec $X = \begin{pmatrix} x \\ y\end{pmatrix}$ , $Y = \begin{pmatrix} e \\ f\end{pmatrix}$ . Si $\det A \neq 0$ , sa solution unique est $X = A^{-1}Y$ . Le même formalisme traite $n$ équations à $n$ inconnues.

30.2 Puissances de matrices et suites récurrentes

Définition 30.8

Pour une matrice carrée $A$ et $k \in \N$ , $A^k = A \times \dots \times A$ ( $k$ facteurs), avec $A^0 = I$ .

Méthode 30.9 (Cas diagonal-plus-nilpotent et diagonalisable)

Deux façons standards de calculer $A^k$ :

Si $A = \lambda I + N$ avec $N^2 = 0$ , la formule du binôme (valable ici car $I$ et $N$ commutent) se réduit à deux termes : $A^k = \lambda^k I + k \lambda^{k-1} N$ .
Si l’on trouve une $P$ inversible avec $A = PDP^{-1}$ et $D$ diagonale, alors $A^k = P D^k P^{-1}$ , et $D^k$ se calcule entrée par entrée. (Trouver une telle $P$ de façon systématique est la théorie de la diagonalisation, développée à l’université ; à ce niveau $P$ est donnée.)

Exemple 30.10 (Suites couplées)

Soient $u_{n+1} = 3u_n + v_n$ et $v_{n+1} = u_n + 3v_n$ . En posant $X_n = \begin{pmatrix} u_n\\ v_n \end{pmatrix}$ et $A = \begin{pmatrix} 3 & 1\\ 1 & 3\end{pmatrix}$ , on obtient $X_{n+1} = AX_n$ , donc $X_n = A^n X_0$ . Les suites auxiliaires $s_n = u_n + v_n$ et $d_n = u_n - v_n$ vérifient $s_{n+1} = 4s_n$ et $d_{n+1} = 2d_n$ , donc $s_n = 4^n s_0$ , $d_n = 2^n d_0$ et

u_n = \frac{4^n(u_0+v_0) + 2^n(u_0-v_0)}{2}, \qquad v_n = \frac{4^n(u_0+v_0) - 2^n(u_0-v_0)}{2}.

(En coulisse : $(1,1)$ et $(1,-1)$ sont des directions propres de $A$ .)

30.3 Graphes et chemins

Définition 30.11 (Graphe, matrice d’adjacence)

Un graphe est constitué de sommets $1, 2, \dots, n$ et d’arêtes joignant certaines paires de sommets (couples ordonnés pour un graphe orienté). Sa matrice d’adjacence est la matrice $n \times n$ $M$ avec $m_{ij} = 1$ s’il y a une arête de $i$ vers $j$ , et $0$ sinon. Un chemin de longueur $k$ de $i$ vers $j$ est une suite de $k$ arêtes consécutives menant de $i$ à $j$ .

M = pmatrix 0 & 1 & 1\\ 0 & 0 & 1\\ 1 & 0 & 0 pmatrix Un graphe orienté et sa matrice d’adjacence () : m_ij = 1 exactement lorsqu’il y a une arête de i vers j. — $M = \begin{pmatrix} 0 & 1 & 1\\ 0 & 0 & 1\\ 1 & 0 & 0 \end{pmatrix}$ Un graphe orienté et sa matrice d’adjacence (Exercice 30.6) : $m_{ij} = 1$ exactement lorsqu’il y a une arête de $i$ vers $j$ .

Théorème 30.12 (Dénombrement des chemins)

Le nombre de chemins de longueur $k$ du sommet $i$ au sommet $j$ est l’entrée $(i,j)$ de $M^k$ .

Démonstration. Récurrence sur $k$ . Pour $k = 1$ c’est la définition de $M$ . Supposer le résultat pour $k$ . Un chemin de longueur $k+1$ de $i$ à $j$ est un chemin de longueur $k$ de $i$ vers un certain sommet $l$ , suivi d’une arête de $l$ vers $j$ ; par les principes d’addition et de multiplication, leur nombre est

\sum_{l=1}^{n} \bigl(M^k\bigr)_{il}\, m_{lj} = \bigl(M^{k+1}\bigr)_{ij}. \qedhere

∎

Exemple 30.13

Pour le graphe triangle ( $3$ sommets, toutes les paires jointes), $M = \begin{pmatrix} 0&1&1\\ 1&0&1\\ 1&1&0\end{pmatrix}$ et $M^2 = \begin{pmatrix} 2&1&1\\ 1&2&1\\ 1&1&2\end{pmatrix}$ : depuis chaque sommet il y a $2$ chemins de longueur $2$ vers soi-même (via l’un ou l’autre voisin) et $1$ vers chaque autre sommet.

30.4 Exercices

Exercice 30.1 ★

Soient $A = \begin{pmatrix} 1 & 2\\ 0 & 1 \end{pmatrix}$ et $B = \begin{pmatrix} 2 & 0\\ 1 & 1 \end{pmatrix}$ . Calculer $A + B$ , $AB$ , $BA$ et $A^2$ .

Solution

Solution de Exercice 30.1.

A + B = \begin{pmatrix} 3 & 2\\ 1 & 2\end{pmatrix}, \quad AB = \begin{pmatrix} 4 & 2\\ 1 & 1\end{pmatrix}, \quad BA = \begin{pmatrix} 2 & 4\\ 1 & 3\end{pmatrix}, \quad A^2 = \begin{pmatrix} 1 & 4\\ 0 & 1\end{pmatrix}.

Noter $AB \neq BA$ .

Exercice 30.2 ★

Déterminer si les matrices suivantes sont inversibles, et calculer les inverses lorsqu’ils existent :

A = \begin{pmatrix} 2 & 5\\ 1 & 3\end{pmatrix}, \qquad B = \begin{pmatrix} 3 & 6\\ 2 & 4\end{pmatrix}.

Solution

Solution de Exercice 30.2.

$\det A = 6 - 5 = 1 \neq 0$ : $A^{-1} = \begin{pmatrix} 3 & -5\\ -1 & 2 \end{pmatrix}$ . $\det B = 12 - 12 = 0$ : $B$ n’est pas inversible.

Exercice 30.3 ★

Résoudre par inversion matricielle le système $\begin{cases} 2x + 5y = 1\\ x + 3y = 2 . \end{cases}$

Solution

Solution de Exercice 30.3.

Le système est $AX = Y$ avec $A$ comme dans l’Exercice 30.2 et $Y = \begin{pmatrix} 1\\ 2\end{pmatrix}$ :

X = A^{-1}Y = \begin{pmatrix} 3 & -5\\ -1 & 2\end{pmatrix} \begin{pmatrix} 1\\ 2\end{pmatrix} = \begin{pmatrix} -7\\ 3\end{pmatrix}: \qquad x = -7,\ y = 3 .

Exercice 30.4 ★★

Soit $A = \begin{pmatrix} 2 & 1\\ 0 & 2\end{pmatrix} = 2I + N$ avec $N = \begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix}$ .

Vérifier que $N^2 = 0$ et que $I$ et $N$ commutent.
En déduire $A^k$ pour tout $k \in \N$ et vérifier la formule pour $k=2$ par calcul direct.

Solution

Solution de Exercice 30.4.

1. $N^2 = \begin{pmatrix} 0&1\\0&0\end{pmatrix} \begin{pmatrix} 0&1\\0&0\end{pmatrix} = 0$ , et $I$ commute avec toute matrice.

2. Comme les deux termes commutent, la formule du binôme s’applique et tous les termes contenant $N^2$ s’annulent :

A^k = (2I + N)^k = 2^k I + k\,2^{k-1} N = \begin{pmatrix} 2^k & k\,2^{k-1}\\ 0 & 2^k \end{pmatrix}.

Vérification pour $k = 2$ : $A^2 = \begin{pmatrix} 2&1\\0&2\end{pmatrix}^2 = \begin{pmatrix} 4&4\\0&4\end{pmatrix}$ , et la formule donne $2^2 = 4$ , $2 \times 2 = 4$ . ✓

Exercice 30.5 ★★

Soient $A = \begin{pmatrix} 0 & 1\\ 1 & 1\end{pmatrix}$ et $F_n$ la suite de Fibonacci ( $F_0 = 0$ , $F_1 = 1$ , $F_{n+2} = F_{n+1} + F_n$ ). Montrer par récurrence que pour $n \geq 1$ ,

A^n = \begin{pmatrix} F_{n-1} & F_n\\ F_n & F_{n+1}\end{pmatrix},

et en déduire l’identité $F_{n+1}F_{n-1} - F_n^2 = (-1)^n$ . (Indication : les déterminants se multiplient : $\det(MN) = \det M \det N$ , ce que l’on peut vérifier pour les matrices $2\times2$ .)

Solution

Solution de Exercice 30.5.

Récurrence. Pour $n = 1$ : $A^1 = \begin{pmatrix} 0&1\\1&1\end{pmatrix} = \begin{pmatrix} F_0 & F_1\\ F_1 & F_2\end{pmatrix}$ . Supposer la formule pour $n$ ; alors

A^{n+1} = A^n A = \begin{pmatrix} F_{n-1} & F_n\\ F_n & F_{n+1}\end{pmatrix} \begin{pmatrix} 0 & 1\\ 1 & 1\end{pmatrix} = \begin{pmatrix} F_n & F_{n-1} + F_n\\ F_{n+1} & F_n + F_{n+1}\end{pmatrix} = \begin{pmatrix} F_n & F_{n+1}\\ F_{n+1} & F_{n+2}\end{pmatrix}.

Identité. Pour les matrices $2\times2$ , le développement montre $\det(MN) = \det M \det N$ ; d’où $\det(A^n) = (\det A)^n = (-1)^n$ , et $\det A^n = F_{n-1}F_{n+1} - F_n^2$ . (C’est l’identité de Cassini.)

Exercice 30.6 ★★

Un graphe orienté sur les sommets $\{1, 2, 3\}$ a les arêtes $1\to2$ , $2\to3$ , $3\to1$ et $1\to3$ .

Écrire la matrice d’adjacence $M$ et calculer $M^2$ et $M^3$ .
Combien de chemins de longueur $3$ vont de $1$ à $1$ ? Les lister.

Solution

Solution de Exercice 30.6.

1. En ordonnant les sommets $1, 2, 3$ :

M = \begin{pmatrix} 0&1&1\\ 0&0&1\\ 1&0&0\end{pmatrix}, \quad M^2 = \begin{pmatrix} 1&0&1\\ 1&0&0\\ 0&1&1\end{pmatrix}, \quad M^3 = \begin{pmatrix} 1&1&1\\ 1&0&1\\ 1&0&1 \end{pmatrix}.

2. $\bigl(M^3\bigr)_{11} = 1$ : exactement un chemin fermé de longueur $3$ au sommet $1$ , à savoir $1 \to 2 \to 3 \to 1$ . (Le chemin $1 \to 3 \to 1$ n’a que longueur $2$ , et $1 \to 3$ puis $3\to1$ puis $1\to3$ se termine en $3$ .)

Exercice 30.7 ★★

Une société d’autopartage déplace des véhicules entre deux villes $A$ et $B$ . Chaque semaine, $80\%$ des voitures en $A$ restent en $A$ et $20\%$ passent en $B$ ; $30\%$ des voitures en $B$ passent en $A$ et $70\%$ restent. Soient $a_n, b_n$ les proportions de la flotte dans chaque ville.

Écrire $X_{n+1} = MX_n$ avec $X_n = \begin{pmatrix} a_n\\ b_n\end{pmatrix}$ et identifier $M$ .
Trouver les proportions d’équilibre (résoudre $MX = X$ avec $a + b = 1$ ).
Montrer que $c_n = a_n - 0.6$ vérifie $c_{n+1} = 0.5\,c_n$ , et conclure que la répartition de la flotte converge vers l’équilibre.

Solution

Solution de Exercice 30.7.

1. $a_{n+1} = 0.8a_n + 0.3b_n$ , $b_{n+1} = 0.2a_n + 0.7b_n$ : $M = \begin{pmatrix} 0.8 & 0.3\\ 0.2 & 0.7\end{pmatrix}$ .

2. $MX = X$ donne $0.8a + 0.3b = a$ , c.-à-d. $0.3b = 0.2a$ , donc $b = \frac23 a$ ; avec $a + b = 1$ : $a = 0.6$ , $b = 0.4$ .

3. En utilisant $b_n = 1 - a_n$ : $a_{n+1} = 0.8a_n + 0.3(1 - a_n) = 0.5a_n + 0.3$ , donc

c_{n+1} = a_{n+1} - 0.6 = 0.5a_n + 0.3 - 0.6 = 0.5(a_n - 0.6) = 0.5\,c_n .

D’où $c_n = 0.5^n c_0 \to 0$ : $a_n \to 0.6$ et $b_n \to 0.4$ , quelle que soit la répartition initiale.

Exercice 30.8 ★★★

Soient $A = \begin{pmatrix} 3 & 1\\ 1 & 3 \end{pmatrix}$ , $P = \begin{pmatrix} 1 & 1\\ 1 & -1 \end{pmatrix}$ .

Calculer $P^{-1}$ , puis $D = P^{-1}AP$ , et vérifier que $D$ est diagonale.
En déduire une formule fermée pour $A^n$ et comparer avec Exemple 30.10.

Solution

Solution de Exercice 30.8.

1. $\det P = -2$ , donc $P^{-1} = -\frac12\begin{pmatrix} -1 & -1\\ -1 & 1\end{pmatrix} = \frac12\begin{pmatrix} 1 & 1\\ 1 & -1\end{pmatrix}$ . Puis

AP = \begin{pmatrix} 4 & 2\\ 4 & -2 \end{pmatrix}, \qquad D = P^{-1}AP = \frac12\begin{pmatrix} 1&1\\1&-1\end{pmatrix} \begin{pmatrix} 4&2\\4&-2\end{pmatrix} = \begin{pmatrix} 4 & 0\\ 0 & 2\end{pmatrix}.

2. De $A = PDP^{-1}$ , une récurrence immédiate donne $A^n = PD^nP^{-1}$ avec $D^n = \begin{pmatrix} 4^n & 0\\ 0 & 2^n\end{pmatrix}$ , donc

A^n = P D^n P^{-1} = \begin{pmatrix} 4^n & 2^n\\ 4^n & -2^n\end{pmatrix}\cdot \frac12\begin{pmatrix} 1&1\\1&-1\end{pmatrix} = \frac12\begin{pmatrix} 4^n + 2^n & 4^n - 2^n\\ 4^n - 2^n & 4^n + 2^n\end{pmatrix}.

Appliquer $A^n$ à $X_0 = \begin{pmatrix} u_0\\v_0\end{pmatrix}$ reproduit exactement les formules de l’Exemple 30.10.