\documentclass[10pt]{article}
\usepackage[french]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage[version=4]{mhchem}
\usepackage{stmaryrd}
\usepackage{bbold}

\title{Conception : ESSEC - HEC Paris }

\author{MATHÉMATIQUES APPLIQUÉES}
\date{}


\DeclareUnicodeCharacter{25B3}{\ifmmode\triangle\else{$\triangle$}\fi}

\begin{document}
\maketitle


\section*{FILIÈRE ÉCONOMIQUE ET COMMERCIALE}
\section*{VOIE GÉNÉRALE}
Jeudi 24 avril 2025, de 14 h. à 18 h.

La présentation, la lisibilité, l'orthographe, la qualité de la rédaction, la clarté et la précision des raisonnements entreront pour une part importante dans l'appréciation des copies.\\
Les candidats sont invités à encadrer dans la mesure du possible les résultats de leurs calculs.\\
Aucun document n'est autorisé. L'utilisation de toute calculatrice et de tout matériel électronique est interdite. Seule l'utilisation d'une règle graduée est autorisée.\\
Si au cours de l'épreuve, un candidat repère ce qui lui semble être une erreur d'énoncé, il la signalera sur sa copie et poursuivra sa composition en expliquant les raisons des initiatives qu'il sera amené à prendre.

Dans cet énoncé \(r\) est un entier naturel, \(r \geqslant 2\) et \(\llbracket 1, r \rrbracket\) désigne l'ensemble des entiers naturels \(k\) tels que \(1 \leqslant k \leqslant r\).\\
On s'intéresse dans ce problème aux chaînes de Markov homogènes à espace d'états fini \(\llbracket 1, r \rrbracket\) réversibles.\\
Ce type de chaîne intervient dans les marches aléatoires sur les sommets d'un graphe non orienté, les processus de naissance et mort, la méthode de Métropolis par exemple.\\
Le problème comporte trois parties. Les parties 2 et 3 sont indépendantes. Seules les questions 1 et 2 de la partie 1 sont utiles pour la partie 2 .\\
Un aide-mémoire Python se trouve à la fin de l'énoncé.\\
Pour les scripts et fonctions Python, on supposera que les instructions suivantes ont été exécutées :\\
import numpy as np, numpy, random as rd\\
On considère, dans la suite du problème, une chaîne de Markov \(\left(X_{n}\right)_{n \in \mathbb{N}}\), sur un espace probabilisé \((\Omega, \mathcal{A}, \mathbb{P})\), vérifiant les propriétés suivantes :\\
(H1) Pour tout \(n \geqslant 0, X_{n}(\Omega)=\llbracket 1, r \rrbracket\).\\
(H2) Pour tout \(i \in \llbracket 1, i \rrbracket\), il existe \(n \in \mathbb{N}\) tel que \(\mathbb{P}\left(X_{n}=i\right) \neq 0\). On note \(S_{i}\) l'ensemble des entiers positifs \(n\) tels que \(\mathbb{P}\left(X_{n}=i\right) \neq 0\).\\
(H3) Pour tout \((i, j) \in \llbracket 1, r \rrbracket^{2}\), la fonction \(n \mapsto \mathbb{P}_{\left[X_{n}=i\right]}\left(X_{n+1}=j\right)\) est constante sur son ensemble de définition \(S_{i}\) et on note \(p_{i, j}\) cette constante.\\
La matrice \(P=\left(p_{i, j}\right)_{1 \leqslant i, j \leqslant r}\) s'appelle la matrice de transition de la chaine.\\
On rappelle que l'on a pour tout \(i \in \llbracket 1, v^{\prime} \rrbracket, \sum_{j=1}^{r} p_{i, j}=1\).\\
On note \(\mathcal{S} \mathcal{T}_{r}\) l'ensemble des matrices \(M=\left(m_{i, j}\right)_{1 \leqslant i, j \leqslant r}\) à coefficients positifs telles que pour tout \(i \in \llbracket 1, r \rrbracket, \sum_{j=1}^{r} m_{i, j}=1\). Donc \(P \in \mathcal{S} \mathcal{T}\).

