Graphes et matrices

1. 1

   Exercice 1

   Facile

   On considère les matrices

   $$A = \begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix} \qquad\text{et}\qquad B = \begin{pmatrix} 2 & 0 \\ -1 & 3 \end{pmatrix}.$$

   1. Calculer $A + B$, puis les produits $AB$ et $BA$. La multiplication des matrices est-elle commutative ?
   2. Calculer le déterminant de $A$. La matrice $A$ est-elle inversible ?
   3. Déterminer $A^{-1}$ et vérifier le résultat en calculant $A\,A^{-1}$.
   Voir un indice

   Pour une matrice $2\times 2$, $M = \begin{pmatrix} a & b \\ c & d \end{pmatrix}$ a pour déterminant $\det M = ad - bc$ et, si $\det M \neq 0$, on a $M^{-1} = \dfrac{1}{ad-bc}\begin{pmatrix} d & -b \\ -c & a \end{pmatrix}$. Le produit $AB$ se calcule ligne par colonne ; comparer avec $BA$.

   Voir la correction

   1. La somme s'obtient coefficient par coefficient :

   $$A + B = \begin{pmatrix} 3 & 2 \\ 2 & 7 \end{pmatrix}.$$

   Pour le produit $AB$, chaque coefficient est le produit scalaire d'une ligne de $A$ par une colonne de $B$ :

   $$AB = \begin{pmatrix} 1\cdot 2 + 2\cdot(-1) & 1\cdot 0 + 2\cdot 3 \\ 3\cdot 2 + 4\cdot(-1) & 3\cdot 0 + 4\cdot 3 \end{pmatrix} = \begin{pmatrix} 0 & 6 \\ 2 & 12 \end{pmatrix},$$ $$BA = \begin{pmatrix} 2\cdot 1 + 0\cdot 3 & 2\cdot 2 + 0\cdot 4 \\ -1\cdot 1 + 3\cdot 3 & -1\cdot 2 + 3\cdot 4 \end{pmatrix} = \begin{pmatrix} 2 & 4 \\ 8 & 10 \end{pmatrix}.$$

   Comme $AB \neq BA$, la multiplication matricielle n'est pas commutative en général.

   2. $\det A = 1\cdot 4 - 2\cdot 3 = -2 \neq 0$, donc $A$ est inversible.

   3. On applique la formule :

   $$A^{-1} = \frac{1}{-2}\begin{pmatrix} 4 & -2 \\ -3 & 1 \end{pmatrix} = \begin{pmatrix} -2 & 1 \\[2pt] \tfrac{3}{2} & -\tfrac{1}{2} \end{pmatrix}.$$

   Vérification :

   $$A\,A^{-1} = \begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix}\begin{pmatrix} -2 & 1 \\ \tfrac{3}{2} & -\tfrac{1}{2} \end{pmatrix} = \begin{pmatrix} -2+3 & 1-1 \\ -6+6 & 3-2 \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} = I_2 .$$
2. 2

   Exercice 2

   Facile

   Soit la matrice

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

   1. Calculer $A^2$ et $A^3$.
   2. Conjecturer une expression de $A^n$ pour tout entier $n \geq 1$.
   3. Démontrer cette conjecture par récurrence.
   Voir un indice

   Calculer $A^3 = A^2 \times A$. Pour l'hérédité, écrire $A^{n+1} = A^n \times A$ et utiliser l'hypothèse de récurrence.

   Voir la correction

   1.

   $$A^2 = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} = \begin{pmatrix} 1 & 2 \\ 0 & 1 \end{pmatrix}, \qquad A^3 = A^2 A = \begin{pmatrix} 1 & 2 \\ 0 & 1 \end{pmatrix}\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} = \begin{pmatrix} 1 & 3 \\ 0 & 1 \end{pmatrix}.$$

   2. On conjecture $A^n = \begin{pmatrix} 1 & n \\ 0 & 1 \end{pmatrix}$ pour tout $n \geq 1$.

   3. Initialisation. Pour $n=1$, $\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} = A$ : la propriété est vraie.

   Hérédité. Supposons $A^n = \begin{pmatrix} 1 & n \\ 0 & 1 \end{pmatrix}$ pour un entier $n \geq 1$. Alors

   $$A^{n+1} = A^n A = \begin{pmatrix} 1 & n \\ 0 & 1 \end{pmatrix}\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} = \begin{pmatrix} 1 & n+1 \\ 0 & 1 \end{pmatrix}.$$

   La propriété est héréditaire, donc vraie pour tout $n \geq 1$.

