We consider a Markov kernel $K$. We assume that 1 is a simple eigenvalue of $K$. We assume that there exists a probability $\pi \in \mathscr{M}_{1,N}(\mathbf{R})$ such that:
(a) For all $j \in \llbracket 1;N \rrbracket$, $\pi[j] \neq 0$.
(b) $\forall (i,j) \in \llbracket 1;N \rrbracket^2$, $\pi[i] K[i,j] = K[j,i] \pi[j]$; we say that $K$ is $\pi$-reversible. Show that $\pi K = \pi$.

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]$, and the endomorphism $u : X \mapsto (I_N - K)X$ with $q_u(X) = (u(X) \mid X)$. Show that for all $X \in E$, $$q_u(X) = \frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} (X[i] - X[j])^2 K[i,j] \pi[i]$$ What can be said about the eigenvalues of $u$?

Let $J \in M_{n}(\mathbb{C})$ be the matrix defined by
$$J = \left( \begin{array}{ccccc} 0 & 1 & 0 & \ldots & 0 \\ 0 & 0 & 1 & \cdots & 0 \\ \vdots & \ddots & \ddots & \ddots & \vdots \\ \vdots & & \ddots & 0 & 1 \\ 1 & 0 & \ldots & 0 & 0 \end{array} \right).$$
Calculate the eigenvalues of $J$.

We consider $M \in \mathscr { D } _ { \rho } \left( S _ { n } ( \mathbb { R } ) \right)$ and we set $\chi = \operatorname { det } \left( X I _ { n } - M \right) \in \mathscr { D } _ { \rho } \left( \mathbb { R } _ { n } [ X ] \right)$.
Show that $M _ { \mid t = 0 }$ admits a real eigenvalue.

We consider $M \in \mathscr { D } _ { \rho } \left( S _ { n } ( \mathbb { R } ) \right)$ and we set $\chi = \operatorname { det } \left( X I _ { n } - M \right) \in \mathscr { D } _ { \rho } \left( \mathbb { R } _ { n } [ X ] \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 }$. By Theorem 1, there exists $\rho _ { 1 } \in \mathbb { R } _ { + } ^ { * }$, $\rho _ { 1 } \leqslant \rho$ such that $\chi$ factors in the form $\chi = F G$ with $F \in \mathscr { D } _ { \rho _ { 1 } } \left( \mathbb { R } _ { d } [ X ] \right)$ and $G \in \mathscr { D } _ { \rho _ { 1 } } \left( \mathbb { R } _ { n - d } [ X ] \right)$ and $F _ { \mid t = 0 } = ( X - \lambda ) ^ { d }$.
Only in this question, we assume that $d = n$. Show that there exists a symmetric matrix $M _ { 0 } \in \mathscr { D } _ { \rho _ { 1 } } \left( S _ { n } ( \mathbb { R } ) \right)$ such that $M = \lambda I _ { n } + t M _ { 0 }$ for all $t \in U _ { \rho _ { 1 } }$.

Let $\mathscr{P}$ be the set of row vectors of size $d$ with non-negative coefficients whose coordinate sum equals 1: $$\mathscr{P} = \left\{ u \in \mathscr{M}_{1,d}\left(\mathbb{R}_{+}\right) : \sum_{j=1}^{d} u_j = 1 \right\}.$$ We consider a square matrix $P \in \mathscr{M}_d\left(\mathbb{R}_{+}\right)$ such that for all $i \in \{1,\ldots,d\}$, $$\sum_{j=1}^{d} P_{i,j} = 1$$ We further assume that there exist $\nu \in \mathscr{P}$ and $c > 0$ such that for all $i,j \in \{1,\ldots,d\}$, $$P_{i,j} \geqslant c\nu_j.$$
Show that there exists a unique element $\mu$ of $\mathscr{P}$ such that $\mu P = \mu$.

We denote by $\mathbf{e}$ the matrix of $\mathcal{M}_{n,1}(\mathbb{R})$ whose coefficients are all equal to 1, $P = I_n - \frac{1}{n}\mathbf{e}\cdot\mathbf{e}^T$, and $\Delta_n$ the set of EDM of order $n$.
Specify the sum $\displaystyle\sum_{i=1}^{n} \lambda_i$ of the eigenvalues of an EDM of order $n$.

Determine the characteristic polynomial of the double star with $d _ { 1 } + d _ { 2 } + 2$ vertices, consisting respectively of two disjoint stars with $d _ { 1 }$ and $d _ { 2 }$ branches, to which an additional edge has been added connecting the two centers of the two stars. What is the rank of the adjacency matrix of this double star?

