We equip $\mathcal{M}_n(\mathbb{R})$ with its usual inner product defined by: $\forall (M_1, M_2) \in \mathcal{M}_n(\mathbb{R}), \langle M_1, M_2 \rangle = \operatorname{tr}({}^t M_1 M_2)$. We denote by $\mathcal{S}_{k+1}$ the restriction of $\mathcal{S}$ to $\Delta_{k+1}$ and $\mathcal{S}_k^*$ the restriction of $\mathcal{S}^*$ to $\Delta_k$.
Verify that for all $X$ in $\Delta_{k+1}$ and $Y$ in $\Delta_k$, $\langle \mathcal{S}_{k+1} X, Y \rangle = \langle X, \mathcal{S}_k^* Y \rangle$. Deduce that $\ker(\mathcal{S}_k^*)$ and $\operatorname{Im}(\mathcal{S}_{k+1})$ are orthogonal complements in $\Delta_k$, that is $$\Delta_k = \ker(\mathcal{S}_k^*) \oplus^{\perp} \operatorname{Im}(\mathcal{S}_{k+1})$$

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 fix a vector $(u_{1}, \ldots, u_{d})$ in $\mathbb{R}^{d}$ with $\|u\| = 1$, and define $g(M) = \|M \cdot u\|$. Let $X = (\varepsilon_{ij})_{1 \leqslant i \leqslant k, 1 \leqslant j \leqslant d}$ be a random variable taking values in $\mathcal{M}_{k,d}(\mathbb{R})$, whose coefficients $\varepsilon_{ij}$ are independent Rademacher random variables.
Show that, for every strictly positive real number $t$
$$\mathbb{P}(|g(X) - \sqrt{k}| \geqslant t) \leqslant 4 \exp(4) \exp\left(-\frac{1}{16} t^{2}\right)$$

