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})$$
Verify that, in the case where $n = 3$, $J_N^{(2)}$ is the matrix such that, for all $(i,j) \in \llbracket 1,9 \rrbracket^2$, the coefficient with index $(i,j)$ equals 1 if the vertices $i$ and $j$ of the graph are connected by an edge (the edges count whether they are dashed or solid), and equals 0 otherwise.

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

Calculate $H^2$, $HMH^{-1}$ and, for a polynomial $P$ of $\mathbb{C}[X]$, calculate $HP(M)H^{-1}$.

Prove that if a complex number $\lambda$ is an eigenvalue of $M$, then $-\lambda$ is also an eigenvalue of $M$ with the same multiplicity.

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

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 $\mathbb{C}_{n-1}[X]$.
Calculate $s_1^2$, $s_2^2$ and express $s_1 \circ s_2$ in terms of $g$ and $Id_{\mathbb{C}_{n-1}[X]}$.

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

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 $$\left(\begin{array}{cc} 0_r & B_0 \\ A_0 & 0_s \end{array}\right) \quad \text{and} \quad \left(\begin{array}{cc} \mathrm{I}_r & 0 \\ 0 & -\mathrm{I}_s \end{array}\right),$$ 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 = \left(\begin{array}{ccccc} 1 & 0 & \cdots & 0 & 0 \\ 0 & \ddots & \ddots & \vdots & \vdots \\ \vdots & \ddots & \ddots & 0 & \vdots \\ 0 & \cdots & 0 & 1 & 0 \end{array}\right)_{s \times (s+1)} \quad \text{and} \quad B_0 = \left(\begin{array}{ccccc} 0 & \cdots & \cdots & 0 \\ 1 & \ddots & & \vdots \\ 0 & \ddots & \ddots & \vdots \\ \vdots & \ddots & \ddots & 0 \\ 0 & \cdots & 0 & 1 \end{array}\right)_{(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 = \left(\begin{array}{cccc} 0 & \cdots & \cdots & 0 \\ 1 & \ddots & & \vdots \\ 0 & \ddots & \ddots & \vdots \\ \vdots & \ddots & \ddots & 0 \\ 0 & \cdots & 0 & 1 \end{array}\right)_{(r+1) \times r} \quad \text{and} \quad B_0 = \left(\begin{array}{ccccc} 1 & 0 & \cdots & 0 & 0 \\ 0 & \ddots & \ddots & \vdots & \vdots \\ \vdots & \ddots & \ddots & 0 & \vdots \\ 0 & \cdots & 0 & 1 & 0 \end{array}\right)_{r \times (r+1)}.$$

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

In this question, we assume that $M$ is invertible. Prove that $m = n$ and that $A$ and $B$ are invertible.

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 $$\left(\begin{array}{cc} 0_r & B_1 \\ A_1 & 0_r \end{array}\right) \quad \text{and} \quad \left(\begin{array}{cc} \mathrm{I}_r & 0_r \\ 0_r & -\mathrm{I}_r \end{array}\right),$$ where $$A_1 = \mathrm{I}_r \quad \text{and} \quad B_1 = \lambda \mathrm{I}_r + J_r$$ for $r$ nonzero integer and $\lambda$ nonzero complex suitable.

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

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