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.

30.5 Problème : la matrice qui connaît Fibonacci (et la météo)

Problème 30.1

Devoir du week-end — une seule matrice $2 \times 2$ porte tout Fibonacci, une matrice de Markov prévoit la météo à long terme, et un vecteur propre vaut un milliard

Une matrice est une machine qui avale un état et renvoie le suivant — et ses puissances contiennent donc des avenirs entiers. Ce problème s’ouvre sur l’étonnante matrice dont les puissances égrènent les nombres de Fibonacci (et démontrent leurs identités en une ligne chacune), fait ensuite tourner la météo comme une chaîne de Markov jusqu’à son état stationnaire, et se referme sur le vecteur propre sur lequel un moteur de recherche a été bâti (Théorème 30.12, Méthode 30.9).

Partie I — Aisance.

Avec $A = \begin{pmatrix} 1 & 2\\ 3 & 4\end{pmatrix}$ et $B = \begin{pmatrix} 0 & 1\\ 1 & 0\end{pmatrix}$ : calculer $AB$ et $BA$ . Verdict sur la commutativité ?
Inverser $\begin{pmatrix} 2 & 1\\ 5 & 3\end{pmatrix}$ (Proposition 30.6) et se servir de l’inverse pour résoudre $2x + y = 4$ , $5x + 3y = 7$ .
Soit $N = \begin{pmatrix} 0 & 1\\ 0 & 0\end{pmatrix}$ : calculer $N^2$ , et en déduire $(I + N)^n = I + nN$ pour tout $n$ .
Le graphe triangle (trois sommets, toutes les paires reliées) : écrire sa matrice d’adjacence $A$ , calculer $A^3$ , et interpréter les coefficients diagonaux (Théorème 30.12).
Pour $D = \begin{pmatrix} 2 & 0\\ 0 & \frac12 \end{pmatrix}$ : donner $D^n$ et son comportement quand $n \to \infty$ .

Partie II — La matrice de Fibonacci. Posons $F = \begin{pmatrix} 1 & 1\\ 1 & 0\end{pmatrix}$ et notons $F_1 = F_2 = 1, F_3 = 2, \dots$ les nombres de Fibonacci du Problème 13.1.

Calculer $F^2$ , $F^3$ , $F^4$ et conjecturer la forme générale de $F^n$ en fonction des nombres de Fibonacci.
Démontrer la conjecture $F^n = \begin{pmatrix} F_{n+1} & F_n\\ F_n & F_{n-1} \end{pmatrix}$ par récurrence.
Prendre le déterminant des deux membres (le déterminant d’un produit est le produit des déterminants — le vérifier sur des matrices $2 \times 2$ si vous ne l’avez jamais vu) : en déduire l’identité de Cassini $F_{n+1}F_{n-1} - F_n^2 = (-1)^n$ — le moteur du carré évanoui, démontré en une ligne.
À partir de $F^{m+n} = F^m F^n$ , lire les coefficients en haut à droite et en déduire la formule d’addition

$F_{m+n} = F_{m+1} F_n + F_m F_{n-1} .$

La vérifier pour $m = n = 3$ .
Déduire de la formule d’addition (récurrence sur $k$ ) que $F_n$ divise $F_{kn}$ , et le vérifier sur $F_3 \mid F_6$ et $F_3 \mid F_9$ .
Pour calculer $F_{100}$ , nul besoin de multiplier $100$ matrices : élever au carré de façon répétée ( $F^2, F^4, F^8, \dots$ ) puis combiner. Combien de multiplications de matrices suffisent, et de quelle antique astuce de multiplication du volume précédent s’agit-il, promue aux matrices ?

Partie III — La machine à météo. Dans une certaine ville : après une journée ensoleillée, la suivante est ensoleillée avec la probabilité $0.8$ ; après une journée pluvieuse, elle est ensoleillée avec la probabilité $0.4$ . On code la loi du jour par une colonne $\binom{p_{\text{soleil}}}{p_{\text{pluie}}}$ et l’évolution par

M = \begin{pmatrix} 0.8 & 0.4\\ 0.2 & 0.6 \end{pmatrix}.

