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.

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$.

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}$. We consider $n+1$ distinct points in $I$, denoted $x_0 < x_1 < \cdots < x_n$, and a continuous function $f$ from $I$ to $\mathbb{R}$.
Show that the linear map $\varphi : \left|\,\begin{array}{ccl} \mathbb{R}_n[X] & \rightarrow & \mathbb{R}^{n+1} \\ P & \mapsto & \left(P(x_0), P(x_1), \ldots, P(x_n)\right) \end{array}\right.$ is an isomorphism.

In this part, $E$ denotes a $\mathbf{C}$-vector space of dimension $n$ and $u$ denotes an endomorphism of $E$. We assume that $u$ is diagonalizable. We denote by $\mathcal{B} = (v_{1}, v_{2}, \ldots, v_{n})$ a basis of $E$ formed of eigenvectors of $u$. Let $F$ be a vector subspace of $E$, different from $\{0_{E}\}$ and from $E$.
We denote $$\mathcal{A} = \left\{H \text{ vector subspace of } E \text{ such that } u(H) \subset H \text{ and } F \cap H = \{0_{E}\}\right\}$$ and $$\mathcal{L} = \left\{p \in \mathbf{N}^{*} \mid \exists H \in \mathcal{A} : p = \operatorname{dim}(H)\right\}$$
Prove that $\mathcal{L}$ has a greatest element which we call $r$.

In this part, $E$ denotes a $\mathbf{C}$-vector space of dimension $n$ and $u$ denotes an endomorphism of $E$. We assume that $u$ is diagonalizable. We denote by $\mathcal{B} = (v_{1}, v_{2}, \ldots, v_{n})$ a basis of $E$ formed of eigenvectors of $u$. Let $F$ be a vector subspace of $E$, different from $\{0_{E}\}$ and from $E$.
We denote $$\mathcal{A} = \left\{H \text{ vector subspace of } E \text{ such that } u(H) \subset H \text{ and } F \cap H = \{0_{E}\}\right\}$$ and $$\mathcal{L} = \left\{p \in \mathbf{N}^{*} \mid \exists H \in \mathcal{A} : p = \operatorname{dim}(H)\right\}$$
Prove that $F$ has a complement $G$ in $E$, stable under $u$.

Let $p \in \llbracket 1, d \rrbracket$. We define a relation on the set of bases of a subspace $V$ of dimension $p$ of $E$ by: $e$ and $e^{\prime}$ are in relation if $\det_e(e^{\prime}) > 0$ where $\det_e(e^{\prime})$ is the determinant of $e^{\prime}$ in the basis $e$. We admit that this relation is an equivalence relation on the set of bases of $V$ for which there exist exactly two equivalence classes called orientations of $V$. An oriented subspace is a pair $(V, C)$ where $C$ is an orientation of $V$.
We denote by $\widetilde{\operatorname{Gr}}(p, E)$ the set of oriented subspaces of dimension $p$ of $E$.
(a) Show that if $e$ and $e^{\prime}$ are two free families of cardinal $p$ of $E$ then $\Omega_p(e)$ and $\Omega_p(e^{\prime})$ are collinear if and only if $\operatorname{Vect}(e) = \operatorname{Vect}(e^{\prime})$.
(b) Show that for all oriented vector subspace $(V, C)$ of dimension $p$ of $E$, there exists a unique $\Psi(V, C) \in \mathcal{A}_p(E, \mathbb{R})$ such that for all $e \in C$ we have $\Omega_p(e) = \operatorname{vol}_p(e) \Psi(V, C)$.

Let $M \in \mathcal{M}_{k \times d}(\mathbb{R})$ with $\operatorname{rank}(M) = k$, $b \in \mathbb{R}^k \backslash \{0\}$, and fix $\bar{x} \in C$ where $C := \{x \in \mathbb{R}^d : Mx = b, \|x\|_1 = r\}$. Let $K$ be as defined in question 24. Show that if $y \in \operatorname{Ext}(K)$ then $$h \in \operatorname{Ker}(M) \text{ and } I_0(y) \subset I_0(h) \Rightarrow h = 0.$$