Let $u = (u_k)_{k \geqslant 0}$ be a sequence of $\mathbb{C}$ such that $\mathbb{M}_n(u) \neq \emptyset$. Let $A \in \mathbb{M}_n(u)$. Show that if $A \in \mathscr{M}_n(\mathbb{R})$ then $\varphi_A$ has real coefficients (that is, $\varphi_A \in \mathbb{R}[X]$).

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 $G \in \mathscr{M}_n(\mathbb{C})$ be the matrix defined by $$G = Y\, {}^t Z$$ where $Y, Z \in \mathscr{M}_{n,1}(\mathbb{R})$ are two column vectors such that ${}^t Y Y = {}^t Z Z = 1$.
(a) Show that $G$ has rank 1 and give its image.
(b) Show that $0$ and ${}^t Z Y$ are the only eigenvalues of $G$.
(c) Deduce that $G \in \mathbb{M}_n(u)$.
(d) Determine $\varphi_G$ when ${}^t Z Y \neq 0$.
(e) Deduce that if ${}^t Z Y \neq 0$ then $$u(G) = U(0) I_n + \frac{U({}^t Z Y) - U(0)}{{}^t Z Y} G.$$ (f) Determine a simple expression for $u(G)$ when ${}^t Z Y = 0$.

We consider $R \in \mathrm{O}_{d}(\mathbb{R})$.

• [(a)] Show that if $\lambda$ is an eigenvalue of $R$ then $\lambda \in \{+1, -1\}$.
• [(b)] Show that $\operatorname{det}(R + I) = \operatorname{det}(R) \operatorname{det}(I + R^{T})$.
• [(c)] Deduce that if $\operatorname{det}(R) = -1$ then $\operatorname{det}(R + I) = 0$.

Let $A$ be a matrix belonging to $\mathbf{GL}_n$. Suppose in this question that $A$ is similar to its inverse. Specify the values that the determinant of $A$ can take, and deduce that $\chi_A$ is either reciprocal or antireciprocal.

Let $A$ be a matrix belonging to $\mathbf{GL}_n$. We assume in this question that $A$ is similar to its inverse. Specify the values that the determinant of $A$ can take, and deduce that $\chi_A$ is either reciprocal or antireciprocal.

Prove the Schur-Cohn criterion: If $J(p)$ is invertible then $p$ has no stable root and $\sigma(p) = \pi(J(p))$.

Problem 2, Part 2: Linear recurrence sequences with constant coefficients
We consider a sequence $\left( u _ { n } \right) _ { n \geqslant 0 }$ of complex numbers defined by the data of $u _ { 0 } , \ldots , u _ { d }$ and the linear recurrence relation $$u _ { n + d } = \sum _ { i = 0 } ^ { d - 1 } a _ { i } u _ { n + i } + b ,$$ where the $a _ { i }$ and $b$ are complex numbers. We define $P \in \mathbb { C } [ X ]$ by $P ( X ) = X ^ { d } - \sum _ { i = 0 } ^ { d - 1 } a _ { i } X ^ { i }$ and we assume that all complex roots of $P$ have modulus strictly less than 1. The matrix $A \in \mathrm{M}_d(\mathbb{C})$ is as defined in question 7.
Calculate the characteristic polynomial of the matrix $A$ (one may reason by induction on $d$).

Properties of $h$ In this part, we are given: a finite-dimensional vector space $V$; a nilpotent endomorphism $u$ of $V$; a nonzero natural integer $N$ and the complex number $\zeta = \exp\frac{2\mathrm{i}\pi}{N}$; an invertible endomorphism $h$ of $V$ such that $h^N = \operatorname{id}_V$ and $h \circ u \circ h^{-1} = \zeta u$.
a) Prove that $h$ is diagonalizable.
b) Let $j$ be a natural integer strictly less than $N$. By denoting $V_j = \ker(h - \zeta^j \operatorname{id}_V)$ and $V_N = V_0$, verify that $u(V_j) \subset V_{j+1}$.
c) Calculate, for $k$ relative integer, $h^k \circ u \circ h^{-k}$ and, for $l$ natural integer, $h \circ u^l \circ h^{-1}$.

Two linear maps: decomposition We fix two nonzero natural integers $m$ and $n$, matrices $(A,B) \in \mathcal{M}_{n,m}(\mathbb{C}) \times \mathcal{M}_{m,n}(\mathbb{C})$, and denote $M = M_{A,B} = \begin{pmatrix} 0_m & B \\ A & 0_n \end{pmatrix}$ and $H = \begin{pmatrix} \mathrm{I}_m & 0_{m,n} \\ 0_{n,m} & -\mathrm{I}_n \end{pmatrix}$.
a) Calculate $H^2$, $HMH^{-1}$ and, for a polynomial $P$ of $\mathbb{C}[X]$, calculate $HP(M)H^{-1}$.
b) Prove that if a complex number $\lambda$ is an eigenvalue of $M$, then $-\lambda$ is also an eigenvalue of $M$ with the same multiplicity.
c) Let $\chi_M$ be the characteristic polynomial of $M$. We write it as $\chi_M = X^r Q$ where $r$ is an integer and $Q$ is a polynomial whose constant coefficient is nonzero. Briefly justify that $$\mathbb{C}^{m+n} = \ker M^r \oplus \ker Q(M)$$ and verify that these subspaces are stable under $H$.

Let $\lambda$ be an eigenvalue of $A$ with multiplicity $m \geqslant 2$. We set $E = \operatorname{Ker}\left(A - \lambda \mathbb{I}_n\right)$.
(a) Show that $\operatorname{dim}\left(E \cap \{\mathbf{u}\}^\perp\right) \geqslant m - 1$.
(b) Deduce that $\lambda$ is an eigenvalue of $B$ with multiplicity at least $m - 1$.

