Let $E$ be a Euclidean space of dimension $N$. We denote by $(|)$ the inner product and $\|\cdot\|$ the associated Euclidean norm. Let $u$ be a self-adjoint endomorphism of $E$. We define $q_u : E \rightarrow \mathbf{R}$ by $q_u : x \mapsto (u(x) \mid x)$ and we assume that for all $x \in E$, $q_u(x) \geq 0$. State the spectral theorem for the endomorphism $u$. What can be said about the eigenvalues of $u$?

Let $E$ be a Euclidean space of dimension $N$. Let $u$ be a self-adjoint endomorphism of $E$ such that for all $x \in E$, $q_u(x) = (u(x) \mid x) \geq 0$. We assume that 0 is a simple eigenvalue of $u$ and we denote by $\lambda_2$ the smallest nonzero eigenvalue of $u$. We denote by $p : E \rightarrow E$ the orthogonal projection onto the vector line $\ker(u)$. Show that for all $x \in E$, $q_u(x - p(x)) \geq \lambda_2 \|x - p(x)\|^2$.

Consider $a = (a_1, \ldots, a_d) \in \left(\mathbb{R}_{+}^{*}\right)^d$ and $b = (b_1, \ldots, b_{d-1}) \in \left(\mathbb{R}_{+}^{*}\right)^{d-1}$ and introduce the matrix $$M = \begin{pmatrix} a_1 & b_1 & 0 & \ldots & 0 & 0 \\ a_2 & 0 & b_2 & \ldots & 0 & 0 \\ a_3 & 0 & 0 & \ldots & 0 & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ a_{d-1} & 0 & 0 & \ldots & 0 & b_{d-1} \\ a_d & 0 & 0 & \ldots & 0 & 0 \end{pmatrix}.$$
(a) Justify that there exists a unique pair $(\lambda, \pi) \in \mathbb{R}_{+}^{*} \times \mathscr{P}$ such that $\pi M = \lambda \pi$. Express $\pi$ explicitly in terms of $a$, $b$ and $\lambda$.
(b) Show that there exists a unique $h \in \mathscr{M}_{d,1}\left(\mathbb{R}_{+}^{*}\right)$ such that $\langle \pi, h \rangle = 1$ and $$Mh = \lambda h.$$
(c) Deduce that the sequence $\left(\lambda^{-n} M^n\right)_{n \geqslant 1}$ converges as $n$ tends to infinity and give an expression for its limit in terms of $h$ and $\mu$.

Let $T$ be a delta endomorphism of $\mathbb{K}[X]$. For $n \in \mathbb{N}$, we denote by $T_n$ the restriction of $T$ to $\mathbb{K}_n[X]$.
Show that $T_n$ is an endomorphism of $\mathbb{K}_n[X]$. Is it diagonalizable?

Let $n$ be a natural integer with $n \geqslant 2$. For any real number $x$, we consider the following matrix in $\mathscr{M}_{n}(\mathbb{R})$ $$M_{x} = \left(\begin{array}{ccccc} x & 1 & \cdots & 1 & 1 \\ 1 & x & \cdots & 1 & 1 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 1 & 1 & \cdots & x & 1 \\ 1 & 1 & \cdots & 1 & x \end{array}\right)$$ Show that the matrix $-M_{0}$ is diagonalizable and determine its eigenvalues and eigenspaces.

Let $n$ be a natural integer with $n \geqslant 2$. For any real number $x$, we consider the following matrix in $\mathscr{M}_n(\mathbb{R})$ $$M_x = \left(\begin{array}{ccccc} x & 1 & \cdots & 1 & 1 \\ 1 & x & \cdots & 1 & 1 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 1 & 1 & \cdots & x & 1 \\ 1 & 1 & \cdots & 1 & x \end{array}\right).$$ Show that the matrix $-M_0$ is diagonalizable and determine its eigenvalues and eigenspaces.

Justify that an adjacency matrix of a non-empty graph is diagonalizable.

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$, $S_k$ a vector subspace of $\mathbf{R}^n$ of dimension $k$, and $T_k = \operatorname{Vect}(e_k, \ldots, e_n)$.
By considering $x \in S_k \cap T_k$, justify that: $$\max_{x \in S_k, \|x\|=1} (x, f(x)) \geq \lambda_k.$$