Let $T$ be an upper triangular matrix, $A = N + T$ and $k \geqslant 0$. Show that $A$ is similar to a matrix $L$ whose diagonal coefficients of order $k$ are all equal and satisfying $\forall i \in \llbracket -1, k-1 \rrbracket, L^{(i)} = A^{(i)}$.

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 fix a vector $(u_{1}, \ldots, u_{d})$ in $\mathbb{R}^{d}$ with $\|u\| = 1$, and define $g(M) = \|M \cdot u\|$. Let $X = (\varepsilon_{ij})_{1 \leqslant i \leqslant k, 1 \leqslant j \leqslant d}$ be a random variable taking values in $\mathcal{M}_{k,d}(\mathbb{R})$, whose coefficients $\varepsilon_{ij}$ are independent Rademacher random variables. We set $A_{k} = \frac{X}{\sqrt{k}}$. Let $\varepsilon$ be in $]0, 1[$ and $\delta$ be in $]0, 1/2[$. We assume that $k \geqslant 160 \frac{\ln(1/\delta)}{\varepsilon^{2}}$.
Show that, for every unit vector $u$ in $\mathbb{R}^{d}$:
$$\mathbb{P}\left(\left|\left\|A_{k} \cdot u\right\| - 1\right| > \varepsilon\right) < \delta$$

Deduce that every cyclic matrix is similar to a Toeplitz matrix.

Let $h$ be a function from $\mathbb{R}$ to $\mathbb{R}$, continuous and $2\pi$-periodic on $\mathbb{R}$. We seek to solve the Dirichlet problem on the unit disk; we need to determine the function or functions $f$ defined and continuous on $\overline{D(0,1)}$, of class $\mathcal{C}^2$ on $D(0,1)$, and such that $$\begin{cases} \Delta f = 0 \text{ on } D(0,1) \\ \forall t \in \mathbb{R}, f(\cos(t), \sin(t)) = h(t) \end{cases}$$ For this, we set, for any complex number $z$ such that $|z| < 1$, $$g(z) = \frac{1}{2\pi} \int_0^{2\pi} h(t) \mathcal{P}(t,z) \, \mathrm{d}t \quad \text{where} \quad \mathcal{P}(t,z) = \operatorname{Re}\left(\frac{\mathrm{e}^{\mathrm{i}t} + z}{\mathrm{e}^{\mathrm{i}t} - z}\right)$$ Show the existence and uniqueness of the solution to the Dirichlet problem studied in this part.

We set $A_{k} = \frac{X}{\sqrt{k}}$ where $X = (\varepsilon_{ij})_{1 \leqslant i \leqslant k, 1 \leqslant j \leqslant d}$ is a random variable taking values in $\mathcal{M}_{k,d}(\mathbb{R})$, whose coefficients $\varepsilon_{ij}$ are independent Rademacher random variables. Let $\varepsilon$ be in $]0, 1[$ and $\delta$ be in $]0, 1/2[$. We assume that $k \geqslant 160 \frac{\ln(1/\delta)}{\varepsilon^{2}}$. Let $v_{1}, \ldots, v_{N}$ be distinct vectors in $\mathbb{R}^{d}$. For every $(i, j) \in \llbracket 1, N \rrbracket^{2}$ such that $i < j$ we denote by $E_{ij}$ the event
$$(1 - \varepsilon) \|v_{i} - v_{j}\| \leqslant \|A_{k} \cdot v_{i} - A_{k} \cdot v_{j}\| \leqslant (1 + \varepsilon) \|v_{i} - v_{j}\|$$
Show that $\mathbb{P}\left(\overline{E_{ij}}\right) < \delta$, where $\overline{E_{ij}}$ denotes the complementary event of $E_{ij}$.

We set $A_{k} = \frac{X}{\sqrt{k}}$ where $X = (\varepsilon_{ij})_{1 \leqslant i \leqslant k, 1 \leqslant j \leqslant d}$ is a random variable taking values in $\mathcal{M}_{k,d}(\mathbb{R})$, whose coefficients $\varepsilon_{ij}$ are independent Rademacher random variables. Let $\varepsilon$ be in $]0, 1[$ and $\delta$ be in $]0, 1/2[$. We assume that $k \geqslant 160 \frac{\ln(1/\delta)}{\varepsilon^{2}}$. Let $v_{1}, \ldots, v_{N}$ be distinct vectors in $\mathbb{R}^{d}$. For every $(i, j) \in \llbracket 1, N \rrbracket^{2}$ such that $i < j$ we denote by $E_{ij}$ the event
$$(1 - \varepsilon) \|v_{i} - v_{j}\| \leqslant \|A_{k} \cdot v_{i} - A_{k} \cdot v_{j}\| \leqslant (1 + \varepsilon) \|v_{i} - v_{j}\|$$
Deduce that $\mathbb{P}\left(\bigcap_{1 \leqslant i < j \leqslant N} E_{ij}\right) \geqslant 1 - \frac{N(N-1)}{2} \delta$.

We set $A_{k} = \frac{X}{\sqrt{k}}$ where $X = (\varepsilon_{ij})_{1 \leqslant i \leqslant k, 1 \leqslant j \leqslant d}$ is a random variable taking values in $\mathcal{M}_{k,d}(\mathbb{R})$, whose coefficients $\varepsilon_{ij}$ are independent Rademacher random variables. Let $\varepsilon$ be in $]0, 1[$ and $\delta$ be in $]0, 1/2[$. We assume that $k \geqslant 160 \frac{\ln(1/\delta)}{\varepsilon^{2}}$. Let $v_{1}, \ldots, v_{N}$ be distinct vectors in $\mathbb{R}^{d}$. For every $(i, j) \in \llbracket 1, N \rrbracket^{2}$ such that $i < j$ we denote by $E_{ij}$ the event
$$(1 - \varepsilon) \|v_{i} - v_{j}\| \leqslant \|A_{k} \cdot v_{i} - A_{k} \cdot v_{j}\| \leqslant (1 + \varepsilon) \|v_{i} - v_{j}\|$$
Deduce the Johnson-Lindenstrauss theorem: there exists an absolute constant $c$ strictly positive such that for any natural integers $N$ and $d$ greater than or equal to 2, and for any distinct $v_{1}, \ldots, v_{N}$ in $\mathbb{R}^{d}$, it suffices that
$$k \geqslant c \frac{\ln(N)}{\varepsilon^{2}}$$
for there to exist an $\varepsilon$-isometry $f : \mathbb{R}^{d} \rightarrow \mathbb{R}^{k}$ for $v_{1}, \ldots, v_{N}$.

Let $A \in \mathcal { S } _ { N } ( \mathbb { R } )$. Show that $A \in \mathcal { S } _ { N } ^ { + } ( \mathbb { R } )$ if and only if the eigenvalues of $A$ are all strictly positive real numbers.

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

Let $A \in \mathcal { S } _ { N } ( \mathbb { R } )$ and let $P \in \mathbb { R } [ X ]$ be a polynomial. Show that $P ( A ) \in \mathcal { S } _ { N } ( \mathbb { R } )$ and specify the eigenvalues and eigenvectors of $P ( A )$ in terms of those of $A$.

Let $A \in \mathcal { S } _ { N } ^ { + } ( \mathbb { R } )$. We denote by $0 < \lambda _ { 1 } < \cdots < \lambda _ { d }$ the $d$ eigenvalues of $A$ (distinct pairwise) and $F _ { 1 } , \ldots , F _ { d }$ the associated eigenspaces. We consider the linear map from $\mathbb { R } ^ { N }$ to $\mathbb { R } ^ { N }$: $$x \mapsto \sum _ { i = 1 } ^ { d } \lambda _ { i } ^ { 1 / 2 } p _ { F _ { i } } ( x )$$ where $p _ { F _ { i } }$ is the orthogonal projection (for the canonical inner product) onto $F _ { i }$. We denote by $A ^ { 1 / 2 }$ the matrix associated with this linear map in the canonical basis.
a) We write $A = U D U ^ { T }$, where $D \in \mathcal { M } _ { N } ( \mathbb { R } )$ is the diagonal matrix containing the eigenvalues of $A$ in increasing order, with their multiplicities, and $U$ an orthogonal matrix. We denote by $D ^ { 1 / 2 }$ the diagonal matrix whose diagonal coefficients are the square roots of those of $D$. Show that $A ^ { 1 / 2 } = U D ^ { 1 / 2 } U ^ { T }$.
b) Show that $A ^ { 1 / 2 } \in \mathcal { S } _ { N } ^ { + } ( \mathbb { R } )$, that $A ^ { 1 / 2 } A ^ { 1 / 2 } = A$, and that $A ^ { 1 / 2 }$ commutes with $A$.
c) Show that, for all $x \in \mathbb { R } ^ { N } , \| x \| _ { A } = \left\| A ^ { 1 / 2 } x \right\|$, where $\| x \| _ { A }$ is the norm defined in question 4.