\section*{Partie 1 - Matrice stochastique réversible, exemples et caractérisation de Kolmogorov}
On considère \(\mu=\left(\mu_{1} \ldots \mu_{r}\right)\) une matrice ligne appartenant à \(\mathcal{M}_{1, r}(\mathbb{R})\) dont les coefficients sont strictement positifs et tels que \(\sum_{k=1}^{r} \mu_{k}=1\).\\
On dit que la matrice \(M=\left(m_{i, j}\right)_{1 \leqslant i, j \leqslant r}\) est \(\mu\)-réversible si \(M\) appartient à \(S \mathcal{T}_{r}\) et vérifie :

\[
\forall(i, j) \in \llbracket 1, r \rrbracket^{2}, \mu_{i} m_{i, j}=\mu_{j} m_{j, i}
\]

Dans cette partie \(M=\left(m_{i, j}\right)_{1 \leqslant i, j \leqslant r}\) appartient à \(S \mathcal{T}_{r}\).

\begin{enumerate}
  \item a) Montrer que si \(M\) est \(\mu\)-réversible et si \(m_{i, j} \neq 0\) pour un couple \((i, j) \in \llbracket 1, r \rrbracket^{2}\) alors \(m_{j, i} \neq 0\).\\
b) On suppose dans cette question que \(M\) est symétrique. Déterminer \(\mu\) telle que \(M\) est \(\mu\)-réversible.\\
c) On note \(\Delta\) la matrice diagonale d'ordre \(r\) dont les éléments diagonaux sont \(\mu_{1}, \ldots, \mu_{r}\). Montrer que \(M\) est \(\mu\)-réversible si et seulement si \(\Delta M={ }^{t} M \Delta\).
  \item Montrer que si \(M\) est \(\mu\)-réversible alors \(\mu M=\mu\).
  \item Un premier exemple - On suppose que \(r=3\) et que \(P=\frac{1}{3}\left(\begin{array}{lll}1 & 2 & 0 \\ 1 & 0 & 2 \\ 0 & 2 & 1\end{array}\right)\) est la matrice de transition d'une chaîne de Markov.\\
a) Représenter le graphe probabiliste associé à cette matrice de transition.\\
b) Déterminer \(\mu\) telle que \(P\) soit \(\mu\)-réversible.
  \item Un deuxième exemple - Soit \(G\) un graphe à \(r\) sommets \(1, \ldots, r\), non orienté, connexe, simple (deux sommets ne peuvent être reliés que par une seule arête).\\
On considère l'expérience aléatoire qui consiste à se déplacer d'un sommet à l'autre de la manière suìvante :
\end{enumerate}

\begin{itemize}
  \item on choisit un sommet au hasard ce qui définit la valeur de \(X_{0}\);
  \item si on se trouve au sommet \(k\) après \(n\) déplacements, on a alors \(X_{n}=k\), on se déplace vers un sommet adjacent au sommet \(k\), ce qui définit \(X_{n+1}\). Tous les sommets en question peuvent être choisis de manière équiprobable.\\
On admet que l'on définit ainsi une chaîne de Markov et on note encore \(P=\left(p_{i, j}\right)_{1 \leqslant i, j \leqslant r}\) sa matrice de transition .\\
a) Écrire une fonction Python Trajectoire( \(\mathrm{L}, \mathrm{n}\) ) qui étant donnée la liste des listes d'adjacence L du graphe \(G\) et un entier \(n\), simule \(n\) déplacements sur le graphe et renvoie la liste des sommets visités.\\[0pt]
On notera que les sommets reliés au sommet i par une arête se trouvent dans la liste L[i-1].
  \item On note \(A=\left(a_{i, j}\right)_{1 \leqslant i, j \leqslant r}\) la matrice d'adjacence de \(G_{1} d_{i}\) le degré du sommet \(i\).\\
b) Montrer que pour tout \((i, j) \in \llbracket 1, r \rrbracket^{2}, p_{i, j}=\frac{a_{i, j}}{d_{i}}\).\\
c) En déduire \(\mu\) pour laquelle \(P\) est \(\mu\)-réversible.
  \item On note, pour tout \(n \in \mathbb{N}^{*}, m_{i, j}^{(n)}\) les coefficients de la matrice \(M^{n}\).