Deduce the characteristic polynomial of a graph with $n$ vertices whose non-isolated vertices form a star with $d$ branches with $1 \leq d \leq n - 1$. Then determine the eigenvalues and eigenvectors of an adjacency matrix of this graph.

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)$. For $k \in \llbracket 1, n \rrbracket$, let $\pi_k$ denote the set of vector subspaces of $\mathbf{R}^n$ of dimension $k$.
Let $k \in \llbracket 1, n \rrbracket$. Using $S = \operatorname{Vect}(e_1, \ldots, e_k) \in \pi_k$, show the equality: $$\lambda_k = \min_{S \in \pi_k} \left( \max_{x \in S, \|x\|=1} (x, f(x)) \right)$$ This is the Courant-Fischer theorem.

Let $G _ { 1 } = \left( S _ { 1 } , A _ { 1 } \right)$ and $G _ { 2 } = \left( S _ { 2 } , A _ { 2 } \right)$ be two non-empty graphs such that $S _ { 1 }$ and $S _ { 2 }$ are disjoint, that is, such that $S _ { 1 } \cap S _ { 2 } = \varnothing$. Let $s _ { 1 } \in S _ { 1 }$ and let $s _ { 2 } \in S _ { 2 }$.
We define the graph $G = ( S , A )$ with $S = S _ { 1 } \cup S _ { 2 }$ and $A = A _ { 1 } \cup A _ { 2 } \cup \left\{ \left\{ s _ { 1 } , s _ { 2 } \right\} \right\}$.
Show that : $$\chi _ { G } = \chi _ { G _ { 1 } } \times \chi _ { G _ { 2 } } - \chi _ { G _ { 1 } \backslash s _ { 1 } } \times \chi _ { G _ { 2 } \backslash s _ { 2 } }$$

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)$. Let $P \in \mathscr{V}(A)$. Show that $\varphi_A$ divides $P$.

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 the roots of $\varphi_A$ in $\mathbb{C}$ are exactly the eigenvalues of $A$.

Let $Z \in \mathscr{M}_{d}(\mathbb{R})$ be an invertible matrix. We denote $\mathrm{S} = Z^{T}Z$. Show that there exists a decreasing family $(\lambda_{i})_{1 \leqslant i \leqslant d}$ of strictly positive real numbers and an orthonormal basis $(u_{1}, \ldots, u_{d})$ of $\mathbb{R}^{d}$ such that $Su_{i} = \lambda_{i} u_{i}$ for all $1 \leqslant i \leqslant d$.

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$.
Let $D$ be a non-zero EDM of order $n$. Let $\lambda_1, \ldots, \lambda_n$ be its eigenvalues, ordered in increasing order. Show $$\lambda_{n-1} \leqslant 0$$ and deduce that $D$ has exactly one strictly positive eigenvalue.

Let $H$ be a Hadamard matrix of order $n$ with first row constant equal to 1. Let $\lambda_1, \ldots, \lambda_n$ be real numbers such that $$\lambda_1 > 0 \geq \lambda_2 \geq \ldots \geq \lambda_n$$ and $$\sum_{i=1}^{n} \lambda_i = 0.$$ We denote by $U$ the matrix $\frac{1}{\sqrt{n}} H$ and $\Lambda$ the diagonal matrix whose diagonal coefficients are the $\lambda_i$. We finally denote by $D = U^T \Lambda U$.
Show that $D$ is symmetric, with non-negative coefficients and zero diagonal, and has eigenvalues $\lambda_1, \ldots, \lambda_n$, with $\lambda_1$ having eigenspace of dimension 1.

Problem 2, Part 1: Adapted norms
We denote by $\mathrm { M } _ { d } ( \mathbb { C } )$ the space of $d \times d$ square matrices with complex coefficients and we identify $\mathbb { C } ^ { d }$ with the space of column vectors of size $d$. For a vector $x = \left( x _ { 1 } , \ldots , x _ { d } \right) \in \mathbb { C } ^ { d }$, we define $\| x \| _ { \infty } = \max _ { 1 \leqslant i \leqslant d } \left| x _ { i } \right|$. If $A$ is a matrix in $\mathrm { M } _ { d } ( \mathbb { C } )$ we denote by $\operatorname { Sp } ( A )$ the spectrum of $A$ and we define the spectral radius $\sigma ( A ) = \max \{ | \lambda | , \lambda \in \operatorname { Sp } ( A ) \}$.
Let $T = \left( t _ { i , j } \right) _ { 1 \leqslant i , j \leqslant d }$ be an upper triangular matrix. Show that for all $\varepsilon > 0$, there exists a norm $\| \cdot \| ^ { \prime }$ on $\mathbb { C } ^ { d }$ such that for all $x \in \mathbb { C } ^ { d }$ we have $$\| T x \| ^ { \prime } \leqslant ( \sigma ( T ) + \varepsilon ) \| x \| ^ { \prime }$$ (one may choose $\| \cdot \| ^ { \prime }$ in the form $\| x \| ^ { \prime } = \| P x \| _ { \infty }$ for a suitably chosen matrix $P$).