Let $A \in \mathcal { S } _ { N } ^ { + } ( \mathbb { R } )$. We are given $b \in \mathbb { R } ^ { N }$ and we denote by $\tilde { x } \in \mathbb { R } ^ { N }$ the unique vector satisfying $A \tilde { x } = b$. We are given a vector $x _ { 0 } \in \mathbb { R } ^ { N }$, different from $\tilde { x }$, and we denote by $r _ { 0 } = b - A x _ { 0 }$. We set $H _ { 0 } = \{ 0 \}$ and for $k \geq 1$, $$H _ { k } = \left\{ P ( A ) r _ { 0 } \mid P \in \mathbb { R } [ X ] , \operatorname { deg } ( P ) \leq k - 1 \right\}$$ where $\operatorname { deg } ( P ) \in \mathbb { N }$ denotes the degree of the polynomial $P$.
Show that the $H _ { k }$ form a sequence of vector subspaces of $\mathbb { R } ^ { N }$, and show that $H _ { k } \subset H _ { k + 1 }$ for all $k \in \mathbb { N }$.
a) Show that there necessarily exists $k$ such that $H _ { k + 1 } = H _ { k }$. We then denote by $m$ the smallest integer $k$ such that $H _ { k + 1 } = H _ { k }$.
b) Show that $\operatorname { dim } \left( H _ { k } \right) = m$ for all $k \geq m$, and that $\operatorname { dim } \left( H _ { k } \right) = k$ for $k \leq m$.

