Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Matrice à coefficients positifs
Résumé
Une matrice de type est à coefficients positifs lorsque tous ses éléments sont réels positifs ; on écrira alors .
Elle est dite strictement positive lorsque tous ses éléments sont strictement positifs ; on écrira alors .
et étant deux matrices réelles on définit une relation d'ordre partiel sur ces matrices en posant .
Il est immédiat que cette relation d'ordre est compatible avec l'addition. De même elle est compatible avec la multiplication (à gauche ou à droite) par une matrice positive.
À toute matrice carrée positive nous associons le graphe (orienté) défini par :
l'ensemble des sommets est ,
un arc (orienté) joint le sommet au sommet si .
Rappelons par ailleurs qu'un chemin de longueur est une suite de arcs telle que l'extrémité de chaque arc soit l'origine du suivant. L'origine du premier arc est l'origine du chemin et l'extrémité du dernier arc est l'extrémité du chemin. On peut considérer qu'un chemin de longueur relie chaque sommet à lui-même.
Il est aisé (par exemple en faisant une récurrence) de vérifier :
Rappelons qu'un graphe est fortement connexe si pour tout couple de sommets il existe un chemin joignant à .
Il résulte alors aisément par utilisation du second lemme ci-dessus que est fortement connexe si et seulement s'il existe un naturel tel que .
Tout chemin dans un graphe peut être simplifié en supprimant les cycles (chemin dont l'origine coïncide avec l'extrémité) parcourus dans ce chemin. Par conséquent un tel chemin simplifié ne peut passer qu'une fois au plus par chaque sommet et est donc de longueur inférieure ou égale à . Le graphe est donc fortement connexe si et seulement s'il existe un naturel tel que .
Nous dirons que la matrice carrée positive est irréductible si le graphe est fortement connexe.
En particulier une matrice strictement positive est irréductible puisque chaque sommet de est relié à tout sommet par un arc (chemin de longueur 1).
L'étude ci-dessus montre qu'une caractérisation des matrices positives irréductibles est la suivante : Il existe un naturel tel que .
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.