With the notation of questions 23 and 24, show that if $y \in \operatorname{Ext}(K)$ then $$h \in \operatorname{Ker}(M) \text{ and } I_0(y) \subset I_0(h) \Rightarrow h = 0.$$

For $\ell \in \mathcal { L } ( E , \mathbb { R } )$, we denote by $\left. \ell \right| _ { F }$ the restriction of $\ell$ to $F$. The restriction map is $r _ { F } : \mathcal { L } ( E , \mathbb { R } ) \rightarrow \mathcal { L } ( F , \mathbb { R } )$, $\ell \mapsto \left. \ell \right| _ { F }$, and $d_{\omega} : E \rightarrow \mathcal{L}(E,\mathbb{R})$, $x \mapsto \omega(x,\cdot)$. The $\omega$-orthogonal is $F ^ { \omega } = \{ x \in E \mid \forall y \in F , \omega ( x , y ) = 0 \}$.
Specify the kernel of $r _ { F } \circ d _ { \omega }$. Deduce that $\operatorname { dim } F ^ { \omega } = \operatorname { dim } E - \operatorname { dim } F$.

Let $A$ be a real antisymmetric and nilpotent matrix. Show that $A ^ { \top } A = 0 _ { n }$, then that $A = 0 _ { n }$.

Let $\left( E _ { 1 } , \ldots , E _ { n } \right)$ be the canonical basis of $\mathcal { M } _ { n , 1 } ( \mathbb { R } )$. We denote $V = \sum _ { k = 1 } ^ { n } E _ { k }$.
For $i \in \llbracket 1 , n \rrbracket$, express $E _ { i }$ in terms of $V$ and of $V - 2 E _ { i }$. Deduce that $\mathcal { M } _ { n , 1 } ( \mathbb { R } ) = \operatorname { Vect } \left( \mathcal { V } _ { n , 1 } \right)$.

