We consider the space $E = \mathcal{M}_{k,d}(\mathbb{R})$ equipped with the inner product defined by
$$\forall (A, B) \in E^{2}, \quad \langle A \mid B \rangle = \operatorname{tr}\left(A^{\top} \cdot B\right)$$
We denote by $\|\cdot\|_{F}$ the associated Euclidean norm. We fix a vector $(u_{1}, \ldots, u_{d})$ in $\mathbb{R}^{d}$ with $\|u\| = 1$, and define
$$g : \left\lvert \, \begin{aligned} & \mathcal{M}_{k,d}(\mathbb{R}) \rightarrow \mathbb{R} \\ & M \mapsto \|M \cdot u\| \end{aligned} \right.$$
Show that for every matrix $M$ in $\mathcal{M}_{k,d}(\mathbb{R})$
$$\|M \cdot u\| \leqslant \|M\|_{F}$$

Let $u \in \mathbb { R } ^ { p }$. Show that $\| A u \| _ { 2 } \leqslant \| A \| _ { F } \| u \| _ { 2 }$.

Show that $\| A C \| _ { F } \leqslant \| A \| _ { F } \| C \| _ { F }$.

When $x \in \mathbb{C}^n$, verify that $\|x\|_2^2 = \bar{x}^T x$.

Let $U \in \mathcal{M}_n(\mathbb{C})$ be a unitary matrix. Show that $\|Ux\|_2 = \|x\|_2$ for all $x \in \mathbb{C}^n$.

If $D \in \mathcal{M}_n(\mathbb{C})$ is a diagonal matrix whose diagonal coefficients are $d_0, \ldots, d_{n-1}$, show that $\|D\| = \max_{0 \leq i \leq n-1} |d_i|$.

Let $A, B \in \mathcal{M}_n(\mathbb{C})$. Suppose that there exists a unitary matrix $U \in \mathcal{M}_n(\mathbb{C})$ such that $B = UAU^{-1}$. Show that $\|A\| = \|B\|$.

We fix a polynomial $f \in \mathbb{C}[X]$ of degree $n \geq 1$. We consider a complex number $z \in \overline{\mathbb{D}}$ and we define the matrices $M \in \mathcal{M}_{n+1}(\mathbb{C})$ and $P \in \mathcal{M}_{n+1,1}(\mathbb{C})$ by $$M = \left(\begin{array}{cccccc} z & 0 & 0 & \ldots & 0 & \sqrt{1-|z|^2} \\ \sqrt{1-|z|^2} & 0 & 0 & \ldots & 0 & -\bar{z} \\ 0 & & & & & 0 \\ 0 & & & & & 0 \\ \vdots & & I_{n-1} & & & \vdots \\ 0 & & & & & 0 \end{array}\right)$$ and $$P = \left(\begin{array}{c} 1 \\ 0 \\ \vdots \\ 0 \end{array}\right)$$ Show that $|f(z)| \leq \|f(M)\|$.

We fix a polynomial $f \in \mathbb{C}[X]$ of degree $n \geq 1$. We consider a complex number $z \in \overline{\mathbb{D}}$ and we define the matrices $M \in \mathcal{M}_{n+1}(\mathbb{C})$ and $P \in \mathcal{M}_{n+1,1}(\mathbb{C})$ by $$M = \left(\begin{array}{cccccc} z & 0 & 0 & \ldots & 0 & \sqrt{1-|z|^2} \\ \sqrt{1-|z|^2} & 0 & 0 & \ldots & 0 & -\bar{z} \\ 0 & & & & & 0 \\ 0 & & & & & 0 \\ \vdots & & I_{n-1} & & & \vdots \\ 0 & & & & & 0 \end{array}\right)$$ and $$P = \left(\begin{array}{c} 1 \\ 0 \\ \vdots \\ 0 \end{array}\right)$$ Prove Theorem 1: Let $f \in \mathbb{C}[X]$ be a polynomial. Then $$\sup_{z \in \overline{\mathbb{D}}} |f(z)| = \sup_{z \in \mathbb{S}} |f(z)|$$