\end{itemize}

S'il existe \(\sigma \in \mathbb{N}^{*}\) tel que, pour tout \((i, j) \in \llbracket 1, r \rrbracket^{2}, m_{i, j}^{(\sigma)}>0\), on dit que \(M\) est une matrice ergodique.\\
On définit aussi pour tout \(n \in \mathbb{N}^{*}\) et \(\left(i_{0}, \ldots, i_{n}\right) \in \llbracket 1, r \rrbracket^{n+1}\) :

\[
\theta_{M}\left(i_{0}, \ldots, i_{n}\right)=m_{i_{0}, i_{1}} \times \ldots \times m_{i_{n-1}, i_{n}}=\prod_{k=1}^{n} m_{i_{k-1}, i_{k}}
\]

En particulier, pour tout \((i, j) \in \llbracket 1, r \rrbracket^{2}, \theta_{M}(i, j)=m_{i, j}\).\\
5. Montrer que pour tous \((n, s) \in\left(\mathbb{N}^{*}\right)^{2}, i_{0}, \ldots, i_{n}\) et \(j_{0}, \ldots, j_{s}\) éléments de \(\llbracket 1, r \rrbracket\) tels que \(i_{n}=j_{0}\),

\[
\theta_{M}\left(i_{0}, \ldots, i_{n}\right) \theta_{M}\left(j_{0}, \ldots, j_{s}\right)=\theta_{M}\left(i_{0}, \ldots, i_{n}, j_{1}, \ldots, j_{s}\right)
\]

\begin{itemize}
  \item On dit que \(M\) vérifie la propriété \((K)\) si, pour tout \(n \in \mathbb{N}^{*}\) et \(i_{0}, \ldots, i_{n}\) éléments de \(\llbracket 1, r \rrbracket\) :
\end{itemize}

\[
\theta_{M}\left(i_{0}, i_{1}, \ldots, i_{n}, i_{0}\right)=\theta_{M}\left(i_{0}, i_{n}, \ldots, i_{1}, i_{0}\right)
\]

On admet qu'il suffit de vérifier ( \(K\) ) lorsque les \(i_{k}\) sont deux à deux distincts et \(n \geqslant 2\).\\
On établit dans la fin de cette partie que, si \(M\) est ergodique, il existe \(\mu\) telle que \(M\) est \(\mu\)-réversible si seulement si \(M\) vérifie la propriété \((K)\).\\
6. Si \(r=3\), montrer que \(M\) vérifie \((K)\) si et senlement si \(m_{1,2} m_{2,3} m_{3,1}=m_{1,3} m_{3,2} m_{2,1}\).

Montrer que la matrice \(P\) de la question 3 vérifie \((K)\).\\
7. On suppose dans cette question que \(M\) est \(\mu\)-réversible.\\
a) Montrer que pour tout \(n \in \mathbb{N}^{*}\) et \(i_{0}, \ldots, i_{n}\) éléments de \(\llbracket 1, r \rrbracket\) :

\[
\left(\prod_{k=1}^{n} \mu_{i_{k-1}}\right) \theta_{M}\left(i_{0}, \ldots, i_{n}\right)=\left(\prod_{k=1}^{n} \mu_{i_{k}}\right) \theta_{M}\left(i_{n}, \ldots, i_{0}\right)
\]