Problem 2, Part 1: Adapted norms
We denote by $\mathrm { M } _ { d } ( \mathbb { C } )$ the space of $d \times d$ square matrices with complex coefficients. If $A$ is a matrix in $\mathrm { M } _ { d } ( \mathbb { C } )$ we denote by $\operatorname { Sp } ( A )$ the spectrum of $A$ and we define the spectral radius $\sigma ( A ) = \max \{ | \lambda | , \lambda \in \operatorname { Sp } ( A ) \}$. We define $\| A \| = \sup _ { \| x \| _ { \infty } \leqslant 1 } \| A x \| _ { \infty }$.
Application: norm and spectral radius. a. Let $T \in \mathrm { M } _ { d } ( \mathbb { C } )$ be an upper triangular matrix. Show that for all $\varepsilon > 0$, there exists a constant $C$ such that for all $n$ we have $\left\| T ^ { n } \right\| \leqslant C ( \sigma ( T ) + \varepsilon ) ^ { n }$. b. Show that $\lim _ { n \rightarrow \infty } \left\| T ^ { n } \right\| ^ { 1 / n } = \sigma ( T )$. c. Let now $A \in \mathrm { M } _ { d } ( \mathbb { C } )$ be an arbitrary matrix. Show that $\lim _ { n \rightarrow \infty } \left\| A ^ { n } \right\| ^ { 1 / n } = \sigma ( A )$. d. Show the equivalence $$A ^ { n } \underset { n \rightarrow \infty } { \longrightarrow } 0 \Leftrightarrow \sigma ( A ) < 1 .$$

For all $k \in \llbracket 1,n \rrbracket$, we denote by $C_{n,k}$ the matrix of $\mathcal{M}_n(\mathbb{R})$ defined by $$\forall (i,j) \in \llbracket 1,n \rrbracket^2, \quad C_{n,k}(i,j) = \begin{cases} 1 & \text{if } (i \in \llbracket 1,k \rrbracket \text{ and } j = i+n-k) \text{ or } (i \in \llbracket k+1,n \rrbracket \text{ and } j = i-k) \\ 0 & \text{otherwise} \end{cases}$$ We note that $C_{n,n} = I_n$. We set $J_n^{(1)} = C_{n,1} + C_{n,n-1}$.
Deduce an annihilating polynomial of $C_{n,1}$, then its spectrum.

For all $k \in \llbracket 1,n \rrbracket$, we denote by $C_{n,k}$ the matrix of $\mathcal{M}_n(\mathbb{R})$ defined by $$\forall (i,j) \in \llbracket 1,n \rrbracket^2, \quad C_{n,k}(i,j) = \begin{cases} 1 & \text{if } (i \in \llbracket 1,k \rrbracket \text{ and } j = i+n-k) \text{ or } (i \in \llbracket k+1,n \rrbracket \text{ and } j = i-k) \\ 0 & \text{otherwise} \end{cases}$$ We note that $C_{n,n} = I_n$. We set $J_n^{(1)} = C_{n,1} + C_{n,n-1}$.
Deduce that $J_n^{(1)}$ admits the following eigenvalues, enumerated with their multiplicity: $$\lambda_k = 2\cos\left(\frac{2\pi k}{n}\right), \quad k \in \llbracket 0, n-1 \rrbracket.$$

In this subsection, we assume that $J_n = J_n^{(1)}$, the matrix introduced in subsection A-IV.
We set $A = \begin{pmatrix} \mathrm{e}^{\beta - h} & \mathrm{e}^{-\beta - h} \\ \mathrm{e}^{-\beta + h} & \mathrm{e}^{\beta + h} \end{pmatrix}$.
Determine the eigenvalues of the matrix $A$.

In this subsection, we assume that $J_n = J_n^{(1)}$, the matrix introduced in subsection A-IV.
We set $A = \begin{pmatrix} \mathrm{e}^{\beta - h} & \mathrm{e}^{-\beta - h} \\ \mathrm{e}^{-\beta + h} & \mathrm{e}^{\beta + h} \end{pmatrix}$.
Show then that $$\psi_n(h) \underset{n \rightarrow +\infty}{\longrightarrow} \ln\left(\mathrm{e}^{\beta} \operatorname{ch}(h) + \sqrt{\mathrm{e}^{2\beta} \operatorname{ch}^2(h) - 2\operatorname{sh}(2\beta)}\right).$$