3. 3

   Exercice 3

   Facile

   On considère le graphe $G$ non orienté dont les sommets sont $A$, $B$, $C$, $D$ et les arêtes sont :

   $$A\!-\!B, \quad A\!-\!C, \quad B\!-\!C, \quad C\!-\!D.$$

   1. Donner l'ordre du graphe et le degré de chaque sommet.
   2. Le graphe est-il connexe ? Est-il complet ? Justifier.
   3. Écrire la matrice d'adjacence $M$ de $G$ (sommets rangés dans l'ordre $A,B,C,D$).
   4. Vérifier que la somme de tous les degrés est égale au double du nombre d'arêtes.
   Voir un indice

   Le degré d'un sommet est le nombre d'arêtes qui lui sont incidentes. La matrice d'adjacence est symétrique et son coefficient $(i,j)$ vaut $1$ si les sommets $i$ et $j$ sont adjacents, $0$ sinon. Un graphe est complet si chaque paire de sommets distincts est reliée par une arête.

   Voir la correction

   1. L'ordre du graphe (nombre de sommets) est $4$. Les degrés :

   $$\deg(A)=2,\quad \deg(B)=2,\quad \deg(C)=3,\quad \deg(D)=1.$$

   2. Depuis $A$ on atteint tout sommet ($A\!-\!C\!-\!D$, $A\!-\!B$) : le graphe est connexe. Il n'est pas complet : un graphe complet d'ordre $4$ aurait $\binom{4}{2}=6$ arêtes et tous les degrés égaux à $3$ ; ici il n'y a que $4$ arêtes (par exemple $A$ et $D$ ne sont pas adjacents).

   3.

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

   4. Somme des degrés : $2+2+3+1 = 8 = 2\times 4$, soit deux fois le nombre d'arêtes (chaque arête est comptée à ses deux extrémités).

4. 4

   Exercice 4

   Facile

   On considère le graphe non orienté $G$ de sommets $A$, $B$, $C$, $D$ dont la matrice d'adjacence (dans l'ordre $A,B,C,D$) est

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

   1. Décrire les arêtes de $G$ et donner le degré de chaque sommet.
   2. Calculer $M^2$.
   3. En déduire le nombre de chaînes de longueur $2$ reliant $A$ à $C$, puis les énumérer.
   4. Calculer le coefficient $(A,A)$ de $M^3$ et interpréter le résultat.
   Voir un indice

   Le coefficient $(i,j)$ de $M^n$ donne le nombre de chaînes de longueur $n$ reliant le sommet $i$ au sommet $j$. Les coefficients diagonaux de $M^2$ redonnent les degrés. Pour le coefficient $(A,A)$ de $M^3$, calculer la première ligne de $M^2$ multipliée par la première colonne de $M$.

   Voir la correction

   1. Les arêtes sont $A\!-\!B$, $A\!-\!C$, $A\!-\!D$, $B\!-\!C$, $C\!-\!D$. Degrés : $\deg(A)=3$, $\deg(B)=2$, $\deg(C)=3$, $\deg(D)=2$.

   2. En effectuant le produit ligne par colonne :

   $$M^2 = \begin{pmatrix} 3 & 1 & 2 & 1 \\ 1 & 2 & 1 & 2 \\ 2 & 1 & 3 & 1 \\ 1 & 2 & 1 & 2 \end{pmatrix}.$$

   On vérifie que la diagonale $(3,2,3,2)$ redonne bien les degrés des sommets.

   3. Le coefficient $(A,C)$ de $M^2$ vaut $2$ : il y a $2$ chaînes de longueur $2$ de $A$ à $C$, à savoir $A\!-\!B\!-\!C$ et $A\!-\!D\!-\!C$.

   4. Le coefficient $(A,A)$ de $M^3$ est la première ligne de $M^2$ multipliée par la première colonne de $M$ :

   $$\begin{pmatrix} 3 & 1 & 2 & 1 \end{pmatrix}\begin{pmatrix} 0 \\ 1 \\ 1 \\ 1 \end{pmatrix} = 3\cdot 0 + 1\cdot 1 + 2\cdot 1 + 1\cdot 1 = 4.$$

   Il existe donc $4$ chaînes fermées de longueur $3$ partant et revenant en $A$. Cela correspond aux deux triangles contenant $A$ ($A\!-\!B\!-\!C\!-\!A$ et $A\!-\!C\!-\!D\!-\!A$), chacun parcouru dans les deux sens.

