Exercice 0.1 : Calculer avec des matrices : dix calculs directs

Pour chaque ligne, effectuez le calcul demandé puis donnez le ou les coefficients indiqués du résultat. Le coefficient $(i,j)$ est celui de la ligne $i$ et de la colonne $j$ .

Une seule règle porte tout le chapitre : le coefficient $(i,j)$ d'un produit $PQ$ s'obtient en faisant courir la ligne $i$ de $P$ contre la colonne $j$ de $Q$ , terme à terme, puis en additionnant. Avant de calculer, on vérifie les tailles : un $m\times n$ par un $n\times p$ donne un $m\times p$ . Pour un déterminant $2\times 2$ , c'est $ad-bc$ ; pour un $3\times 3$ , on développe selon la première ligne avec les signes $+$ , $-$ , $+$ .

a) $A=\begin{pmatrix} 3 & -1 \\ 2 & 5 \end{pmatrix}$ et $B=\begin{pmatrix} 1 & 4 \\ -2 & 0 \end{pmatrix}$ : calculez $2A-B$ , puis donnez ses coefficients $(1,2)$ et $(2,1)$ .
b) $C=\begin{pmatrix} 2 & 0 & -3 \\ 1 & 4 & 5 \end{pmatrix}$ : écrivez la transposée $C^{T}$ , puis donnez ses coefficients $(3,1)$ et $(1,2)$ .
c) $P=\begin{pmatrix} 2 & -3 \\ 1 & 4 \end{pmatrix}$ et $Q=\begin{pmatrix} 5 & 1 \\ -2 & 3 \end{pmatrix}$ : calculez $PQ$ , puis donnez ses coefficients $(1,2)$ et $(2,1)$ .
d) $D=\begin{pmatrix} 1 & 2 & 0 \\ -1 & 3 & 2 \end{pmatrix}$ et $E=\begin{pmatrix} 2 & 1 \\ 0 & -1 \\ 4 & 3 \end{pmatrix}$ : calculez $DE$ , puis donnez ses coefficients $(2,1)$ et $(2,2)$ .
e) $F=\begin{pmatrix} 1 & 0 & 2 \\ 3 & -1 & 1 \\ 0 & 2 & -2 \end{pmatrix}$ et $\vec{v}=\begin{pmatrix} 3 \\ -1 \\ 2 \end{pmatrix}$ : calculez $F\vec{v}$ , puis donnez ses deuxième et troisième composantes.
f) $M=\begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix}$ est la matrice d'adjacence d'un graphe orienté : calculez $M^{2}$ , puis donnez ses coefficients $(2,2)$ et $(2,3)$ .
g) Avec la même matrice $M$ : calculez $M^{3}$ , puis donnez ses coefficients $(1,3)$ et $(3,1)$ .
h) Calculez $\det\begin{pmatrix} -4 & 5 \\ 3 & -6 \end{pmatrix}$ .
i) $G=\begin{pmatrix} 4 & 3 \\ 2 & 2 \end{pmatrix}$ : calculez $G^{-1}$ , puis donnez ses coefficients $(1,2)$ et $(2,1)$ .
j) Calculez $\det\begin{pmatrix} 2 & -1 & 3 \\ 1 & 0 & 4 \\ -2 & 1 & 1 \end{pmatrix}$ par développement selon la première ligne.

Tape tes réponses, la page te dit juste ou faux 0/18

a)

coefficient

(1,2)

coefficient

(2,1)

b)

coefficient

(3,1)

de

C^{T}

coefficient

(1,2)

de

C^{T}

c)

coefficient

(1,2)

coefficient

(2,1)

d)

coefficient

(2,1)

coefficient

(2,2)

e)

deuxième composante

troisième composante

f)

coefficient

(2,2)

de

M^{2}

coefficient

(2,3)

de

M^{2}

g)

coefficient

(1,3)

de

M^{3}

coefficient

(3,1)

de

M^{3}

h)

déterminant

i)

coefficient

(1,2)

de

G^{-1}

coefficient

(2,1)

de

G^{-1}

j)

déterminant

Voir la correction

Réponses

a) $2A-B=\begin{pmatrix} 5 & -6 \\ 6 & 10 \end{pmatrix}$ ; $-6$ et $6$
b) $C^{T}=\begin{pmatrix} 2 & 1 \\ 0 & 4 \\ -3 & 5 \end{pmatrix}$ ; $-3$ et $1$
c) $PQ=\begin{pmatrix} 16 & -7 \\ -3 & 13 \end{pmatrix}$ ; $-7$ et $-3$
d) $DE=\begin{pmatrix} 2 & -1 \\ 6 & 2 \end{pmatrix}$ ; $6$ et $2$
e) $F\vec{v}=\begin{pmatrix} 7 \\ 12 \\ -6 \end{pmatrix}$ ; $12$ et $-6$
f) $M^{2}=\begin{pmatrix} 1 & 1 & 1 \\ 0 & 2 & 1 \\ 1 & 0 & 1 \end{pmatrix}$ ; $2$ et $1$
g) $M^{3}=\begin{pmatrix} 1 & 2 & 2 \\ 2 & 1 & 2 \\ 0 & 2 & 1 \end{pmatrix}$ ; $2$ et $0$
h) $(-4)(-6)-(5)(3)=9$
i) $G^{-1}=\begin{pmatrix} 1 & -\frac{3}{2} \\ -1 & 2 \end{pmatrix}$ ; $-\frac{3}{2}$ et $-1$
j) $2(-4)+1(9)+3(1)=4$

Le geste qui décide de tout : écrire la taille du résultat AVANT de calculer, puis viser le coefficient demandé par sa ligne et sa colonne. On ne calcule pas un produit en multipliant terme à terme, on fait courir une ligne contre une colonne.

a)

Terme à terme : $2A=\begin{pmatrix} 6 & -2 \\ 4 & 10 \end{pmatrix}$ , donc $2A-B=\begin{pmatrix} 6-1 & -2-4 \\ 4-(-2) & 10-0 \end{pmatrix}=\begin{pmatrix} 5 & -6 \\ 6 & 10 \end{pmatrix}$ . Coefficients : $(1,2)=-6$ et $(2,1)=6$ . Piège : $4-(-2)=6$ , le double signe moins.

b)

Les lignes de $C$ deviennent les colonnes : $C^{T}=\begin{pmatrix} 2 & 1 \\ 0 & 4 \\ -3 & 5 \end{pmatrix}$ , une matrice $3\times 2$ . Coefficients : $(C^{T})_{31}=C_{13}=-3$ et $(C^{T})_{12}=C_{21}=1$ . Piège : garder la taille $2\times 3$ et lire $(1,2)$ dans $C$ , ce qui donne $0$ .

c)

$PQ=\begin{pmatrix} 2(5)+(-3)(-2) & 2(1)+(-3)(3) \\ 1(5)+4(-2) & 1(1)+4(3) \end{pmatrix}=\begin{pmatrix} 16 & -7 \\ -3 & 13 \end{pmatrix}$ . Coefficients : $(1,2)=-7$ et $(2,1)=-3$ . Piège : multiplier terme à terme, ce qui donnerait $(1,2)=-3$ .

d)

Un $2\times 3$ par un $3\times 2$ donne un $2\times 2$ . Ligne 2 de $D$ , $(-1,3,2)$ , contre la colonne 1 de $E$ , $(2,0,4)$ : $-2+0+8=6$ ; contre la colonne 2, $(1,-1,3)$ : $-1-3+6=2$ . En entier, $DE=\begin{pmatrix} 2 & -1 \\ 6 & 2 \end{pmatrix}$ . Piège : croire que le résultat est $3\times 3$ , ce qui est la taille de $ED$ .

e)

Chaque ligne de $F$ contre $\vec{v}$ : $1(3)+0(-1)+2(2)=7$ , $3(3)+(-1)(-1)+1(2)=12$ , $0(3)+2(-1)+(-2)(2)=-6$ . Donc $F\vec{v}=\begin{pmatrix} 7 \\ 12 \\ -6 \end{pmatrix}$ , deuxième composante $12$ , troisième $-6$ . Piège : $(-1)(-1)=+1$ dans la deuxième ligne.

