Show that, for every natural integer $k$, $P ^ { ( k + 1 ) } = P ^ { ( k ) } T$.

Show that $$\|A - B\|_{F}^{2} = \sum_{1 \leqslant i,j \leqslant n} p_{i,j}^{2}\left(\lambda_{i}(A) - \lambda_{j}(B)\right)^{2}.$$

Deduce from this, for every natural integer $k$, an expression for $P ^ { ( k ) }$ as a function of $T$, $k$ and $P ^ { ( 0 ) }$.

We denote $\mathcal{B}_{n}(\mathbb{R})$ the set of doubly stochastic matrices in $\mathcal{M}_{n}(\mathbb{R})$, that is the set of matrices $M = \left(m_{i,j}\right)_{1 \leqslant i,j \leqslant n}$ whose coefficients are all non-negative and such that $\sum_{j=1}^{n} m_{i,j} = \sum_{j=1}^{n} m_{j,i} = 1$ for every $i \in \llbracket 1, n \rrbracket$.
We denote $f : \left|\, \begin{array}{ccc} \mathcal{M}_{n}(\mathbb{R}) & \rightarrow & \mathbb{R} \\ M & \mapsto & \sum_{1 \leqslant i,j \leqslant n} m_{i,j}\left(\lambda_{i}(A) - \lambda_{j}(B)\right)^{2}. \end{array}\right.$
Justify that $f$ admits a minimum on $\mathcal{B}_{n}(\mathbb{R})$.

Suppose that the sequence of vectors $\left( P ^ { ( k ) } \right) _ { k \in \mathbb { N } }$ converges to a vector $P = \left( p _ { 1 } , \ldots , p _ { n } \right)$. Show that $P T = P$, that for all $i \in \llbracket 1 , n \rrbracket$, $p _ { i } \geqslant 0$ and that $p _ { 1 } + \cdots + p _ { n } = 1$.

We denote $\mathcal{B}_{n}(\mathbb{R})$ the set of doubly stochastic matrices in $\mathcal{M}_{n}(\mathbb{R})$, that is the set of matrices $M = \left(m_{i,j}\right)_{1 \leqslant i,j \leqslant n}$ whose coefficients are all non-negative and such that $\sum_{j=1}^{n} m_{i,j} = \sum_{j=1}^{n} m_{j,i} = 1$ for every $i \in \llbracket 1, n \rrbracket$.
We denote $f : \left|\, \begin{array}{ccc} \mathcal{M}_{n}(\mathbb{R}) & \rightarrow & \mathbb{R} \\ M & \mapsto & \sum_{1 \leqslant i,j \leqslant n} m_{i,j}\left(\lambda_{i}(A) - \lambda_{j}(B)\right)^{2}. \end{array}\right.$
Let $(i,j,k) \in \llbracket 1,n \rrbracket^{3}$ such that $j \geqslant i$ and $k \geqslant i$. Show that, for $M \in \mathcal{M}_{n}(\mathbb{R})$ and for $x \in \mathbb{R}^{+}$, $$f\left(M + xE_{ii} + xE_{jk} - xE_{ik} - xE_{ji}\right) - f(M) = 2x\left(\lambda_{i}(A) - \lambda_{j}(A)\right)\left(\lambda_{k}(B) - \lambda_{i}(B)\right) \leqslant 0$$

