Chapitre 3 — Matrices et graphes

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.

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

Corrigé :

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

2. 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}$.

1. 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

1. Multiplication matricielle non commutative. $AB \neq BA$ en général.
2. Erreur de dimensions. Toujours vérifier que $AB$ a un sens (cols($A$) = lignes($B$)).
3. Inverse n'existe pas toujours. Une matrice est inversible ssi son déterminant est non nul.
4. Confondre matrice et graphe. La matrice d'adjacence représente le graphe, mais n'est pas le graphe lui-même.
5. 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.