Vérifier que chaque colonne de $M$ a pour somme $1$ , et dire pourquoi toute machine à météo doit posséder cette propriété.
Aujourd’hui il fait soleil. Calculer la prévision pour demain, puis pour après-demain.
Déterminer l’état stationnaire : la loi $v$ telle que $Mv = v$ (et dont les coefficients ont pour somme $1$ ). Quelle fraction des jours est ensoleillée à long terme ?
Partir d’une journée pluvieuse, $\binom01$ , et appliquer $M$ quatre fois en suivant à chaque pas la distance à l’état stationnaire. Par quel facteur l’écart se réduit-il à chaque pas — et de quel type de convergence s’agit-il ?
Le PageRank en miniature : trois pages, avec les liens $A \to B$ , $A \to C$ , $B \to C$ , $C \to A$ . Un internaute aléatoire suit un lien sortant uniformément au hasard. Écrire la matrice de transition, déterminer l’état stationnaire, et classer les pages.
Interpréter le classement : pourquoi $C$ obtient-il un score aussi élevé que $A$ alors qu’il reçoit des liens de moins de pages — que mesure au juste l’état stationnaire ? (Le vrai PageRank ajoute un facteur d’amortissement pour les impasses et les sauts ; l’idée du vecteur propre est exactement celle-ci.)

Partie IV — Les dividendes de la diagonale.

Deux quantités couplées obéissent à $u_{n+1} = 3u_n + v_n$ , $v_{n+1} = u_n + 3v_n$ , c’est-à-dire à la matrice $A$ de l’Exercice 30.8. À l’aide de la diagonalisation de cet exercice ( $D = \operatorname{diag}(4, 2)$ ), donner la formule close de $u_n$ pour $u_0 = 1$ , $v_0 = 0$ , et la confronter au calcul direct pour $n = 1, 2, 3$ .
En une ou deux phrases : que fait la diagonalisation à un système couplé — et en quel sens l’état stationnaire de Markov de la question 14 est-il lui aussi une histoire de vecteur propre ?
Pour finir — les trois visages de la matrice ce week-end : la tenue de comptes (systèmes et inverses), le dénombrement (chemins et liens comptés par les puissances) et l’évolution (Fibonacci, la météo, le web — des avenirs lus sur les directions propres). Une phrase pour chacun, plus l’annonce : l’algèbre linéaire des volumes universitaires fait de chacun de ces visages une théorie.

Solution

Solution de Problème 30.1.

1. $AB = \begin{pmatrix} 2 & 1\\ 4 & 3\end{pmatrix}$ et $BA = \begin{pmatrix} 3 & 4\\ 1 & 2\end{pmatrix}$ : la multiplication des matrices n’est pas commutative — $B$ échange les colonnes à droite, les lignes à gauche.

2. Déterminant $6 - 5 = 1$ , d’où l’inverse $\begin{pmatrix} 3 & -1\\ -5 & 2\end{pmatrix}$ . En l’appliquant à $\binom{4}{7}$ : $x = 12 - 7 = 5$ , $y = -20 + 14 = -6$ .

3. $N^2 = 0$ . Alors $(I + N)^n = I + nN$ par récurrence : $(I + nN)(I + N) = I + (n+1)N + nN^2 = I + (n+1)N$ .

4. $A = \begin{pmatrix} 0&1&1\\ 1&0&1\\ 1&1&0 \end{pmatrix}$ , et $A^3$ a pour coefficients diagonaux $2$ : depuis chaque sommet, exactement deux chemins fermés de longueur $3$ (le triangle parcouru dans un sens ou dans l’autre) — le théorème de dénombrement à l’œuvre.

5. $D^n = \begin{pmatrix} 2^n & 0\\ 0 & 2^{-n} \end{pmatrix}$ : une direction explose, l’autre s’éteint — sur la diagonale, les destins sont des suites géométriques indépendantes.

6. $F^2 = \begin{pmatrix} 2 & 1\\ 1 & 1\end{pmatrix}$ , $F^3 = \begin{pmatrix} 3 & 2\\ 2 & 1\end{pmatrix}$ , $F^4 = \begin{pmatrix} 5 & 3\\ 3 & 2\end{pmatrix}$ : du Fibonacci partout, d’où la conjecture énoncée.

7. Si $F^n = \begin{pmatrix} F_{n+1} & F_n\\ F_n & F_{n-1}\end{pmatrix}$ , alors

F^{n+1} = F^n F = \begin{pmatrix} F_{n+1} + F_n & F_{n+1}\\ F_n + F_{n-1} & F_n \end{pmatrix} = \begin{pmatrix} F_{n+2} & F_{n+1}\\ F_{n+1} & F_n \end{pmatrix} :

hérédité ; l’initialisation en $n = 1$ n’est autre que $F$ lui-même, avec la convention $F_0 = 0$ (qui prolonge la récurrence vers l’arrière).

8. $\det F = -1$ , donc $\det(F^n) = (\det F)^n = (-1)^n$ ; et directement $\det(F^n) = F_{n+1}F_{n-1} - F_n^2$ : c’est Cassini, en une ligne. (La règle du produit pour les déterminants $2 \times 2$ est un agréable développement de cinq minutes.)