5. 5

   Chaîne de Markov à deux états

   Moyen

   Une population d'abonnés à un service peut être, chaque mois, dans l'état « actif » $(A)$ ou « inactif » $(I)$. Chaque mois :

   • un abonné actif le reste avec probabilité $0{,}7$ ;
   • un abonné inactif redevient actif avec probabilité $0{,}4$.

   On note $\pi_n = \begin{pmatrix} a_n & i_n \end{pmatrix}$ la distribution (matrice ligne) au mois $n$, l'ordre des états étant $(A, I)$. Initialement tous les abonnés sont actifs : $\pi_0 = \begin{pmatrix} 1 & 0 \end{pmatrix}$.

   1. Écrire la matrice de transition $P$ et vérifier qu'elle est stochastique.
   2. Calculer $P^2$ et interpréter son coefficient $(A,A)$.
   3. Montrer que $a_{n+1} = 0{,}3\,a_n + 0{,}4$, puis en déduire l'expression de $a_n$ en fonction de $n$.
   4. Déterminer la distribution invariante $\pi$, et retrouver la limite de $\pi_n$.
   Voir un indice

   Une matrice de transition est stochastique lorsque la somme des coefficients de chaque ligne vaut $1$. La distribution après $n$ transitions est $\pi_n = \pi_0 P^n$. Pour la suite $a_{n+1} = 0{,}3\,a_n + 0{,}4$, introduire son point fixe $\ell$ vérifiant $\ell = 0{,}3\,\ell + 0{,}4$ et étudier $a_n - \ell$. Une distribution invariante $\pi$ vérifie $\pi P = \pi$ avec somme des coefficients égale à $1$.

   Voir la correction

   Ce contenu est réservé : laisse tes coordonnées pour débloquer toutes les indications et corrections du site, gratuitement.

   Ta classeTroisièmeSecondePremièreTerminalePrépa scientifique 1ère annéePrépa scientifique 2ème annéePrépa ECG 1ère annéeAutre

   Débloquer

   Tes coordonnées servent uniquement à t'informer de nos ressources et stages — jamais de spam. Politique de confidentialité

6. 6

   Suite matricielle affine et point fixe

   Moyen

   On étudie la suite de matrices colonnes $(U_n)$ définie par $U_0 = \begin{pmatrix} 0 \\ 0 \end{pmatrix}$ et, pour tout $n \geq 0$,

   $$U_{n+1} = A\,U_n + C, \qquad A = \begin{pmatrix} \tfrac{1}{2} & 0 \\[2pt] \tfrac{1}{4} & \tfrac{1}{2} \end{pmatrix}, \qquad C = \begin{pmatrix} 1 \\ 1 \end{pmatrix}.$$

   1. Déterminer la matrice colonne $U^\ast$ vérifiant $U^\ast = A\,U^\ast + C$.
   2. On pose $V_n = U_n - U^\ast$. Montrer que $V_{n+1} = A\,V_n$, puis exprimer $V_n$ en fonction de $A^n$ et $V_0$.
   3. Admettant que $A^n = \begin{pmatrix} (\tfrac{1}{2})^n & 0 \\[2pt] n\,(\tfrac{1}{2})^{n+1} & (\tfrac{1}{2})^n \end{pmatrix}$, donner l'expression de $U_n$, puis sa limite.
   Voir un indice

   Le point fixe vérifie $(I - A)\,U^\ast = C$, donc $U^\ast = (I-A)^{-1} C$. Pour $V_n$, soustraire la relation $U^\ast = A\,U^\ast + C$ de $U_{n+1} = A\,U_n + C$. Une suite du type $V_{n+1} = A\,V_n$ donne $V_n = A^n V_0$.

   Voir la correction

   Ce contenu est réservé : laisse tes coordonnées pour débloquer toutes les indications et corrections du site, gratuitement.

   Ta classeTroisièmeSecondePremièreTerminalePrépa scientifique 1ère annéePrépa scientifique 2ème annéePrépa ECG 1ère annéeAutre

   Débloquer

   Tes coordonnées servent uniquement à t'informer de nos ressources et stages — jamais de spam. Politique de confidentialité