f)

Chaque ligne de $M^{2}$ est la somme des lignes de $M$ que désignent les $1$ de la ligne de départ. Ligne 1 : lignes 2 et 3, $(1,1,1)$ . Ligne 2 : lignes 1 et 3, $(0,2,1)$ . Ligne 3 : ligne 2, $(1,0,1)$ . Donc $M^{2}=\begin{pmatrix} 1 & 1 & 1 \\ 0 & 2 & 1 \\ 1 & 0 & 1 \end{pmatrix}$ , coefficients $(2,2)=2$ et $(2,3)=1$ . Piège : élever chaque coefficient au carré, ce qui redonne $M$ .

g)

$M^{3}=M^{2}M$ : la ligne 1 de $M^{2}$ , $(1,1,1)$ , additionne les trois lignes de $M$ , soit $(1,2,2)$ ; la ligne 3, $(1,0,1)$ , additionne les lignes 1 et 3, soit $(0,2,1)$ . Donc $M^{3}=\begin{pmatrix} 1 & 2 & 2 \\ 2 & 1 & 2 \\ 0 & 2 & 1 \end{pmatrix}$ , coefficients $(1,3)=2$ et $(3,1)=0$ . Le $0$ dit qu'aucun chemin de longueur 3 ne mène du sommet 3 au sommet 1.

h)

$ad-bc=(-4)(-6)-(5)(3)=24-15=9$ . Piège : $-24-15=-39$ , en perdant le signe du produit de deux négatifs.

i)

$\det G=4(2)-3(2)=2$ . On échange la diagonale, on change le signe de l'antidiagonale, on divise par $2$ : $G^{-1}=\frac{1}{2}\begin{pmatrix} 2 & -3 \\ -2 & 4 \end{pmatrix}=\begin{pmatrix} 1 & -\frac{3}{2} \\ -1 & 2 \end{pmatrix}$ . Coefficients : $(1,2)=-\frac{3}{2}$ et $(2,1)=-1$ . Piège : oublier de diviser par le déterminant.

j)

$2\begin{vmatrix} 0 & 4 \\ 1 & 1 \end{vmatrix}-(-1)\begin{vmatrix} 1 & 4 \\ -2 & 1 \end{vmatrix}+3\begin{vmatrix} 1 & 0 \\ -2 & 1 \end{vmatrix}=2(0-4)+1(1+8)+3(1-0)=-8+9+3=4$ . Piège : le signe moins devant le deuxième terme, qui transforme $-(-1)$ en $+1$ ; l'oublier donne $-14$ .

Contrôle : un produit se recoupe en recalculant un autre coefficient par le chemin inverse, ligne contre colonne. Pour l'inverse, $GG^{-1}$ doit redonner l'identité : la ligne 1 de $G$ contre la colonne 2 de $G^{-1}$ fait $4\left(-\frac{3}{2}\right)+3(2)=0$ . Pour un déterminant $3\times 3$ , on refait le calcul selon une autre ligne ou par Sarrus.

Coche ici les exercices faits ou à revoir : un compte gratuit, sans mot de passe, retient tes coches et tes réponses justes d'une visite à l'autre, te dit quel chapitre attaquer ensuite et te permet de demander l'exercice qui te manque. Crée ton espace, un courriel suffit.

Exercice 1 : Vocabulaire des graphes : sommets, arêtes, degrés

Un graphe non orienté $G = (S, \mathcal{A})$ est la donnée d'un ensemble $S$ de sommets et d'un ensemble $\mathcal{A}$ d'arêtes, chaque arête étant une paire de sommets. Le degré d'un sommet est le nombre d'arêtes qui y aboutissent. Le graphe ci-dessous compte cinq sommets.

a) Donnez $S$ et $\mathcal{A}$ en extension. Combien y a-t-il d'arêtes ?
b) Donnez le degré de chaque sommet.
c) Vérifiez le lemme des poignées de main : la somme des degrés vaut deux fois le nombre d'arêtes.
d) Expliquez pourquoi ce lemme est vrai pour tout graphe, et déduisez-en que le nombre de sommets de degré impair est pair.
e) Combien d'arêtes compte au maximum un graphe simple à 5 sommets ? Et à $n$ sommets ?
f) Existe-t-il un chemin de $A$ à $E$ ? Le graphe est-il connexe ?

Tape tes réponses, la page te dit juste ou faux 0/15

a)

Nombre de sommets

Nombre d'arêtes

b)

\deg(A)

\deg(B)

\deg(C)

\deg(D)

\deg(E)

c)

Somme des degrés

Deux fois le nombre d'arêtes

d)

Chaque arête contribue à la somme des degrés pour

Sommets de degré impair

e)

Arêtes au maximum sur 5 sommets

Sur

n

sommets, le maximum vaut

f)

Le graphe est

Arêtes minimales d'un graphe connexe à 5 sommets

Voir la correction

Réponses

a) $S = \{A,B,C,D,E\}$ et $\mathcal{A} = \{AB, AC, BC, BD, CD, DE\}$ , soit 6 arêtes
b) $2, 3, 3, 3, 1$
c) $2+3+3+3+1 = 12 = 2 \times 6$
d) Chaque arête compte 2 dans la somme, qui est donc paire : les sommets de degré impair sont en nombre pair, ici quatre
e) $\dbinom{5}{2} = 10$ , et $\dfrac{n(n-1)}{2}$ en général
f) Oui, $A \to B \to D \to E$ : le graphe est connexe

a)

$S = \{A, B, C, D, E\}$ et $\mathcal{A} = \{AB, AC, BC, BD, CD, DE\}$ , soit 6 arêtes. On les relève en balayant le dessin dans un ordre fixe, par exemple alphabétique sur le premier sommet, pour n'en oublier aucune ni en compter deux fois.

b)

$\deg(A) = 2$ (vers $B$ et $C$ ), $\deg(B) = 3$ (vers $A$ , $C$ , $D$ ), $\deg(C) = 3$ (vers $A$ , $B$ , $D$ ), $\deg(D) = 3$ (vers $B$ , $C$ , $E$ ), $\deg(E) = 1$ (vers $D$ ).

c)

Somme des degrés : $2+3+3+3+1 = 12$ . Nombre d'arêtes : 6. On a bien $12 = 2 \times 6$ . Ce contrôle est le premier à faire après avoir relevé un graphe : s'il échoue, c'est qu'une arête a été oubliée ou comptée deux fois.

d)

Chaque arête a deux extrémités et contribue donc pour 1 au degré de chacune d'elles, soit 2 au total de la somme des degrés. En sommant sur toutes les arêtes, on obtient $\sum_{s} \deg(s) = 2\lvert \mathcal{A} \rvert$ . Cette somme est paire ; or les sommets de degré pair y contribuent une quantité paire, donc la contribution des sommets de degré impair doit elle aussi être paire, ce qui n'est possible que s'ils sont en nombre pair. Ici, les sommets de degré impair sont $B$ , $C$ , $D$ et $E$ : ils sont bien quatre.

e)

Dans un graphe simple, il y a au plus une arête par paire de sommets et aucune boucle : le maximum est le nombre de paires, $\dbinom{5}{2} = \dfrac{5 \times 4}{2} = 10$ arêtes, et $\dfrac{n(n-1)}{2}$ en général. Un tel graphe est dit complet. Notre graphe en compte 6 sur 10 possibles.

f)

Oui : $A \to B \to D \to E$ est un chemin, et il en existe d'autres, comme $A \to C \to D \to E$ . Le graphe est connexe, puisque de proche en proche tout sommet est atteint depuis $A$ : $B$ et $C$ directement, $D$ par $B$ , $E$ par $D$ . Un graphe à $n$ sommets connexe compte au moins $n-1$ arêtes ; ici $6 \ge 4$ , ce qui est cohérent, sans être une preuve à soi seul.