Throughout this part, $\mathcal{A}$ is a subalgebra of $\mathcal{M}_{n}(\mathbb{R})$ strictly contained in $\mathcal{M}_{n}(\mathbb{R})$ and we denote by $d$ its dimension. The trace of any matrix $M$ of $\mathcal{M}_{n}(\mathbb{R})$ is denoted $\operatorname{tr}(M)$.
Show that the map defined on $\mathcal{M}_{n}(\mathbb{R}) \times \mathcal{M}_{n}(\mathbb{R})$ by $(A, B) \mapsto \langle A \mid B \rangle = \operatorname{tr}(A^{\top} B)$ is an inner product on $\mathcal{M}_{n}(\mathbb{R})$.

For any matrix $B \in \mathcal { M } _ { N } ( \mathbb { R } )$, we set $\| B \| = \sup _ { \| x \| = 1 } \| B x \|$.
After justifying the existence of $\| B \|$, show that $B \mapsto \| B \|$ is a norm on $\mathcal { M } _ { N } ( \mathbb { R } )$ satisfying $$\forall x \in \mathbb { R } ^ { N } \quad \| B x \| \leq \| B \| \| x \|$$

Let $A \in \mathcal { S } _ { N } ( \mathbb { R } )$ be a matrix with eigenvalues (not necessarily distinct) $\lambda _ { 1 } , \ldots , \lambda _ { N }$. Show that $$\| A \| = \max _ { 1 \leq i \leq N } \left| \lambda _ { i } \right|$$

Let $A \in \mathcal { S } _ { N } ^ { + } ( \mathbb { R } )$. For all $x \in \mathbb { R } ^ { N }$, we set $\| x \| _ { A } = \langle x , A x \rangle ^ { 1 / 2 }$.
a) Show that the map $x \mapsto \| x \| _ { A }$ is a norm on $\mathbb { R } ^ { N }$.
b) Show that there exist constants $C _ { 1 }$ and $C _ { 2 }$ strictly positive, which we will express in terms of the eigenvalues of $A$, such that $$\forall x \in \mathbb { R } ^ { N } \quad C _ { 1 } \| x \| \leq \| x \| _ { A } \leq C _ { 2 } \| x \| .$$

We keep the notations from Parts II and III. We denote $e _ { k } = x _ { k } - \tilde { x }$ and $e _ { 0 } = x _ { 0 } - \tilde { x }$. We recall that $I _ { N }$ is the identity matrix of order $N$.
Show that $$\left\| e _ { k } \right\| _ { A } = \min \left\{ \left\| \left( I _ { N } + A Q ( A ) \right) e _ { 0 } \right\| _ { A } \mid Q \in \mathbb { R } [ X ] , \operatorname { deg } ( Q ) \leq k - 1 \right\}$$

We keep the notations from Parts II and III. We denote $e _ { k } = x _ { k } - \tilde { x }$ and $e _ { 0 } = x _ { 0 } - \tilde { x }$. We recall that $I _ { N }$ is the identity matrix of order $N$, and $\| \cdot \|$ denotes the matrix norm defined in question 2.
Show that $$\left\| e _ { k } \right\| _ { A } \leq \left\| e _ { 0 } \right\| _ { A } \min \left\{ \left\| I _ { N } + A Q ( A ) \right\| \mid Q \in \mathbb { R } [ X ] , \operatorname { deg } ( Q ) \leq k - 1 \right\}$$ (One may use the properties of $A ^ { 1 / 2 }$ demonstrated in question 6.)

