For every polynomial $P = P(X) \in \mathbf{C}_{n-1}[X]$ we set $$\left\{\begin{array}{l} s_1(P) = P(-X) \\ s_2(P) = P(1-X) \\ g(P) = P(X+1) - P(X) \end{array}\right.$$ We thus define three endomorphisms of the vector space $\mathbf{C}_{n-1}[X]$. Calculate $s_1^2$, $s_2^2$ and express $s_1 \circ s_2$ in terms of $g$ and $Id_{\mathbf{C}_{n-1}[X]}$.

We want to show that for every matrix $M \in S_n(\mathbf{R})$ we have $\pi(M) = d(M)$. By contradiction, assuming the existence of a vector subspace $G$ of $\mathcal{M}_{n,1}(\mathbf{R})$ of dimension $\dim G > \pi(M)$ satisfying condition $(\mathcal{C}_M)$, show $\dim(F_M^\perp \cap G) \geq 1$, deduce a contradiction and conclude.

Two linear maps: nilpotent case 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}$. In this question, we assume that $M$ is nilpotent.
Prove that $(M, H)$ is simultaneously similar to a pair of block diagonal matrices whose diagonal blocks are respectively of the form $$\begin{pmatrix} 0_r & B_0 \\ A_0 & 0_s \end{pmatrix} \quad \text{and} \quad \begin{pmatrix} \mathrm{I}_r & 0 \\ 0 & -\mathrm{I}_s \end{pmatrix},$$ where $r$ and $s$ are natural integers with $|r - s| \leqslant 1$ and $A_0$ and $B_0$ form one of the following pairs: $$A_0 = \begin{pmatrix} 1 & 0 & \cdots & 0 & 0 \\ 0 & \ddots & \ddots & \vdots & \vdots \\ \vdots & \ddots & \ddots & 0 & \vdots \\ 0 & \cdots & 0 & 1 & 0 \end{pmatrix}_{s \times (s+1)} \quad \text{and} \quad B_0 = \begin{pmatrix} 0 & \cdots & \cdots & 0 \\ 1 & \ddots & & \vdots \\ 0 & \ddots & \ddots & \vdots \\ \vdots & \ddots & \ddots & 0 \\ 0 & \cdots & 0 & 1 \end{pmatrix}_{(s+1) \times s};$$ $$A_0 = \mathrm{I}_r \quad \text{and} \quad B_0 = J_r;$$ $$A_0 = J_r \quad \text{and} \quad B_0 = \mathrm{I}_r;$$ $$A_0 = \begin{pmatrix} 0 & \cdots & \cdots & 0 \\ 1 & \ddots & & \vdots \\ 0 & \ddots & \ddots & \vdots \\ \vdots & \ddots & \ddots & 0 \\ 0 & \cdots & 0 & 1 \end{pmatrix}_{(r+1) \times r} \quad \text{and} \quad B_0 = \begin{pmatrix} 1 & 0 & \cdots & 0 & 0 \\ 0 & \ddots & \ddots & \vdots & \vdots \\ \vdots & \ddots & \ddots & 0 & \vdots \\ 0 & \cdots & 0 & 1 & 0 \end{pmatrix}_{r \times (r+1)}.$$

We denote by $\chi_A(x) = \operatorname{det}\left(x \mathbb{I}_n - A\right)$ the characteristic polynomial of $A$, and $\chi_B(x) = \operatorname{det}\left(x \mathbb{I}_n - B\right)$ that of $B$. Show that, for all $x \in \mathbb{R} \backslash \left\{\lambda_1, \ldots, \lambda_n\right\}$, we have $$\chi_B(x) = \chi_A(x)\left(1 - \sum_{k=1}^n \frac{\left\langle \mathbf{w}_k, \mathbf{u} \right\rangle^2}{x - \lambda_k}\right).$$

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 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$. We denote by $\chi_A(x) = \operatorname{det}\left(x \mathbb{I}_n - A\right)$ the characteristic polynomial of $A$, and $\chi_B(x) = \operatorname{det}\left(x \mathbb{I}_n - B\right)$ that of $B$. Show that, for all $x \in \mathbb{R} \backslash \left\{\lambda_1, \ldots, \lambda_n\right\}$, we have $$\chi_B(x) = \chi_A(x)\left(1 - \sum_{k=1}^n \frac{\left\langle \mathbf{w}_k, \mathbf{u} \right\rangle^2}{x - \lambda_k}\right).$$

For every polynomial $P = P(X) \in \mathbf{C}_{n-1}[X]$ we set $$g(P) = P(X+1) - P(X)$$
Let $P$ be a non-constant polynomial. Express the degree of the polynomial $g(P)$ in terms of the degree of $P$.