Exercice 2 : Matrice d'adjacence d'un graphe orienté

La matrice d'adjacence $M$ d'un graphe à $n$ sommets est la matrice $n \times n$ dont le coefficient $M_{ij}$ vaut 1 s'il existe un arc du sommet $i$ vers le sommet $j$ , et 0 sinon. Elle contient exactement la même information que le dessin, mais elle se calcule. Le graphe orienté ci-dessous a quatre sommets numérotés de 1 à 4.

a) Relevez les six arcs, puis écrivez la matrice d'adjacence $M$ .
b) Que représentent la somme des coefficients d'une ligne ? Et d'une colonne ?
c) Donnez les degrés sortant et entrant de chaque sommet, puis vérifiez que les deux sommes sont égales.
d) La matrice d'adjacence d'un graphe non orienté possède une propriété particulière : laquelle, et pourquoi ?
e) Que signifierait un coefficient non nul sur la diagonale ?

Tape tes réponses, la page te dit juste ou faux 0/14

a)

Coefficients à 1

M_{13}

M_{31}

M_{21}

M_{43}

b)

La somme d'une LIGNE est

La somme d'une COLONNE est

c)

Somme des degrés sortants

Somme des degrés entrants

Degré entrant du sommet 3

d)

Elle est

Notre matrice

e)

Un 1 sur la diagonale signalerait

Boucles de ce graphe

Voir la correction

Réponses

a) Six arcs, $1\to2$ , $1\to3$ , $2\to3$ , $2\to4$ , $3\to1$ , $4\to3$ , et 6 coefficients à 1
b) Ligne : degré SORTANT. Colonne : degré ENTRANT
c) Sortants $2,2,1,1$ et entrants $1,1,3,1$ : les deux sommes valent 6, le nombre d'arcs
d) Elle est SYMÉTRIQUE. La nôtre ne l'est pas : $M_{12}=1$ et $M_{21}=0$
e) Une BOUCLE. Notre diagonale est nulle

a)

Les arcs sont $1 \to 2$ , $1 \to 3$ , $2 \to 3$ , $2 \to 4$ , $3 \to 1$ et $4 \to 3$ . En rangeant les sommets dans l'ordre 1, 2, 3, 4, la ligne $i$ décrit les arcs QUI PARTENT de $i$ : $M = \begin{pmatrix} 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{pmatrix}$ . Contrôle : la matrice compte 6 coefficients égaux à 1, autant que le graphe a d'arcs.

b)

La somme de la ligne $i$ est le nombre d'arcs partant de $i$ , c'est-à-dire son degré SORTANT. La somme de la colonne $j$ est le nombre d'arcs arrivant en $j$ , son degré ENTRANT. Confondre les deux est l'erreur qui fausse toute la suite du chapitre, parce qu'elle revient à transposer le graphe.

c)

Degrés sortants : $2, 2, 1, 1$ , de somme 6. Degrés entrants : sommet 1 reçoit de 3, donc 1 ; sommet 2 reçoit de 1, donc 1 ; sommet 3 reçoit de 1, 2 et 4, donc 3 ; sommet 4 reçoit de 2, donc 1. Somme : $1+1+3+1 = 6$ . Les deux sommes valent 6, le nombre d'arcs : chaque arc a exactement un départ et une arrivée. C'est la version orientée du lemme des poignées de main, sans facteur 2.

d)

Elle est SYMÉTRIQUE, c'est-à-dire égale à sa transposée. Une arête non orientée entre $i$ et $j$ se lit dans les deux sens, donc $M_{ij} = M_{ji}$ . Réciproquement, une matrice d'adjacence symétrique décrit un graphe qu'on peut considérer comme non orienté. Notre matrice ne l'est pas : $M_{12} = 1$ mais $M_{21} = 0$ , ce qui confirme que le graphe est bien orienté.

e)

Un coefficient $M_{ii} = 1$ signalerait une BOUCLE, c'est-à-dire un arc d'un sommet vers lui-même. Notre graphe n'en a aucune, sa diagonale est nulle. Les boucles sont interdites dans un graphe dit simple, mais elles apparaissent naturellement dès qu'on modélise un automate ou une page web qui pointe vers elle-même.

Exercice 3 : Opérations sur les matrices et non-commutativité

On pose $A = \begin{pmatrix} 1 & 2 \\ 3 & -1 \end{pmatrix}$ et $B = \begin{pmatrix} 0 & 4 \\ 2 & 1 \end{pmatrix}$ . Le coefficient de rang $(i,j)$ du produit $AB$ s'obtient en faisant courir la ligne $i$ de $A$ contre la colonne $j$ de $B$ : c'est la seule règle du chapitre, et elle explique à elle seule pourquoi le produit n'est pas commutatif.

a) Calculez $A + B$ et $2A - 3B$ .
b) Calculez $AB$ et $BA$ . Que constatez-vous ?
c) Donnez $A^{T}$ et $B^{T}$ .
d) Vérifiez sur cet exemple que $(AB)^{T} = B^{T}A^{T}$ .
e) À quelle condition sur les dimensions le produit $PQ$ existe-t-il ?
f) Calculez $A^{2}$ . Est-ce la matrice des carrés des coefficients de $A$ ?

Tape tes réponses, la page te dit juste ou faux 0/18

a)

(A+B)_{12}

(A+B)_{21}

(2A-3B)_{12}

(2A-3B)_{22}

b)

(AB)_{11}

(AB)_{22}

(BA)_{11}

(BA)_{12}

On constate que

c)

(A^{T})_{12}

(B^{T})_{12}

d)

\big((AB)^{T}\big)_{12}

(B^{T}A^{T})_{21}

La transposée d'un produit est

e)

Le produit

PQ

existe si et seulement si

f)

(A^{2})_{11}

(A^{2})_{12}

Est-ce la matrice des carrés des coefficients ?

Voir la correction

Réponses

a) $A+B = \begin{pmatrix} 1 & 6 \\ 5 & 0 \end{pmatrix}$ et $2A-3B = \begin{pmatrix} 2 & -8 \\ 0 & -5 \end{pmatrix}$
b) $AB = \begin{pmatrix} 4 & 6 \\ -2 & 11 \end{pmatrix}$ et $BA = \begin{pmatrix} 12 & -4 \\ 5 & 3 \end{pmatrix}$ : le produit n'est pas commutatif
c) $A^{T} = \begin{pmatrix} 1 & 3 \\ 2 & -1 \end{pmatrix}$ et $B^{T} = \begin{pmatrix} 0 & 2 \\ 4 & 1 \end{pmatrix}$
d) Les deux valent $\begin{pmatrix} 4 & -2 \\ 6 & 11 \end{pmatrix}$ : l'ordre s'INVERSE
e) Colonnes de $P$ = lignes de $Q$ , et le produit est de taille $m \times p$
f) $A^{2} = 7I$ , et non la matrice des carrés : $A$ est inversible, d'inverse $\dfrac{1}{7}A$

a)

$A+B = \begin{pmatrix} 1 & 6 \\ 5 & 0 \end{pmatrix}$ , terme à terme. Pour la combinaison : $2A = \begin{pmatrix} 2 & 4 \\ 6 & -2 \end{pmatrix}$ et $3B = \begin{pmatrix} 0 & 12 \\ 6 & 3 \end{pmatrix}$ , donc $2A - 3B = \begin{pmatrix} 2 & -8 \\ 0 & -5 \end{pmatrix}$ .

b)

$AB = \begin{pmatrix} 1(0)+2(2) & 1(4)+2(1) \\ 3(0)+(-1)(2) & 3(4)+(-1)(1) \end{pmatrix} = \begin{pmatrix} 4 & 6 \\ -2 & 11 \end{pmatrix}$ . Et $BA = \begin{pmatrix} 0(1)+4(3) & 0(2)+4(-1) \\ 2(1)+1(3) & 2(2)+1(-1) \end{pmatrix} = \begin{pmatrix} 12 & -4 \\ 5 & 3 \end{pmatrix}$ . Les deux produits diffèrent : le produit matriciel n'est PAS commutatif. C'est la différence la plus importante avec le produit des nombres réels, et en infographie elle a un sens concret : tourner puis translater ne donne pas la même image que translater puis tourner.