The bilinear form $B$ is defined by $$B:\left(\begin{pmatrix}x\\y\\z\end{pmatrix},\begin{pmatrix}x'\\y'\\z'\end{pmatrix}\right)\mapsto 3xx'+3yy'-zz'.$$ Given a vector $v\in V$, the pseudo-orthogonal of $v$ is $v^\perp = \{w\in V \mid B(v,w)=0\}$.
Let $v$ be a non-zero vector of $V$. Show that $v^\perp$ is a vector subspace of $V$ of codimension 1, and that $v^\perp$ is a complement of the line generated by $v$ if and only if $B(v,v)\neq 0$.

In this part, $a$ denotes an endomorphism of $\mathbf { C } ^ { n }$. We use the decomposition $\mathbf { C } ^ { n } = \bigoplus _ { i = 1 } ^ { r } E _ { i }$ where $E _ { i } = \operatorname { Ker } \left( a - \lambda _ { i } id _ { \mathbf { C } ^ { n } } \right) ^ { m _ { i } }$, with the projections $p_i$ and inclusions $q_i$ as defined.
Let $( i , j ) \in \llbracket 1 ; r \rrbracket ^ { 2 }$. Express $p _ { i } q _ { j }$ and then $\sum _ { i = 1 } ^ { r } q _ { i } p _ { i }$ in terms of the endomorphisms $id _ { \mathbf { C } ^ { n } }$ and $id _ { E _ { j } }$.

In this part, $a$ denotes an endomorphism of $\mathbf { C } ^ { n }$. We use the decomposition $\mathbf { C } ^ { n } = \bigoplus _ { i = 1 } ^ { r } E _ { i }$ where $E _ { i } = \operatorname { Ker } \left( a - \lambda _ { i } id _ { \mathbf { C } ^ { n } } \right) ^ { m _ { i } }$, with the projections $p_i$, inclusions $q_i$, and $a_i = p_i a q_i$ the endomorphism of $E_i$.
Show that: $a = \sum _ { i = 1 } ^ { r } q _ { i } a _ { i } p _ { i }$.

We consider the Euclidean space $E = \mathscr{M}_{N,1}(\mathbf{R})$ equipped with the inner product $\langle X, Y \rangle = \sum_{i=1}^{N} X[i] Y[i] \pi[i]$, where $\pi$ is a $\pi$-reversible probability for the Markov kernel $K$. We consider the endomorphism of $E$ defined by $u : X \mapsto (I_N - K)X$. Show that $\ker(u) = \operatorname{Vect}(U)$ and that $u$ is a self-adjoint endomorphism of $E$.

We consider $M \in \mathscr { D } _ { \rho } \left( S _ { n } ( \mathbb { R } ) \right)$. We fix a real eigenvalue $\lambda$ of $M _ { \mid t = 0 }$ and denote by $d$ its multiplicity as a root of $\chi _ { \mid t = 0 }$ where $\chi = \det(XI_n - M)$. We set $A = F ( M )$ and $B = G ( M )$; we thus have $A , B \in \mathscr { D } _ { \rho _ { 1 } } \left( S _ { n } ( \mathbb { R } ) \right)$. For $a \in U _ { \rho _ { 1 } }$, we set $A _ { a } = A _ { \mid t = a }$ and $B _ { a } = B _ { \mid t = a }$.
Show that there exist two matrices $U \in \mathscr { M } _ { n , d } ( \mathbb { R } )$ and $V \in \mathscr { M } _ { n , n - d } ( \mathbb { R } )$ such that:

• $\operatorname { im } \left( B _ { 0 } U \right) = \operatorname { im } \left( B _ { 0 } \right)$,
• $\operatorname { im } \left( A _ { 0 } V \right) = \operatorname { im } \left( A _ { 0 } \right)$ and
• the block matrix $\left( B _ { 0 } U \mid A _ { 0 } V \right)$ is invertible.

We consider $M \in \mathscr { D } _ { \rho } \left( S _ { n } ( \mathbb { R } ) \right)$. We fix a real eigenvalue $\lambda$ of $M _ { \mid t = 0 }$ and denote by $d$ its multiplicity as a root of $\chi _ { \mid t = 0 }$ where $\chi = \det(XI_n - M)$. We set $A = F ( M )$, $B = G ( M )$, $Q = ( B U \mid A V ) \in \mathscr { D } _ { \rho _ { 2 } } \left( \mathscr { M } _ { n } ( \mathbb { R } ) \right)$. For $a \in U _ { \rho _ { 2 } }$, we set $A _ { a } = A _ { \mid t = a }$ and $B _ { a } = B _ { \mid t = a }$. We consider a real number $a \in U _ { \rho _ { 2 } }$.
22a. Show that $\operatorname { im } \left( B _ { a } U \right) \oplus \operatorname { im } \left( A _ { a } V \right) = \mathbb { R } ^ { n }$.
22b. Show the equalities:

• $\operatorname { im } \left( B _ { a } U \right) = \operatorname { im } \left( B _ { a } \right) = \operatorname { ker } \left( A _ { a } \right)$ and
• $\operatorname { im } \left( A _ { a } V \right) = \operatorname { im } \left( A _ { a } \right) = \operatorname { ker } \left( B _ { a } \right)$.

(One may begin by showing the inclusions from left to right, then use a dimension argument.)

We consider $M \in \mathscr { D } _ { \rho } \left( S _ { n } ( \mathbb { R } ) \right)$. We fix a real eigenvalue $\lambda$ of $M _ { \mid t = 0 }$ and denote by $d$ its multiplicity as a root of $\chi _ { \mid t = 0 }$ where $\chi = \det(XI_n - M)$. We set $A = F ( M )$, $B = G ( M )$, $Q = ( B U \mid A V ) \in \mathscr { D } _ { \rho _ { 2 } } \left( \mathscr { M } _ { n } ( \mathbb { R } ) \right)$.
Show that $Q ^ { - 1 } \cdot M \cdot Q = \operatorname { Diag } \left( M _ { 1 } , M _ { 2 } \right)$ with $M _ { 1 } \in \mathscr { D } _ { \rho _ { 2 } } \left( \mathscr { M } _ { d } ( \mathbb { R } ) \right) , M _ { 2 } \in \mathscr { D } _ { \rho _ { 2 } } \left( \mathscr { M } _ { n - d } ( \mathbb { R } ) \right)$.

Let $f$ be a symmetric endomorphism of $\mathbf{R}^n$ with eigenvalues $\lambda_1 \leqslant \ldots \leqslant \lambda_n$ and associated orthonormal eigenbasis $(e_1, \ldots, e_n)$.
Let $k \in \llbracket 1, n \rrbracket$ and $S_k$ a vector subspace of $\mathbf{R}^n$ of dimension $k$. We set $T_k = \operatorname{Vect}(e_k, \ldots, e_n)$.
Justify that $S_k \cap T_k \neq \{0\}$.

Show that $\mathbb{M}_n(u) \neq \{0_n\}$.

In this part, we assume that $n \geqslant 4$. Let $u = (u_k)_{k \geqslant 0}$ be a sequence of $\mathbb{C}$ satisfying the condition $(C^\star)$: $R_u > 1$.
Let $H \in \mathscr{M}_n(\mathbb{C})$ be the matrix given by $$H = \begin{pmatrix} 0 & 1 & 0 & \cdots & 0 \\ 0 & 0 & 1 & \ddots & \vdots \\ \vdots & \ddots & \ddots & \ddots & 0 \\ \vdots & & \ddots & \ddots & 1 \\ 0 & \cdots & \cdots & 0 & 0 \end{pmatrix}.$$
(a) Determine the polynomial $\varphi_H$ in this case.
(b) Let $A = H + \alpha I_n$ where $\alpha \in \mathbb{C}$ is such that $|\alpha| < R_u$. Show that $$u(A) = \sum_{k=0}^{n-1} \frac{U^{(k)}(\alpha)}{k!} H^k$$ and deduce that $$u(A) = \begin{pmatrix} U(\alpha) & \frac{U^{(1)}(\alpha)}{1!} & \frac{U^{(2)}(\alpha)}{2!} & \cdots & \frac{U^{(n-1)}(\alpha)}{(n-1)!} \\ 0 & U(\alpha) & \frac{U^{(1)}(\alpha)}{1!} & \ddots & \vdots \\ \vdots & \ddots & \ddots & \ddots & \frac{U^{(2)}(\alpha)}{2!} \\ \vdots & & \ddots & \ddots & \frac{U^{(1)}(\alpha)}{1!} \\ 0 & \cdots & \cdots & 0 & U(\alpha) \end{pmatrix}.$$

Let $m \in \mathbb{N}$. We consider the matrix $$M = \left(\begin{array}{cccccc} \binom{0}{0} & 0 & \cdots & \cdots & \cdots & 0 \\ \binom{1}{0} & \binom{1}{1} & 0 & & & \vdots \\ \vdots & & \ddots & \ddots & & \vdots \\ \vdots & & & \ddots & \ddots & \vdots \\ \binom{m-1}{0} & & & & \binom{m-1}{m-1} & 0 \\ \binom{m}{0} & \cdots & \cdots & \cdots & \cdots & \binom{m}{m} \end{array}\right) \in \mathscr{M}_{m+1}(\mathbb{R}).$$ Justify that the families $\left(1, X, \ldots, X^{m}\right)$ and $\left(1, (X-1), \ldots, (X-1)^{m}\right)$ are bases of $\mathbb{R}_{m}[X]$.

Let $m \in \mathbb{N}$. We consider the matrix $$M = \left(\begin{array}{cccccc} \binom{0}{0} & 0 & \cdots & \cdots & \cdots & 0 \\ \binom{1}{0} & \binom{1}{1} & 0 & & & \vdots \\ \vdots & & \ddots & \ddots & & \vdots \\ \vdots & & & \ddots & \ddots & \vdots \\ \binom{m-1}{0} & & & & \binom{m-1}{m-1} & 0 \\ \binom{m}{0} & \cdots & \cdots & \cdots & \cdots & \binom{m}{m} \end{array}\right) \in \mathscr{M}_{m+1}(\mathbb{R}).$$ Show that the transpose of $M$ is the matrix of the linear map identity $$\begin{array}{ccc} \mathbb{R}_{m}[X] & \longrightarrow & \mathbb{R}_{m}[X] \\ P & \longmapsto & P \end{array}$$ in the bases $\left(1, X, \ldots, X^{m}\right)$ at the start and $\left(1, (X-1), \ldots, (X-1)^{m}\right)$ at the end.