Let $\pi$ be the endomorphism of $\mathbb{R}^n$ whose representation in the canonical basis is the matrix $P = I_n - \frac{1}{n}J$, where $J = Z^t Z$ and $Z = \left(\begin{array}{c}1\\ \vdots \\ 1\end{array}\right) \in \mathcal{M}_{n,1}(\mathbb{R})$. Show that $\pi$ is an orthogonal projector and specify its characteristic elements.
We consider the endomorphism $\Phi$ of $\mathcal{M}_n(\mathbb{R})$ defined by: $$\forall M \in \mathcal{M}_n(\mathbb{R}), \quad \Phi(M) = PMP$$ where $P = I_n - \frac{1}{n}J$. 1) Show that $\Phi$ is an orthogonal projector in the Euclidean space $(\mathcal{M}_n(\mathbb{R}), (\cdot \mid \cdot))$. 2) Show that $\operatorname{Im}\Phi = \left\{M \in \mathcal{M}_n(\mathbb{R}) \mid MZ = 0 \text{ and } {}^t MZ = 0\right\}$.
Let $U_1, U_2, \cdots, U_n$, $n$ elements of $\mathbb{R}^p$ satisfying $\sum_{i=1}^n U_i = 0$. We define the matrix of squared mutual distances $M = \left(\|U_i - U_j\|^2\right)_{(i,j) \in \llbracket 1,n\rrbracket^2} \in \mathcal{S}_n(\mathbb{R})$. We denote $U$ the matrix of $\mathcal{M}_{p,n}(\mathbb{R})$ having as column vectors the elements $U_1, U_2, \cdots, U_n$. Show that ${}^t UU = -\frac{1}{2}\Phi(M)$.
Let $U_1, U_2, \cdots, U_n$, $n$ elements of $\mathbb{R}^p$ satisfying $\sum_{i=1}^n U_i = 0$. We define the matrix of squared mutual distances $M = \left(\|U_i - U_j\|^2\right)_{(i,j) \in \llbracket 1,n\rrbracket^2} \in \mathcal{S}_n(\mathbb{R})$. It has been shown that ${}^t UU = -\frac{1}{2}\Phi(M)$. Deduce, for every pair $(i,j) \in \llbracket 1,n\rrbracket^2$, an expression for the inner product $\langle U_i, U_j\rangle = {}^t U_i U_j$ as a function of $$\alpha_{ij} = -\frac{1}{n}\left(S(M)_i + S(M)_j\right) + \frac{1}{n^2}\sigma(M)$$ and of $m_{ij}$ (Torgerson relation).
Let $M = (m_{ij})_{(i,j) \in \llbracket 1,n\rrbracket^2} \in \mathcal{S}_n(\mathbb{R})$ such that for every pair $(i,j) \in \llbracket 1,n\rrbracket^2$, $m_{ij} \geqslant 0$ and $m_{ii} = 0$. We assume in this question that there exist $U_1, U_2, \cdots, U_n$ elements of $\mathbb{R}^p$ such that for every $(i,j) \in \llbracket 1,n\rrbracket^2$, $m_{ij} = \|U_i - U_j\|^2$. 1) Show that the eigenvalues of $\Phi(M)$ are all real and non-positive. 2) We further assume (if necessary by performing a translation) that the $(U_i)_{i \in \llbracket 1,n\rrbracket}$ are centered, that is, $\sum_{i=1}^n U_i = 0$. Show that $\operatorname{rg}(U) = \operatorname{rg}(U_1 | U_2 | \cdots | U_n) = \operatorname{rg}(\Phi(M))$ and that $p \geqslant \operatorname{rg}(\Phi(M))$.
Let $M = (m_{ij})_{(i,j) \in \llbracket 1,n\rrbracket^2} \in \mathcal{S}_n(\mathbb{R})$ such that for every pair $(i,j) \in \llbracket 1,n\rrbracket^2$, $m_{ij} \geqslant 0$ and $m_{ii} = 0$. Conversely, we assume that the eigenvalues of $\Phi(M)$ are all non-positive and we set $\Psi(M) = -\frac{1}{2}\Phi(M)$ and $r = \operatorname{rg}(\Psi(M))$. 1) Show that there exists a matrix $U \in \mathcal{M}_{r,n}(\mathbb{R})$ such that ${}^t UU = \Psi(M)$. 2) We denote $U_1, U_2, \cdots, U_n$ the columns of the matrix $U$. We seek to show that for every $(i,j) \in \llbracket 1,n\rrbracket^2$, $m_{ij} = \|U_i - U_j\|^2$. a) Show that the $(U_i)$ are centered, that is, $\sum_{i=1}^n U_i = 0$. b) Show that the matrix $N = (n_{ij})$ defined by: $$\forall (i,j) \in \llbracket 1,n\rrbracket^2, \quad n_{ij} = \|U_i - U_j\|^2$$ satisfies $\Psi(N) = \Psi(M)$. c) Show that $M = N$ and conclude.
We consider four distinct points $A, B, C$ and $D$ in the canonical Euclidean space $\mathbb{R}^3$ such that $AB = BC = CD = DA = 1$, $AC = a > 0$ and $BD = b > 0$. We assume that the four points $A, B, C$ and $D$ exist and are coplanar. What relation do $a$ and $b$ then satisfy?
We consider four distinct points $A, B, C$ and $D$ in the canonical Euclidean space $\mathbb{R}^3$ such that $AB = BC = CD = DA = 1$, $AC = a > 0$ and $BD = b > 0$. We assume that the four distinct points $A, B, C$ and $D$ are not coplanar. We denote $I$ the midpoint of $[AC]$ and $J$ the midpoint of $[BD]$. a) Show that $(IJ)$ is the common perpendicular to the lines $(AC)$ and $(BD)$. b) By projecting the points $B$ and $D$ onto the plane containing $(AC)$ and perpendicular to $(IJ)$, show that $a^2 + b^2 < 4$.
We consider four distinct points $A, B, C$ and $D$ in the canonical Euclidean space $\mathbb{R}^3$ such that $AB = BC = CD = DA = 1$, $AC = a > 0$ and $BD = b > 0$. Show that if strictly positive reals $a$ and $b$ satisfy the relation $a^2 + b^2 \leqslant 4$, then there indeed exist four distinct points $A, B, C$ and $D$ in the canonical Euclidean space $\mathbb{R}^3$ satisfying $AB = BC = CD = DA = 1$, $AC = a$ and $BD = b$.
We consider four points $U_1, U_2, U_3, U_4$ in $\mathbb{R}^3$ satisfying $U_1U_2 = U_2U_3 = U_3U_4 = U_4U_1 = 1$, $U_1U_3 = a$ and $U_2U_4 = b$. We use the notations of the previous parts with $n = 4$. We set $M = \left(\|U_i - U_j\|^2\right)_{(i,j) \in \llbracket 1,4\rrbracket^2} \in \mathcal{S}_4(\mathbb{R})$. Write the matrix $M$ then calculate $S(M)$ and $\sigma(M)$.
We consider four points $U_1, U_2, U_3, U_4$ in $\mathbb{R}^3$ satisfying $U_1U_2 = U_2U_3 = U_3U_4 = U_4U_1 = 1$, $U_1U_3 = a$ and $U_2U_4 = b$. We set $\Psi(M) = -\frac{1}{2}\Phi(M)$. Show that the vectors $$\left(\begin{array}{r}1\\0\\-1\\0\end{array}\right), \left(\begin{array}{r}0\\1\\0\\-1\end{array}\right), \left(\begin{array}{r}-1\\1\\-1\\1\end{array}\right), \left(\begin{array}{l}1\\1\\1\\1\end{array}\right)$$ form a basis of eigenvectors of the matrix $\Psi(M)$ and determine the eigenvalues of the matrix $\Psi(M)$.
We consider four points $U_1, U_2, U_3, U_4$ in $\mathbb{R}^3$ satisfying $U_1U_2 = U_2U_3 = U_3U_4 = U_4U_1 = 1$, $U_1U_3 = a$ and $U_2U_4 = b$. We set $\Psi(M) = -\frac{1}{2}\Phi(M)$. Determine the rank of $\Psi(M)$ according to the values taken by $a$ and $b$.
We consider four points $U_1, U_2, U_3, U_4$ in $\mathbb{R}^3$ satisfying $U_1U_2 = U_2U_3 = U_3U_4 = U_4U_1 = 1$, $U_1U_3 = a$ and $U_2U_4 = b$. We set $\Psi(M) = -\frac{1}{2}\Phi(M)$. What equality do the reals $a$ and $b$ satisfy when the points $U_1, U_2, U_3$ and $U_4$ are coplanar?
We consider four points $U_1, U_2, U_3, U_4$ in $\mathbb{R}^3$ satisfying $U_1U_2 = U_2U_3 = U_3U_4 = U_4U_1 = 1$, $U_1U_3 = a$ and $U_2U_4 = b$. We set $\Psi(M) = -\frac{1}{2}\Phi(M)$. Conversely, if $a^2 + b^2 \leqslant 4$, give a family of points $U_1, U_2, U_3$ and $U_4$ satisfying the mutual distance constraints.
We consider a matrix $M = (m_{ij}) \in \mathcal{S}_n(\mathbb{R})$ such that for every $(i,j) \in \llbracket 1,n\rrbracket^2$, $m_{ij} \geqslant 0$ and $m_{ii} = 0$. We assume that $\Psi(M)$ has at least one strictly negative eigenvalue. We seek to prove that there exists a unique symmetric matrix $T_0$ with non-negative eigenvalues that minimizes $\|\Psi(M) - T\|_{\mathcal{M}_n(\mathbb{R})}$ when $T$ ranges over $\mathcal{S}_n^+(\mathbb{R})$. a) Show that $$\forall Q \in \mathcal{O}_n(\mathbb{R}), \forall A \in \mathcal{M}_n(\mathbb{R}), \quad \|{}^t QAQ\|_{\mathcal{M}_n(\mathbb{R})} = \|A\|_{\mathcal{M}_n(\mathbb{R})}$$ b) Justify the existence of a matrix $Q_0 \in \mathcal{O}_n(\mathbb{R})$ such that the matrix ${}^t Q_0 \Psi(M) Q_0$ is diagonal. c) Show that a necessary condition for $\|\Psi(M) - T_0\|_{\mathcal{M}_n(\mathbb{R})}$ to minimize $\|\Psi(M) - T\|_{\mathcal{M}_n(\mathbb{R})}$ when $T$ ranges over $\mathcal{S}_n^+(\mathbb{R})$ is that the matrix ${}^t Q_0 T_0 Q_0$ is diagonal. d) Prove the existence and uniqueness of the matrix $T_0$ sought.
We consider a matrix $M = (m_{ij}) \in \mathcal{S}_n(\mathbb{R})$ such that for every $(i,j) \in \llbracket 1,n\rrbracket^2$, $m_{ij} \geqslant 0$ and $m_{ii} = 0$. We assume that $\Psi(M)$ has at least one strictly negative eigenvalue. Let $T_0$ be the unique symmetric matrix with non-negative eigenvalues minimizing $\|\Psi(M) - T\|_{\mathcal{M}_n(\mathbb{R})}$ over $\mathcal{S}_n^+(\mathbb{R})$. We assume in this question that $T_0$ is non-zero. We want to show that there exists a minimal integer $p \in \llbracket 1, n-1\rrbracket$ that we will specify such that we can determine vectors $U_1, U_2, \cdots, U_n$ elements of $\mathbb{R}^p$ satisfying the condition $\sum_{i=1}^n U_i = 0$ and for which the matrix $\widetilde{M} = \left(\|U_i - U_j\|^2\right)_{(i,j) \in \llbracket 1,n\rrbracket^2}$ satisfies the relation $\Psi(\widetilde{M}) = T_0$. We use the notations of part II and denote $U = (U_1 | U_2 | \cdots | U_n)$. a) Show that the integer $p$ satisfies $p \geqslant \operatorname{rg}(T_0)$ and that $\operatorname{rg}(T_0) \in \llbracket 1, n-1\rrbracket$. b) Construct a matrix $U \in \mathcal{M}_{r,n}(\mathbb{R})$ such that ${}^t UU = T_0$ for $r = \operatorname{rg}(T_0)$. Hint. Assuming that ${}^t Q_0 T_0 Q_0$ is of the form $\left(\begin{array}{ll}\Delta & \\ & 0_{n-r}\end{array}\right)$ with $\Delta \in \mathcal{M}_r(\mathbb{R})$, diagonal with non-zero values, we will seek $U$ in the form $U = \left((\Delta_1)(0)\right) \times Q_0 \in \mathcal{M}_{r,n}(\mathbb{R})$ with $\Delta_1 \in \mathcal{M}_r(\mathbb{R})$, diagonal. c) Show that $\sum_{i=1}^n U_i = 0$ (we may study the vector $UZ$). d) Deduce that $\Psi(\widetilde{M}) = T_0$ with $\widetilde{M} = \left(\|U_i - U_j\|^2\right)_{(i,j) \in \llbracket 1,n\rrbracket^2}$ and conclude.
We set $\xi_i^j = \begin{cases}0 & \text{if } i = j \\ 1 & \text{otherwise}\end{cases}$ and $N_k = (m_{ij} + k\xi_i^j)$ with $k$ a strictly positive real number. Let $A \in \mathcal{M}_n(\mathbb{R})$. Show that the hyperplane $\mathcal{H}$ with normal vector $Z$ (and equation $x_1 + \cdots + x_n = 0$) is stable under the canonical endomorphism associated with the matrix $\Psi(A)$.
We set $\xi_i^j = \begin{cases}0 & \text{if } i = j \\ 1 & \text{otherwise}\end{cases}$ and $N_k = (m_{ij} + k\xi_i^j)$ with $k$ a strictly positive real number. Express the matrix $N_k$ as a function of the matrices $M, J, I_n$ and the real $k$.
We set $\xi_i^j = \begin{cases}0 & \text{if } i = j \\ 1 & \text{otherwise}\end{cases}$ and $N_k = (m_{ij} + k\xi_i^j)$ with $k$ a strictly positive real number. Show that there exists a minimal real $k_0$ that we will specify as a function of the eigenvalues of $\Psi(M)$, such that the matrix $\Psi(N_{k_0})$ has non-negative eigenvalues.
We set $D = (d_{ij})_{(i,j) \in \llbracket 1,n\rrbracket^2} = (\sqrt{m_{ij}})_{(i,j) \in \llbracket 1,n\rrbracket^2} \in \mathcal{M}_n(\mathbb{R})$ and $M_c = \left((d_{ij} + c\xi_i^j)^2\right)$ with $c > 0$, where $\xi_i^j = \begin{cases}0 & \text{if } i = j \\ 1 & \text{otherwise}\end{cases}$. Show that, for all $X \in \mathbb{R}^n$, $${}^t X \Psi(M_c) X = {}^t X \Psi(M) X + 2c\, {}^t X \Psi(D) X + \frac{c^2}{2}\, {}^t X P X$$
We set $D = (d_{ij})_{(i,j) \in \llbracket 1,n\rrbracket^2} = (\sqrt{m_{ij}})_{(i,j) \in \llbracket 1,n\rrbracket^2} \in \mathcal{M}_n(\mathbb{R})$ and $M_c = \left((d_{ij} + c\xi_i^j)^2\right)$ with $c > 0$. The hyperplane $\mathcal{H}$ has normal vector $Z$ and equation $x_1 + \cdots + x_n = 0$. Show that if $\lambda_{\min}$ and $\mu_{\min}$ denote the respective minimal eigenvalues of $\Psi(M)$ and $\Psi(D)$, then $$\forall X \in \mathcal{H}, \quad {}^t X \Psi(M) X \geqslant \lambda_{\min}\, {}^t XX \quad \text{and} \quad {}^t X \Psi(D) X \geqslant \mu_{\min}\, {}^t XX$$
We set $D = (d_{ij})_{(i,j) \in \llbracket 1,n\rrbracket^2} = (\sqrt{m_{ij}})_{(i,j) \in \llbracket 1,n\rrbracket^2} \in \mathcal{M}_n(\mathbb{R})$ and $M_c = \left((d_{ij} + c\xi_i^j)^2\right)$ with $c > 0$. Let $\lambda_{\min}$ and $\mu_{\min}$ denote the respective minimal eigenvalues of $\Psi(M)$ and $\Psi(D)$. Deduce that for $c = \widetilde{c} = -2\mu_{\min} + \sqrt{4\mu_{\min}^2 - 2\lambda_{\min}} > 0$, $\Psi(M_c)$ has non-negative eigenvalues and that for all $c > \widetilde{c}$ and for all non-zero vector $X \in \mathcal{H}$, ${}^t X \Psi(M_c) X > 0$.
We set $D = (d_{ij})_{(i,j) \in \llbracket 1,n\rrbracket^2} = (\sqrt{m_{ij}})_{(i,j) \in \llbracket 1,n\rrbracket^2} \in \mathcal{M}_n(\mathbb{R})$ and $M_c = \left((d_{ij} + c\xi_i^j)^2\right)$ with $c > 0$. We seek the minimal constant $c^* > 0$ (if it exists) satisfying:
$\Psi(M_{c^*})$ has non-negative eigenvalues,
for all $c > c^*$ and for all non-zero vector $X \in \mathcal{H}$, ${}^t X \Psi(M_c) X > 0$.
We know that $c^*$ is bounded above by $\widetilde{c}$. We consider $\mathcal{A} = \left\{X \in \mathcal{H} \mid \|X\| = 1 \text{ and } 4\left({}^t X \Psi(D) X\right)^2 - 2\, {}^t X \Psi(M) X \geqslant 0\right\}$ and we define the mapping $$\alpha: \begin{cases}\mathcal{A} \longrightarrow \mathbb{R} \\ X \longmapsto -2\, {}^t X \Psi(D) X + \sqrt{4\left({}^t X \Psi(D) X\right)^2 - 2\, {}^t X \Psi(M) X}\end{cases}$$ Show that there exists $X^* \in \mathcal{A}$ such that $\alpha(X^*) = \sup_{X \in \mathcal{A}} \alpha(X)$ and $\alpha(X^*) > 0$.
We set $D = (d_{ij})_{(i,j) \in \llbracket 1,n\rrbracket^2} = (\sqrt{m_{ij}})_{(i,j) \in \llbracket 1,n\rrbracket^2} \in \mathcal{M}_n(\mathbb{R})$ and $M_c = \left((d_{ij} + c\xi_i^j)^2\right)$ with $c > 0$. Let $X^* \in \mathcal{A}$ be such that $\alpha(X^*) = \sup_{X \in \mathcal{A}} \alpha(X) > 0$, and denote $\alpha^* = \alpha(X^*)$. Show that:
${}^t X^* \Psi(M_{\alpha^*}) X^* = 0$,
$\Psi(M_{\alpha^*})$ has non-negative eigenvalues,
for all $c > \alpha^*$ and for all non-zero vector $X \in \mathcal{H}$, ${}^t X \Psi(M_c) X > 0$.
We set $D = (d_{ij})_{(i,j) \in \llbracket 1,n\rrbracket^2} = (\sqrt{m_{ij}})_{(i,j) \in \llbracket 1,n\rrbracket^2} \in \mathcal{M}_n(\mathbb{R})$ and $M_c = \left((d_{ij} + c\xi_i^j)^2\right)$ with $c > 0$. Let $c^* = \alpha^*$ be the minimal constant found previously, and $X^*$ the associated vector. a) Show that $\Psi(M_{c^*}) X^* = 0$. We set $Y^* = \frac{2}{c^*} \Psi(M) X^*$. b) Show that the column vector $\binom{Y^*}{X^*}$ is an eigenvector of the $2n \times 2n$ matrix $\left(\begin{array}{cc}0 & 2\Psi(M) \\ -I_n & -4\Psi(D)\end{array}\right)$ and that $c^*$ is an eigenvalue of this matrix.
We set $D = (d_{ij})_{(i,j) \in \llbracket 1,n\rrbracket^2} = (\sqrt{m_{ij}})_{(i,j) \in \llbracket 1,n\rrbracket^2} \in \mathcal{M}_n(\mathbb{R})$ and $M_c = \left((d_{ij} + c\xi_i^j)^2\right)$ with $c > 0$. We consider $\gamma$ a real eigenvalue of the matrix $\left(\begin{array}{cc}0 & 2\Psi(M) \\ -I_n & -4\Psi(D)\end{array}\right)$ and $\binom{X_1}{X_2}$ an associated eigenvector. a) Show that ${}^t X_2 \Psi(M_\gamma) X_2 = 0$ and that $X_2 \neq 0$. Conclude that $\gamma \leqslant c^*$. b) What conclusion do we draw from this on the calculation of the smallest additive constant $c^*$?