b) En déduire que \(M\) vérifie ( \(K\) ).\\
8. Soit \((i, j) \in \llbracket 1, r \|^{2}\). Montrer par récurrence sur \(s \in \mathbb{N}^{*}\) que \(m_{i, j}^{(s)}>0\) si et seulement si il existe \(\left(i_{0}, i_{1}, \ldots, i_{s}\right)\) appartenant à \([1, \tau]^{s+1}\) tels que \(i_{0}=i, i_{s}=j\) et \(\theta_{M}\left(i_{0}, \ldots, i_{s}\right)>0\).\\
9. On suppose que la matrice \(M\) vérifie ( \(K\) ) et est ergodique avec pour tout \((i, j) \in[1, r]^{2}\), \(m_{i, j}^{(\sigma)}>0\), où \(\sigma\) est un entier naturel non nul.\\
On veut montrer qu'alors \(M\) est \(\mu\)-réversible pour \(\mu\) à définir.\\
a) Montrer que, pour tout \(i \in \llbracket 1, r \rrbracket\), il existe ( \(i_{0}, i_{1}, \ldots, i_{\sigma}\) ) appartenant à \(\llbracket 1, r \rrbracket^{\sigma+1}\) tels que \(i_{0}=i_{,} i_{\sigma}=1\) et \(\theta_{M}\left(i_{0}, \ldots, i_{\sigma}\right)>0\).\\
Montrer que si \(m_{1, i}>0\), alors \(\theta_{M}\left(i_{\sigma}, \ldots, i_{0}\right)>0\) et \(m_{i, 1}>0\).

\begin{itemize}
  \item Pour tout \(i \in \llbracket 1, r \rrbracket\), on pose alors \(\nu_{i}=\frac{\theta_{M}\left(i_{\sigma}, \ldots, i_{0}\right)}{\theta_{M}\left(i_{0}, \ldots, i_{\sigma}\right)}\) où \(i_{0}, \ldots, i_{\sigma}\) sont définis comme dans la question a).\\
b) Établir que pour tout \((i, j) \in \llbracket 1, r \rrbracket^{2}, \nu_{i} m_{i, j}=\nu_{j} m_{j, i}\), puis en interprétant matriciellement les égalités précédentes que, pour tout \((i, j) \in \llbracket 1, r \rrbracket, \nu_{i} m_{i, j}^{(\sigma)}=\nu_{j} m_{j, i}^{(\sigma)}\).\\
c) Montrer qu'il existe \(i \in \llbracket 1, r \rrbracket\) tel que \(m_{1, i}>0\). En déduire que pour tout \(j \in \llbracket 1, r \rrbracket\), \(\nu_{j}>0\).\\
d) Définir alors \(\mu\) telle que \(M\) soit \(\mu\)-réversible.
\end{itemize}

\section*{Partie 2 - Matrice de transition réversible ergodique, convergence}
On conserve les notations de la partie 1. On rappelle que seules les questions 1 et 2 de la partie 1 sont utiles dans cette partie.\\
On considère que la matrice de transition \(P\) de la chaîne de Markov \(\left(X_{n}\right)_{n \in \mathbb{N}}\) est \(\mu\)-réversible.\\
On note \(Q\) la transposée de \(P\) et \(q_{i, j}\) ses coefficients.\\
10. On rappelle que △ désigne la matrice diagonale appartenant à \(\mathcal{M}_{r}(\mathbb{R})\) dont les éléments diagonaux sont \(\mu_{1}, \ldots, \mu_{r}\).\\
a) Déterminer une matrice diagonale \(D\) inversible telle que \(D^{2}=\Delta\).\\
b) En utilisant la question 1.c), en déduire que \(D^{-1} Q D\) est diagonalisable.\\
c) En conclure que \(Q\) est diagonalisable.

\begin{itemize}
  \item On admet que si \(M\) est une matrice carrée appartenant à \(\mathcal{M}_{r}(\mathbb{R})\) et \(Z\) une matrice ligne appartenant à \(\mathcal{M}_{1, r}(\mathbb{R})\) alors \({ }^{t}(Z M)={ }^{t} M^{t} Z\).
\end{itemize}

\begin{enumerate}
  \setcounter{enumi}{10}
  \item Montrer que \(Q^{t} \mu={ }^{t} \mu\). Que peut-on en déduire pour \(\operatorname{Sp}(Q)\) ?
  \item Soit \(\lambda\) une valeur propre de \(Q\) et \(Y=\left(\begin{array}{c}y_{1} \\ \vdots \\ y_{r}\end{array}\right)\) un vecteur propre associé.\\
