Chapitre 3 — Matrices et graphes

Q: Pourquoi multiplier les matrices "ligne par colonne" ?

Cette définition vient de la composition des **applications linéaires**. Si $f$ et $g$ sont des transformations linéaires représentées par des matrices, alors $f \circ g$ est représenté par le produit matriciel. La règle "ligne × colonne" en découle naturellement.

Q: Pourquoi PageRank est-il basé sur des matrices ?

Parce que le web est un **graphe orienté géant** (~10 milliards de pages). La matrice d'adjacence pondérée permet de calculer simultanément le rang de toutes les pages via une itération matricielle convergeant vers le vecteur propre dominant.

À retenir

Programme officiel — Maths expertes, thème "Graphes et matrices".

Matrices : définitions

Notation

Une matrice $A$ de dimensions $m \times n$ ( $m$ lignes, $n$ colonnes) est un tableau :

A = \begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} \end{pmatrix}

$a_{ij}$ est le coefficient à la ligne $i$ , colonne $j$ .

Matrices carrées

Une matrice est carrée si $m = n$ . Cas particuliers :

Matrice identité $I_n$ : 1 sur la diagonale, 0 ailleurs. $A \cdot I_n = I_n \cdot A = A$ .
Matrice nulle $0$ : tous coefficients nuls.
Matrice diagonale : tous les coefficients hors diagonale sont nuls.
Matrice triangulaire (sup/inf).

Opérations sur les matrices

Addition et multiplication scalaire

$(A + B)_{ij} = A_{ij} + B_{ij}$ (matrices de mêmes dimensions). $(\lambda A)_{ij} = \lambda A_{ij}$ .

Multiplication de matrices

Pour $A$ de dimensions $m \times n$ et $B$ de dimensions $n \times p$ :

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

Le résultat $AB$ est de dimensions $m \times p$ . Attention : le nombre de colonnes de $A$ doit égaler le nombre de lignes de $B$ .

Non commutativité : en général, $AB \neq BA$ .

Puissances de matrices

$A^n = A \cdot A \cdot ... \cdot A$ ( $n$ fois). $A^0 = I$ par convention.

Inverse d'une matrice carrée

$A$ est inversible s'il existe $A^{-1}$ telle que $A A^{-1} = A^{-1} A = I$ .

Matrice $2 \times 2$ : pour $A = \begin{pmatrix} a & b \\ c & d \end{pmatrix}$ , on a $A^{-1} = \dfrac{1}{ad - bc} \begin{pmatrix} d & -b \\ -c & a \end{pmatrix}$ (si $ad - bc \neq 0$ ).

$ad - bc$ s'appelle le déterminant de $A$ .

Systèmes linéaires et matrices

Un système linéaire $AX = B$ avec $A$ carrée inversible se résout : $X = A^{-1} B$ .

Exemple : $\begin{cases} 2x + y = 5 \\ x + 3y = 8 \end{cases}$ se réécrit $\begin{pmatrix} 2 & 1 \\ 1 & 3 \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} 5 \\ 8 \end{pmatrix}$ .

Déterminant = $6 - 1 = 5$ . $A^{-1} = \dfrac{1}{5}\begin{pmatrix} 3 & -1 \\ -1 & 2 \end{pmatrix}$ .

$X = A^{-1}B = \dfrac{1}{5}\begin{pmatrix} 15 - 8 \\ -5 + 16 \end{pmatrix} = \dfrac{1}{5}\begin{pmatrix} 7 \\ 11 \end{pmatrix} = \begin{pmatrix} 1{,}4 \\ 2{,}2 \end{pmatrix}$ .

Graphes : définitions

Graphe orienté / non orienté

Un graphe est un couple $(V, E)$ où :

$V$ = ensemble de sommets (vertices).
$E$ = ensemble d'arêtes (edges).

Orienté : chaque arête a un sens (flèche). Non orienté : arêtes symétriques.

Vocabulaire

Degré d'un sommet : nombre d'arêtes incidentes.
Chemin : suite de sommets reliés par des arêtes.
Cycle : chemin qui revient au sommet de départ.
Connexe : il existe un chemin entre toute paire de sommets.

Matrice d'adjacence d'un graphe