c)

$A^{T} = \begin{pmatrix} 1 & 3 \\ 2 & -1 \end{pmatrix}$ et $B^{T} = \begin{pmatrix} 0 & 2 \\ 4 & 1 \end{pmatrix}$ : la première ligne devient la première colonne.

d)

$(AB)^{T} = \begin{pmatrix} 4 & -2 \\ 6 & 11 \end{pmatrix}$ . Et $B^{T}A^{T} = \begin{pmatrix} 0(1)+2(2) & 0(3)+2(-1) \\ 4(1)+1(2) & 4(3)+1(-1) \end{pmatrix} = \begin{pmatrix} 4 & -2 \\ 6 & 11 \end{pmatrix}$ . Les deux coïncident. Le point à retenir est l'INVERSION de l'ordre : la transposée d'un produit est le produit des transposées prises à l'envers. La même inversion se produit pour l'inverse d'un produit.

e)

Le produit $PQ$ existe si et seulement si le nombre de COLONNES de $P$ égale le nombre de LIGNES de $Q$ . Si $P$ est de taille $m \times n$ et $Q$ de taille $n \times p$ , alors $PQ$ est de taille $m \times p$ . C'est la vérification à faire avant tout calcul : bien souvent, $AB$ existe et $BA$ n'existe pas, ce qui règle la question de la commutativité sans le moindre calcul.

f)

$A^{2} = AA = \begin{pmatrix} 1(1)+2(3) & 1(2)+2(-1) \\ 3(1)+(-1)(3) & 3(2)+(-1)(-1) \end{pmatrix} = \begin{pmatrix} 7 & 0 \\ 0 & 7 \end{pmatrix}$ . Ce n'est évidemment pas la matrice des carrés, qui vaudrait $\begin{pmatrix} 1 & 4 \\ 9 & 1 \end{pmatrix}$ . Le résultat est ici remarquable : $A^{2} = 7I$ , donc $A$ se comporte comme une racine carrée de 7 fois l'identité. On en déduit d'ailleurs immédiatement que $A$ est inversible, d'inverse $\dfrac{1}{7}A$ .

Exercice 4 : Puissances de la matrice d'adjacence et comptage de chemins

On reprend la matrice $M$ du graphe orienté de l'exercice 2. Le théorème central du chapitre : le coefficient $(i,j)$ de $M^{k}$ est le NOMBRE de chemins de longueur exactement $k$ allant de $i$ à $j$ . Un chemin a le droit de repasser par un sommet déjà visité.

Le graphe de l'exercice 2 est rappelé ci-dessous.

a) Calculez $M^{2}$ .
b) Interprétez le coefficient $(1,1)$ de $M^{2}$ en exhibant le chemin correspondant.
c) Calculez $M^{3}$ et lisez le nombre de chemins de longueur 3 allant de 1 à 3. Écrivez-les tous.
d) Démontrez le théorème dans le cas $k=2$ .
e) Combien de chemins de longueur 2 partent du sommet 1, toutes destinations confondues ?

Tape tes réponses, la page te dit juste ou faux 0/13

a)

(M^{2})_{11}

(M^{2})_{14}

(M^{2})_{32}

(M^{2})_{41}

b)

Valeur du coefficient

Le chemin correspondant est

Les coefficients diagonaux de

M^{k}

comptent

c)

(M^{3})_{13}

Le second chemin est

d)

Le terme

M_{ik}M_{kj}

vaut 1 exactement quand

Le passage au cas général se fait

e)

Chemins de longueur 2 partant de 1

Contrôle par les successeurs

Voir la correction

Réponses

a) $M^{2} = \begin{pmatrix} 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 0 \end{pmatrix}$
b) Il vaut 1 : l'unique cycle $1 \to 3 \to 1$ de longueur 2
c) $(M^{3})_{13} = 2$ : $1 \to 2 \to 4 \to 3$ et $1 \to 3 \to 1 \to 3$
d) $(M^{2})_{ij} = \sum_{k} M_{ik}M_{kj}$ , chaque terme valant 1 pour un chemin $i \to k \to j$
e) $1+0+1+1 = 3$ , que confirme le compte par successeurs $2+1 = 3$

a)

On multiplie $M$ par elle-même. Ligne 1 : le sommet 1 pointe vers 2 et 3, donc la ligne 1 de $M^{2}$ est la somme des lignes 2 et 3 de $M$ , soit $(0,0,1,1) + (1,0,0,0) = (1,0,1,1)$ . Ligne 2 : le sommet 2 pointe vers 3 et 4, somme des lignes 3 et 4 : $(1,0,0,0)+(0,0,1,0) = (1,0,1,0)$ . Ligne 3 : le sommet 3 pointe vers 1, donc la ligne 1 de $M$ : $(0,1,1,0)$ . Ligne 4 : le sommet 4 pointe vers 3, donc la ligne 3 de $M$ : $(1,0,0,0)$ . D'où $M^{2} = \begin{pmatrix} 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 0 \end{pmatrix}$ . Ce procédé, où chaque ligne du produit est une somme de lignes, est beaucoup plus rapide que le calcul coefficient par coefficient quand la matrice ne contient que des 0 et des 1.

b)

Le coefficient $(1,1)$ de $M^{2}$ vaut 1 : il existe exactement un chemin de longueur 2 du sommet 1 vers lui-même, à savoir $1 \to 3 \to 1$ . C'est un cycle de longueur 2, et il apparaît sur la diagonale : les coefficients diagonaux de $M^{k}$ comptent les cycles de longueur $k$ passant par chaque sommet.

c)

$M^{3} = M^{2}M$ . Ligne 1 : $(1,0,1,1)$ sélectionne les lignes 1, 3 et 4 de $M$ , dont la somme vaut $(0,1,1,0)+(1,0,0,0)+(0,0,1,0) = (1,1,2,0)$ . En continuant : $M^{3} = \begin{pmatrix} 1 & 1 & 2 & 0 \\ 1 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 \end{pmatrix}$ . Le coefficient $(1,3)$ vaut 2 : il y a deux chemins de longueur 3 de 1 vers 3, à savoir $1 \to 2 \to 4 \to 3$ et $1 \to 3 \to 1 \to 3$ . Le second repasse par des sommets déjà vus, ce qui est autorisé : c'est bien pour cela que le coefficient vaut 2 et non 1. Confondre chemin et chemin sans répétition est l'erreur qui fait rater ce théorème.

d)

Par définition du produit, $(M^{2})_{ij} = \sum_{k} M_{ik}M_{kj}$ . Chaque terme de cette somme vaut 1 exactement quand $M_{ik} = 1$ ET $M_{kj} = 1$ , c'est-à-dire quand il existe un arc de $i$ vers $k$ ET un arc de $k$ vers $j$ : cela décrit précisément un chemin $i \to k \to j$ de longueur 2 passant par $k$ . La somme sur $k$ compte donc tous les chemins de longueur 2 de $i$ à $j$ , un par sommet intermédiaire possible. Le passage au cas général se fait par récurrence, en écrivant $M^{k+1} = M^{k}M$ et en découpant chaque chemin de longueur $k+1$ en un chemin de longueur $k$ suivi d'un arc.

e)

C'est la somme de la première ligne de $M^{2}$ : $1+0+1+1 = 3$ . Autre lecture : le sommet 1 a deux successeurs, 2 et 3, qui ont respectivement 2 et 1 successeurs, soit $2+1 = 3$ chemins. Les deux comptes coïncident, ce qui valide le calcul matriciel.

Exercice 5 : Connexité et matrice d'accessibilité

Savoir s'il existe un chemin, sans se soucier de sa longueur, revient à réunir toutes les puissances de la matrice d'adjacence en remplaçant l'addition par un OU logique. La matrice obtenue s'appelle matrice d'accessibilité, ou fermeture transitive : son coefficient $(i,j)$ vaut 1 dès qu'un chemin mène de $i$ à $j$ .