a) Montrer que \(\sum_{i=1}^{r}\left(\sum_{j=1}^{r} q_{i, j}\left|y_{j}\right|\right)=\sum_{j=1}^{r}\left|y_{j}\right|\).\\
b) En déduire que \(|\lambda|\left(\sum_{i=1}^{r}\left|y_{i}\right|\right) \leqslant \sum_{i=1}^{r}\left|y_{i}\right|\).\\
c) En conclure que \(\operatorname{Sp}(Q) \subset[-1,1]\).
  \item On suppose dans cette question que tous les coefficients de \(P\), donc de \(Q\), sont strictement positifs. Dans cette question on détermine \(E_{1}(Q)\) où \(E_{1}(Q)\) désigne le sous-espace propre de \(Q\) associé à la valeur propre 1.\\
a) Soit un vecteur propre \(Y=\left(\begin{array}{c}y_{1} \\ \vdots \\ y_{r}\end{array}\right)\) de \(Q\) pour la valeur propre 1 dont l'un au moins des coefficients, noté \(y_{k}\), est strictement positif.\\
On suppose qu'il existe \(\ell\) tel que \(y_{\ell}<0\). Montrer que \(y_{k}<\sum_{j=1}^{r} q_{k, j}\left|y_{j}\right|\), puis que \(\sum_{i=1}^{r}\left|y_{i}\right|<\sum_{i=1}^{r}\left|y_{i}\right|\). Conclusion ?\\
b) En déduire que tous les vecteurs propres de \(Q\) pour la valeur propre 1 ont des composantes qui sont toutes, soit positives, soit négatives. Que peut-on dire d'un élément de \(E_{1}(Q)\) dont la somme des composantes est nulle?\\
c) Soit \(Y\) un vecteur propre de \(Q\) pour la valeur propre 1 . Montrer que \(Y=\left(\sum_{i=1}^{r} y_{i}\right)^{t} \mu\). En conclure que \(E_{1}(Q)=\operatorname{Vect}\left({ }^{t} \mu\right)\).\\
d) Soit \(Y=\left(\begin{array}{c}y_{1} \\ \vdots \\ y_{r}\end{array}\right)\) tel que \(Q Y=-Y\). Montrer que \(\sum_{i=1}^{r} y_{i}=0\). En raisonnant par l'absurde, montrer que -1 n'est pas une valeur propre de \(Q\).
\end{enumerate}

\begin{itemize}
  \item Dans la suite de cette partie on suppose que \(P\) est ergodique avec pour tout \((i, j) \in \llbracket 1, \tau \rrbracket^{2}, p_{i, j}^{(u)}>0\), où \(u\) est un entier naturel non nul .
  \item En appliquant la question précédente à la matrice de transition \(P^{u}\) qui est aussi \(\mu\) réversible, on a :
\end{itemize}

\[
\left.\left.\operatorname{Sp}\left(Q^{u}\right) \subset\right]-1,1\right] \text { et } E_{1}\left(Q^{u}\right)=\operatorname{Vect}\left({ }^{t} \mu\right)
\]

\begin{enumerate}
  \setcounter{enumi}{13}
  \item a) Montrer que \(E_{1}(Q)=\operatorname{Vect}\left({ }^{t} \mu\right)\).\\
b) En distinguant les cas, \(u\) pair et \(u\) impair, montrer par l'absurde que -1 n'est pas une valeur propre de \(Q\).
  \item On note \(\lambda_{1}, \ldots, \lambda_{r}\) les coefficients d'une matrice diagonale semblable à \(Q\), avec \(\lambda_{1}=1\), pour tout \(i \in\{2, \ldots, r\},-1<\lambda_{i}<1\) et \(\left({ }^{t} \mu, Y_{2}, \ldots, Y_{r}\right)\) une base associée de vecteurs propres.\\
On note aussi pour \(n \in \mathbb{N}, L_{n}\) la matrice élément de \(\mathcal{M}_{1, r}(\mathbb{R}):\left(\mathbb{P}\left(X_{n}=1\right) \ldots \mathbb{P}\left(X_{n}=r\right)\right)\).\\
a) Établir que pour tout \(n \in \mathbb{N}, L_{n+1}=L_{n} P\) puis que \(L_{n}=L_{0} P^{n}\).\\
b) Montrer qu'il existe \(\left(\alpha_{1}, \ldots, \alpha_{r}\right) \in \mathbb{R}^{r}\) tel que, pour tout \(n \in \mathbb{N}\) :
\end{enumerate}

