We now assume that all coefficients $m _ { i , j } ( 1 \leqslant i , j \leqslant n )$ of the stochastic matrix $M$ are strictly positive. We set $\varepsilon = \min _ { 1 \leqslant i , j \leqslant n } m _ { i , j }$. We are interested in the sequence $\left( M ^ { k } \right) _ { k \in \mathbb { N } }$ of powers of $M$. We denote by $m _ { i , j } ^ { ( k ) }$ the coefficient of the matrix $M ^ { k }$ located in row $i$ and column $j$.
For all $j \in \llbracket 1 , n \rrbracket$, we set $$\left\{ \begin{array} { l } \alpha _ { j } ^ { ( k ) } = \min _ { 1 \leqslant i \leqslant n } m _ { i , j } ^ { ( k ) } , \\ \beta _ { j } ^ { ( k ) } = \max _ { 1 \leqslant i \leqslant n } m _ { i , j } ^ { ( k ) } . \end{array} \right.$$
In the following four questions, $j$ is a fixed integer in $\llbracket 1 , n \rrbracket$ and $k$ is fixed in $\mathbb { N }$. Prove the inequalities $\alpha _ { j } ^ { ( k ) } \leqslant \alpha _ { j } ^ { ( k + 1 ) } \leqslant \beta _ { j } ^ { ( k + 1 ) } \leqslant \beta _ { j } ^ { ( k ) }$.

We now assume that all coefficients $m _ { i , j } ( 1 \leqslant i , j \leqslant n )$ of the stochastic matrix $M$ are strictly positive. We set $\varepsilon = \min _ { 1 \leqslant i , j \leqslant n } m _ { i , j }$. We are interested in the sequence $\left( M ^ { k } \right) _ { k \in \mathbb { N } }$ of powers of $M$. We denote by $m _ { i , j } ^ { ( k ) }$ the coefficient of the matrix $M ^ { k }$ located in row $i$ and column $j$.
For all $j \in \llbracket 1 , n \rrbracket$, we set $$\left\{ \begin{array} { l } \alpha _ { j } ^ { ( k ) } = \min _ { 1 \leqslant i \leqslant n } m _ { i , j } ^ { ( k ) } , \\ \beta _ { j } ^ { ( k ) } = \max _ { 1 \leqslant i \leqslant n } m _ { i , j } ^ { ( k ) } . \end{array} \right.$$
In the following four questions, $j$ is a fixed integer in $\llbracket 1 , n \rrbracket$ and $k$ is fixed in $\mathbb { N }$. Prove that there exists a pair $\left( i _ { 0 } , j _ { 0 } \right) \in \llbracket 1 , n \rrbracket ^ { 2 }$ such that $$\alpha _ { j } ^ { ( k + 1 ) } - \alpha _ { j } ^ { ( k ) } \geqslant m _ { i _ { 0 } , j _ { 0 } } \left( \beta _ { j } ^ { ( k ) } - \alpha _ { j } ^ { ( k ) } \right) .$$

We now assume that all coefficients $m _ { i , j } ( 1 \leqslant i , j \leqslant n )$ of the stochastic matrix $M$ are strictly positive. We set $\varepsilon = \min _ { 1 \leqslant i , j \leqslant n } m _ { i , j }$. We are interested in the sequence $\left( M ^ { k } \right) _ { k \in \mathbb { N } }$ of powers of $M$. We denote by $m _ { i , j } ^ { ( k ) }$ the coefficient of the matrix $M ^ { k }$ located in row $i$ and column $j$.
For all $j \in \llbracket 1 , n \rrbracket$, we set $$\left\{ \begin{array} { l } \alpha _ { j } ^ { ( k ) } = \min _ { 1 \leqslant i \leqslant n } m _ { i , j } ^ { ( k ) } , \\ \beta _ { j } ^ { ( k ) } = \max _ { 1 \leqslant i \leqslant n } m _ { i , j } ^ { ( k ) } . \end{array} \right.$$
In the following four questions, $j$ is a fixed integer in $\llbracket 1 , n \rrbracket$ and $k$ is fixed in $\mathbb { N }$. Prove that there exists a pair $\left( i _ { 1 } , j _ { 1 } \right) \in \llbracket 1 , n \rrbracket ^ { 2 }$ such that $$\beta _ { j } ^ { ( k ) } - \beta _ { j } ^ { ( k + 1 ) } \geqslant m _ { i _ { 1 } , j _ { 1 } } \left( \beta _ { j } ^ { ( k ) } - \alpha _ { j } ^ { ( k ) } \right) .$$

For all $n \in \mathbb { N }$, let $G _ { n } = \left( \left( X ^ { i - 1 } \mid X ^ { j - 1 } \right) \right) _ { 1 \leqslant i , j \leqslant n + 1 }$ be the Gram matrix and let $\left( V _ { n } \right) _ { n \in \mathbb { N } }$ be an orthogonal system. Let $Q _ { n } = \left( q _ { i , j } \right) _ { 1 \leqslant i , j \leqslant n + 1 }$ be the matrix of the family $\left( V _ { 0 } , V _ { 1 } , \ldots , V _ { n } \right)$ in the basis $\left( 1 , X , \ldots , X ^ { n } \right)$ of $\mathbb { R } _ { n } [ X ]$. Show that $Q _ { n }$ is upper triangular and that $\operatorname { det } Q _ { n } = 1$.

We now assume that all coefficients $m _ { i , j } ( 1 \leqslant i , j \leqslant n )$ of the stochastic matrix $M$ are strictly positive. We set $\varepsilon = \min _ { 1 \leqslant i , j \leqslant n } m _ { i , j }$. We are interested in the sequence $\left( M ^ { k } \right) _ { k \in \mathbb { N } }$ of powers of $M$. We denote by $m _ { i , j } ^ { ( k ) }$ the coefficient of the matrix $M ^ { k }$ located in row $i$ and column $j$.
For all $j \in \llbracket 1 , n \rrbracket$, we set $$\left\{ \begin{array} { l } \alpha _ { j } ^ { ( k ) } = \min _ { 1 \leqslant i \leqslant n } m _ { i , j } ^ { ( k ) } , \\ \beta _ { j } ^ { ( k ) } = \max _ { 1 \leqslant i \leqslant n } m _ { i , j } ^ { ( k ) } . \end{array} \right.$$
Deduce that $\beta _ { j } ^ { ( k + 1 ) } - \alpha _ { j } ^ { ( k + 1 ) } \leqslant ( 1 - 2 \varepsilon ) \left( \beta _ { j } ^ { ( k ) } - \alpha _ { j } ^ { ( k ) } \right)$.

For all $n \in \mathbb { N }$, let $G _ { n } = \left( \left( X ^ { i - 1 } \mid X ^ { j - 1 } \right) \right) _ { 1 \leqslant i , j \leqslant n + 1 }$, let $G _ { n } ^ { \prime } = \left( \left( V _ { i - 1 } \mid V _ { j - 1 } \right) \right) _ { 1 \leqslant i , j \leqslant n + 1 }$, and let $Q _ { n }$ be the matrix of the family $\left( V _ { 0 } , V _ { 1 } , \ldots , V _ { n } \right)$ in the basis $\left( 1 , X , \ldots , X ^ { n } \right)$. Show that $Q _ { n } ^ { \top } G _ { n } Q _ { n } = G _ { n } ^ { \prime }$, where $Q _ { n } ^ { \top }$ is the transpose of the matrix $Q _ { n }$.

We now assume that all coefficients $m _ { i , j } ( 1 \leqslant i , j \leqslant n )$ of the stochastic matrix $M$ are strictly positive. We set $\varepsilon = \min _ { 1 \leqslant i , j \leqslant n } m _ { i , j }$.
Prove that the sequence $\left( M ^ { k } \right)$ converges to a stochastic matrix $B = \left( \begin{array} { l l l } b _ { 1 } & \cdots & b _ { n } \\ b _ { 1 } & \cdots & b _ { n } \\ b _ { 1 } & \cdots & b _ { n } \end{array} \right)$ all of whose rows are equal.

For all $n \in \mathbb { N }$, let $G _ { n } = \left( \left( X ^ { i - 1 } \mid X ^ { j - 1 } \right) \right) _ { 1 \leqslant i , j \leqslant n + 1 }$ and let $\left( V _ { n } \right) _ { n \in \mathbb { N } }$ be an orthogonal system. Deduce that $\operatorname { det } G _ { n } = \prod _ { i = 0 } ^ { n } \left\| V _ { i } \right\| ^ { 2 }$.

We model the web by a directed graph with $n$ vertices. For every integer $i \in \llbracket 1 , n \rrbracket$, $\lambda _ { i }$ denotes the number of outgoing edges from page $i$. We assume that no page points to itself. A surfer navigates the web in the following way: when on page $i$,

• if page $i$ points to other pages, he goes randomly, with equal probability, to one of these pages;
• if page $i$ points to no other page, he remains on page $i$.

Verify that the transition matrix associated with this navigation model is the matrix $A = \left( a _ { i , j } \right) _ { 1 \leqslant i , j \leqslant n }$ with $$\left\{ \begin{array} { l } a _ { i , i } = \begin{cases} 1 & \text { if page } i \text { points to no other page } \\ 0 & \text { otherwise } \end{cases} \\ a _ { i , j } = \left\{ \begin{array} { l l } 0 & \text { if } i \nrightarrow j \\ 1 / \lambda _ { i } & \text { if } i \rightarrow j \end{array} \quad \text { for } i \neq j \right. \end{array} \right.$$

We model the web by a directed graph with $n$ vertices. The matrix $A$ is the stochastic matrix described in question 29. We define $$B = ( 1 - \alpha ) A + \frac { \alpha } { n } J _ { n }$$ where $J _ { n }$ is the matrix in $\mathcal { M } _ { n } ( \mathbb { R } )$ whose coefficients are all equal to $1$, $A$ is the stochastic matrix described in question 29 and $\alpha$ is a real number in $] 0,1 [$, called the damping factor.
Show that $B$ is a stochastic matrix whose coefficients are all strictly positive.

We model the web by a directed graph with $n$ vertices. The matrix $A$ is the stochastic matrix described in question 29. We define $$B = ( 1 - \alpha ) A + \frac { \alpha } { n } J _ { n }$$ where $J _ { n }$ is the matrix in $\mathcal { M } _ { n } ( \mathbb { R } )$ whose coefficients are all equal to $1$, $A$ is the stochastic matrix described in question 29 and $\alpha$ is a real number in $] 0,1 [$, called the damping factor.
In the navigation model admitting $B$ as its transition matrix, give the probability of leaving a page containing no links to another page.

Let $n \in \mathbb { N }$. Deduce from the previous parts the value of the determinant $$H _ { n } = \operatorname { det } \left( C _ { i + j - 2 } \right) _ { 1 \leqslant i , j \leqslant n + 1 } = \left| \begin{array} { c c c c c c } C _ { 0 } & C _ { 1 } & C _ { 2 } & \ldots & C _ { n - 1 } & C _ { n } \\ C _ { 1 } & \therefore & & \therefore & \therefore & C _ { n + 1 } \\ C _ { 2 } & & \ddots & \ddots & \therefore & \vdots \\ \vdots & \therefore & \ddots & \ddots & & C _ { 2 n - 2 } \\ C _ { n - 1 } & \therefore & \ddots & & \therefore & C _ { 2 n - 1 } \\ C _ { n } & C _ { n + 1 } & \cdots & C _ { 2 n - 2 } & C _ { 2 n - 1 } & C _ { 2 n } \end{array} \right|.$$

We set, for all $n \in \mathbb { N }$, $$D _ { n } ( X ) = \left| \begin{array} { c c c c c c } C _ { 0 } & C _ { 1 } & C _ { 2 } & \ldots & C _ { n - 1 } & C _ { n } \\ C _ { 1 } & \therefore & & \therefore & \therefore & C _ { n + 1 } \\ C _ { 2 } & & \ddots & \therefore & \ddots & \vdots \\ \vdots & \ddots & \ddots & \ddots & & C _ { 2 n - 2 } \\ C _ { n - 1 } & C _ { n } & C _ { n + 1 } & \ldots & C _ { 2 n - 2 } & C _ { 2 n - 1 } \\ 1 & X & \cdots & X ^ { n - 2 } & X ^ { n - 1 } & X ^ { n } \end{array} \right|$$ with the inner product $( P \mid Q ) = \frac { 2 } { \pi } \int _ { 0 } ^ { 1 } P ( 4 x ) Q ( 4 x ) \frac { \sqrt { 1 - x } } { \sqrt { x } } \mathrm { ~d} x$. Let $( n , k ) \in \mathbb { N } ^ { 2 }$ such that $k < n$. Show $\left( D _ { n } \mid X ^ { k } \right) = 0$.

We set, for all $n \in \mathbb { N }$, $$D _ { n } ( X ) = \left| \begin{array} { c c c c c c } C _ { 0 } & C _ { 1 } & C _ { 2 } & \ldots & C _ { n - 1 } & C _ { n } \\ C _ { 1 } & \therefore & & \therefore & \therefore & C _ { n + 1 } \\ C _ { 2 } & & \ddots & \therefore & \ddots & \vdots \\ \vdots & \ddots & \ddots & \ddots & & C _ { 2 n - 2 } \\ C _ { n - 1 } & C _ { n } & C _ { n + 1 } & \ldots & C _ { 2 n - 2 } & C _ { 2 n - 1 } \\ 1 & X & \cdots & X ^ { n - 2 } & X ^ { n - 1 } & X ^ { n } \end{array} \right|$$ and $$H _ { n } ^ { \prime } = \left| \begin{array} { c c c c c c } C _ { 1 } & C _ { 2 } & C _ { 3 } & \ldots & C _ { n - 1 } & C _ { n } \\ C _ { 2 } & \therefore & & \ddots & \ddots & C _ { n + 1 } \\ C _ { 3 } & & \ddots & \ddots & \ddots & \vdots \\ \vdots & \ddots & \ddots & \ddots & & C _ { 2 n - 3 } \\ C _ { n - 1 } & \therefore & \ddots & & \ddots & C _ { 2 n - 2 } \\ C _ { n } & C _ { n + 1 } & \cdots & C _ { 2 n - 3 } & C _ { 2 n - 2 } & C _ { 2 n - 1 } \end{array} \right|.$$ Deduce that $\forall n \in \mathbb { N } , D _ { n } = U _ { n }$, then determine, for all $n \in \mathbb { N } ^ { * }$, the value of the determinant $H _ { n } ^ { \prime }$.

We are given two matrices $A$ and $B$ in $\mathcal{M}_n(\mathbf{K})$. We assume that $A$ and $B$ commute.
$\mathbf{1}$ ▷ Show that the matrices $A$ and $e^{B}$ commute.

Let $A$ be the matrix in $M_{2}(\mathbf{R})$ defined by: $$A = \left(\begin{array}{cc} 1 & 1 \\ -1 & 3 \end{array}\right)$$ Is the matrix $A$ semi-simple?

Let $V$ and $V^{\prime}$ be two subspaces of $E$ of dimension $p$ (we recall that $p \geqslant 1$).
(a) Show that there exist $u_1 \in V$ and $u_1^{\prime} \in V^{\prime}$ of norm 1 such that $$\left\langle u_1, u_1^{\prime}\right\rangle = \sup\left\{\left\langle a, a^{\prime}\right\rangle \mid\left(a, a^{\prime}\right) \in V \times V^{\prime},\|a\|=\left\|a^{\prime}\right\|=1\right\}.$$
(b) Extend this result by showing that there exist a family $u = (u_1, \ldots, u_p)$ of vectors of $V$ and a family $u^{\prime} = (u_1^{\prime}, \ldots, u_p^{\prime})$ of vectors of $V^{\prime}$ such that $u$ and $u^{\prime}$ are orthonormal and satisfy the following two conditions:
(i) For $k = 1$, we have $$\left\langle u_1, u_1^{\prime}\right\rangle = \sup\left\{\left\langle a, a^{\prime}\right\rangle \mid\left(a, a^{\prime}\right) \in V \times V^{\prime},\|a\|=\left\|a^{\prime}\right\|=1\right\}.$$
(ii) For $k \in \llbracket 2, p \rrbracket$, we have $$\left\langle u_k, u_k^{\prime}\right\rangle = \sup\left\{\left\langle a, a^{\prime}\right\rangle \mid\left(a, a^{\prime}\right) \in V \times V^{\prime},\|a\|=\left\|a^{\prime}\right\|=1,\right.$$ $$\left.\left\langle a, u_l\right\rangle=\left\langle a^{\prime}, u_l^{\prime}\right\rangle=0 \text{ for all } l \in \llbracket 1, k-1 \rrbracket\right\}.$$
(Hint: One may construct the vectors $u_k$ and $u_k^{\prime}$ by induction on the integer $k$.)

Let $A$ and $B$ be two matrices in $\mathcal { M } _ { n } ( \mathbb { R } )$ such that
$$\forall ( X , Y ) \in \left( \mathcal { M } _ { n , 1 } ( \mathbb { R } ) \right) ^ { 2 } , \quad X ^ { \top } A Y = X ^ { \top } B Y .$$
Show that $A = B$.

Prove that the application $$\begin{array} { | c l l } \mathcal { M } _ { n } ( \mathbb { R } ) & \rightarrow & \mathbb { R } \\ M & \mapsto & \operatorname { tr } ( M ) \end{array}$$ is a linear form and that $$\forall ( A , B ) \in \left( \mathcal { M } _ { n } ( \mathbb { R } ) \right) ^ { 2 } , \quad \operatorname { tr } ( A B ) = \operatorname { tr } ( B A ) .$$

Justify that if $M \in \mathcal{M}_{n}(\mathbf{C})$, the map $$X \in \Sigma_{n} \longmapsto \|MX\|$$ attains its maximum, which we denote by $\|M\|_{\text{op}}$. Establish the two properties $$\begin{gathered} \forall M \in \mathcal{M}_{n}(\mathbf{C}), \quad \|M\|_{\mathrm{op}} = \max\left\{\frac{\|MX\|}{\|X\|}; X \in \mathcal{M}_{n,1}(\mathbf{C}) \backslash \{0\}\right\}, \\ \forall (M, M^{\prime}) \in \mathcal{M}_{n}(\mathbf{C})^{2}, \quad \|M^{\prime}M\|_{\mathrm{op}} \leq \|M^{\prime}\|_{\mathrm{op}} \|M\|_{\mathrm{op}}. \end{gathered}$$

We fix two orthonormal families $u = (u_1, \ldots, u_p)$ of vectors of $V$ and $u^{\prime} = (u_1^{\prime}, \ldots, u_p^{\prime})$ of vectors of $V^{\prime}$ satisfying the conditions of question (1).
Show that if $\operatorname{dim}(V \cap V^{\prime}) \geqslant 1$, then $u_k = u_k^{\prime}$ for all $1 \leqslant k \leqslant \operatorname{dim}(V \cap V^{\prime})$.

Let $A \in \mathrm { M } _ { 2 } ( \mathbb { C } )$ be a matrix and let $\epsilon > 0$ be a real number.
(a) Show the existence of a real number $\alpha > 0$ such that for every positive integer $n$ the absolute values of the coefficients of $A ^ { n }$ are bounded by $\alpha ( \rho ( A ) + \epsilon ) ^ { n }$.
(b) Deduce the existence of a real number $\beta > 0$ such that for every positive integer $n$ and all $x \in \mathbb { C } ^ { 2 }$ we have $$\left\| A ^ { n } x \right\| \leqslant \beta ( \rho ( A ) + \epsilon ) ^ { n } \| x \|$$

Let $A \in \mathrm { M } _ { 2 } ( \mathbb { C } )$ be a matrix and let $\eta$ be a strictly positive real number.
(a) For $x \in \mathbb { C } ^ { 2 }$, show that the series $$\sum _ { n } ( \rho ( A ) + \eta ) ^ { - n } \left\| A ^ { n } x \right\|$$ is convergent.
We denote $$N ( x ) = \sum _ { n = 0 } ^ { \infty } ( \rho ( A ) + \eta ) ^ { - n } \left\| A ^ { n } x \right\|$$ the sum of this series.
(b) Show that $x \mapsto N ( x )$ is a norm on $\mathbb { C } ^ { 2 }$, which satisfies the following inequality $$\forall x \in \mathbb { C } ^ { 2 } , \quad N ( A x ) \leqslant ( \rho ( A ) + \eta ) N ( x ) .$$
(c) Show that there exists a real $C > 0$ such that for all $x \in \mathbb { C } ^ { 2 }$ we have $$\| x \| \leqslant N ( x ) \leqslant C \| x \|$$

(a) If $B \in \mathrm { M } _ { \ell } ( \mathbb { C } )$ is diagonalizable, show that there exists a norm $\| \cdot \| _ { B }$ on $\mathbb { C } ^ { \ell }$ such that $\| B x \| _ { B } \leqslant \rho ( B ) \| x \| _ { B }$ for all $x \in \mathbb { C } ^ { \ell }$. Hint: one may verify that if $P \in \mathrm { GL } _ { \ell } ( \mathbb { C } )$, then $x \mapsto \| P x \|$ is a norm on $\mathbb { C } ^ { \ell }$.
(b) Show that there exists a matrix $C \in \mathrm { M } _ { 2 } ( \mathbb { C } )$ such that, for every norm $N$ on $\mathbb { C } ^ { 2 }$ there exists $y \in \mathbb { C } ^ { 2 }$ such that $N ( C y ) > \rho ( C ) N ( y )$.

Let $\phi : \mathbb { R } ^ { 2 } \rightarrow \mathbb { R } ^ { 2 }$ be a map and let $x ^ { * }$ be a fixed point of $\phi$. Let $A \in \mathrm { M } _ { 2 } ( \mathbb { R } )$ be a matrix satisfying $\rho ( A ) < 1$, and let $M > 0$ be a real number. We assume that $\phi$ satisfies $$\forall x \in \mathbb { R } ^ { 2 } , \quad \left\| \phi ( x ) - \phi \left( x ^ { * } \right) - A \left( x - x ^ { * } \right) \right\| \leqslant M \left\| x - x ^ { * } \right\| ^ { 2 }$$ Show that there exists $\varepsilon > 0$ such that for all $x _ { 0 } \in \mathbb { R } ^ { 2 }$ satisfying $\left\| x _ { 0 } - x ^ { * } \right\| < \varepsilon$, the sequence $\left( x _ { n } \right) _ { n \geqslant 0 }$ defined by $x _ { n + 1 } = \phi \left( x _ { n } \right)$ (for $n \geqslant 0$) converges to $x ^ { * }$ when $n \rightarrow + \infty$.