Let $A \in \mathbf{M}_n$ and $U, V \in \mathbf{O}_n$. Show that $\|UAV\| = \|A\|$.

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}'$.
Show that $s_{qq}' + s_{pp}' = s_{qq} + s_{pp}$.

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}'$.
Express the coefficients $s_{ij}'$ of $S'$ in terms of those of $S$.

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}'$.
We seek an angle $\theta \in \left]-\frac{\pi}{2}, \frac{\pi}{2}\right[$ for which we have $s_{pq}' = 0$.
(a) Show that $s_{pq}' = 0$ if and only if $t = \tan\theta$ satisfies the equation $$t^2 + \frac{s_{pp} - s_{qq}}{s_{pq}} t - 1 = 0 \tag{1}$$
(b) Show that this equation admits one solution $t_0 \in ]-1, 1]$ and another $t_1 \notin ]-1, 1]$. What is the relationship between the angles $\theta_0$ and $\theta_1$ that correspond to these roots?
(c) In all that follows, we choose one of the two roots $t$ of equation (1). We thus have $s_{pq}' = 0$. A more precise choice will be made starting from question 12. Verify that $s_{pp}' - s_{pp} = t s_{pq}$; establish an analogous formula for $s_{qq}' - s_{qq}$.
(d) We decompose $S$ in the form $S = D + E$ with $D$ diagonal and $E$ with zero diagonal. We similarly decompose $S' = D' + E'$. Calculate $\|E'\|^2$ in terms of $\|E\|^2$ and $\left(s_{pq}\right)^2$.
(e) By justifying that $\|S'\| = \|S\|$, deduce an expression for $\|D'\|^2$ in terms of $\|D\|^2$ and $\left(s_{pq}\right)^2$.

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}'$.
Show that the coefficients of $S'$ are expressed uniquely in terms of those of $S$ and the root ($t_0$ or $t_1$) that we have chosen.

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

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

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

We assume that the conditions of question 12 are satisfied and that $\lambda(0) \neq 0$. Show that $E \circ F = F \circ E + H - H^{-1}$ if and only if for all $i \in \mathbf{Z}$, $$\mu(i) = \mu(i-1) + \lambda(0) q^{-2i} - \lambda(0)^{-1} q^{2i}$$

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.

We assume that the conditions of questions 12 and 14 are satisfied and that $\lambda(0) \neq 0$.
15a. Show that $\lambda$ and $\mu$ are periodic on $\mathbf{Z}$, with periods dividing $\ell$.
15b. Show that the period of $\lambda$ is equal to $\ell$.
15c. Show that the period of $\mu$ is also equal to $\ell$.

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

We assume that the conditions of questions 12 and 14 are satisfied and that $\lambda(0) \neq 0$. Let $C = (q - q^{-1}) E \circ F + q^{-1} H + q H^{-1}$ with $H^{-1}$ the inverse of $H$.
16a. Show that $C = (q - q^{-1}) F \circ E + q H + q^{-1} H^{-1}$.
16b. For $i \in \mathbf{Z}$, show that $v_i$ is an eigenvector of $C$.
16c. Deduce that $C$ is a homothety of $V$ and calculate its ratio $R(\lambda(0), \mu(0), q)$ in terms of $\lambda(0), \mu(0)$ and $q$.
16d. We fix $q$ and $\lambda(0)$. Show that the map $\mu(0) \mapsto R(\lambda(0), \mu(0), q)$ is a bijection from $\mathbf{C}$ to $\mathbf{C}$.
16e. We fix $q$ and $\mu(0)$. Show that the map $\lambda(0) \mapsto R(\lambda(0), \mu(0), q)$ is a surjection from $\mathbf{C}^*$ to $\mathbf{C}$ but not a bijection.

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 $\ell, W_{\ell}, a, P_a$ be as in Part II. We say that an element $\phi$ of $\mathcal{L}(V)$ is compatible with $P_a$ if $P_a \circ \phi \circ P_a = P_a \circ \phi$.
17a. Show that if $\phi \in \mathcal{L}(V)$ commutes with $P_a$, then $\phi$ is compatible with $P_a$.
17b. Show that $H$ and $H^{-1}$ are compatible with $P_a$.

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 $\mathcal{U}_q$ be the set of endomorphisms $\phi \in \mathcal{L}(V)$ that are compatible with $P_a$. Show that $\mathcal{U}_q$ is a subalgebra of $\mathcal{L}(V)$.

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?

Let $\mathcal{U}_q$ be the set of endomorphisms $\phi \in \mathcal{L}(V)$ that are compatible with $P_a$. Show that $E \in \mathcal{U}_q$ and $F \in \mathcal{U}_q$.

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

Let $\mathcal{U}_q$ be the set of endomorphisms $\phi \in \mathcal{L}(V)$ that are compatible with $P_a$.
20a. Show that there exists a unique algebra morphism $\Psi_a : \mathcal{U}_q \rightarrow \mathcal{L}(W_{\ell})$ such that $$\forall \phi \in \mathcal{U}_q, \quad \Psi_a(\phi) \circ P_a = P_a \circ \phi$$
20b. Show that $\phi \in \mathcal{U}_q$ is contained in the kernel of $\Psi_a$ if and only if the image of $\phi$ is in the subspace of $V$ spanned by the vectors $v_i - a^p v_r, i \in \mathbf{Z}$, where $i = p\ell + r$ is the Euclidean division of $i$ by $\ell$.

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

Let $\mathcal{U}_q$ be the set of endomorphisms $\phi \in \mathcal{L}(V)$ that are compatible with $P_a$, and $\Psi_a : \mathcal{U}_q \rightarrow \mathcal{L}(W_{\ell})$ the unique algebra morphism such that $\Psi_a(\phi) \circ P_a = P_a \circ \phi$ for all $\phi \in \mathcal{U}_q$. We study $\Psi_a(E)$ in this question.
21a. Determine $\Psi_a(E)(v_0)$.
21b. Deduce $\Psi_a(E^{\ell})$.
21c. Calculate the dimension of the vector subspace $\mathbf{C}[\Psi_a(E)]$.
21d. Calculate the eigenvectors of $\Psi_a(E)$.