\[
L_{n}=\alpha_{1} \mu+\sum_{k=2}^{r} \alpha_{k} \lambda_{k}^{n}\left({ }^{t} Y_{k}\right)
\]

c) En déduire que pour tout \(j \in \llbracket 1, r \rrbracket, \lim _{n \rightarrow+\infty} \mathbb{P}\left(X_{n}=j\right)=\alpha_{1} \mu_{j}\).\\
d) Montrer que \(\alpha_{1}=1\). En conclure que \(\left(X_{n}\right)_{n \in \mathbb{N}}\) converge en loi vers une variable aléatoire \(X\) à valeurs dans \(\llbracket 1, r \rrbracket\) telle que, \(\forall j \in \llbracket 1, r \rrbracket, \mathbb{P}(X=j)=\mu_{j}\).

\section*{Partie 3 - Un algorithme pour la réversibilité}
On conserve les notations de la partie 1. On rappelle que cette partie est indépendante de la précédente.\\
Soit \(\alpha \in] 0,1]\). On définit deux opérations élémentaires sur les matrices \(M=\left(m_{i, j}\right)_{1 \leqslant i, j \leqslant r}\) appartenant à \(S T_{r}\) comme suit :

\begin{itemize}
  \item On modifie la ligne \(k\) de \(M\), où \(k \in \llbracket 1, r \rrbracket\), en remplaçant pour tout \(j \neq k, m_{k, j}\) par \(m_{k, j}^{\prime}=\alpha m_{k, j}\) et \(m_{k, k} \operatorname{par} m_{k, k}^{\prime}=1-\alpha+\alpha m_{k, k}\).
  \item On modifie la colonne \(k\) de \(M\), où \(k \in \llbracket 1, r \rrbracket\), et sa diagonale en remplaçant pour tout \(i \neq k, m_{i, k}\) par \(m_{i, k}^{\prime}=\alpha m_{i, k}\) et \(m_{i, i}\) par \(m_{i, i}^{\prime}=m_{i, i}+(1-\alpha) m_{i, k}\).
  \item Par exemple si \(M=\left(\begin{array}{ccc}\frac{1}{3} & \frac{1}{3} & \frac{1}{3} \\ \frac{1}{3} & 0 & \frac{2}{3} \\ \frac{1}{6} & \frac{2}{3} & \frac{1}{6}\end{array}\right), k=1\) et \(\alpha=\frac{1}{2}\), la première opération donne
\end{itemize}

\[
M^{\prime}=\left(\begin{array}{ccc}
\frac{4}{6} & \frac{1}{6} & \frac{1}{6} \\
\frac{1}{3} & 0 & \frac{2}{3} \\
\frac{1}{6} & \frac{2}{3} & \frac{1}{6}
\end{array}\right) \text { et la deuxième } M^{\prime}=\left(\begin{array}{ccc}
\frac{1}{3} & \frac{1}{3} & \frac{1}{3} \\
\frac{1}{6} & \frac{1}{6} & \frac{2}{3} \\
\frac{1}{12} & \frac{2}{3} & \frac{1}{4}
\end{array}\right) \text {. }
\]

Dans les deux cas on obtient ainsi à partir de \(M \in S \mathcal{T}_{r,} M=\left(m_{i, j}\right)_{1 \leqslant i, j \leqslant r}\), une matrice que l'on notera dans la suite \(M^{\prime}=\left(m_{i, j}^{\prime}\right)_{1 \leqslant i, j \leqslant r}\) qui appartient à \(\mathcal{S} \mathcal{T}_{r}\).\\
On remarquera que l'on ne modifie ainsi tout au plus, pour ce qui est des éléments non diagonaux de \(M\), que ceux de la ligne \(k\), pour la première opération, et ceux de la colonne \(k\) pour la deuxième.\\
16. Ecrire une fonction Python opLigne ( \(\mathrm{M}, \mathrm{k}, \mathrm{alph}\) ) qui réalise l'opération élémentaire sur la \(k\)-ième ligne de \(M\) représentée par la matrice numpy M et \(\alpha\) représenté par alph.