Le graphe de l'exercice 2 est rappelé ci-dessous.

a) Jusqu'à quelle puissance de $M$ faut-il aller dans un graphe à $n$ sommets ?
b) Déterminez la matrice d'accessibilité du graphe orienté de l'exercice 2.
c) Ce graphe est-il fortement connexe ?
d) Le graphe non orienté de l'exercice 1 est connexe. Combien d'arêtes faut-il retirer pour obtenir un arbre couvrant, et combien en restera-t-il ?
e) Quel est le coût en opérations de l'algorithme de Warshall sur $n$ sommets ?

Tape tes réponses, la page te dit juste ou faux 0/11

a)

Il faut aller jusqu'à

b)

Coefficients à 1 de la matrice d'accessibilité

Coefficients à 1 en s'arrêtant à

M^{3}

La case comblée en dernier est

c)

Le graphe est

Le cycle qui le prouve est

d)

Arêtes d'un arbre couvrant

Arêtes à retirer

Ce nombre s'appelle

e)

Le coût de Warshall est

Calculer puis réunir les puissances coûterait

Voir la correction

Réponses

a) Jusqu'à $M^{n}$ : un retour sur soi peut demander $n$ arcs
b) Entièrement remplie de 1 ; à $M^{3}$ il manquait encore la case $(4,4)$
c) Oui, fortement connexe : le cycle $4 \to 3 \to 1 \to 2 \to 4$ passe par les quatre sommets
d) Un arbre couvrant compte $5-1 = 4$ arêtes : il faut en retirer 2, le nombre cyclomatique
e) Warshall coûte $n^{3}$ , contre $n^{4}$ pour la réunion des puissances

a)

Un chemin qui repasse deux fois par le même sommet contient un cycle que l'on peut supprimer sans changer ses extrémités. Pour $i \neq j$ , s'il existe un chemin de $i$ à $j$ , il en existe donc un sans répétition : il visite au plus $n$ sommets et compte au plus $n-1$ arcs. Pour un retour de $i$ vers lui-même, en revanche, le cycle peut visiter les $n$ sommets et compter alors $n$ arcs. Il faut donc aller jusqu'à $M^{n}$ , et $M^{n-1}$ ne suffit que si l'on se limite aux couples de sommets distincts. La question suivante montre que cette nuance n'est pas théorique.

b)

On réunit $M$ , $M^{2}$ , $M^{3}$ et $M^{4}$ en mettant un 1 dès que l'une des quatre en a un. $M$ donne les paires $(1,2), (1,3), (2,3), (2,4), (3,1), (4,3)$ ; $M^{2}$ ajoute $(1,1), (1,4), (2,1), (3,2), (3,3), (4,1)$ ; $M^{3}$ ajoute $(2,2), (3,4), (4,2)$ . À ce stade, une seule position reste à 0, la position $(4,4)$ : quinze cases sur seize sont remplies. Elle est comblée par $M^{4}$ , grâce au cycle $4 \to 3 \to 1 \to 2 \to 4$ , qui compte quatre arcs. La matrice d'accessibilité est donc entièrement remplie de 1. C'est l'illustration exacte de la question a) : ce cycle passe par les quatre sommets, il lui faut donc quatre arcs, et s'arrêter à $M^{3}$ aurait conclu à tort que le sommet 4 ne peut pas revenir à lui-même.

c)

Oui. Un graphe orienté est fortement connexe quand tout sommet est accessible depuis tout autre, ce qui se lit exactement sur une matrice d'accessibilité entièrement remplie de 1. Le cycle $4 \to 3 \to 1 \to 2 \to 4$ suffit d'ailleurs à s'en convaincre sans matrice : il passe par les quatre sommets, donc en le parcourant assez longtemps on va de n'importe quel sommet à n'importe quel autre.

d)

Un arbre couvrant d'un graphe connexe à $n$ sommets compte exactement $n-1$ arêtes, ici $5-1 = 4$ . Le graphe en a 6, il faut donc en retirer $6-4 = 2$ , en veillant à ne casser aucune connexion. Par exemple retirer $BC$ et $CD$ laisse $AB$ , $AC$ , $BD$ , $DE$ , qui relient bien les cinq sommets sans cycle. Le nombre d'arêtes à retirer, $\lvert \mathcal{A} \rvert - \lvert S \rvert + 1$ , s'appelle le nombre cyclomatique et compte les cycles indépendants du graphe.

e)

L'algorithme de Warshall est fait de trois boucles imbriquées sur les sommets, chacune de longueur $n$ : son coût est en $n^{3}$ opérations. C'est plus économique que de calculer et de réunir les $n$ premières puissances de $M$ , ce qui coûterait de l'ordre de $n$ multiplications de matrices à $n^{3}$ opérations chacune, soit $n^{4}$ . La différence tient à une seule idée : Warshall met à jour la matrice EN PLACE, en autorisant progressivement les sommets intermédiaires.

Exercice 6 : Transformations du plan : matrices et infographie

En infographie, un point du plan est un vecteur colonne $\begin{pmatrix} x \\ y \end{pmatrix}$ , et une transformation linéaire est une matrice $2 \times 2$ qui le multiplie. On applique ici trois transformations au triangle $T$ de sommets $P_{1}(1,1)$ , $P_{2}(4,1)$ et $P_{3}(1,3)$ .

a) Écrivez la matrice $H$ de l'homothétie de rapport 2 centrée à l'origine, et donnez l'image de $T$ .
b) Écrivez la matrice $R$ de la rotation d'angle $90$ degrés autour de l'origine, et donnez l'image de $T$ .
c) Écrivez la matrice $S$ de la symétrie par rapport à l'axe des abscisses.
d) Calculez l'aire de $T$ , puis celle de $H(T)$ et de $R(T)$ .
e) Quel lien voyez-vous entre le déterminant d'une matrice et l'effet de la transformation sur les aires ?
f) Une translation de vecteur $(3,1)$ peut-elle s'écrire comme une matrice $2 \times 2$ ?

Tape tes réponses, la page te dit juste ou faux 0/17

a)

H_{11}

Image de

P_{2}(4,1)

b)

Les colonnes de

R

sont

Image de

P_{1}(1,1)

Les colonnes d'une matrice sont

c)

S_{11}

S_{22}

d)

Aire de

T

Aire de

H(T)

Aire de

R(T)

e)

\det H

\det R

\det S

L'aire est multipliée par

Un déterminant nul signifie que la transformation

f)

Une translation

Le problème se règle par

Voir la correction

Réponses

a) $H = 2I$ , et $T$ devient $(2,2)$ , $(8,2)$ , $(2,6)$
b) $R = \begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix}$ , et $T$ devient $(-1,1)$ , $(-1,4)$ , $(-3,1)$
c) $S = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}$
d) Aire de $T$ : 3 ; de $H(T)$ : 12 ; de $R(T)$ : 3
e) L'aire est multipliée par $\lvert \det \rvert$ : 4 pour $H$ , 1 pour $R$ , 1 pour $S$ avec l'orientation renversée
f) Non : une transformation linéaire fixe l'origine. Il faut les coordonnées homogènes

a)

$H = \begin{pmatrix} 2 & 0 \\ 0 & 2 \end{pmatrix} = 2I$ . Les images sont $H(P_{1}) = (2,2)$ , $H(P_{2}) = (8,2)$ et $H(P_{3}) = (2,6)$ : chaque coordonnée est doublée. Une homothétie de rapport $k$ centrée à l'origine est toujours $kI$ , et c'est la seule famille de matrices qui commute avec toutes les autres.

b)

La rotation de $90$ degrés envoie $(1,0)$ sur $(0,1)$ et $(0,1)$ sur $(-1,0)$ . Ces images sont les colonnes de la matrice, d'où $R = \begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix}$ , c'est-à-dire $(x,y) \mapsto (-y,x)$ . Images : $R(P_{1}) = (-1,1)$ , $R(P_{2}) = (-1,4)$ et $R(P_{3}) = (-3,1)$ . La règle générale vaut la peine d'être retenue : les colonnes d'une matrice sont les images des vecteurs de base.

