Faire parler chaque coefficient de la matrice

Un graphe choisit des sommets et des relations. Une arête relie sans direction ; un arc possède une origine et une extrémité. Selon la question, un sommet peut représenter une ville, une personne, un état ou une tâche. Deux modèles différents peuvent décrire la même situation pour des objectifs différents.

Avant tout calcul, on précise si les boucles, arêtes multiples, poids et directions sont autorisés. Une carte géographique n'est pas automatiquement un graphe de transport : il faut décider si la relation signifie route directe, temps maximal, correspondance ou autre critère.

Dans un graphe non orienté, le degré d'un sommet compte les arêtes incidentes. La somme des degrés vaut deux fois le nombre d'arêtes car chaque arête touche deux extrémités. Dans un graphe orienté, on distingue degré entrant et sortant.

Un chemin est une suite de sommets reliés ; sa longueur compte les arêtes ou arcs parcourus. Un cycle revient à son point de départ. La connexité signifie qu'un chemin relie toute paire de sommets dans le cas non orienté. Il faut distinguer existence d'un chemin et chemin le plus court.

Après avoir fixé l'ordre des sommets, la matrice d'adjacence A contient $\text{aᵢj=1}$ s'il existe un lien de i vers j, 0 sinon dans un graphe simple non pondé. Pour un graphe non orienté, la matrice est symétrique. Changer l'ordre permute lignes et colonnes sans changer le graphe.

Le coefficient (i,j) de A⁽k⁾ compte les marches de longueur k de i vers j. Le produit matriciel encode le choix d'un sommet intermédiaire à chaque étape. Une marche peut répéter des sommets ; elle n'est pas nécessairement un chemin simple.

Deux matrices de même taille s'additionnent coefficient par coefficient. Le produit AB est défini si le nombre de colonnes de A égale le nombre de lignes de B. Le coefficient (i,j) est le produit scalaire de la ligne i de A et de la colonne j de B.

Le produit matriciel n'est en général pas commutatif : AB peut différer de BA ou l'un des deux peut ne pas être défini. L'ordre traduit la composition des transformations. Une calculatrice vérifie un produit mais ne choisit ni les dimensions ni l'interprétation.

Un système linéaire s'écrit $\text{AX=B}$. Les opérations élémentaires sur les lignes correspondent à des transformations qui conservent l'ensemble des solutions lorsqu'elles sont réversibles. Pour une matrice carrée inversible, $\text{X=}{A}^{\mathrm{-}}{}^{1}B$ fournit l'unique solution.

L'inverse ne doit pas être supposé. Une matrice peut représenter des équations redondantes ou incompatibles. La résolution doit donc contrôler nombre de solutions et substitution. Dans un contexte, une solution négative ou non entière peut aussi être inadmissible.

Une chaîne de Markov modélise des transitions entre états lorsque la loi du prochain état dépend seulement de l'état actuel. Dans ce cours, P est une matrice de transition en convention lignes : la ligne i donne les probabilités de quitter l'état i vers les colonnes j, donc chaque ligne somme à 1. La convention est fixée pour tous les calculs qui suivent.

Un vecteur-ligne d'état $x_n$ donne la distribution à l'instant n et la transition s'écrit $x_{\mathrm{n+1}}\text{=}{x}_n\text{P}$. Les puissances donnent $x_n\text{=}{x}_0{P}^{\mathrm{n}}$. Un état stable $\pi$ vérifie $\text{πP=π}$ dans cette même convention. Son existence n'implique pas que toute distribution converge vers lui ; la structure de la chaîne doit être examinée.