We consider the directed graph $G = ( S , A )$ where $$\left\{ \begin{array} { l } S = \{ 1,2,3,4 \} \\ A = \{ ( 1,2 ) , ( 2,1 ) , ( 1,3 ) , ( 3,1 ) , ( 1,4 ) , ( 4,1 ) , ( 2,3 ) , ( 3,2 ) , ( 2,4 ) , ( 4,2 ) , ( 3,4 ) , ( 4,3 ) \} \end{array} \right.$$ We assume that, when the point is on one of the vertices of the graph, it has the same probability of going to each of the three other vertices of the graph. We set $$J _ { 4 } = \left( \begin{array} { l l l l } 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \end{array} \right)$$ Express the transition matrix $T$ as a function of $J _ { 4 }$ and $I _ { 4 }$.

We denote $\mathcal{B}_{n}(\mathbb{R})$ the set of doubly stochastic matrices in $\mathcal{M}_{n}(\mathbb{R})$, that is the set of matrices $M = \left(m_{i,j}\right)_{1 \leqslant i,j \leqslant n}$ whose coefficients are all non-negative and such that $\sum_{j=1}^{n} m_{i,j} = \sum_{j=1}^{n} m_{j,i} = 1$ for every $i \in \llbracket 1, n \rrbracket$.
We denote $f : \left|\, \begin{array}{ccc} \mathcal{M}_{n}(\mathbb{R}) & \rightarrow & \mathbb{R} \\ M & \mapsto & \sum_{1 \leqslant i,j \leqslant n} m_{i,j}\left(\lambda_{i}(A) - \lambda_{j}(B)\right)^{2}. \end{array}\right.$
Let $n \geqslant 2$ and $M = \left(m_{i,j}\right)_{1 \leqslant i,j \leqslant n} \in \mathcal{B}_{n}(\mathbb{R})$ a matrix different from the identity. We denote $i$ the smallest integer belonging to $\llbracket 1,n \rrbracket$ such that $m_{i,i} \neq 1$. Show that there exists a matrix $M^{\prime} = \left(m_{i,j}^{\prime}\right)_{1 \leqslant i,j \leqslant n} \in \mathcal{B}_{n}(\mathbb{R})$ such that $f\left(M^{\prime}\right) \leqslant f(M)$ and $m_{j,j}^{\prime} = 1$ for every $j \in \llbracket 1,i \rrbracket$.

We consider the directed graph $G = ( S , A )$ where $$\left\{ \begin{array} { l } S = \{ 1,2,3,4 \} \\ A = \{ ( 1,2 ) , ( 2,1 ) , ( 1,3 ) , ( 3,1 ) , ( 1,4 ) , ( 4,1 ) , ( 2,3 ) , ( 3,2 ) , ( 2,4 ) , ( 4,2 ) , ( 3,4 ) , ( 4,3 ) \} \end{array} \right.$$ We assume that, when the point is on one of the vertices of the graph, it has the same probability of going to each of the three other vertices of the graph. We set $$J _ { 4 } = \left( \begin{array} { l l l l } 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \end{array} \right)$$ Prove that there exists a matrix $Q \in \mathcal { O } _ { 4 } ( \mathbb { R } )$ such that $$T = \frac { 1 } { 3 } Q \left( \begin{array} { c c c c } - 1 & 0 & 0 & 0 \\ 0 & - 1 & 0 & 0 \\ 0 & 0 & - 1 & 0 \\ 0 & 0 & 0 & 3 \end{array} \right) Q ^ { \top }$$

We denote $\mathcal{B}_{n}(\mathbb{R})$ the set of doubly stochastic matrices in $\mathcal{M}_{n}(\mathbb{R})$, that is the set of matrices $M = \left(m_{i,j}\right)_{1 \leqslant i,j \leqslant n}$ whose coefficients are all non-negative and such that $\sum_{j=1}^{n} m_{i,j} = \sum_{j=1}^{n} m_{j,i} = 1$ for every $i \in \llbracket 1, n \rrbracket$.
We denote $f : \left|\, \begin{array}{ccc} \mathcal{M}_{n}(\mathbb{R}) & \rightarrow & \mathbb{R} \\ M & \mapsto & \sum_{1 \leqslant i,j \leqslant n} m_{i,j}\left(\lambda_{i}(A) - \lambda_{j}(B)\right)^{2}. \end{array}\right.$
Deduce that $$\min\left\{f(M) \mid M \in \mathcal{B}_{n}(\mathbb{R})\right\} = f\left(I_{n}\right)$$

We consider the directed graph $G = ( S , A )$ where $$\left\{ \begin{array} { l } S = \{ 1,2,3,4 \} \\ A = \{ ( 1,2 ) , ( 2,1 ) , ( 1,3 ) , ( 3,1 ) , ( 1,4 ) , ( 4,1 ) , ( 2,3 ) , ( 3,2 ) , ( 2,4 ) , ( 4,2 ) , ( 3,4 ) , ( 4,3 ) \} \end{array} \right.$$ We assume that, when the point is on one of the vertices of the graph, it has the same probability of going to each of the three other vertices of the graph. Show that the sequence of matrices $\left( T ^ { k } \right) _ { k \in \mathbb { N } }$ converges and identify geometrically the endomorphism canonically associated with the limit matrix.

Deduce that $$\forall (A,B) \in \mathcal{S}_{n}(\mathbb{R})^{2}, \quad \sum_{i=1}^{n}\left(\lambda_{i}(A) - \lambda_{i}(B)\right)^{2} \leqslant \|A - B\|_{F}^{2}.$$

We consider the directed graph $G = ( S , A )$ where $$\left\{ \begin{array} { l } S = \{ 1,2,3,4 \} \\ A = \{ ( 1,2 ) , ( 2,1 ) , ( 1,3 ) , ( 3,1 ) , ( 1,4 ) , ( 4,1 ) , ( 2,3 ) , ( 3,2 ) , ( 2,4 ) , ( 4,2 ) , ( 3,4 ) , ( 4,3 ) \} \end{array} \right.$$ We assume that, when the point is on one of the vertices of the graph, it has the same probability of going to each of the three other vertices of the graph. Show that, for any row vector $P ^ { ( 0 ) } = \left( p _ { 1 } ^ { ( 0 ) } , p _ { 2 } ^ { ( 0 ) } , p _ { 3 } ^ { ( 0 ) } , p _ { 4 } ^ { ( 0 ) } \right)$, where for $1 \leqslant i \leqslant 4$, $p _ { i } ^ { ( 0 ) }$ is the probability that the point is initially on vertex $i$, the sequence $\left( P ^ { ( k ) } \right) _ { k \in \mathbb { N } }$ converges to the row vector $( 1 / 4,1 / 4,1 / 4,1 / 4 )$.

We consider the graph $G$ represented in Figure 2. We recall that, when the point is on one of the vertices of the graph, it has the same probability of going to each of the vertices to which it is connected. We assume that initially, the point is on vertex 1, so that $P ^ { ( 0 ) } = ( 1,0,0,0,0,0,0,0 )$. We denote $S _ { 1 } = \{ 1,3,6,8 \}$ and $S _ { 2 } = \{ 2,4,5,7 \}$.
Give the transition matrix $T$ of this graph and calculate $$( 1,1,1,1,1,1,1,1 ) T .$$

We consider the graph $G$ represented in Figure 2. We denote $S _ { 1 } = \{ 1,3,6,8 \}$ and $S _ { 2 } = \{ 2,4,5,7 \}$.
Show that, if the point is on a vertex of part $S _ { 1 }$ at a given step, it will be on a vertex of part $S _ { 2 }$ at the next step and that, if it is on a vertex of $S _ { 2 }$ at a given step, it will be on a vertex of $S _ { 1 }$ at the next step.

We consider the graph $G$ represented in Figure 2. We denote $S _ { 1 } = \{ 1,3,6,8 \}$ and $S _ { 2 } = \{ 2,4,5,7 \}$. We assume that initially, the point is on vertex 1, so that $P ^ { ( 0 ) } = ( 1,0,0,0,0,0,0,0 )$.
Is the sequence of vectors $\left( P ^ { ( k ) } \right) _ { k \in \mathbb { N } }$ convergent?

Let $M \in M _ { n } ( \mathbb { R } )$, all of whose coefficients are non-negative. Show that $M$ is a stochastic matrix if and only if $$M \left( \begin{array} { c } 1 \\ \vdots \\ 1 \end{array} \right) = \left( \begin{array} { c } 1 \\ \vdots \\ 1 \end{array} \right) .$$

Show that the transition matrix of a graph (defined in part I) is a stochastic matrix and that, for every natural integer $k$, the vector $P ^ { ( k ) }$, also defined in part I, is a probability distribution.

Let $M \in \mathcal { M } _ { n } ( \mathbb { R } )$ and $N \in \mathcal { M } _ { n } ( \mathbb { R } )$ be two stochastic matrices, $X \in \mathbb { R } ^ { n }$ a probability distribution and $\alpha \in [ 0,1 ]$. Show that $X M$ is a probability distribution.

Let $M \in \mathcal { M } _ { n } ( \mathbb { R } )$ and $N \in \mathcal { M } _ { n } ( \mathbb { R } )$ be two stochastic matrices, $X \in \mathbb { R } ^ { n }$ a probability distribution and $\alpha \in [ 0,1 ]$. Show that $M N$ is a stochastic matrix.

Let $M \in \mathcal { M } _ { n } ( \mathbb { R } )$ and $N \in \mathcal { M } _ { n } ( \mathbb { R } )$ be two stochastic matrices, $X \in \mathbb { R } ^ { n }$ a probability distribution and $\alpha \in [ 0,1 ]$. Show that $\alpha M + ( 1 - \alpha ) N$ is a stochastic matrix.

Let $M = \left( m _ { i , j } \right)$ be a stochastic matrix of $\mathcal { M } _ { n } ( \mathbb { R } )$ and $\lambda$ an eigenvalue (real or complex) of $M$. We denote by $\left( u _ { 1 } , \ldots , u _ { n } \right)$ the components (real or complex), in the canonical basis, of an eigenvector $u$ associated with $\lambda$.
Let $h \in \{ 1 , \ldots , n \}$ such that $\left| u _ { h } \right| = \max _ { 1 \leqslant i \leqslant n } \left| u _ { i } \right|$. Show that $\left| \lambda - m _ { h , h } \right| \leqslant 1 - m _ { h , h }$. Deduce that $| \lambda | \leqslant 1$.

Let $M = \left( m _ { i , j } \right)$ be a stochastic matrix of $\mathcal { M } _ { n } ( \mathbb { R } )$ and $\lambda$ an eigenvalue (real or complex) of $M$. We denote by $\left( u _ { 1 } , \ldots , u _ { n } \right)$ the components (real or complex), in the canonical basis, of an eigenvector $u$ associated with $\lambda$.
Let $\delta = \min _ { 1 \leqslant i \leqslant n } m _ { i , i }$. Show that $| \lambda - \delta | \leqslant 1 - \delta$. Give a geometric interpretation of this result and show that, if all diagonal terms of $M$ are strictly positive, then 1 is the only eigenvalue of $M$ with modulus 1.

We now assume that all coefficients $m _ { i , j } ( 1 \leqslant i , j \leqslant n )$ of the stochastic matrix $M$ are strictly positive.
Prove that $\operatorname { dim } \left( \operatorname { ker } \left( M - I _ { n } \right) \right) = 1$.
If $\left( u _ { 1 } , \ldots , u _ { n } \right)$ denotes the components (real) in the canonical basis of a vector of $\operatorname { ker } \left( M - I _ { n } \right)$, one may use $\min _ { 1 \leqslant i \leqslant n } u _ { i }$.

We now assume that all coefficients $m _ { i , j } ( 1 \leqslant i , j \leqslant n )$ of the stochastic matrix $M$ are strictly positive.
Deduce that there exists at most one probability distribution $X$ invariant by $M$, that is, satisfying $X M = X$.