On définit de même une fonction Python opCol(M,k,alph) qui réalise l'opération élémentaire sur la \(k\)-ième colonne et la diagonale de \(M\) (cette fonction n'est pas demandée).\\
17. Soit \(M \in S \mathcal{T}_{r}, M=\left(m_{i, j}\right)_{1 \leqslant i, j \leqslant r}\).\\
a) Montrer que \(M\) vérifie la propriété \((K)\) si et seulement si \(M^{\prime}\) aussi.\\
b) Montrer que pour tout \((i, j) \in \llbracket 1, r \rrbracket^{2}\), si \(m_{i, j}>0\) alors \(m_{i, j}^{\prime}>0\).\\
c) Établir que si \(M\) est ergodique \(M^{\prime}\) l'est aussi.

\begin{itemize}
  \item Soit \(I\) un sous-ensemble non vide de \(\llbracket 1, r \rrbracket\) et \(M \in S \mathcal{T}_{r}, M=\left(m_{i, j}\right)_{1 \leqslant i, j \leqslant r}\).
\end{itemize}

On définit le graphe non orienté \(G_{M}(I)\) dont l'ensemble des sommets est \(I\) et tel que \(\{i, j\}\) est une arête si \(i \neq j, m_{i, j} \neq 0\) et \(m_{j, i}=m_{i, j}\).\\
Donc si \(I\) est réduit à un seul élément le graphe ne comporte pas d'arête.\\
Par exemple si \(M=\left(\begin{array}{ccc}\frac{1}{3} & \frac{1}{3} & \frac{1}{3} \\ \frac{1}{3} & 0 & \frac{2}{3} \\ \frac{1}{6} & \frac{2}{3} & \frac{1}{6}\end{array}\right)\), avec \(I=\{1,2,3\}\) les arêtes sont \(\{1,2\}\) et \(\{2,3\}\), et avec \(I=\{1,3\}\) il n'y a aucune arète.\\
18. On suppose que \(I\) est tel que \(G_{M}(I)\) est connexe et qu'il existe \(\ell \in I\) et \(k \notin I\) tels que \(m_{\ell, k}\) et \(m_{k, \ell}\) sont non nuls.\\
Si \(m_{\ell, k} \leqslant m_{k, \ell}\), on pose \(\alpha=\frac{m_{\ell, k}}{m_{k, \ell}}\) et on fait l'opération élémentaire sur la ligne \(k\) avec ce coefficient, sinon on pose \(\alpha=\frac{m_{k, \ell}}{m_{\ell, k}}\) et on fait l'opération élémentaire sur la colonne \(k\) avec ce coefficient.\\
On note encore \(M^{\prime}\) la matrice obtenue. Montrer que \(\{k, \ell\}\) est une arête de \(G_{M^{\prime}}(I \cup\{k\})\) et que ce graphe est connexe.

\begin{itemize}
  \item On suppose que \(M \in S \mathcal{T}_{r}, M=\left(m_{i, j}\right)_{1 \leqslant i, j \leqslant r}\) est ergodique dans la suite de cette partie.
\end{itemize}

\begin{enumerate}
  \setcounter{enumi}{18}
  \item On suppose dans cette question que \(M\) vérifie ( \(K\) ).\\