c)

La symétrie par rapport à l'axe des abscisses laisse $x$ inchangé et change le signe de $y$ : $S = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}$ . C'est la transformation que subit implicitement toute image affichée à l'écran, où l'axe vertical est dirigé vers le bas.

d)

$T$ est rectangle en $P_{1}$ , de côtés $P_{1}P_{2} = 3$ et $P_{1}P_{3} = 2$ : son aire vaut $\dfrac{3 \times 2}{2} = 3$ . Après l'homothétie, les deux côtés doublent et l'aire est multipliée par 4 : elle vaut 12. Après la rotation, la figure est superposable à la figure de départ : l'aire reste 3.

e)

L'aire est multipliée par $\lvert \det \rvert$ . En effet $\det H = 4$ et l'aire a été multipliée par 4 ; $\det R = 0 \times 0 - (-1)(1) = 1$ et l'aire est conservée ; $\det S = -1$ , l'aire est conservée mais l'orientation est renversée, ce que le signe négatif signale. Une matrice de déterminant nul écrase la figure sur une droite ou sur un point : l'aire devient nulle, et la transformation n'est pas réversible.

f)

Non. Une transformation linéaire fixe toujours l'origine, puisque $M \begin{pmatrix} 0 \\ 0 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \end{pmatrix}$ , alors qu'une translation déplace l'origine en $(3,1)$ . Aucune matrice $2 \times 2$ ne peut donc translater. C'est précisément le problème que règlent les coordonnées homogènes, en ajoutant une troisième coordonnée valant 1 et en travaillant avec des matrices $3 \times 3$ .

Exercice 7 : Déterminant, matrice inverse et réversibilité

Une matrice carrée est inversible exactement quand son déterminant est non nul, et l'inverse défait ce que la matrice a fait. Pour une matrice $2 \times 2$ , $\begin{pmatrix} a & b \\ c & d \end{pmatrix}^{-1} = \dfrac{1}{ad-bc}\begin{pmatrix} d & -b \\ -c & a \end{pmatrix}$ : on échange la diagonale, on change le signe de l'antidiagonale, on divise par le déterminant.

a) Calculez $\det A$ pour $A = \begin{pmatrix} 1 & 2 \\ 3 & -1 \end{pmatrix}$ , puis $A^{-1}$ .
b) Vérifiez que $AA^{-1} = I$ .
c) Calculez le déterminant de $N = \begin{pmatrix} 2 & 1 & 0 \\ 1 & 3 & 1 \\ 0 & 1 & 2 \end{pmatrix}$ par développement suivant la première ligne.
d) Donnez l'inverse de la matrice de rotation $R$ de l'exercice précédent, et interprétez-le.
e) La matrice $\begin{pmatrix} 2 & 4 \\ 1 & 2 \end{pmatrix}$ est-elle inversible ? Que fait-elle géométriquement ?
f) Pourquoi $(PQ)^{-1} = Q^{-1}P^{-1}$ et non $P^{-1}Q^{-1}$ ?

Tape tes réponses, la page te dit juste ou faux 0/13

a)

\det A

A^{-1}

vaut

b)

(AA^{-1})_{11}

(AA^{-1})_{12}

c)

Premier mineur

Deuxième mineur

\det N

d)

R^{-1}

est

On remarque aussi que

e)

Son déterminant

Géométriquement, elle

f)

Il faut défaire les opérations

La vérification est

Voir la correction

Réponses

a) $\det A = -7$ et $A^{-1} = \dfrac{1}{7}A = \begin{pmatrix} 1/7 & 2/7 \\ 3/7 & -1/7 \end{pmatrix}$
b) $AA^{-1} = \dfrac{1}{7}(7I) = I$
c) $\det N = 2(5) - 1(2) + 0 = 8$
d) $R^{-1} = \begin{pmatrix} 0 & 1 \\ -1 & 0 \end{pmatrix}$ , la rotation de $-90$ degrés, et $R^{-1} = R^{T}$
e) Non, son déterminant est nul : elle écrase le plan sur la droite dirigée par $(2,1)$
f) Parce qu'on défait dans l'ordre inverse : $(PQ)(Q^{-1}P^{-1}) = I$

a)

$\det A = (1)(-1) - (2)(3) = -1 - 6 = -7$ , non nul, donc $A$ est inversible. La formule donne $A^{-1} = \dfrac{1}{-7}\begin{pmatrix} -1 & -2 \\ -3 & 1 \end{pmatrix} = \begin{pmatrix} 1/7 & 2/7 \\ 3/7 & -1/7 \end{pmatrix}$ . On retrouve le résultat de l'exercice 3 : puisque $A^{2} = 7I$ , on a bien $A^{-1} = \dfrac{1}{7}A$ .

b)

$AA^{-1} = \dfrac{1}{7}A^{2} = \dfrac{1}{7}(7I) = I$ . En détaillant : le coefficient $(1,1)$ vaut $1(1/7) + 2(3/7) = 1/7 + 6/7 = 1$ ; le coefficient $(1,2)$ vaut $1(2/7) + 2(-1/7) = 0$ . La vérification par le produit est obligatoire, parce qu'une erreur de signe dans la formule de l'inverse ne se voit pas autrement.

c)

On développe suivant la première ligne : $\det N = 2\begin{vmatrix} 3 & 1 \\ 1 & 2 \end{vmatrix} - 1\begin{vmatrix} 1 & 1 \\ 0 & 2 \end{vmatrix} + 0 = 2(6-1) - 1(2-0) + 0 = 10 - 2 = 8$ . Le troisième terme est nul parce que son coefficient l'est : choisir la ligne ou la colonne la plus creuse épargne un mineur entier, et ici la première ligne comme la troisième contiennent un zéro.

d)

$\det R = 1$ , et la formule donne $R^{-1} = \begin{pmatrix} 0 & 1 \\ -1 & 0 \end{pmatrix}$ . C'est la matrice de la rotation de $-90$ degrés : défaire une rotation, c'est tourner dans l'autre sens. On remarque aussi que $R^{-1} = R^{T}$ , ce qui est vrai pour toute matrice de rotation et rend l'inversion gratuite dans un moteur graphique.

e)

$\det = (2)(2) - (4)(1) = 0$ : elle n'est pas inversible. Géométriquement, elle écrase tout le plan sur une droite : les deux colonnes $(2,1)$ et $(4,2)$ sont proportionnelles, donc toutes les images sont des multiples de $(2,1)$ . L'information est perdue, plusieurs points différents ont la même image, et aucune matrice ne peut défaire cela. C'est exactement ce que traduit un déterminant nul : l'aire est écrasée à zéro.

f)

Parce qu'il faut défaire les opérations dans l'ordre inverse de celui où on les a faites. Vérification : $(PQ)(Q^{-1}P^{-1}) = P(QQ^{-1})P^{-1} = PIP^{-1} = PP^{-1} = I$ . La même inversion apparaît pour la transposée, $(PQ)^{T} = Q^{T}P^{T}$ . Image concrète : pour défaire « mettre ses chaussettes puis ses chaussures », on retire les chaussures d'abord.

Exercice 8 : Cinq affirmations à corriger

Chacune des cinq affirmations suivantes est FAUSSE. Dites pourquoi et donnez l'énoncé correct.

1) « Le produit de deux matrices est commutatif : $PQ = QP$ . »
2) « La somme des degrés d'un graphe est égale à son nombre d'arêtes. »
3) « Si $\det(P) = 0$ , alors $P$ admet une matrice inverse. »
4) « La matrice d'adjacence d'un graphe orienté est toujours symétrique. »
5) « Le coefficient $(i,j)$ de $M^{2}$ donne le nombre d'arêtes entre $i$ et $j$ . »