Let $A \in \mathcal { S } _ { N } ^ { + } ( \mathbb { R } )$. We are given $b \in \mathbb { R } ^ { N }$ and we denote by $\tilde { x } \in \mathbb { R } ^ { N }$ the unique vector satisfying $A \tilde { x } = b$. We are given a vector $x _ { 0 } \in \mathbb { R } ^ { N }$, different from $\tilde { x }$, and we denote by $r _ { 0 } = b - A x _ { 0 }$. We set $H _ { 0 } = \{ 0 \}$ and for $k \geq 1$, $$H _ { k } = \left\{ P ( A ) r _ { 0 } \mid P \in \mathbb { R } [ X ] , \operatorname { deg } ( P ) \leq k - 1 \right\}$$ We denote by $m$ the smallest integer $k$ such that $H _ { k + 1 } = H _ { k }$. We denote by $d$ the number of distinct eigenvalues of $A$.
a) In the special case where $r _ { 0 }$ is an eigenvector of $A$, show that the integer $m$ is equal to 1.
b) In the general case, show that $m$ is less than or equal to $d$.
c) For any integer $n$ between 1 and $d$, construct an $x _ { 0 }$ such that the integer $m$ is equal to $n$.
d) Show that the set of $x _ { 0 }$ for which the dimension $m$ is exactly equal to $d$ is the complement of a finite union of sets of the form $\tilde { x } + E$, where $E$ is a vector space of dimension less than or equal to $N - 1$.

Let $A \in \mathcal { S } _ { N } ^ { + } ( \mathbb { R } )$. We are given $b \in \mathbb { R } ^ { N }$ and we denote by $\tilde { x } \in \mathbb { R } ^ { N }$ the unique vector satisfying $A \tilde { x } = b$. We are given a vector $x _ { 0 } \in \mathbb { R } ^ { N }$, different from $\tilde { x }$, and we denote by $r _ { 0 } = b - A x _ { 0 }$. We set $H _ { 0 } = \{ 0 \}$ and for $k \geq 1$, $$H _ { k } = \left\{ P ( A ) r _ { 0 } \mid P \in \mathbb { R } [ X ] , \operatorname { deg } ( P ) \leq k - 1 \right\}$$ We denote by $m$ the smallest integer $k$ such that $H _ { k + 1 } = H _ { k }$.
Show that there exists a polynomial $Q$ of degree $m$ such that $Q ( A ) e _ { 0 } = 0$, where $e _ { 0 } = x _ { 0 } - \tilde { x }$.

Let $A \in \mathcal { S } _ { N } ^ { + } ( \mathbb { R } )$. We are given $b \in \mathbb { R } ^ { N }$ and we denote by $\tilde { x } \in \mathbb { R } ^ { N }$ the unique vector satisfying $A \tilde { x } = b$. We are given a vector $x _ { 0 } \in \mathbb { R } ^ { N }$, different from $\tilde { x }$, and we denote by $r _ { 0 } = b - A x _ { 0 }$. We denote by $m$ the smallest integer $k$ such that $H _ { k + 1 } = H _ { k }$, and $Q$ is the polynomial of degree $m$ from question 9 such that $Q ( A ) e _ { 0 } = 0$ where $e _ { 0 } = x _ { 0 } - \tilde { x }$.
Show that the polynomial $Q$ satisfies $Q ( 0 ) \neq 0$.

Let $A \in \mathcal { S } _ { N } ^ { + } ( \mathbb { R } )$. We are given $b \in \mathbb { R } ^ { N }$ and we denote by $\tilde { x } \in \mathbb { R } ^ { N }$ the unique vector satisfying $A \tilde { x } = b$. We are given a vector $x _ { 0 } \in \mathbb { R } ^ { N }$, different from $\tilde { x }$, and we denote by $r _ { 0 } = b - A x _ { 0 }$. We set $H _ { 0 } = \{ 0 \}$ and for $k \geq 1$, $$H _ { k } = \left\{ P ( A ) r _ { 0 } \mid P \in \mathbb { R } [ X ] , \operatorname { deg } ( P ) \leq k - 1 \right\}$$ We denote by $m$ the smallest integer $k$ such that $H _ { k + 1 } = H _ { k }$. We define $x _ { 0 } + H _ { k }$ as the subset of points of $\mathbb { R } ^ { N }$ of the form $x _ { 0 } + x$ where $x$ ranges over the vector space $H _ { k }$.
a) Show that $\tilde { x } \in x _ { 0 } + H _ { m }$.
b) Show that, for all $k \in \{ 0 , \ldots , m - 1 \}$, we have $\tilde { x } \notin x _ { 0 } + H _ { k }$.