We denote by $\lambda _ { 1 }$ (respectively $\lambda _ { N }$) the smallest (respectively largest) eigenvalue of $A$, and we define $$\Lambda _ { k } = \{ Q \in \mathbb { R } [ X ] \mid \operatorname { deg } ( Q ) \leq k , Q ( 0 ) = 1 \}$$
Show that $$\left\| e _ { k } \right\| _ { A } \leq \left\| e _ { 0 } \right\| _ { A } \min _ { Q \in \Lambda _ { k } } \max _ { t \in \left[ \lambda _ { 1 } , \lambda _ { N } \right] } | Q ( t ) |$$

We denote by $\kappa = \lambda _ { N } / \lambda _ { 1 }$. Show that the real number $\alpha$ from question 22 equals $\alpha = \frac { \sqrt { \kappa } - 1 } { \sqrt { \kappa } + 1 }$ and deduce that $$\left\| e _ { k } \right\| _ { A } \leq 2 \left\| e _ { 0 } \right\| _ { A } \left( \frac { \sqrt { \kappa } - 1 } { \sqrt { \kappa } + 1 } \right) ^ { k }$$

Throughout part II, $A \in \mathcal{M}_n(\mathbb{R})$ is a strictly positive matrix. Show that, for all $x \in \mathbb{R}^n$, $$\left\{\begin{array}{l} x \geqslant 0 \Longrightarrow Ax \geqslant 0 \\ x \geqslant 0 \text{ and } x \neq 0 \Longrightarrow Ax > 0. \end{array}\right.$$

Throughout part II, $A \in \mathcal{M}_n(\mathbb{R})$ is a strictly positive matrix satisfying $\rho(A) = 1$. We consider an eigenvalue $\lambda \in \mathbb{C}$ of $A$ with modulus 1 and $x$ an eigenvector associated with $\lambda$. We assume that $|x| < A|x|$. Show that there exists $\varepsilon > 0$ such that $A^2|x| - A|x| > \varepsilon A|x|$.

We set, for all $n \geq 0$ and all $x \in \mathbf{R}$, $P_n(x) = \sum_{k=0}^{n} \frac{x^k}{k!}$ where $k!$ denotes the factorial of $k$.
Let $A \in \operatorname{Sym}^+(p)$.
(a) Show that for all $(i,j) \in \llbracket 1,p \rrbracket^2$, we have $$\lim_{n \rightarrow +\infty} P_n[A]_{ij} = \exp\left(A_{ij}\right)$$
(b) Show that $\exp[A] \in \operatorname{Sym}^+(p)$.
(c) Let $u \in \mathbf{R}^p$. Show that $\exp[A] \odot \left(uu^T\right) \in \operatorname{Sym}^+(p)$.

Show that, for every $M$ in $\mathcal{M}_{n}(\mathbb{R})$ and for all $P$ and $Q$ in $\mathcal{O}_{n}(\mathbb{R})$, we have $\|PMQ\|_{F} = \|M\|_{F}$.

We denote $\mathcal{B}_{n}(\mathbb{R})$ the set of doubly stochastic matrices in $\mathcal{M}_{n}(\mathbb{R})$, that is the set of matrices $M = \left(m_{i,j}\right)_{1 \leqslant i,j \leqslant n}$ whose coefficients are all non-negative and such that $\sum_{j=1}^{n} m_{i,j} = \sum_{j=1}^{n} m_{j,i} = 1$ for every $i \in \llbracket 1, n \rrbracket$.
We denote $f : \left|\, \begin{array}{ccc} \mathcal{M}_{n}(\mathbb{R}) & \rightarrow & \mathbb{R} \\ M & \mapsto & \sum_{1 \leqslant i,j \leqslant n} m_{i,j}\left(\lambda_{i}(A) - \lambda_{j}(B)\right)^{2}. \end{array}\right.$
Justify that $f$ admits a minimum on $\mathcal{B}_{n}(\mathbb{R})$.

We denote $\mathcal{B}_{n}(\mathbb{R})$ the set of doubly stochastic matrices in $\mathcal{M}_{n}(\mathbb{R})$, that is the set of matrices $M = \left(m_{i,j}\right)_{1 \leqslant i,j \leqslant n}$ whose coefficients are all non-negative and such that $\sum_{j=1}^{n} m_{i,j} = \sum_{j=1}^{n} m_{j,i} = 1$ for every $i \in \llbracket 1, n \rrbracket$.
We denote $f : \left|\, \begin{array}{ccc} \mathcal{M}_{n}(\mathbb{R}) & \rightarrow & \mathbb{R} \\ M & \mapsto & \sum_{1 \leqslant i,j \leqslant n} m_{i,j}\left(\lambda_{i}(A) - \lambda_{j}(B)\right)^{2}. \end{array}\right.$
Let $(i,j,k) \in \llbracket 1,n \rrbracket^{3}$ such that $j \geqslant i$ and $k \geqslant i$. Show that, for $M \in \mathcal{M}_{n}(\mathbb{R})$ and for $x \in \mathbb{R}^{+}$, $$f\left(M + xE_{ii} + xE_{jk} - xE_{ik} - xE_{ji}\right) - f(M) = 2x\left(\lambda_{i}(A) - \lambda_{j}(A)\right)\left(\lambda_{k}(B) - \lambda_{i}(B)\right) \leqslant 0$$

We denote $\mathcal{B}_{n}(\mathbb{R})$ the set of doubly stochastic matrices in $\mathcal{M}_{n}(\mathbb{R})$, that is the set of matrices $M = \left(m_{i,j}\right)_{1 \leqslant i,j \leqslant n}$ whose coefficients are all non-negative and such that $\sum_{j=1}^{n} m_{i,j} = \sum_{j=1}^{n} m_{j,i} = 1$ for every $i \in \llbracket 1, n \rrbracket$.
We denote $f : \left|\, \begin{array}{ccc} \mathcal{M}_{n}(\mathbb{R}) & \rightarrow & \mathbb{R} \\ M & \mapsto & \sum_{1 \leqslant i,j \leqslant n} m_{i,j}\left(\lambda_{i}(A) - \lambda_{j}(B)\right)^{2}. \end{array}\right.$
Let $n \geqslant 2$ and $M = \left(m_{i,j}\right)_{1 \leqslant i,j \leqslant n} \in \mathcal{B}_{n}(\mathbb{R})$ a matrix different from the identity. We denote $i$ the smallest integer belonging to $\llbracket 1,n \rrbracket$ such that $m_{i,i} \neq 1$. Show that there exists a matrix $M^{\prime} = \left(m_{i,j}^{\prime}\right)_{1 \leqslant i,j \leqslant n} \in \mathcal{B}_{n}(\mathbb{R})$ such that $f\left(M^{\prime}\right) \leqslant f(M)$ and $m_{j,j}^{\prime} = 1$ for every $j \in \llbracket 1,i \rrbracket$.

We denote $\mathcal{B}_{n}(\mathbb{R})$ the set of doubly stochastic matrices in $\mathcal{M}_{n}(\mathbb{R})$, that is the set of matrices $M = \left(m_{i,j}\right)_{1 \leqslant i,j \leqslant n}$ whose coefficients are all non-negative and such that $\sum_{j=1}^{n} m_{i,j} = \sum_{j=1}^{n} m_{j,i} = 1$ for every $i \in \llbracket 1, n \rrbracket$.
We denote $f : \left|\, \begin{array}{ccc} \mathcal{M}_{n}(\mathbb{R}) & \rightarrow & \mathbb{R} \\ M & \mapsto & \sum_{1 \leqslant i,j \leqslant n} m_{i,j}\left(\lambda_{i}(A) - \lambda_{j}(B)\right)^{2}. \end{array}\right.$
Deduce that $$\min\left\{f(M) \mid M \in \mathcal{B}_{n}(\mathbb{R})\right\} = f\left(I_{n}\right)$$