We are given a matrix $S \in \mathbf{S}_n$, an angle $\theta \in \left]-\frac{\pi}{2}, \frac{\pi}{2}\right[$ and integers $1 \leqslant p < q \leqslant n$ such that $s_{pq} \neq 0$. We define $S' = {}^t R_{p,q}(\theta) S R_{p,q}(\theta)$ and denote its coefficients by $s_{ij}'$.
Suppose in this question that $s_{pq}$ is the coefficient of largest absolute value in $E$.
(a) Show that $\|E'\| \leqslant \rho \|E\|$ where $\rho < 1$ is a constant that we will make explicit.
(b) If we choose the root $t_0$, show furthermore that $\|D' - D\| \leqslant \|E\|$.

Let $W_{\ell} = \bigoplus_{0 \leq i < \ell} \mathbf{C} v_i$ and $a \in \mathbf{C}^*$. We define a linear map $P_a : V \rightarrow V$ by $P_a(v_i) = a^p v_r$ where for $i \in \mathbf{Z}$, we define $r$ and $p$ respectively as the remainder and quotient of the Euclidean division of $i$ by $\ell$; in other words, $i = p\ell + r$ where $0 \leq r < \ell$ and $p \in \mathbf{Z}$. Show that $P_a$ is a projector with image $W_{\ell}$.

We are given a matrix $S \in \mathbf{S}_n$, an angle $\theta \in \left]-\frac{\pi}{2}, \frac{\pi}{2}\right[$ and integers $1 \leqslant p < q \leqslant n$ such that $s_{pq} \neq 0$. We define $S' = {}^t R_{p,q}(\theta) S R_{p,q}(\theta)$ and denote its coefficients by $s_{ij}'$.
By calculating $\left(s_{qq}' - s_{pp}'\right)^2 - \left(s_{qq} - s_{pp}\right)^2$, show that $$\left|s_{qq}' - s_{pp}'\right| \geqslant \left|s_{qq} - s_{pp}\right|$$

Let $\lambda, \mu \in \mathbf{C}^{\mathbf{Z}}$ and $H \in \mathcal{L}(V)$ defined by $H(v_i) = \lambda(i) v_i$. Show that $H \circ E = q^2 E \circ H$ if and only if for all $i \in \mathbf{Z}, \lambda(i) = \lambda(0) q^{-2i}$.

We are given a matrix $S \in \mathbf{S}_n$, an angle $\theta \in \left]-\frac{\pi}{2}, \frac{\pi}{2}\right[$ and integers $1 \leqslant p < q \leqslant n$ such that $s_{pq} \neq 0$. We define $S' = {}^t R_{p,q}(\theta) S R_{p,q}(\theta)$ and denote its coefficients by $s_{ij}'$.
From now on, and until the end of the problem, we choose the root $t_0$ of (1) and thus the angle $\theta_0$, mentioned in Question 8b.
(a) Show that $s_{pp} - s_{pp}'$ and $s_{qq}' - s_{qq}$ have the same sign as $s_{qq} - s_{pp}$.
(b) If $1 \leqslant i \leqslant n$, show that $$\left|s_{ii} - s_{qq}'\right| + \left|s_{ii} - s_{pp}'\right| - \left|s_{ii} - s_{pp}\right| - \left|s_{ii} - s_{qq}\right| \geqslant 0$$

We assume that the conditions of question 12 are satisfied and that $\lambda(0) \neq 0$. Show that $H \in \mathrm{GL}(V)$.

We are given a matrix $S \in \mathbf{S}_n$, an angle $\theta \in \left]-\frac{\pi}{2}, \frac{\pi}{2}\right[$ and integers $1 \leqslant p < q \leqslant n$ such that $s_{pq} \neq 0$. We define $S' = {}^t R_{p,q}(\theta) S R_{p,q}(\theta)$ and denote its coefficients by $s_{ij}'$. From now on we choose the root $t_0$ of (1).
We define $$R = \sum_{i,j=1}^{n} \left|s_{jj} - s_{ii}\right| \quad \text{and} \quad R' = \sum_{i,j=1}^{n} \left|s_{jj}' - s_{ii}'\right|$$
Show that $$R' - R \geqslant 2\left(\left|s_{qq}' - s_{qq}\right| + \left|s_{pp}' - s_{pp}\right|\right) = 2\sum_{i=1}^{n} \left|s_{ii}' - s_{ii}\right|$$

In the Jacobi algorithm, we start with a matrix $\Sigma \in \mathbf{S}_n$ and construct a sequence of symmetric matrices $\Sigma^{(m)}$, whose coefficients are denoted $\sigma_{ij}^{(m)}$, as follows:

• We set $\Sigma^{(0)} = \Sigma$.
• When $\Sigma^{(m)}$ is known, we choose a pair $(p_m, q_m)$ with $p_m < q_m$.
• We then apply the calculations from Part 2 to the matrix $S = \Sigma^{(m)}$ and the pair $(p,q) = (p_m, q_m)$: we form the matrix $S'$ studied in this part, and call it $\Sigma^{(m+1)}$.

We define $$R_m = \sum_{i,j=1}^{n} \left|\sigma_{jj}^{(m)} - \sigma_{ii}^{(m)}\right|, \quad \varepsilon_m = \sum_{i=1}^{n} \left|\sigma_{ii}^{(m+1)} - \sigma_{ii}^{(m)}\right|$$
Verify that $R_{m+1} - R_m \geqslant 2\varepsilon_m$. Deduce that the series $\sum_{m=1}^{\infty} \varepsilon_m$ is convergent.

In the Jacobi algorithm, we start with a matrix $\Sigma \in \mathbf{S}_n$ and construct a sequence of symmetric matrices $\Sigma^{(m)}$, whose coefficients are denoted $\sigma_{ij}^{(m)}$. We decompose $\Sigma^{(m)}$ in the form $D^{(m)} + E^{(m)}$ where $D^{(m)}$ is diagonal and $E^{(m)}$ has zero diagonal.
Show that the sequence $\left(D^{(m)}\right)_{m \in \mathbb{N}}$ is convergent. We denote its limit by $D$.

Let $\left(A^{(m)}\right)_{m \in \mathbb{N}}$ be a sequence in $\mathbf{M}_n$. We assume that for all $m \in \mathbb{N}$, the matrix $A^{(m+1)}$ is similar to $A^{(m)}$.
Show that $A^{(m)}$ is similar to $A^{(0)}$.

Let $\left(A^{(m)}\right)_{m \in \mathbb{N}}$ be a sequence in $\mathbf{M}_n$. We assume that for all $m \in \mathbb{N}$, the matrix $A^{(m+1)}$ is similar to $A^{(m)}$. We further assume that this sequence converges to a diagonal matrix $D$. If $P_m$ denotes the characteristic polynomial of $A^{(m)}$, show that the coefficients of $P_m$ converge to those of the characteristic polynomial of $D$ when $m \rightarrow +\infty$.
Deduce that the characteristic polynomial of $D$ is equal to that of $A^{(0)}$.

Let $\left(A^{(m)}\right)_{m \in \mathbb{N}}$ be a sequence in $\mathbf{M}_n$. We assume that for all $m \in \mathbb{N}$, the matrix $A^{(m+1)}$ is similar to $A^{(m)}$, and that this sequence converges to a diagonal matrix $D$.
Finally, show that the diagonal entries of $D$ are the eigenvalues of $A^{(0)}$. What can be said about their multiplicities?

In the optimal version of the Jacobi algorithm, we choose for each $m$ a pair $(p_m, q_m)$ such that the absolute value of the coefficient $\sigma_{ij}^{(m)}$ is maximal precisely when $(i,j) = (p_m, q_m)$. In other words, $$\forall i < j, \quad \left|\sigma_{ij}^{(m)}\right| \leqslant \left|\sigma_{p_m q_m}^{(m)}\right|$$
Show that as $m \rightarrow +\infty$, the sequence $\left(\Sigma^{(m)}\right)_{m \in \mathbb{N}}$ converges to the diagonal matrix $D$.

In the optimal version of the Jacobi algorithm, we choose for each $m$ a pair $(p_m, q_m)$ such that the absolute value of the coefficient $\sigma_{ij}^{(m)}$ is maximal precisely when $(i,j) = (p_m, q_m)$. In other words, $$\forall i < j, \quad \left|\sigma_{ij}^{(m)}\right| \leqslant \left|\sigma_{p_m q_m}^{(m)}\right|$$
Show then that the diagonal coefficients of $D$ are the eigenvalues of $\Sigma$.

In the optimal version of the Jacobi algorithm, we choose for each $m$ a pair $(p_m, q_m)$ such that the absolute value of the coefficient $\sigma_{ij}^{(m)}$ is maximal precisely when $(i,j) = (p_m, q_m)$. In other words, $$\forall i < j, \quad \left|\sigma_{ij}^{(m)}\right| \leqslant \left|\sigma_{p_m q_m}^{(m)}\right|$$
Let $m \in \mathbb{N}$. Show that $$\left\|D - D^{(m)}\right\| \leqslant \frac{\rho^m}{1 - \rho} \left\|E^{(0)}\right\|$$

Based on your answers to the previous questions, give your opinion on the speed of convergence of the $d_{ii}^{(m)}$ to the eigenvalues of $\Sigma$.

Show that, for every polynomial $P \in \mathbb{C}[X]$, the map $f_P : A \mapsto P(A)$ is a continuous function from $\mathcal{M}_d(\mathbb{R})$ to $\mathcal{M}_d(\mathbb{C})$.

Show that the map $(A, B) \mapsto \operatorname{Tr}\left({}^t A \times B\right)$ is an inner product on the space $\mathcal{M}_d(\mathbb{R})$.

In the rest of the problem, we denote by $\|\cdot\|$ the norm associated with the inner product $(A, B) \mapsto \operatorname{Tr}({}^t A \times B)$.
For all integers $i, j$ between 1 and $d$ and every matrix $A \in \mathcal{M}_d(\mathbb{R})$, compare $\left|A_{i,j}\right|$ and $\|A\|$.

In the rest of the problem, we denote by $\|\cdot\|$ the norm associated with the inner product $(A, B) \mapsto \operatorname{Tr}({}^t A \times B)$.
Show that: $\forall (A, B) \in \mathcal{M}_d(\mathbb{R})^2, \|A \times B\| \leqslant \|A\| \cdot \|B\|$.

In the rest of the problem, we denote by $\|\cdot\|$ the norm associated with the inner product $(A, B) \mapsto \operatorname{Tr}({}^t A \times B)$.
For $n \in \mathbb{N}^*$ and $A \in \mathcal{M}_d(\mathbb{R})$, compare $\left\|A^n\right\|$ and $\|A\|^n$.

We are given a power series with complex coefficients $\sum_{n \geqslant 0} a_n z^n$ with radius of convergence $R$ strictly positive, possibly equal to $+\infty$. We denote by $\|\cdot\|$ the norm associated with the inner product $(A,B)\mapsto\operatorname{Tr}({}^tA\times B)$ on $\mathcal{M}_d(\mathbb{R})$.
Let $\mathcal{B} = \left\{A \in \mathcal{M}_d(\mathbb{R}), \|A\| < R\right\}$. Show that the map $\varphi : A \mapsto \varphi(A) = \sum_{n=0}^{+\infty} a_n A^n$ is defined and continuous on $\mathcal{B}$.

We are given a power series with complex coefficients $\sum_{n \geqslant 0} a_n z^n$ with radius of convergence $R$ strictly positive, possibly equal to $+\infty$. We denote by $\|\cdot\|$ the norm associated with the inner product $(A,B)\mapsto\operatorname{Tr}({}^tA\times B)$ on $\mathcal{M}_d(\mathbb{R})$, and $\varphi(A) = \sum_{n=0}^{+\infty} a_n A^n$.
Let $A \in \mathcal{M}_d(\mathbb{R})$ be a nonzero matrix such that $\|A\| < R$.
1) Establish the existence of an integer $r \in \mathbb{N}^*$ such that the family $\left(A^k\right)_{0 \leqslant k \leqslant r-1}$ is free and the family $\left(A^k\right)_{0 \leqslant k \leqslant r}$ is dependent.
2) For $n \in \mathbb{N}$, show the existence and uniqueness of an $r$-tuple $(\lambda_{0,n}, \ldots, \lambda_{r-1,n})$ in $\mathbb{R}^r$ such that $$A^n = \sum_{k=0}^{r-1} \lambda_{k,n} A^k$$
3) Show that there exists a constant $C > 0$ such that: $$\forall n \in \mathbb{N}, \quad \sum_{k=0}^{r-1} |\lambda_{k,n}| \leqslant C \left\|A^n\right\|$$
4) Deduce that, for every integer $k$ between 0 and $(r-1)$, the series $\sum_{n \geqslant 0} a_n \lambda_{k,n}$ is absolutely convergent in $\mathbb{C}$.
5) Conclude that there exists a unique polynomial $P \in \mathbb{R}[X]$ such that $\varphi(A) = P(A)$ and $\deg P < r$.
6) Determine this polynomial $P$ when $A = \begin{pmatrix} 0 & -1 & -1 \\ -1 & 0 & -1 \\ 1 & 1 & 2 \end{pmatrix}$ and $a_n = \frac{1}{n!}$ for all $n \in \mathbb{N}$.

We are given a power series with complex coefficients $\sum_{n \geqslant 0} a_n z^n$ with radius of convergence $R$ strictly positive, possibly equal to $+\infty$, and $\varphi(A) = \sum_{n=0}^{+\infty} a_n A^n$ defined on $\mathcal{B} = \{A \in \mathcal{M}_d(\mathbb{R}), \|A\| < R\}$.
Find a necessary and sufficient condition on the power series $\sum_{n \geqslant 0} a_n z^n$ for there to exist $P \in \mathbb{R}[X]$ such that $$\forall A \in \mathcal{M}_d(\mathbb{R}), \quad \varphi(A) = P(A)$$

State the theorem allowing the product of two series of complex numbers. (We admit in the rest of Part III that the result valid for series of complex numbers still holds for series of matrices in $\mathcal{M}_d(\mathbb{C})$.)