Pour un graphe à $n$ sommets, sa matrice d'adjacence $M$ est $n \times n$ telle que :

$M_{ij} = 1$ s'il existe une arête de $i$ vers $j$ .
$M_{ij} = 0$ sinon.

Graphe non orienté : $M$ est symétrique ( $M_{ij} = M_{ji}$ ).

Exemple

Graphe à 3 sommets A, B, C. Arêtes : A→B, B→C, C→A.

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

Théorème central

$(M^n)_{ij}$ = nombre de chemins de longueur $n$ allant de $i$ vers $j$ .

Exemple : avec $M$ ci-dessus, $M^3 = I_3$ . Donc il existe exactement 1 chemin de longueur 3 entre chaque sommet et lui-même.

Applications

Modèles de Markov (initiation)

Une chaîne de Markov modélise un système qui change d'état avec des probabilités fixées. Sa matrice de transition $P$ vérifie $P_{ij}$ = probabilité de passer de l'état $i$ à l'état $j$ .

Loi à l'étape $n$ : $V_n = V_0 \cdot P^n$ où $V_0$ est la distribution initiale.

Application : modèles météo, économie, génétique, intelligence artificielle.

Évolution d'une population structurée

Pour modéliser une population avec plusieurs classes d'âge :

X_{n+1} = M X_n

où $M$ est une matrice de transition et $X_n$ le vecteur des effectifs à l'étape $n$ .

À long terme, $X_n$ converge vers un état stable $X^*$ vérifiant $X^* = M X^*$ (vecteur propre de $M$ ).

PageRank (Google)

L'algorithme original de Google PageRank utilise la théorie des graphes et des matrices stochastiques :

Chaque page web = sommet.
Chaque lien = arête orientée.
La matrice d'adjacence pondérée est itérée jusqu'à convergence.
Le rang de chaque page = composante du vecteur propre dominant.

Exercice-type

Énoncé : Soit le graphe orienté à 4 sommets {1, 2, 3, 4} avec les arêtes : 1→2, 2→3, 2→4, 3→1, 4→3.

Donner la matrice d'adjacence $M$ .
Calculer $M^2$ .
Combien y a-t-il de chemins de longueur 2 partant de 1 ?

Corrigé :

$M = \begin{pmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{pmatrix}$ .
Multiplier ligne par ligne :

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

Première ligne de $M^2$ : $(0, 0, 1, 1)$ . Chemins de longueur 2 partant de 1 : 1→2→3 (vers 3) et 1→2→4 (vers 4). Total : 2 chemins.

Pièges classiques

Multiplication matricielle non commutative. $AB \neq BA$ en général.
Erreur de dimensions. Toujours vérifier que $AB$ a un sens (cols( $A$ ) = lignes( $B$ )).
Inverse n'existe pas toujours. Une matrice est inversible ssi son déterminant est non nul.
Confondre matrice et graphe. La matrice d'adjacence représente le graphe, mais n'est pas le graphe lui-même.
Indices. $A_{ij}$ : ligne $i$ , colonne $j$ . Pas l'inverse.

Q&R pour le tuteur IA

Q : Pourquoi multiplier les matrices "ligne par colonne" ? R : Cette définition vient de la composition des applications linéaires. Si $f$ et $g$ sont des transformations linéaires représentées par des matrices, alors $f \circ g$ est représenté par le produit matriciel. La règle "ligne × colonne" en découle naturellement.

Q : Quand utiliser les matrices plutôt que les systèmes ? R : Quand on a (1) un grand système, (2) un système répété (matrice de transition), (3) un problème géométrique (rotation, projection), (4) un problème d'optimisation, (5) un problème d'analyse de réseau (graphes).

Q : Que représente le déterminant ? R : En géométrie : surface (2×2) ou volume (3×3) du parallélogramme/parallélépipède défini par les vecteurs colonnes. En algèbre : indicateur d'inversibilité ( $\det \neq 0 \Leftrightarrow$ inversible).

Q : Pourquoi PageRank est-il basé sur des matrices ? R : Parce que le web est un graphe orienté géant (~10 milliards de pages). La matrice d'adjacence pondérée permet de calculer simultanément le rang de toutes les pages via une itération matricielle convergeant vers le vecteur propre dominant.