Let $J = \left\{k \in \{1, 2, \ldots, n\}, \left\langle \mathbf{w}_k, \mathbf{u} \right\rangle \neq 0\right\}$ be the set of indices $k$ such that $\left\langle \mathbf{w}_k, \mathbf{u} \right\rangle \neq 0$.
(a) Show that $J \neq \varnothing$.
(b) Let $\ell \notin J$. Show that $\lambda_\ell$ is an eigenvalue of $B$.
(c) Suppose that $J = \{j\}$ for some $j \in \{1, 2, \ldots, n\}$. Show that the eigenvalues of $B$ are $$\left(\lambda_1, \lambda_2, \ldots, \lambda_{j-1}, \lambda_j + 1, \lambda_{j+1}, \ldots, \lambda_n\right).$$

Suppose in this question that $\lambda_1 < \lambda_2 < \cdots < \lambda_n$, and that $J = \{1, 2, \ldots, n\}$. For $x \in \mathbb{R} \backslash \left\{\lambda_1, \ldots, \lambda_n\right\}$ we set $$f(x) = \sum_{k=1}^n \frac{\left\langle \mathbf{w}_k, \mathbf{u} \right\rangle^2}{x - \lambda_k}$$ (a) Show that $f$ is of class $C^\infty$ on $\mathbb{R} \backslash \left\{\lambda_1, \ldots, \lambda_n\right\}$, and calculate its derivative $f'(x)$.
(b) Show that the equation $f(x) = 1$ has a unique solution in each interval $]\lambda_\ell, \lambda_{\ell+1}[$ for all $\ell \in \{1, 2, \ldots, n-1\}$, and in $]\lambda_n, +\infty[$.
(c) We denote by $\mu_1 \leqslant \mu_2 \leqslant \cdots \leqslant \mu_n$ the eigenvalues of $B$. Show that $$\lambda_1 < \mu_1 < \lambda_2 < \mu_2 < \cdots < \lambda_n < \mu_n$$

We denote by $\lambda_{\text{max}}$ the largest of the eigenvalues of $J_n$ and $\lambda_{\text{min}}$ the smallest. Show that $$\forall x \in \Lambda_n, \quad n\lambda_{\min} \leqslant \sum_{1 \leqslant i,j \leqslant n} J_n(i,j) x_i x_j \leqslant n\lambda_{\max}$$

We denote by $J_n^{(\mathrm{C})}$ the matrix of $\mathcal{M}_n(\mathbb{R})$ whose coefficients all equal $\frac{1}{n}$, except for its diagonal coefficients, which are zero. Each particle thus interacts in the same way with all other particles.
Determine the spectrum of $U_n = nJ_n^{(\mathrm{C})} + I_n$, then that of $J_n^{(\mathrm{C})}$.

We set $N = n^2$ and $$J_N^{(2)} = I_n \otimes J_n^{(1)} + J_n^{(1)} \otimes I_n \in \mathcal{M}_N(\mathbb{R})$$
Show that the eigenvalues of $J_N^{(2)}$ are the $\lambda_j + \lambda_k$, for $(j,k) \in \llbracket 1,n \rrbracket^2$.

We consider $A \in \mathcal{S}_n(\mathbb{R})$ symmetric with $B = A + \mathbf{u u}^T$ where $\|\mathbf{u}\| = 1$. Let $\lambda$ be an eigenvalue of $A$ with multiplicity $m \geqslant 2$. We set $E = \operatorname{Ker}\left(A - \lambda \mathbb{I}_n\right)$.
(a) Show that $\operatorname{dim}\left(E \cap \{\mathbf{u}\}^\perp\right) \geqslant m - 1$.
(b) Deduce that $\lambda$ is an eigenvalue of $B$ with multiplicity at least $m - 1$.

We consider $A \in \mathcal{S}_n(\mathbb{R})$ symmetric with eigenvalues $\lambda_1 \leqslant \cdots \leqslant \lambda_n$ and corresponding orthonormal basis of eigenvectors $\left(\mathbf{w}_1, \ldots, \mathbf{w}_n\right)$. We set $B = A + \mathbf{u u}^T$ with $\|\mathbf{u}\| = 1$. Let $J = \left\{k \in \{1,2,\ldots,n\}, \left\langle \mathbf{w}_k, \mathbf{u} \right\rangle \neq 0\right\}$ be the set of indices $k$ such that $\left\langle \mathbf{w}_k, \mathbf{u} \right\rangle \neq 0$.
(a) Show that $J \neq \varnothing$.
(b) Let $\ell \notin J$. Show that $\lambda_\ell$ is an eigenvalue of $B$.
(c) Suppose that $J = \{j\}$ for some $j \in \{1,2,\ldots,n\}$. Show that the eigenvalues of $B$ are $$\left(\lambda_1, \lambda_2, \ldots, \lambda_{j-1}, \lambda_j + 1, \lambda_{j+1}, \ldots, \lambda_n\right).$$