As in the third part, we suppose that $B = A + \mathbf{u}\mathbf{u}^T$ with $A \in \mathcal{S}_n(\mathbb{R})$ a symmetric matrix, and $\mathbf{u} \in \mathbb{R}^n$ a vector such that $\|\mathbf{u}\| = 1$. We denote by $\lambda_1 \leqslant \lambda_2 \leqslant \cdots \leqslant \lambda_n$ the eigenvalues of $A$ and $\mu_1 \leqslant \mu_2 \leqslant \cdots \leqslant \mu_n$ those of $B$. We admit that $$\lambda_1 \leqslant \mu_1 \leqslant \lambda_2 \leqslant \mu_2 \leqslant \cdots \leqslant \lambda_n \leqslant \mu_n.$$ We further suppose that there exists an integer $m \in \{1, 2, \ldots, n-1\}$ such that the eigenvalues of $A$ satisfy $$0 = \lambda_1 = \lambda_2 = \cdots = \lambda_m < \lambda_{m+1} \leqslant \cdots \leqslant \lambda_n.$$ Let $\varepsilon \in ]0, \lambda_{m+1}[$. We suppose that $\left\langle \mathbf{u}, \left(A - \varepsilon \mathbb{I}_n\right)^{-1}\mathbf{u}\right\rangle < -1$.
Show that $\mu_m > \varepsilon$.

As in the third part, we assume that $B = A + \mathbf{u u}^T$ with $A \in \mathcal{S}_n(\mathbb{R})$ a symmetric matrix, and $\mathbf{u} \in \mathbb{R}^n$ a vector such that $\|\mathbf{u}\| = 1$. We denote by $\lambda_1 \leqslant \lambda_2 \leqslant \cdots \leqslant \lambda_n$ the eigenvalues of $A$ and $\mu_1 \leqslant \mu_2 \leqslant \cdots \leqslant \mu_n$ those of $B$. We admit that $$\lambda_1 \leqslant \mu_1 \leqslant \lambda_2 \leqslant \mu_2 \leqslant \cdots \leqslant \lambda_n \leqslant \mu_n.$$ We further assume that there exists an integer $m \in \{1,2,\ldots,n-1\}$ such that the eigenvalues of $A$ satisfy $$0 = \lambda_1 = \lambda_2 = \cdots = \lambda_m < \lambda_{m+1} \leqslant \cdots \leqslant \lambda_n.$$ Let $\varepsilon \in ]0, \lambda_{m+1}[$. We suppose that $\left\langle \mathbf{u}, \left(A - \varepsilon \mathbb{I}_n\right)^{-1} \mathbf{u} \right\rangle < -1$. Show that $\mu_m > \varepsilon$.

We fix an integer $d \in \mathbb{N}^*$, and we equip $\mathbb{R}^d$ with the usual inner product denoted $\langle \cdot, \cdot \rangle$ and the associated Euclidean norm $\|\cdot\|$. We denote $C := \{x \in \mathbb{R}^d \mid \|x\| \leq 1\}$ the closed unit ball of $\mathbb{R}^d$. Let $M$ be a nonzero real symmetric matrix of size $d \times d$ such that $\forall x \in \mathbb{R}^d,\, \langle x, Mx \rangle \geq 0$. We define $f(x) := -\frac{1}{2}\langle x, Mx \rangle$, so that $\nabla f(x) = -Mx$. The sequence $(x_n)_{n \in \mathbb{N}}$ is defined by $$x_{n+1} := P_C(x_n - \tau \nabla f(x_n)), \quad \text{with} \quad P_C(x) := \begin{cases} x & \text{if } \|x\| \leq 1, \\ x/\|x\| & \text{otherwise.} \end{cases}$$ Suppose in this question that $\|x_0\| \geq 1$. a) Show that $$\forall n \in \mathbb{N} \setminus \{0\},\, x_n = \frac{(\mathrm{I}_d + \tau M)^n x_0}{\|(\mathrm{I}_d + \tau M)^n x_0\|}$$ b) Calculate $\lim_{n \rightarrow \infty} x_n$. Hint. Decompose $x_0 = \sum_{1 \leq i \leq d} \alpha_i e_i$ in an orthonormal basis of eigenvectors $(e_1, \cdots, e_d)$, associated with the eigenvalues $\lambda_1, \cdots, \lambda_d$ of $M$. Introduce the set of indices $I := \{i \in \llbracket 1, d \rrbracket \mid \alpha_i \neq 0\}$, the eigenvalue $\lambda := \max_{i \in I} \lambda_i$, and the vector $x_0' := \sum_{i \in I'} \alpha_i e_i$ where $I' := \{i \in I \mid \lambda_i = \lambda\}$.