Tape tes réponses, la page te dit juste ou faux 0/10

1)

Le produit matriciel est

(AB)_{11}

(BA)_{11}

2)

Somme des degrés du graphe de l'exercice 1

Son nombre d'arêtes

3)

Une matrice est inversible si et seulement si son déterminant est

4)

La symétrie caractérise

5)

(M^{k})_{ij}

donne

(M^{2})_{11}

du graphe de l'exercice 2

Boucles sur le sommet 1

Voir la correction

Réponses

1) FAUX : $AB \neq BA$ , et parfois $BA$ n'existe même pas
2) FAUX : $\sum_{s} \deg(s) = 2\lvert \mathcal{A} \rvert$ , soit 12 pour 6 arêtes
3) FAUX : c'est l'inverse, $P$ est inversible si et seulement si $\det(P) \neq 0$
4) FAUX : la symétrie caractérise les graphes NON orientés
5) FAUX : $(M^{k})_{ij}$ compte les CHEMINS de longueur $k$ , répétitions permises

1)

FAUX. Contre-exemple de l'exercice 3 : $AB = \begin{pmatrix} 4 & 6 \\ -2 & 11 \end{pmatrix}$ tandis que $BA = \begin{pmatrix} 12 & -4 \\ 5 & 3 \end{pmatrix}$ . Il arrive même que $PQ$ existe et que $QP$ n'existe pas, si les dimensions ne se recollent que dans un sens. Énoncé correct : le produit matriciel est associatif et distributif, mais pas commutatif ; seules quelques familles particulières commutent, comme les multiples de l'identité.

2)

FAUX. Chaque arête compte pour 1 dans le degré de chacune de ses DEUX extrémités. Contre-exemple : le graphe de l'exercice 1 a 6 arêtes et une somme des degrés égale à 12. Énoncé correct : $\sum_{s} \deg(s) = 2\lvert \mathcal{A} \rvert$ , c'est le lemme des poignées de main.

3)

FAUX. C'est exactement le contraire : une matrice est inversible si et seulement si son déterminant est NON nul. Contre-exemple : $\begin{pmatrix} 2 & 4 \\ 1 & 2 \end{pmatrix}$ a un déterminant nul et écrase le plan sur une droite, donc plusieurs points ont la même image et aucune transformation ne peut les distinguer. Énoncé correct : $P$ est inversible si et seulement si $\det(P) \neq 0$ .

4)

FAUX. La symétrie caractérise les graphes NON orientés, où une arête se parcourt dans les deux sens. Contre-exemple : dans le graphe de l'exercice 2, $M_{12} = 1$ et $M_{21} = 0$ , car l'arc va de 1 vers 2 et pas l'inverse. Énoncé correct : la matrice d'adjacence est symétrique si et seulement si le graphe est non orienté.

5)

FAUX. Le nombre d'arêtes de $i$ à $j$ se lit dans $M$ elle-même, pas dans son carré. Contre-exemple : dans le graphe de l'exercice 2, $(M^{2})_{11} = 1$ alors qu'il n'existe aucune boucle sur le sommet 1. Énoncé correct : $(M^{k})_{ij}$ est le nombre de CHEMINS de longueur exactement $k$ de $i$ à $j$ , les répétitions de sommets étant autorisées.

Exercice 9 : Problème : réseau routier et matrice des distances

Cinq centres de données $A$ , $B$ , $C$ , $D$ et $E$ sont reliés par des liaisons dont la longueur, en kilomètres, est portée sur le schéma. Une liaison absente signifie qu'aucun câble direct n'existe entre les deux centres.

a) Donnez le degré de chaque sommet et vérifiez le lemme des poignées de main.
b) Écrivez la matrice des poids $W$ , en mettant 0 sur la diagonale et un tiret là où il n'y a pas de liaison.
c) Donnez tous les trajets de $A$ à $E$ qui ne repassent pas deux fois par le même centre, avec leur longueur.
d) Quel est le trajet le plus court de $A$ à $E$ ?
e) Le trajet le plus court est-il celui qui compte le moins de liaisons ?
f) Si la liaison $DE$ tombe en panne, le réseau reste-t-il connexe ? Quel devient le trajet le plus court de $A$ à $E$ ?

Tape tes réponses, la page te dit juste ou faux 0/19

a)

\deg(C)

Somme des degrés

Nombre de liaisons

b)

Poids de

AC

Poids de

BC

Poids de

CE

La matrice est

c)

A \to C \to E

km

A \to C \to D \to E

km

A \to B \to D \to E

km

A \to C \to B \to D \to E

km

d)

Longueur du plus court trajet km

Ce trajet est

e)

Liaisons du trajet le plus court

Liaisons de

A \to C \to E

Minimiser le nombre d'arêtes et minimiser le poids

f)

Le réseau

Nouvelle longueur minimale km

Coût de la panne km

Voir la correction

Réponses

a) $2, 3, 4, 3, 2$ , de somme $14 = 2 \times 7$
b) Matrice symétrique, diagonale nulle, un tiret pour $AD$ , $AE$ et $BE$
c) $A\to C\to E$ : 12 ; $A\to C\to D\to E$ : 12 ; $A\to B\to D\to E$ : 11 ; $A\to C\to B\to D\to E$ : 10 ; $A\to B\to C\to D\to E$ : 15 ; $A\to B\to C\to E$ : 15 ; $A\to B\to D\to C\to E$ : 27
d) $A \to C \to B \to D \to E$ , 10 km
e) Non : il compte QUATRE liaisons, contre deux pour $A \to C \to E$ qui vaut 12 km
f) Oui, $E$ garde sa liaison vers $C$ . Le plus court devient $A \to C \to E$ , 12 km, soit 2 km de plus

a)

$\deg(A) = 2$ (vers $B$ et $C$ ), $\deg(B) = 3$ (vers $A$ , $C$ , $D$ ), $\deg(C) = 4$ (vers $A$ , $B$ , $D$ , $E$ ), $\deg(D) = 3$ (vers $B$ , $C$ , $E$ ), $\deg(E) = 2$ (vers $C$ , $D$ ). Somme : $2+3+4+3+2 = 14$ , et le réseau compte 7 liaisons : $14 = 2 \times 7$ . Le lemme est vérifié, donc aucune liaison n'a été oubliée sur le relevé.

b)

En rangeant les centres dans l'ordre $A, B, C, D, E$ : la ligne de $A$ est $0, 4, 2, -, -$ ; celle de $B$ est $4, 0, 1, 5, -$ ; celle de $C$ est $2, 1, 0, 8, 10$ ; celle de $D$ est $-, 5, 8, 0, 2$ ; celle de $E$ est $-, -, 10, 2, 0$ . La matrice est symétrique, puisque les liaisons ne sont pas orientées. Dans un programme, le tiret se code par une valeur très grande, de façon que tout chemin l'empruntant soit automatiquement écarté par le calcul du minimum.

c)

Il y a sept trajets sans répétition. Quatre sont courts. $A \to C \to E$ : $2+10 = 12$ . $A \to C \to D \to E$ : $2+8+2 = 12$ . $A \to B \to D \to E$ : $4+5+2 = 11$ . $A \to C \to B \to D \to E$ : $2+1+5+2 = 10$ . Les trois autres sont plus longs : $A \to B \to C \to D \to E$ : $4+1+8+2 = 15$ , $A \to B \to C \to E$ : $4+1+10 = 15$ , et $A \to B \to D \to C \to E$ : $4+5+8+10 = 27$ . L'énumération se fait en arbre, en fixant le premier pas puis le deuxième, ce qui garantit de n'oublier aucun trajet : quatre trajets commencent par $A \to B$ et trois par $A \to C$ .

d)

Le plus court est $A \to C \to B \to D \to E$ , avec 10 kilomètres. Il bat de justesse $A \to B \to D \to E$ , qui vaut 11.

e)