a) En utilisant le résultat de la question 8, établir que si \(I\) est un sous-ensemble non vide de \(\llbracket 1, r \rrbracket\), différent de \(\llbracket 1, r \rrbracket\), il existe \(\ell \in I\) et \(k \notin I\) tels que \(m_{\ell, k}\) et \(m_{k, \ell}\) sont non nuls.\\
b) On pose \(I=\{1\}\). Le graphe \(G_{M}(I)\) est alors connexe. En déduire un algorithme, composé de \(r-1\) opérations élémentaires à partir de \(M\) et \(I=\{1\}\), qui la transforme en une matrice \(M^{*}\) ergodique, vérifiant \((K)\) et telle que \(G_{M^{*}}(\llbracket 1, r \rrbracket)\) est connexe.\\
En déduire que \(M^{*}\) est symétrique.
  \item Réciproquement, on suppose qu'à partir de \(M \in S \mathcal{T}_{r}\), une suite d'opérations élémentaires la transforme en une matrice symétrique \(M^{*}\). Montrer que \(M\) vérifie la propriété \((K)\).
  \item On veut implémenter l'algorithme de la question 19.b) en Python.\\
a) Écrire une fonction Python \(\operatorname{NonNul}(\mathrm{M}, \mathrm{I}, \mathrm{J})\) qui, étant donnés une matrice \(M= \left(m_{i, j}\right)_{1 \leqslant i, j \leqslant r}\) représentée par la matrice numpy M et deux ensembles non vides d'indices \(I\) et \(J\), représentés par les listes I et J, renvoie un couple \((i, j)\) tel que \(i \in I\), \(j \in J\) et \(m_{i, j} \neq 0\), c'est à dire M [i-1] [j-1] est non nul, s'il existe un tel couple et le couple \((0,0)\) sinon.\\
b) Compléter la fonction suivante pour qu'elle réalise l'implémentation de l'algorithme de la question 19.b) et renvoie True si \(M\) ergodique vérifie ( \(K\) ) et False sinon.
\end{enumerate}

\begin{verbatim}
def estRev(M):
    r=np.shape(M)[O]
    I=[1]; J=[k for k in range(2,r+1)]
    while len(I)< ... :
        ell,k=NonNul(M,I,J)
        if (ell==0) or M[k-1][ell-1]*M[ell-1][k-1]==0:
            return ...
        else:
            if M[ell-1][k-1]<=M[k-1][ell-1]:
                OpLigne(M,k,M[ell-1][k-1]/M[k-1][ell-1])
            else:
                OpCol(M,k,M[k-1][ell-1]/M[ell-1][k-1])
            I.append (...)
            J,remove(...)
    return (np.transpose(M)==M).all()
    # Teste l'égalité de deux matrices numpy
\end{verbatim}

\section*{Aide-MÉmoire PYTHON}
Toutes les fonctions et instructions présentées ne sont pas utiles et il est possible d'utiliser d'autres fonctions ou instructions absentes de cet aide-mémoire.

Listes\\[0pt]
[] Créer une liste vide\\[0pt]
[a] *n ou \(n *[a]\) Créer une liste avec \(n\) fois l'élément a\\
L. append(a) Ajoute l'élément a à la fin de la liste L

L1 + L2 Concatène les deux listes L1 et L2\\
len (L) Renvoie le nombre d'éléments de la liste L\\
L. count (a) Renvoie le nombre d'occurences de a dans la liste L\\
L. remove (a) Enlève la première occurence de la valeur a de la liste L\\
a in L Vaut True si a se trouve au moins une fois dans L et False sinon\\
Module mathématique numpy\\
import numpy as np\\
np.array (L) Transforme la liste L en vecteur ou matrice numpy\\
np.transpose (M) Renvoie la transposée de \(M\)\\
np. shape (M) Renvole dans un couple le format de la matrice \(M\)\\
Sous module random de numpy pour la simulation probabiliste\\
import numpy.random as rd\\
rd.randint ( \(\mathrm{a}, \mathrm{b},[\mathrm{r}, \mathrm{s}]\) ) Simule une réalisation d'une matrice ( \(r, s\) ) dont les coefficients sont des variables aléatoires indépendantes qui suivent la loi uniforme discrète \(\mathcal{U}([a, b-1])\)

Si le paramètre [ \(x, s\) ] est remplacé par \(x\), cette fonction renvoie la réalisation d'un vecteur de longueur \(r\) correspondant à la loi en question, et si ce paramètre est omis, elles renvoient un seul coefficient suivant les mêmes contraintes.

\section*{FIN DE L'ÉNONCÉ}

\end{document}