For every polynomial $P = P(X) \in \mathbf{C}_{n-1}[X]$ we set $$g(P) = P(X+1) - P(X)$$ Let $P$ be a non-constant polynomial. Express the degree of the polynomial $g(P)$ in terms of the degree of $P$.

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

Two linear maps: invertible case 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}$. In this question, we assume that $M$ is invertible.
a) Prove that $m = n$ and that $A$ and $B$ are invertible.
b) Prove that $(M, H)$ is simultaneously similar to a pair of block diagonal matrices whose diagonal blocks are of even size and are respectively of the form $$\begin{pmatrix} 0_r & B_1 \\ A_1 & 0_r \end{pmatrix} \quad \text{and} \quad \begin{pmatrix} \mathrm{I}_r & 0_r \\ 0_r & -\mathrm{I}_r \end{pmatrix},$$ where $A_1 = \mathrm{I}_r$ and $B_1 = \lambda \mathrm{I}_r + J_r$ for $r$ nonzero integer and $\lambda$ nonzero complex suitable.

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

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

For every polynomial $P = P(X) \in \mathbf{C}_{n-1}[X]$ we set $$\left\{\begin{array}{l} s_1(P) = P(-X) \\ s_2(P) = P(1-X) \\ g(P) = P(X+1) - P(X) \end{array}\right.$$ For every $\lambda \in \mathbb{C}$ nonzero, $J_n(\lambda) = \lambda I_n + N$ where $N = (n_{i,j})_{1 \leq i,j \leq n}$ with $n_{i,j} = 1$ if $j = i+1$ and $n_{i,j} = 0$ otherwise.
Deduce from the previous questions that the matrix $J_n(1)$ is a product of two symmetry matrices.

For every polynomial $P = P(X) \in \mathbf{C}_{n-1}[X]$ we set $$\left\{\begin{array}{l} s_1(P) = P(-X) \\ s_2(P) = P(1-X) \\ g(P) = P(X+1) - P(X) \end{array}\right.$$ For every $\lambda \in \mathbf{C}$ nonzero, $J_n(\lambda) = \lambda I_n + N$ where $N = (n_{i,j})_{1 \leq i,j \leq n}$ with $n_{i,j} = 1$ if $j = i+1$ and $n_{i,j} = 0$ otherwise. Deduce from the previous questions that the matrix $J_n(1)$ is a product of two symmetry matrices.

Show, using questions 9 and 13, that if $p$ has no stable root and if $J(p)$ is not invertible then there exists a non-zero polynomial $q$ with real coefficients of degree at most $n-1$ such that $q(S^\top) U = 0_{n,1}$.

In this subsection, we assume that $J_n = J_n^{(1)}$, the matrix introduced in subsection A-IV. We adopt the following convention: for all $x = (x_1, \ldots, x_n) \in \Lambda_n$, we denote $x_{n+1} = x_1$ and $x_0 = x_n$.
Verify that $$Z_n(h) = \sum_{x \in \Lambda_n} \prod_{i=1}^n \mathrm{e}^{\beta x_i x_{i+1} + h x_i}$$

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

Let $A$ be a matrix of $\mathbf{GL}_n$ similar to its inverse. We admit that $A$ is similar to a block diagonal matrix of the form $$A' = \left(\begin{array}{cccc} J_{n_1}(\lambda_1) & 0 & \cdots & 0 \\ 0 & J_{n_2}(\lambda_2) & \ddots & \vdots \\ \vdots & \ddots & \ddots & 0 \\ 0 & \cdots & 0 & J_{n_r}(\lambda_r) \end{array}\right)$$ where the $\lambda_i$ are the eigenvalues of $A$ (not necessarily distinct) and $r$ as well as the $n_i$, $1 \leq i \leq r$, are nonzero natural integers. Moreover the matrix $A'$ is unique up to the order of the blocks.
Prove that $A^{-1}$ is similar to $\left(\begin{array}{cccc} J_{n_1}\left(\frac{1}{\lambda_1}\right) & 0 & \cdots & 0 \\ 0 & J_{n_2}\left(\frac{1}{\lambda_2}\right) & \ddots & \vdots \\ \vdots & \ddots & \ddots & 0 \\ 0 & \cdots & 0 & J_{n_r}\left(\frac{1}{\lambda_r}\right) \end{array}\right)$.

Let $A$ be a matrix of $\mathbf{GL}_n$ similar to its inverse. We admit that $A$ is similar to a block diagonal matrix of the form $$A' = \left(\begin{array}{cccc} J_{n_1}(\lambda_1) & 0 & \ldots & 0 \\ 0 & J_{n_2}(\lambda_2) & \ddots & \vdots \\ \vdots & \ddots & \ddots & 0 \\ 0 & \ldots & 0 & J_{n_r}(\lambda_r) \end{array}\right)$$ where the $\lambda_i$ are the eigenvalues of $A$ (not necessarily distinct) and $r$ as well as the $n_i$, $1 \leq i \leq r$, are nonzero natural integers. Moreover the matrix $A'$ is unique up to the order of the blocks. Prove that $A^{-1}$ is similar to $\left(\begin{array}{cccc} J_{n_1}\left(\frac{1}{\lambda_1}\right) & 0 & \cdots & 0 \\ 0 & J_{n_2}\left(\frac{1}{\lambda_2}\right) & \ddots & \vdots \\ \vdots & \ddots & \ddots & 0 \\ 0 & \cdots & 0 & J_{n_r}\left(\frac{1}{\lambda_r}\right) \end{array}\right)$.

Deduce that the matrix $J(p)$ is invertible if and only if $p$ has no stable root.

Show that, for all natural integers $p$ and $q$ greater than or equal to 2, for any matrix $M = (M(i,j))_{1 \leqslant i,j \leqslant q} \in \mathcal{M}_q(\mathbb{R})$ and for all $(i,j) \in \llbracket 1,q \rrbracket^2$, the coefficient with index $(i,j)$ of the matrix $M^p$ is $$\sum_{(k_2,\ldots,k_p) \in \llbracket 1,q \rrbracket^{p-1}} M(i,k_2)\left(\prod_{r=2}^{p-1} M(k_r, k_{r+1})\right) M(k_p, j),$$ the product being equal to 1 in the case where $p = 2$.

In this part, we assume that $n$ is a power of 2: we write $n = 2 ^ { k }$ with $k \in \mathbf { N } ^ { \star }$. Deduce that there exists a vector subspace $F$ of dimension $k$ of $\mathbf { R } ^ { n }$ such that: $$\forall x \in F , \quad \alpha _ { 1 } \sqrt { n } \| x \| _ { 2 } ^ { \mathbf { R } ^ { n } } \leq \| x \| _ { 1 } ^ { \mathbf { R } ^ { n } } \leq \beta _ { 1 } \sqrt { n } \| x \| _ { 2 } ^ { \mathbf { R } ^ { n } } .$$ By ordering the $n$ elements of $\{ - 1,1 \} ^ { k }$ arbitrarily, you may use the map $T$ defined on $\mathbf { R } ^ { k }$ by $T \left( a _ { 1 } , \ldots , a _ { k } \right) = \left( \sum _ { i = 1 } ^ { k } a _ { i } \varepsilon _ { i } \right) _ { \left( \varepsilon _ { 1 } , \ldots , \varepsilon _ { k } \right) \in \{ - 1,1 \} ^ { k } }$.

Let $A$ be a matrix of $\mathbf{GL}_n$ similar to its inverse. We admit that $A$ is similar to a block diagonal matrix of the form $$A' = \left(\begin{array}{cccc} J_{n_1}(\lambda_1) & 0 & \cdots & 0 \\ 0 & J_{n_2}(\lambda_2) & \ddots & \vdots \\ \vdots & \ddots & \ddots & 0 \\ 0 & \cdots & 0 & J_{n_r}(\lambda_r) \end{array}\right)$$ where the $\lambda_i$ are the eigenvalues of $A$ (not necessarily distinct) and $r$ as well as the $n_i$, $1 \leq i \leq r$, are nonzero natural integers. Moreover the matrix $A'$ is unique up to the order of the blocks. One may also use that $J_n(-1)$ is a product of two symmetry matrices.
Using the results established in the previous parts, prove that $A$ is a product of two symmetry matrices.

Let $A$ be a matrix of $\mathbf{GL}_n$ similar to its inverse. We admit that $A$ is similar to a block diagonal matrix of the form $$A' = \left(\begin{array}{cccc} J_{n_1}(\lambda_1) & 0 & \ldots & 0 \\ 0 & J_{n_2}(\lambda_2) & \ddots & \vdots \\ \vdots & \ddots & \ddots & 0 \\ 0 & \ldots & 0 & J_{n_r}(\lambda_r) \end{array}\right)$$ where the $\lambda_i$ are the eigenvalues of $A$ (not necessarily distinct) and $r$ as well as the $n_i$, $1 \leq i \leq r$, are nonzero natural integers. Moreover the matrix $A'$ is unique up to the order of the blocks. Using the results established in the previous parts, prove that $A$ is a product of two symmetry matrices.

We assume in this part that all roots of $p$ are stable and have multiplicity 1 and we denote by $h = Xp'$ (where $p'$ is the derivative polynomial of $p$) and $h_0$ the reciprocal polynomial of $h$. We recall that, according to question 3, there exists a real number $\lambda \in \{-1, 1\}$ such that $p = \lambda p_0$.
Show that $J(h)$ is invertible.