9. Coefficient en haut à droite de $F^m F^n$ : $F_{m+1}F_n + F_m F_{n-1}$ ; celui de $F^{m+n}$ : $F_{m+n}$ . Pour $m = n = 3$ : $F_4 F_3 + F_3 F_2 = 3 \times 2 + 2 \times 1 = 8 = F_6$ .

10. Pour $k = 1$ : c’est immédiat. Si $F_n \mid F_{kn}$ , la formule d’addition avec $m = kn$ donne $F_{(k+1)n} = F_{kn+1}F_n + F_{kn}F_{n-1}$ : les deux termes sont des multiples de $F_n$ . Donc $F_n \mid F_{kn}$ pour tout $k$ : vérification, $F_3 = 2$ divise $F_6 = 8$ et $F_9 = 34$ .

11. $F^{100} = F^{64} F^{32} F^4$ : sept élévations au carré ( $F^2, F^4, \dots, F^{64}$ ) plus deux combinaisons — neuf multiplications au lieu de quatre-vingt-dix-neuf. C’est l’astuce de la table de doublements des scribes égyptiens, transposée des nombres aux matrices : écrire $100$ en binaire, puis multiplier les doublements utiles.

12. $0.8 + 0.2 = 1$ et $0.4 + 0.6 = 1$ : demain il fera un temps ou un autre — chaque colonne est une loi de probabilité complète, si bien que les probabilités se conservent.

13. Demain : $\binom{0.8}{0.2}$ . Après-demain : $M\binom{0.8}{0.2} = \binom{0.72}{0.28}$ .

14. $Mv = v$ avec $v = \binom{s}{r}$ et $s + r = 1$ : $0.8s + 0.4r = s$ donne $0.4r = 0.2s$ , soit $s = 2r$ , d’où $v = \binom{2/3}{1/3}$ . À long terme, deux jours sur trois sont ensoleillés — quel que soit le temps qu’il fait aujourd’hui.

15. À partir de $\binom01$ : composantes ensoleillées $0.4$ , $0.56$ , $0.624$ , $0.6496$ ; écarts à $\frac23$ : $0.267$ , $0.107$ , $0.043$ , $0.017$ — chaque pas multiplie l’écart par exactement $0.4$ (la seconde valeur propre de la machine) : convergence géométrique vers l’état stationnaire.

16. Colonnes (issues de $A$ , $B$ , $C$ ) : $P = \begin{pmatrix} 0 & 0 & 1\\ \frac12 & 0 & 0\\ \frac12 & 1 & 0\end{pmatrix}$ . État stationnaire : $v_A = v_C$ , $v_B = \frac{v_A}{2}$ , $v_C = \frac{v_A}{2} + v_B$ ; en sommant à $1$ : $v = \left(\frac25, \frac15, \frac25\right)$ . Classement : $A$ et $C$ à égalité en tête, $B$ dernière.

17. $C$ reçoit tout le trafic de $B$ et la moitié de celui de $A$ , et il renvoie tout vers $A$ : l’état stationnaire mesure où l’internaute passe du temps, et non combien de liens pointent vers la page — un lien depuis une page fréquentée pèse plus que plusieurs liens depuis des pages désertes. Cette pondération récursive est précisément l’idée fondatrice du moteur ; l’amortissement gère les pièges et les impasses.

18. $A^n = P D^n P^{-1}$ donne $u_n = \frac{4^n + 2^n}{2}$ (et $v_n = \frac{4^n - 2^n}{2}$ ). Vérification : $u_1 = 3$ , $u_2 = 10$ , $u_3 = 36$ ; directement, $(1,0) \to (3,1) \to (10,6) \to (36, 28)$ : cela concorde.

19. La diagonalisation change de coordonnées pour des coordonnées dans lesquelles le système couplé se disloque en suites géométriques indépendantes — chaque valeur propre court sa propre course. L’état stationnaire de Markov est le vecteur propre associé à la valeur propre $1$ , et la vitesse de convergence de la question 15 est la valeur propre suivante : la machine à météo était depuis le début une histoire d’éléments propres.

20. Tenue de comptes : un système est une seule équation matricielle, résolue par un seul inverse. Dénombrement : les puissances de la matrice d’adjacence comptent les chemins, les liens et les connexions. Évolution : les puissances de la machine conduisent les états vers leurs destins, et les directions propres (la direction dorée de Fibonacci, l’état stationnaire de la météo, le vecteur de classement du web) sont ces destins. L’algèbre linéaire, dans les volumes universitaires, est la science de tout cela.

Termes définis dans ce chapitre

Voir les 395 termes du glossaire