7. 7

   Système résolu par matrice inverse

   Moyen

   Résoudre, à l'aide d'une matrice inverse, le système

   $$\left\{ \begin{aligned} x + y &= 3 \\ y + z &= 5 \\ x + z &= 4 \end{aligned} \right.$$

   1. Écrire ce système sous la forme matricielle $A\,X = b$.
   2. Calculer $\det A$ et déterminer $A^{-1}$.
   3. En déduire l'unique solution $(x,y,z)$.
   Voir un indice

   Poser $X = \begin{pmatrix} x \\ y \\ z \end{pmatrix}$. Si $A$ est inversible, alors $X = A^{-1} b$. Pour inverser $A$, on peut utiliser la comatrice : $A^{-1} = \dfrac{1}{\det A}\,{}^{\!t}\!\big(\mathrm{com}\,A\big)$.

   Voir la correction

   Ce contenu est réservé : laisse tes coordonnées pour débloquer toutes les indications et corrections du site, gratuitement.

   Ta classeTroisièmeSecondePremièreTerminalePrépa scientifique 1ère annéePrépa scientifique 2ème annéePrépa ECG 1ère annéeAutre

   Débloquer

   Tes coordonnées servent uniquement à t'informer de nos ressources et stages — jamais de spam. Politique de confidentialité

8. 8

   Exercice 8

   Difficile

   On considère la matrice

   $$A = \begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix}.$$

   1. Déterminer les valeurs propres de $A$ et, pour chacune, un vecteur propre.
   2. En déduire une matrice inversible $P$ et une matrice diagonale $D$ telles que $A = P D P^{-1}$.
   3. Démontrer que, pour tout entier $n \geq 0$, $A^n = \frac{1}{2}\begin{pmatrix} 3^n + 1 & 3^n - 1 \\ 3^n - 1 & 3^n + 1 \end{pmatrix}.$
   Voir un indice

   Ce contenu est réservé : laisse tes coordonnées pour débloquer toutes les indications et corrections du site, gratuitement.

   Ta classeTroisièmeSecondePremièreTerminalePrépa scientifique 1ère annéePrépa scientifique 2ème annéePrépa ECG 1ère annéeAutre

   Débloquer

   Tes coordonnées servent uniquement à t'informer de nos ressources et stages — jamais de spam. Politique de confidentialité

   Voir la correction

   Ce contenu est réservé : laisse tes coordonnées pour débloquer toutes les indications et corrections du site, gratuitement.

   Ta classeTroisièmeSecondePremièreTerminalePrépa scientifique 1ère annéePrépa scientifique 2ème annéePrépa ECG 1ère annéeAutre

   Débloquer

   Tes coordonnées servent uniquement à t'informer de nos ressources et stages — jamais de spam. Politique de confidentialité

9. 9

   Exercice 9

   Difficile

   Un mobile se déplace entre trois sites $1$, $2$, $3$. À chaque étape, ses probabilités de transition sont données par le graphe orienté pondéré dont la matrice de transition (états dans l'ordre $1,2,3$) est

   $$P = \begin{pmatrix} \tfrac{1}{2} & \tfrac{1}{2} & 0 \\[2pt] \tfrac{1}{4} & \tfrac{1}{2} & \tfrac{1}{4} \\[2pt] 0 & \tfrac{1}{2} & \tfrac{1}{2} \end{pmatrix}.$$

   1. Vérifier que $P$ est une matrice stochastique et décrire les transitions possibles.
   2. Déterminer la distribution invariante $\pi = \begin{pmatrix} a & b & c \end{pmatrix}$, c'est-à-dire la matrice ligne vérifiant $\pi P = \pi$ et $a+b+c = 1$.
   3. Interpréter concrètement la distribution obtenue.
   Voir un indice

   Ce contenu est réservé : laisse tes coordonnées pour débloquer toutes les indications et corrections du site, gratuitement.

   Ta classeTroisièmeSecondePremièreTerminalePrépa scientifique 1ère annéePrépa scientifique 2ème annéePrépa ECG 1ère annéeAutre

   Débloquer

   Tes coordonnées servent uniquement à t'informer de nos ressources et stages — jamais de spam. Politique de confidentialité

   Voir la correction

   Ce contenu est réservé : laisse tes coordonnées pour débloquer toutes les indications et corrections du site, gratuitement.

   Ta classeTroisièmeSecondePremièreTerminalePrépa scientifique 1ère annéePrépa scientifique 2ème annéePrépa ECG 1ère annéeAutre

   Débloquer

   Tes coordonnées servent uniquement à t'informer de nos ressources et stages — jamais de spam. Politique de confidentialité