Non, et c'est tout l'intérêt de l'exemple. Le trajet le plus court compte QUATRE liaisons, alors que $A \to C \to E$ n'en compte que deux pour 12 kilomètres. Faire un détour par $C$ puis $B$ coûte une liaison de plus mais évite le câble de 10 kilomètres. Minimiser le nombre d'arêtes et minimiser le poids total sont deux problèmes différents : le premier se résout par un parcours en largeur, le second demande un algorithme comme celui de Dijkstra.

f)

Le réseau reste connexe : $E$ garde sa liaison vers $C$ . Le trajet le plus court de $A$ à $E$ devient $A \to C \to E$ , soit 12 kilomètres, puisque tout trajet vers $E$ de moins de 12 kilomètres finissait par la liaison de $D$ à $E$ . Le coût de la panne est donc de 2 kilomètres. Le sommet $E$ étant de degré 2, il faudrait perdre ses deux liaisons pour l'isoler : c'est la mesure élémentaire de robustesse d'un réseau, et elle explique pourquoi on évite les centres de degré 1.

Exercice 10 : Problème : composer des transformations en coordonnées homogènes

Pour qu'une translation devienne un produit de matrices, on ajoute au point une troisième coordonnée valant 1 : le point $(x,y)$ s'écrit $\begin{pmatrix} x \\ y \\ 1 \end{pmatrix}$ et les transformations deviennent des matrices $3 \times 3$ . On note $T$ la translation de vecteur $(3,1)$ et $R$ la rotation de $90$ degrés autour de l'origine, et l'on suit le point $P(2,0)$ .

La figure ci-dessous représente la situation.

a) Écrivez les matrices $3 \times 3$ de $T$ et de $R$ .
b) Calculez $TR$ , puis l'image de $P$ par cette matrice. Décrivez l'ordre des opérations subies par $P$ .
c) Calculez $RT$ , puis l'image de $P$ . Comparez avec la question précédente.
d) Donnez la matrice qui ramène le point à sa position initiale après $TR$ .
e) Vérifiez votre réponse sur le point image trouvé en b).
f) Pourquoi un processeur graphique préfère-t-il composer les matrices plutôt qu'appliquer les transformations une par une ?

Tape tes réponses, la page te dit juste ou faux 0/13

a)

La dernière colonne de

T

porte

La dernière ligne est toujours

b)

Image de

P

L'ordre des opérations est

c)

Image de

P

La comparaison montre

d)

La matrice cherchée est

Son coefficient de rang (1,3)

Son coefficient de rang (2,3)

e)

On retrouve

f)

Produits matrice-vecteur par sommet, sans composer

Après composition

Ce qui garantit l'identité du résultat est

Voir la correction

Réponses

a) $T$ porte $(3,1)$ en dernière colonne, $R$ porte le bloc de rotation en haut à gauche, et la dernière ligne vaut $(0,0,1)$
b) $TR = \begin{pmatrix} 0 & -1 & 3 \\ 1 & 0 & 1 \\ 0 & 0 & 1 \end{pmatrix}$ et l'image vaut $(3,3)$ : $R$ agit d'abord
c) $RT = \begin{pmatrix} 0 & -1 & -1 \\ 1 & 0 & 3 \\ 0 & 0 & 1 \end{pmatrix}$ et l'image vaut $(-1,5)$ , non $(3,3)$
d) $(TR)^{-1} = R^{-1}T^{-1} = \begin{pmatrix} 0 & 1 & -1 \\ -1 & 0 & 3 \\ 0 & 0 & 1 \end{pmatrix}$
e) L'image de $(3,3)$ est $(2,0)$ : on retrouve bien $P$
f) Six produits par sommet contre un seul après composition : l'associativité garantit le même résultat

a)

$T = \begin{pmatrix} 1 & 0 & 3 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{pmatrix}$ : la dernière colonne porte le vecteur de translation. $R = \begin{pmatrix} 0 & -1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix}$ : le bloc $2 \times 2$ en haut à gauche est la rotation, le reste complète l'identité. La dernière ligne est toujours $(0,0,1)$ , ce qui garantit que la troisième coordonnée du résultat reste 1.

b)

$TR = \begin{pmatrix} 0 & -1 & 3 \\ 1 & 0 & 1 \\ 0 & 0 & 1 \end{pmatrix}$ . Appliquée à $P = (2,0,1)$ : la première coordonnée vaut $0(2) + (-1)(0) + 3(1) = 3$ , la deuxième $1(2) + 0(0) + 1(1) = 3$ . L'image est $(3,3)$ . L'ordre est celui de la lecture de droite à gauche : $R$ agit d'abord, envoyant $(2,0)$ sur $(0,2)$ , puis $T$ ajoute $(3,1)$ et donne $(3,3)$ . Le facteur le plus à droite est appliqué EN PREMIER, ce qui déroute tant qu'on ne l'a pas rattaché à l'écriture $T(R(P))$ .

c)

$RT = \begin{pmatrix} 0 & -1 & -1 \\ 1 & 0 & 3 \\ 0 & 0 & 1 \end{pmatrix}$ . Appliquée à $P$ : première coordonnée $0(2) + (-1)(0) + (-1)(1) = -1$ , deuxième $1(2) + 0(0) + 3(1) = 5$ . L'image est $(-1,5)$ , et non $(3,3)$ . Vérification directe : $T$ envoie d'abord $(2,0)$ sur $(5,1)$ , puis $R$ envoie $(5,1)$ sur $(-1,5)$ . Translater puis tourner n'est pas tourner puis translater, parce que la rotation entraîne aussi le déplacement déjà effectué. C'est la non-commutativité du produit matriciel, vue sur une image.

d)

Il faut défaire dans l'ordre inverse : d'abord annuler $T$ , puis annuler $R$ . La matrice cherchée est $(TR)^{-1} = R^{-1}T^{-1}$ , avec $R^{-1}$ la rotation de $-90$ degrés et $T^{-1}$ la translation de $(-3,-1)$ . Le produit vaut $\begin{pmatrix} 0 & 1 & -1 \\ -1 & 0 & 3 \\ 0 & 0 & 1 \end{pmatrix}$ .

e)

On applique cette matrice à $(3,3,1)$ : première coordonnée $0(3) + 1(3) + (-1)(1) = 2$ , deuxième $(-1)(3) + 0(3) + 3(1) = 0$ . On retrouve $P = (2,0)$ . Le contrôle est concluant, et il vaut mieux le faire sur un point que de recalculer le produit $(TR)(R^{-1}T^{-1})$ , plus long et plus exposé aux erreurs de signe.

f)

Parce qu'une scène contient des centaines de milliers de sommets et qu'une transformation en comporte souvent cinq ou six enchaînées. Appliquer les transformations une par une coûterait six produits matrice-vecteur PAR sommet. En composant d'abord les six matrices, ce qui se fait une seule fois pour toute la scène, il ne reste qu'un seul produit par sommet. L'associativité du produit matriciel garantit que le résultat est identique, et le gain est d'un facteur égal au nombre de transformations : c'est la raison pour laquelle un moteur graphique manipule une unique matrice, dite de modèle-vue-projection.

Exercices corrigés : introduction aux graphes et aux matrices (201-N11)

Rappel de cours

Calculs : les calculs matriciels

Exercice 0.1 : Calculer avec des matrices : dix calculs directs

Partie A : les bases (/50)

Exercice 1 : Vocabulaire des graphes : sommets, arêtes, degrés

Exercice 2 : Matrice d'adjacence d'un graphe orienté

Exercice 3 : Opérations sur les matrices et non-commutativité

Exercice 4 : Puissances de la matrice d'adjacence et comptage de chemins

Exercice 5 : Connexité et matrice d'accessibilité

Partie B : problèmes et raisonnement (/50)

Exercice 6 : Transformations du plan : matrices et infographie

Exercice 7 : Déterminant, matrice inverse et réversibilité

Exercice 8 : Cinq affirmations à corriger

Exercice 9 : Problème : réseau routier et matrice des distances

Exercice 10 : Problème : composer des transformations en coordonnées homogènes

Voir aussi

Vous suivez le cours 201-N11 en informatique au cégep ?