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.