We introduce the map $$\begin{aligned} J : \mathbb { R } ^ { N } & \rightarrow \mathbb { R } \\ x & \mapsto \frac { 1 } { 2 } \langle x , A x \rangle - \langle b , x \rangle \end{aligned}$$ where $A \in \mathcal { S } _ { N } ^ { + } ( \mathbb { R } )$, $b \in \mathbb { R } ^ { N }$, and $\tilde { x }$ is the unique vector satisfying $A \tilde { x } = b$.
For all $x \in \mathbb { R } ^ { N }$, express $\| x - \tilde { x } \| _ { A } ^ { 2 } = \langle x - \tilde { x } , A ( x - \tilde { x } ) \rangle$ in terms of $J ( \tilde { x } )$ and $J ( x )$ and deduce that $\tilde { x }$ is the unique minimizer of $J$ on $\mathbb { R } ^ { N }$, that is, $J ( \tilde { x } ) \leq J ( x )$ for all $x \in \mathbb { R } ^ { N }$, and that $\tilde { x }$ is the only point satisfying this property.

We introduce the map $$\begin{aligned} J : \mathbb { R } ^ { N } & \rightarrow \mathbb { R } \\ x & \mapsto \frac { 1 } { 2 } \langle x , A x \rangle - \langle b , x \rangle \end{aligned}$$ where $A \in \mathcal { S } _ { N } ^ { + } ( \mathbb { R } )$, $b \in \mathbb { R } ^ { N }$. We set $H _ { 0 } = \{ 0 \}$ and for $k \geq 1$, $$H _ { k } = \left\{ P ( A ) r _ { 0 } \mid P \in \mathbb { R } [ X ] , \operatorname { deg } ( P ) \leq k - 1 \right\}$$ and $x _ { 0 } + H _ { k }$ denotes the subset of points of $\mathbb { R } ^ { N }$ of the form $x _ { 0 } + x$ where $x$ ranges over $H _ { k }$.
Show that $J$ admits a unique minimizer on the subset $x _ { 0 } + H _ { k }$, for any $k \in \mathbb { N }$.

We introduce the map $$\begin{aligned} J : \mathbb { R } ^ { N } & \rightarrow \mathbb { R } \\ x & \mapsto \frac { 1 } { 2 } \langle x , A x \rangle - \langle b , x \rangle \end{aligned}$$ where $A \in \mathcal { S } _ { N } ^ { + } ( \mathbb { R } )$, $b \in \mathbb { R } ^ { N }$, and $\tilde { x }$ is the unique vector satisfying $A \tilde { x } = b$. We denote by $x _ { k }$ the minimizer of $J$ on $x _ { 0 } + H _ { k }$.
Show that $x _ { k }$ identifies with the projection onto $x _ { 0 } + H _ { k }$ for the norm $\| \cdot \| _ { A }$ associated with the matrix $A$, that is, $$\left\| x _ { k } - \tilde { x } \right\| _ { A } = \min _ { x \in x _ { 0 } + H _ { k } } \| x - \tilde { x } \| _ { A }$$

We keep the notations from Parts II and III. We denote $r _ { k } = b - A x _ { k }$, $e _ { k } = x _ { k } - \tilde { x }$, and note that $r _ { k } = - A e _ { k }$. We denote by $m$ the smallest integer $k$ such that $H _ { k + 1 } = H _ { k }$.
Show that $e _ { k } \neq 0$ for $k \in \{ 0 , \ldots , m - 1 \}$, and that $e _ { k } = 0$ for $k \geq m$.

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