&\leq \left(\max\limits_{j \in [d]} \left|\frac{1}{\sigma_j^2}\right| \right)\|\hat{\Sigma} - \Sigma\|_2 + \sqrt{d} \left(\max\limits_{i,j \in [d]} \left|\frac{1}{\hat{\sigma}_{i}\hat{\sigma}_{j}} - \frac{1}{\sigma_i \sigma_j} \right| \right)\|\Sigma\|_2 + \sqrt{d} \left(\max\limits_{i,j \in [d]} \left|\frac{1}{\hat{\sigma}_{i}\hat{\sigma}_{j}} - \frac{1}{\sigma_i \sigma_j} \right| \right)\|\hat{\Sigma} - \Sigma\|_2  \\
& \leq \frac{1}{\sigma_\mathrm{min}^2} \|\hat{\Sigma} - \Sigma\|_2 + \frac{\sqrt{d}}{\sigma_\mathrm{min}^2} \left(\|D^{1/2}\hat{D}^{-1/2} - I\|_2 \|D^{1/2}\hat{D}^{-1/2}\|_2 + \|D^{1/2}\hat{D}^{-1/2} - I\|_2 \right) + \\
& \quad \quad + \frac{\sqrt{d}}{\sigma_\mathrm{min}^2} \left(\|D^{1/2}\hat{D}^{-1/2} - I\|_2 \|D^{1/2}\hat{D}^{-1/2}\|_2 + \|D^{1/2}\hat{D}^{-1/2} - I\|_2 \right) \|\hat{\Sigma} - \Sigma\|_2 \\
& \leq C_1 \frac{\nu^2}{\sigma_\mathrm{min}^2} \left( \sqrt{\frac{d + \log(4/t)}{n}} \vee \frac{d + \log(4/t)}{n}\right) + C_2 \frac{\nu^2}{\sigma^4_{\mathrm{min}}} \|\Sigma\|_2 \sqrt{\frac{d \log(d/t)}{n}}  \\
& \quad \quad + C_3 \frac{\nu^4}{\sigma^4_{\mathrm{min}}} \left( \sqrt{\frac{d + \log(4/t)}{n}} \vee \frac{d + \log(4/t)}{n} \right) \sqrt{\frac{d \log(d/t)}{n}} \\
& \leq C_1 \frac{\nu^2}{\sigma_\mathrm{min}^2} \left( \sqrt{\frac{d + \log(1/t)}{n}} \vee \frac{d + \log(1/t)}{n}\right) + C_2 \frac{\nu^4}{\sigma^4_{\mathrm{min}}} \sqrt{\frac{d \log(d/t)}{n}}  \\
& \quad \quad + C_3 \frac{\nu^4}{\sigma^4_{\mathrm{min}}} \left( \sqrt{\frac{d + \log(1/t)}{n}} \vee \frac{d + \log(1/t)}{n} \right) \sqrt{\frac{d \log(d/t)}{n}}
\end{align*}

with probability $1-t$, due to the fact that $\|\Sigma\|_2 \leq \nu^2$.

We aim at finding a random threshold $C_{\alpha}(\mathcal{X}_1)$ depending on the first part of the data $\mathcal{X}_1$ such that $\mathbb{P}_{H_0} \left(V(\hat{\sigma}_{\mathbb{S}}^2) + \hat{R}_2 \geq C_{\alpha}(\mathcal{X}_1) \right) \leq \alpha$, and since

\[
\mathbb{P}_{H_0} \left(V(\hat{\sigma}_{\mathbb{S}}^2) + \hat{R}_2 \geq C_{\alpha}(\mathcal{X}_1) \right) \leq \mathbb{P}_{H_0} \left(V(\hat{\sigma}_{\mathbb{S}}^2) \geq C_{\alpha}(\mathcal{X}_1)/2 \right)+\mathbb{P}_{H_0} \left(\hat{R}_2 \geq C_{\alpha}(\mathcal{X}_1) \right),
\]

we can control the first term as in Theorem <ref>, while for the second one it is sufficient to choose $C_{\alpha}(\mathcal{X}_1)$ such that

\[
\mathbb{P}_{H_0} \left(\hat{R}_2 \geq C_{\alpha}(\mathcal{X}_1)/2 \right) = \mathbb{P}_{H_0} \left( - \frac{1}{d} \langle \hat{X}^{(1)}_{\mathbb{S}}, \hat{\Sigma}_{\mathbb{S}}^{(2)} \rangle_{\mathbb{S}} \geq C_{\alpha}(\mathcal{X}_1)/2 \right) \leq \alpha/2.
\]

Using Holder's inequality for sequences of matrices, we have

\begin{align*}
\mathbb{P}_{H_0} \left( - \frac{1}{d} \langle \hat{X}^{(1)}_{\mathbb{S}}, \hat{\Sigma}_{\mathbb{S}}^{(2)} \rangle_{\mathbb{S}} \geq C_{\alpha}(\mathcal{X}_1)/2 \right) &\leq  \mathbb{P}_{H_0} \left( - \frac{1}{d} \langle \hat{X}^{(1)}_{\mathbb{S}}, \hat{\Sigma}_{\mathbb{S}}^{(2)} -  \Sigma_{\mathbb{S}} \rangle_{\mathbb{S}} \geq C_{\alpha}(\mathcal{X}_1)/2  \right) \\
&\leq \mathbb{P}_{H_0} \left(\bigl|\langle \hat{X}^{(1)}_{\mathbb{S}}, \hat{\Sigma}_{\mathbb{S}}^{(2)} -  \Sigma_{\mathbb{S}} \rangle_{\mathbb{S}} \bigr| \geq d C_{\alpha}(\mathcal{X}_1)/2  \right)  \\
& \leq \mathbb{P}_{H_0} \left( \| \hat{X}^{(1)}_{\mathbb{S}}\|_{*, \mathbb{S}} \|\hat{\Sigma}_{\mathbb{S}}^{(2)} -  \Sigma_{\mathbb{S}} \|_{2,\mathbb{S}} \geq d C_{\alpha}(\mathcal{X}_1)/2 \right).
\end{align*}

Thus, if we choose $C_{\alpha}(\mathcal{X}_1) := 2\epsilon \| \hat{X}^{(1)}_{\mathbb{S}}\|_{*, \mathbb{S}}/d$, with $\epsilon > 0$, it remains to choose $\epsilon$ such that

\[
\mathbb{P}_{H_0} \left(\|\hat{\Sigma}_{\mathbb{S}}^{(2)} -  \Sigma_{\mathbb{S}} \|_{2,\mathbb{S}} \geq \epsilon \right) =  \mathbb{P}_{H_0} \left(\max_{S \in \mathbb{S}}\|\hat{\Sigma}_{S}^{(2)} -  \Sigma_{S} \|_{2} \geq \epsilon \right) \leq \alpha/2.
\]

This can be done again using Proposition <ref>, and the result follows.

§.§ Proofs for Section <ref>

For the $d$-cycle, our measure of consistency of the variances is
\[
V(\Sigma_{\mathbb{S}}) =  1 - \min_{j \in [d]} \min_{S \in \{\{j-1,j \}, \{j,j+1 \} \}} \sigma^2_{S,j}.
\]

We will show that testing

\[
H_0: V(\Sigma_\mathbb{S}) = 0 \quad \text{ vs. } \quad H_1(\rho): V(\Sigma_\mathbb{S}) > \rho,
\]

requires at least a separation of the order $\sqrt{\log d/n}$, and since $T = V(\sigma^2_\mathbb{S}) + R(\Sigma_\mathbb{S})$, the statement would follow. Formally, referring to the same $\mathcal{P}_\mathbb{S}(0)$ and $\mathcal{P}_\mathbb{S}(\rho)$ defined in Section <ref>, this corresponds to assuming that $\Sigma_\mathbb{S}$ is always compatible, and constructing prior distributions just on $\{V(\sigma^2_\mathbb{S}) = 0\}$ and$ \{V(\sigma^2_\mathbb{S}) > \rho\}$.  We construct a lower bound to show that the minimax separation in this case is at least $c_1 \sqrt{\log d/\min_{i \in [d]} n_i}$, where $c_1 > 0$ is a universal constant. Let

\[
P_0 = \left(N^{\otimes n_1}\left(\boldsymbol{0}_{2}, \begin{pmatrix}
1 & 0 \\
0 & 1
\end{pmatrix}\right), \ldots, N^{\otimes n_d}\left(\boldsymbol{0}_{2}, \begin{pmatrix}
1 & 0 \\
0 & 1
\end{pmatrix}\right) \right),
\]

\begin{align*}
P_j & = \left(N^{\otimes n_1}\left(\boldsymbol{0}_{2}, \begin{pmatrix}
1 & 0 \\
0 & 1
\end{pmatrix}\right), \ldots, N^{\otimes n_j}\left(\boldsymbol{0}_{2}, \begin{pmatrix}
1 & 0 \\
0 & 1-\delta
\end{pmatrix}\right), \right.\\
& \hspace{4cm} \left. N^{\otimes n_{j+1}}\left(\boldsymbol{0}_{2}, \begin{pmatrix}
1+\delta & 0 \\
0 & 1
\end{pmatrix}\right),
\ldots, N^{\otimes n_d}\left(\boldsymbol{0}_{2}, \begin{pmatrix}
1 & 0 \\
0 & 1
\end{pmatrix}\right) \right),
\end{align*}

for $j \in [d]$, and $\delta > 0$. It is clear that each $P_j$ lies in $H_1(\delta)$, and that
\begin{align*}
\frac{dP_j}{dP_0}((x_{1,1},y_{1,1}), & \ldots,(x_{1,n_1},y_{1,n_1}),(x_{2,1},y_{2,1}),\ldots,(x_{d,n_d},y_{d,n_d}) \\
& =  \prod_{h \in [n_j]}\frac{1}{(1-\delta)^{1/2}}\exp\left\{-\frac{\delta}{2(1-\delta)} y_{j,h}^2\right\} \prod_{h \in [n_{j+1}]} \frac{1}{(1+\delta)^{1/2}}\exp\left\{\frac{\delta}{2(1+\delta)} x_{j+1,h}^2\right\}.
\end{align*}

Now, using the same strategy outlined in Section <ref>, it is enough to control the Total Variation distance

\begin{align*}
4 \operatorname{TV}\Bigg\{P_0, \frac{1}{d}\sum_{j=1}^d P_j \Bigg\}^2 & \leq \operatorname{\chi^2}\left(P_0, \frac{1}{d}\sum_{j=1}^d P_j \right) = \int \frac{\{\frac{1}{d}\sum_{j=1}^d dP_j \}^2}{dP_0} - 1 \\
& = \frac{1}{d^2}\sum_{j_1, j_2 =1}^d\int \frac{d P_{j_1} d P_{j_2}}{d P_0} - 1 = \frac{1}{d^2}\sum_{j_1, j_2 =1}^d \int \frac{d P_{j_1}}{d P_0}\frac{d P_{j_2}}{d P_0}d P_0  - 1.
\end{align*}

Now, it is easy to see that if $j_2 \notin \{j_1 - 1, j_1, j_1 + 1\}$, then $\int \frac{d P_{j_1}}{d P_0}\frac{d P_{j_2}}{d P_0}d P_0 = 1$. This happens to be the case also when $j_2 = j_1 \pm 1$, since, for $j_2 = j_1 - 1 =: j-1$, we have

\begin{align*}
\int \frac{d P_{j_1}}{d P_0}\frac{d P_{j_2}}{d P_0}d P_0 & = \int (1 - \delta)^{-n_{j-1}/2} (1-\delta^2)^{-n_j/2} (1 + \delta)^{-n_{j+1}/2} \prod_{h \in [n_{j-1}]} \exp\left\{-\frac{\delta}{2(1-\delta)} y_{j-1,h}^2\right\} \\
& \quad \quad \quad \times \prod_{h \in [n_j]} \exp\left\{\frac{\delta}{2(1+\delta)} x_{j,h}^2 -\frac{\delta}{2(1-\delta)} y_{j,h}^2\right\} \prod_{h \in [n_{j+1}]} \exp\left\{\frac{\delta}{2(1+\delta)} x_{j+1,h}^2 \right\} dP_0 \\
& = \int \prod_{h \in [n_{j-1}]} \frac{1}{2\pi(1-\delta)^{1/2}}\exp\left\{ - \frac{1}{2} \begin{pmatrix}
x_{j-1,h} \\ y_{j-1,h}
\end{pmatrix}^T \begin{pmatrix}
1 & 0 \\
0 & \frac{1}{1-\delta}
\end{pmatrix} \begin{pmatrix}
x_{j-1,h} \\ y_{j-1,h}
\end{pmatrix} \right\} d \boldsymbol{x}_{j-1} d \boldsymbol{y}_{j-1} \\
& \times \int \prod_{h \in [n_{j}]} \frac{1}{2\pi(1-\delta^2)^{1/2}}\exp\left\{ - \frac{1}{2} \begin{pmatrix}
x_{j,h} \\ y_{j,h}
\end{pmatrix}^T \begin{pmatrix}
\frac{1}{1+\delta} & 0 \\
0 & \frac{1}{1-\delta}
\end{pmatrix} \begin{pmatrix}
x_{j,h} \\ y_{j,h}
\end{pmatrix} \right\} d \boldsymbol{x}_{j} d \boldsymbol{y}_{j} \\
& \times \int \prod_{h \in [n_{j+1}]} \frac{1}{2\pi(1+\delta)^{1/2}}\exp\left\{ - \frac{1}{2} \begin{pmatrix}
x_{j+1,h} \\ y_{j+1,h}
\end{pmatrix}^T \begin{pmatrix}
\frac{1}{1+\delta} & 0 \\
0 & 1
\end{pmatrix} \begin{pmatrix}
x_{j+1,h} \\ y_{j+1,h}
\end{pmatrix} \right\} d \boldsymbol{x}_{j+1} d \boldsymbol{y}_{j+1},
\end{align*}

which is equal to $1$. Similarly, if $j_1 = j_2 = j$,

\begin{align*}
\int & \frac{d P_{j_1}}{d P_0}\frac{d P_{j_2}}{d P_0}d P_0  = \int (1-\delta)^{-n_j}(1+\delta)^{-n_{j+1}} \prod_{h \in [n_j]} \exp\left\{-\frac{\delta}{1-\delta} y_{j,h}^2\right\} \prod_{h \in [n_{j+1}]} \exp\left\{\frac{\delta}{1+\delta} x_{j+1,h}^2\right\} dP_0 \\
& = (1-\delta)^{-n_j}(1+\delta)^{-n_{j+1}} \int \prod_{h \in [n_{j}]} \frac{1}{2\pi}\exp\left\{ - \frac{1}{2} \begin{pmatrix}
x_{j,h} \\ y_{j,h}
\end{pmatrix}^T \begin{pmatrix}
1 & 0 \\
0 & \frac{1+\delta}{1-\delta}
\end{pmatrix} \begin{pmatrix}
x_{j,h} \\ y_{j,h}
\end{pmatrix} \right\} d \boldsymbol{x}_{j} d \boldsymbol{y}_{j} \\
& \quad\quad\quad \quad\quad\quad \times \int \prod_{h \in [n_{j+1}]} \frac{1}{2\pi}\exp\left\{ - \frac{1}{2} \begin{pmatrix}
x_{j+1,h} \\ y_{j+1,h}
\end{pmatrix}^T \begin{pmatrix}
\frac{1-\delta}{1+\delta} & 0 \\
0 & 1
\end{pmatrix} \begin{pmatrix}
x_{j,h} \\ y_{j,h}
\end{pmatrix} \right\} d \boldsymbol{x}_{j+1} d \boldsymbol{y}_{j+1} \\
& = (1-\delta^2)^{-n_j/2} (1-\delta^2)^{-n_{j+1}/2} \int \prod_{h \in [n_{j}]} \frac{1}{2\pi}\sqrt{\frac{1+\delta}{1-\delta}}\exp\left\{ - \frac{1}{2} \begin{pmatrix}
x_{j,h} \\ y_{j,h}
\end{pmatrix}^T \begin{pmatrix}
1 & 0 \\
0 & \frac{1+\delta}{1-\delta}
\end{pmatrix} \begin{pmatrix}
x_{j,h} \\ y_{j,h}
\end{pmatrix} \right\} d \boldsymbol{x}_{j} d \boldsymbol{y}_{j} \\
& \quad\quad\quad \quad\quad\quad \times \int \prod_{h \in [n_{j+1}]} \frac{1}{2\pi}\sqrt{\frac{1-\delta}{1+\delta}}\exp\left\{ - \frac{1}{2} \begin{pmatrix}
x_{j+1,h} \\ y_{j+1,h}
\end{pmatrix}^T \begin{pmatrix}
\frac{1-\delta}{1+\delta} & 0 \\
0 & 1
\end{pmatrix} \begin{pmatrix}
x_{j,h} \\ y_{j,h}
\end{pmatrix} \right\} d \boldsymbol{x}_{j+1} d \boldsymbol{y}_{j+1} \\
& = (1-\delta^2)^{-n_j/2} (1-\delta^2)^{-n_{j+1}/2} = (1-\delta^2)^{-(n_j+n_{j+1})/2}.
\end{align*}

It follows that

\begin{align*}
4 \operatorname{TV}\Bigg\{P_0, \frac{1}{d}\sum_{j=1}^d P_j \Bigg\}^2 & \leq \frac{1}{d^2}\sum_{j_1, j_2 =1}^d \int \frac{d P_{j_1}}{d P_0}\frac{d P_{j_2}}{d P_0}d P_0  - 1 \\
& = \frac{1}{d^2}\sum_{j_1, j_2 =1}^d \mathbbm{1}_{j_1 = j_2} (1-\delta^2)^{-(n_{j_1} + n_{j_1+1})/2} + \mathbbm{1}_{j_1 \neq j_2} \\
& = \frac{1}{d^2} \sum_{j =1}^d (1-\delta^2)^{-(n_j + n_{j+1})/2} - \frac{1}{d} \\
& \leq  \frac{1}{d^2} \sum_{j =1}^d \exp\{-(n_j + n_{j+1})\delta^2/2\} - \frac{1}{d},
\end{align*}

from which we see that $\operatorname{TV}\left\{P_0, \frac{1}{d}\sum_{j=1}^d P_j \right\} \leq 1/2$ if $\delta \leq \sqrt{2\log(1+d)/(n_j + n_{j+1})}$ for all $j \in [d]$. The above bound on the total variation distance demonstrates that we may choose $\delta=\sqrt{\log(1+d)/\min_j n_j}$, and hence that we have

\[
\rho^* \geq \delta = \biggl\{ \frac{\log(1+d)}{\min_j n_j} \biggr\}^{1/2},
\]

as claimed.

We will prove the result using the dual characterisation, which allows expressing $R(\Sigma_{\mathbb{S}_{d}})$ as
\[
1 - \frac{1}{d} \sup\{ \mathrm{tr}(\Sigma) : \Sigma \in \mathcal{P}^*, \Sigma_{11} = \cdots = \Sigma_{dd}, \Sigma_{\mathbb{S}_{d}} - A \Sigma \succeq_{\mathbb{S}_d} 0\}. \]

Suppose that $\prod_{j = d+1}^{d+k} \rho_{j,j+1} = 1$. We will show that $R(\Sigma_{{\mathbb{S}}_{d+k}}) = R(\Sigma_{\mathbb{S}_{d}})$ by proving both $R(\Sigma_{{\mathbb{S}}_{d+k}}) \geq R(\Sigma_{\mathbb{S}_{d}})$ and $R(\Sigma_{{\mathbb{S}}_{d+k}}) \leq R(\Sigma_{\mathbb{S}_{d}})$. As for the first of these, for every $\tilde{\Sigma}$ optimal for $\Sigma_{\mathbb{S}_{d+k}}$, we will show that $\Sigma = \tilde{\Sigma}_{|[d]}$ is feasible for $\Sigma_{\mathbb{S}_d}$. Now, $\Sigma \succeq 0$ since $\tilde{\Sigma} \succeq 0$, and $\Sigma_{11} = \ldots = \Sigma_{dd}$ by definition of $\tilde{\Sigma}$. As for $\Sigma_{\mathbb{S}_d} - A_{\mathbb{S}_d}\Sigma \succeq_{\mathbb{S}}
0$, observe that $\Sigma_{\mathbb{S}_d}$ contains exactly the first $d$ matrices in $\Sigma_{\mathbb{S}_{d}}$, but $\mathbb{S}_d$ contains just $d-1$ patterns of $\Sigma_{\mathbb{S}_{d+k}}$. This is due to the fact that $\mathbb{S}_d$ has $\{d,1\}$ in place of $\{d,d+1\}$, which prevents us from employing Proposition <ref> (ii). Nonetheless, observe that $\tilde{\Sigma}_{1,d} = \tilde{\Sigma}_{d,d+1}$, due to the fact that $\tilde{\Sigma}_{j,j+1} = \rho_{j,j+1}\tilde{\Sigma}_{11} = \pm \tilde{\Sigma}_{11}$ for all $j \in \{d+1, \ldots, d+k\}$. Indeed, $\Sigma_{\mathbb{S}_{d+k}} - A_{\mathbb{S}_{d+k}}\tilde{\Sigma} \succeq_{\mathbb{S}_{d+k}} 0 $ implies that
\[
\begin{pmatrix}
1 & \pm 1 \\
\pm 1 & 1
\end{pmatrix} -
\begin{pmatrix}
\tilde{\Sigma}_{11} & \tilde{\Sigma}_{j,j+1} \\
\tilde{\Sigma}_{j,j+1} & \tilde{\Sigma}_{11}
\end{pmatrix} \succeq 0
\]

for all $j \in \{d+1, \ldots, d+k\}$, which can be satisfied if and only if $\tilde{\Sigma}_{j,j+1} = \pm \tilde{\Sigma}_{11} = \rho_{j,j+1}\tilde{\Sigma}_{11}$, since we must also have $|\tilde{\Sigma}_{j,j+1}| \leq \tilde{\Sigma}_{11}$ in order to have $\tilde{\Sigma} \succeq 0$. The fact that $\tilde{\Sigma}_{j,j+1} = \rho_{j,j+1} \tilde{\Sigma}_{11}$ for all $j \in \{d+1, \ldots, d+k\}$ implies that  $\operatorname{Var}(X_{j+1}- \Tilde{\Sigma}_{j+1,j+2} X_{j+2}) = 0$,
for all $j \in \{d, \cdots, d+k-1\}$, since $A_{\mathbb{S}_{d+k}}\tilde{\Sigma}$ is compatible. By induction, this gives $\operatorname{Var}(X_{d+1}- \prod_{j = d+1}^{d+k} \tilde{\Sigma}_{j,j+1} X_{1}) = 0$ by which

\[
\tilde{\Sigma}_{1,d} = \frac{1}{\prod\limits_{j = d+1}^{d+k} \tilde{\Sigma}_{j,j+1}}\tilde{\Sigma}_{d,d+1} = \frac{1}{\prod\limits_{j = d+1}^{d+k} \rho_{j,j+1}}\tilde{\Sigma}_{d,d+1} = \tilde{\Sigma}_{d,d+1}.
\]

Since $\tilde{\Sigma}_{1,d} = \tilde{\Sigma}_{d,d+1}$, we know that $\Sigma_{\mathbb{S}_{d+k}} - A_{\mathbb{S}_{d+k}}\tilde{\Sigma} \succeq_{\mathbb{S}_{d+k}} 0 $ implies that $\Sigma_{\mathbb{S}_d} - A_{\mathbb{S}_d}\Sigma \succeq_{\mathbb{S}}

To show the reverse inequality, consider an optimal $\Sigma$ for $\Sigma_{\mathbb{S}_{d}}$ coming from the dual formulation above, and define
\[ \tilde{\Sigma} :=
\begin{pmatrix}
\Sigma & B \\
B^T & U
\end{pmatrix},
\]
\[
U := \Sigma_{11}\begin{pmatrix}
U_{11} & \cdots & U_{1k} \\
\vdots & & \vdots \\
U_{k1} & \cdots & U_{kk}
\end{pmatrix}
\]

is such that $U = U^T$, $U_{ii} = 1$ for $i \in [k]$, $U_{i,i+1} = \rho_{d+i,d+i+1}$ for $i \in [k-1]$, $U_{1k} = U_{k1}$ is either $+1$ or $-1$ to make this $(k-1)$-cycle completable, and the other entries are again $+1$ or $-1$ to make the cycle consistent; and
\[B^T := \begin{pmatrix}
B_{11} & \cdots & B_{1d} \\
\vdots & & \vdots \\
B_{k1} & \cdots & B_{kd}
\end{pmatrix}
\]

is such that $B_{ij} = \Sigma_{1j} \cdot U_{i1}$ for $i \in [k], j \in [d]$. If such a $\tilde{\Sigma}$ is feasible for $\Sigma_{{\mathbb{S}}_{d+k}}$, then the result would follow from the fact that $R(\Sigma_{{\mathbb{S}}_{d+k}}) \leq 1-\operatorname{tr}(\tilde{\Sigma})/(d+k) = 1-\Sigma_{11} = R(\Sigma_{{\mathbb{S}}_{d}})$. The condition $\Sigma_{\mathbb{S}_{d+k}} - A_{\mathbb{S}_{d+k}}\tilde{\Sigma} \succeq_{\mathbb{S}_{d+k}} 0 $ is implied by $\Sigma_{\mathbb{S}_{d}} - A\Sigma \succeq_{\mathbb{S}_{d}} 0$, which is satisfied by hypothesis, and $(1-\Sigma_{11})\Sigma_{\{i, i+1\}} \succeq 0$ for $i \in \{d+1, \cdots, d+k-1 \}$, which is again satisfied since $\Sigma_{11} \in [0,1]$ and $\Sigma_{\{i, i+1\}} \succeq 0$. Moreover, being a symmetric block matrix, $\tilde{\Sigma}$ is positive semi-definite if and only if $\Sigma \succeq 0$, which is true by hypothesis, $U - B^T\Sigma^{\dagger}B \succeq 0$, and $(I - \Sigma\Sigma^{\dagger})B = 0$, where $\Sigma^\dagger$ is the Moore-Penrose inverse of $\Sigma$. As for the first of these last two conditions, observe that the $(k,h)$-th entry of $B^T\Sigma^{\dagger}B$ is given by
\[
(B^T\Sigma^{\dagger}B)_{kh} = U_{k1}\Sigma_1^T \Sigma^\dagger \Sigma_1 U_{h1} = U_{k1}U_{h1}\Sigma_1^T \Sigma^\dagger \Sigma_1 = U_{kh}\Sigma_1^T \Sigma^\dagger \Sigma_1,
\]

where $\Sigma_1$ is the first column of $\Sigma$. What is left to prove is to check that $\Sigma_1^T \Sigma^\dagger \Sigma_1 = \operatorname{tr}(\Sigma_1^T \Sigma^\dagger \Sigma_1) = \Sigma_{11}$ and, to this aim, we will use the limit characterisation of the pseudoinverse (see pag. 19 in [Albert, 1972]), which allows writing $\Sigma^{\dagger}$ as $\lim_{\delta \rightarrow 0}\Sigma^T(\Sigma\Sigma^T + \delta^2 I)^{-1}$. With this in mind, and calling $\lambda_i$ the eigenvalues of $\Sigma$, and $\boldsymbol{v}_i$ the associated orthonormal eigenvectors,

\begin{align*}
\operatorname{tr}(\Sigma_1^T \Sigma^\dagger \Sigma_1) &= \operatorname{tr}(\Sigma^\dagger \Sigma_1 \Sigma_1^T) = \operatorname{tr}\left(\lim_{\delta \rightarrow 0}\Sigma^T(\Sigma\Sigma^T + \delta^2 I)^{-1} \Sigma_1 \Sigma_1^T\right) \\
&= \lim_{\delta \rightarrow 0}\operatorname{tr}\left((\Sigma \Sigma^T + \delta^2 I)^{-1} \Sigma_1 \Sigma_1^T \Sigma^T\right) = \lim_{\delta \rightarrow 0}\operatorname{tr}\left(\sum_{i=1}^d \frac{1}{\lambda_i^2 +\delta^2}\boldsymbol{v}_i \boldsymbol{v}_i^T \Sigma_1 \Sigma_1^T \Sigma^T\right)\\
&= \lim_{\delta \rightarrow 0}\sum_{i=1}^d \frac{1}{\lambda_i^2 +\delta^2} \operatorname{tr}\left(\boldsymbol{v}_i \boldsymbol{v}_i^T \Sigma_1 \Sigma_1^T \Sigma^T\right) = \lim_{\delta \rightarrow 0}\sum_{i,j=1}^d \frac{\lambda_j}{\lambda_i^2 +\delta^2} \operatorname{tr}\left( \boldsymbol{v}_j \boldsymbol{v}_j^T \boldsymbol{v}_i \boldsymbol{v}_i^T \Sigma_1 \Sigma_1^T \right) \\
&= \lim_{\delta \rightarrow 0}\sum_{i=1}^d \frac{\lambda_i}{\lambda_i^2 +\delta^2} \| \boldsymbol{v}_i \boldsymbol{v}_i^T \Sigma_1\|_2^2 = \lim_{\delta \rightarrow 0}\sum_{i=1}^d \frac{\lambda_i}{\lambda_i^2 +\delta^2} \| \boldsymbol{v}_i \boldsymbol{v}_i^T \sum_{j=1}^d \lambda_j v_{j1} \boldsymbol{v}_j\|_2^2 \\
&= \lim_{\delta \rightarrow 0}\sum_{i=1}^d \frac{\lambda_i^3}{\lambda_i^2 +\delta^2} \| v_{i1} \boldsymbol{v}_i\|_2^2 = \sum_{i=1}^d \lambda_i v_{i1}^2 = \Sigma_{11}.
\end{align*}

The other condition can be checked easily using again the limit characterisation of $\Sigma^\dagger$ and the spectral decomposition of $\Sigma$. This concludes the proof for the case $\prod_{j = d+1}^{d+k} \rho_{j,j+1} = +1$. On the other hand, if $\prod_{j = d+1}^{d+k} \rho_{j,j+1} = -1$, $R(\Sigma_{{\mathbb{S}}_{d+k}}) \geq R(\Sigma_{\mathbb{S}_{d}})$ follows after noticing that, if $\tilde{\Sigma}$ is optimal for $\Sigma_{{\mathbb{S}}_{d+k}}$, we must have $\tilde{\Sigma}_{d,d+1} = -\tilde{\Sigma}_{d,1}$. As for $R(\Sigma_{{\mathbb{S}}_{d+k}}) \leq R(\Sigma_{\mathbb{S}_{d}})$, the proof follows the exact same line as the one above, with the only exception that $B_{ij}$ should now be defined as $ - \Sigma_{1j} \cdot U_{i1}$ for $i \in [k], j \in [d]$.

Start by considering a $3$-cycle. In the first case, the optimal $\Sigma$ of the dual representation
\[
R(\Sigma_{\mathbb{S}_3}) = 1 - \frac{1}{d} \sup\{ \mathrm{tr}(\Sigma) : \Sigma \in \mathcal{P}^*, \Sigma_\mathbb{S} - A \Sigma \succeq_\mathbb{S} 0, \Sigma_{11}=\Sigma_{22}=\Sigma_{33}  \}
\]

must be of the form
\[
\begin{pmatrix}
\lambda & x & \lambda \\
x & \lambda & y \\
\lambda & y & \lambda
\end{pmatrix}
\]

for some $\lambda \in [0,1]$ and some $x,y \in [-\lambda, \lambda]$ in order to satisfy $\Sigma_\mathbb{S} - A \Sigma \succeq_\mathbb{S} 0$. Furthermore, since $\operatorname{det}(\Sigma) = -\lambda(x-y)^2$, we must have $x=y$ in order to satisfy $\Sigma \succeq 0$. It follows that
\begin{align*}
R(\Sigma_{\mathbb{S}_3}) & = 1 - \sup\{\lambda \in [0,1]: 1- \lambda \geq \max\{|x-\rho_1|,|x-\rho_2| \}, \text{ with }  x \in [-\lambda, \lambda]\} \\
& = \inf\{\epsilon \in [0,1] : \epsilon \geq \max\{|x-\rho_1|,|x-\rho_2| \}, \epsilon \leq 1 - |x| \} \\
& = \inf\{\max\{|x-\rho_1|,|x-\rho_2| \} \in [0,1] : \max\{|x-\rho_1|,|x-\rho_2| \} \leq 1 - |x| \}
\end{align*}

which is equal to $(\cos\theta_2 - \cos\theta_1)/2$. As for the second case with $d=3$, setting $\rho_2=1$ in the above we see that if
\[
\Sigma_{\mathbb{S}_3} = \Bigg\{\begin{pmatrix}
1 & \rho_1 \\
\rho_1 & 1
\end{pmatrix}, \begin{pmatrix}
1 & 1 \\
1 & 1
\end{pmatrix}, \begin{pmatrix}
1 & 1 \\
1 & 1
\end{pmatrix}\Bigg\},
\]

then $R(\Sigma_{\mathbb{S}_3}) = (1-\rho_1)/2 = (1-\cos\theta_1)/2 = \sin^2(\theta_1/2)$. Plugging in $\theta_1 = \pi$ gives the sufficiency part of the second statement. As for the necessity part, Proposition <ref> (i) implies that it is necessary that $|\rho_i| = 1$ for all $i \in [d]$ for $R$ to be $1$.

It is easy to see that we can always transform the original $d$-cycle into a new one where at most $\cos{\theta_1}$ is negative by changing some $X_j$ into $-X_j$. To see why, let $\theta = (\theta_1, \ldots, \theta_d)$ be such that $\theta_j = \mathbbm{1}\{\rho_{j, j+1} \geq 0\}$, and observe that, if $\theta_{j-1} = 0$ and $\theta_{j} = 1$, changing the sign of $X_j$ corresponds to switching $\theta_{j-1}$ with $\theta_j$. Hence, it is easy to see that we can switch signs to some variables in order to reach a configuration of $\theta$ in which all the zeros are at the beginning, and all the ones at the end. It is now sufficient to couple the zeros starting from the end, and switch sign to make it both one, to get $\theta = (\theta_1, \boldsymbol{1}_{d-1})$, where $\theta_1 = +1$ if the number of original $\rho_{j,j+1}$ is even, and zero otherwise. As a by-product, this also shows that we can always assume without loss of generality that at most $\cos\theta_1$ is negative. Now, let $\tilde{\Sigma}_{\mathbb{S}_d}$ be this new $d$-cycle: what we want to show is that $R(\tilde{\Sigma}_{\mathbb{S}_d}) = R(\Sigma_{\mathbb{S}_d})$, and, in order to do so, we will show that we can construct feasible $\tilde{X}_{\mathbb{S}}$ and $\tilde{\Sigma}$ for primal and dual problems of $\tilde{\Sigma}_{\mathbb{S}_d}$ which lead to the same target values, using the optimal $X_{\mathbb{S}}$ and $\Sigma$  for $\Sigma_{\mathbb{S}_d}$.
Starting from the dual problem, let $M$ be a diagonal matrix such that $M_{jj} = -1$ if $X_j$ was replaced with $-X_j$, and $+1$ otherwise. Then, it is easy to see $\tilde{\Sigma} = M \Sigma M$ has the same trace as $\Sigma$, and it is feasible for $\tilde{\Sigma}_{\mathbb{S}_d}$: indeed, $\tilde{\Sigma} \succeq 0$ since it has the same spectrum as $\Sigma$, being similar matrices, and $\tilde{\Sigma}_{\mathbb{S}_d} - A\tilde{\Sigma} \succeq_{\mathbb{S}_d} 0$ because for every $j \in [d]$ we have

\begin{align*}
\tilde{\Sigma}_{\{j,j+1 \}} - &\tilde{\Sigma}_{|\{j,j+1 \}}  = \begin{pmatrix}
1 & \tilde{\rho}_j \\
\tilde{\rho}_j & 1
\end{pmatrix} - \begin{pmatrix}
\tilde{\Sigma}_{j,j}  & \tilde{\Sigma}_{j,j+1} \\
\tilde{\Sigma}_{j,j+1} & \tilde{\Sigma}_{j+1,j+1}
\end{pmatrix} \\
& = \begin{pmatrix}
1 & M_{j,j}M_{j+1,j+1}\rho_j \\
M_{j,j}M_{j+1,j+1}\rho_j  & 1
\end{pmatrix} - \begin{pmatrix}
\Sigma_{j,j} & M_{j,j}M_{j+1,j+1}\Sigma_{j,j+1} \\
M_{j,j}M_{j+1,j+1}\Sigma_{j,j+1}  & \Sigma_{j+1,j+1}
\end{pmatrix} \\
& = \begin{pmatrix}
1 - \Sigma_{j,j} & M_{j,j}M_{j+1,j+1}(\rho_j - \Sigma_j) \\
M_{j,j}M_{j+1,j+1}(\rho_j - \Sigma_j)  & 1 - \Sigma_{j+1,j+1}
\end{pmatrix} \succeq 0,
\end{align*}

since $|M_{j,j}M_{j+1,j+1}(\rho_j - \Sigma_j)| = |\rho_j - \Sigma_j| \leq 1 - \Sigma_{j,j} =  1 - \Sigma_{j+1,j+1}$, due to the fact that $\Sigma$ is feasible for $\Sigma_\mathbb{S}$.
As for the primal problem, it is sufficient to define $\tilde{X}_{\mathbb{S}} = AM \cdot X_{\mathbb{S}} \cdot AM$, where $\cdot$ acts pointwise, which essentially consists in changing the signs of the off-diagonal entries of $X_{\mathbb{S}}$ according to $M$. Let
\[X_{\{j,j+1 \}} = \begin{pmatrix}
x_{j, 11} & x_{j,12} \\
x_{j,21} & x_{j,22}
\end{pmatrix} \text{ and }
\tilde{X}_{\{j,j+1 \}} = \begin{pmatrix}
\tilde{x}_{j, 11} &\tilde{x}_{j,12} \\
\tilde{x}_{j,21} &\tilde{x}_{j,22}
\end{pmatrix} = \begin{pmatrix}
x_{j, 11} &  M_{j,j}M_{j+1,j+1} x_{j, 12}\\
M_{j,j}M_{j+1,j+1} x_{j, 21} & x_{j, 22}
\end{pmatrix},
\]

for all $j \in [d]$. It is easy to show that $\tilde{X}_{\mathbb{S}}$ is feasible, and clearly leads to $
\langle \tilde{X}_{\mathbb{S}}, \tilde{\Sigma}_{\mathbb{S}} \rangle_{\mathbb{S}} =  \langle X_{\mathbb{S}}, \Sigma_{\mathbb{S}} \rangle_{\mathbb{S}}
$ since, for a generic pattern $j \in [d]$, we have
\begin{align*}
\langle \tilde{X}_{\{j,j+1 \}}, \tilde{\Sigma}_{\{j,j+1 \}} \rangle & =
\langle \begin{pmatrix}
\tilde{x}_{j, 11} &\tilde{x}_{j,12} \\
\tilde{x}_{j,21} &\tilde{x}_{j,22}
\end{pmatrix}, \begin{pmatrix}
1 & \tilde{\rho}_j \\
\tilde{\rho}_j & 1
\end{pmatrix}\rangle \\
& = \langle \begin{pmatrix}
x_{j, 11} &  M_{j,j}M_{j+1,j+1} x_{j, 12}\\
M_{j,j}M_{j+1,j+1} x_{j, 21} & x_{j, 22}
\end{pmatrix}, \begin{pmatrix}
1 & M_{j,j}M_{j+1,j+1}\rho_j \\
M_{j,j}M_{j+1,j+1}\rho_j  & 1
\end{pmatrix}\rangle \\
& = x_{j, 11} + x_{j, 22} + M_{j,j}^2M_{j+1,j+1}^2 x_{j, 12}\rho_j + M_{j,j}^2M_{j+1,j+1}^2 x_{j, 21}\rho_j \\
& = x_{j, 11} + x_{j, 22} + x_{j, 12} \rho_j + x_{j, 21} \rho_j \\
& = \langle \begin{pmatrix}
x_{j, 11} & x_{j, 12} \\
x_{j, 21} & x_{j, 22}
\end{pmatrix}, \begin{pmatrix}
1 & \rho_j \\
\rho_j & 1
\end{pmatrix}\rangle = \langle X_{\{j,j+1 \}}, \Sigma_{\{j,j+1 \}} \rangle.
\end{align*}

This completes the proof.

(i)  We may suppose without loss of generality that $|\rho_i| \neq 1$ as, otherwise, we may perform the reduction given in Proposition <ref>. Possibly, this reduces the $d$-cycle to a $3$-cycle: if there are no more correlations equal to $\pm 1$, then we proceed, otherwise we know $R$ exactly thanks to Example <ref> and we can check that the claim holds. Now, calling $M_{i,i+1} = \cos\varphi_i$, we have

\begin{align*}
\lambda^* = 1 - R(\Sigma_{\mathbb{S}}) &= \frac{1}{d} \sup\{ \mathrm{tr}(\Sigma) : \Sigma \succeq 0, \Sigma_{11} = \ldots = \Sigma_{dd}, \Sigma_{\mathbb{S}'} - A \Sigma \succeq_{\mathbb{S}'} 0\} \\
&= \sup\{\lambda : M \succeq 0, M_{11} = \ldots = M_{dd} = 1, 1-\lambda \geq |\rho_i -\lambda\cos\varphi_i| \text{ for all } i \in [d] \}\\
& = \sup\bigg\{\lambda : \lambda \leq  \min_{i \in [d]}\min\bigg\{\frac{1-\rho_i}{1 - \cos\varphi_i}, \frac{1+\rho_i}{1+ \cos\varphi_i} \bigg\} , \\
& \quad \hspace{3cm} \sum\limits_{i \in K} \varphi_i \leq (|K| -1 ) \pi + \sum\limits_{i \not\in K} \varphi_i \text{ for all } K \subseteq [d] \text{ with }|K| \text{ odd}\bigg\}.
\end{align*}

Now, this implies that

\begin{align*}
\frac{1}{\lambda^*} &= \inf\bigg\{z : z \geq  \max_{i \in [d]}\max\bigg\{\frac{1 - \cos\varphi_i}{1-\rho_i}, \frac{1+ \cos\varphi_i}{1+\rho_i} \bigg\} , \\
& \quad \hspace{3cm} \sum\limits_{i \in K} \varphi_i \leq (|K| -1 ) \pi + \sum\limits_{i \not\in K} \varphi_i \text{ for all } K \subseteq [d] \text{ with }|K| \text{ odd}\bigg\}.
\end{align*}

Calling $g(\varphi_i) = (1 - \cos\varphi_i)/(1-\rho_i)$ and $h(\varphi_i) = (1 + \cos\varphi_i)/(1+\rho_i)$ for all $i \in [d]$, this is a linearly constrained finite minimax problem (see Chapter 2 in [Polak, 2012]), namely

\[
\frac{1}{\lambda^*} = \min \max_{i \in [d]}\max\{g(\varphi_i), h(\varphi_i) \}
\]

under the $2^{d-1}$ linear constraints
\[
\sum\limits_{i \in K} \varphi_i \leq (|K| -1 ) \pi + \sum\limits_{i \not\in K} \varphi_i \text{ for all } K \subseteq [d] \text{ with }|K| \text{ odd},
\]

which is equivalent to

\begin{align*}
\text{ minimise } & z \\
\text{ subject to } & g(\varphi_i) \leq z \text { for all } i \in [d], \\
& h(\varphi_i) \leq z \text { for all } i \in [d], \\
& \sum\limits_{i \in K} \varphi_i \leq (|K| -1 ) \pi + \sum\limits_{i \not\in K} \varphi_i \text{ for all } K \subseteq [d] \text{ with }|K| \text{ odd}.
\end{align*}

As a result, every optimal solution $(\varphi_1^*, \ldots, \varphi_d^*)$ must satisfy the Karush–Kuhn–Tucker (KKT) conditions (see Chapter 5 of [Boyd and Vandenberghe, 2004], Chapter 28-30 of [Rockafellar, 1970])

\begin{align*}
(i) \quad & \left(\frac{\lambda_i}{1-\rho_i} - \frac{\lambda_{i+d}}{1+\rho_i}\right)\sin\varphi_i = \mathop{\sum_{|K| odd}}\limits_{i \in K} \mu_K - \mathop{\sum_{|K| odd}}\limits_{i \in K^c} \mu_K, \text{ for all } i \in [d], \\
(ii) \quad & \lambda_i \geq 0, \lambda_{d+i} \geq 0, \text{ for all } i \in [d], \\
(iii) \quad & \sum_{i = 1}^d (\lambda_i + \lambda_{d+i}) = 1, \\
(iv) \quad & \lambda_i (g(\varphi_i) - \max_{i \in [d]}\max\{g(\varphi_i), h(\varphi_i) \}) = 0, \text{ for all } i \in [d], \\
(v) \quad & \lambda_{d+i} (h(\varphi_i) - \max_{i \in [d]}\max\{g(\varphi_i), h(\varphi_i) \}) = 0, \text{ for all } i \in [d], \\
(vi) \quad & g(\varphi_i) \leq \max_{i \in [d]}\max\{g(\varphi_i), h(\varphi_i) \}), \text{ for all } i \in [d], \\
(vii) \quad & h(\varphi_i) \leq \max_{i \in [d]}\max\{g(\varphi_i), h(\varphi_i) \}), \text{ for all } i \in [d], \\
(viii) \quad & \mu_K \geq 0, \text{ for all } K \subseteq [d] \text{ with }|K| \text{ odd}, \\
(ix) \quad & \sum\limits_{i \in K} \varphi_i \leq (|K| -1 ) \pi + \sum\limits_{i \not\in K} \varphi_i \text{ for all } K \subseteq [d] \text{ with }|K| \text{ odd}, \\
(x) \quad & \mu_K\left(\sum\limits_{i \in K} \varphi_i - (|K| -1 ) \pi - \sum\limits_{i \not\in K} \varphi_i\right) =0,  \text{ for all } K \subseteq [d] \text{ with }|K| \text{ odd}. \\
\end{align*}

Now, observe that conditions (iv) and (v) imply that, for all $i \in [d]$, either $g(\varphi_i)$ or $h(\varphi_i)$ reaches the maximum, meaning that the minimal $1/\lambda^*$ is equal to this common value. Indeed, if the original $d$-cycle is completable, this statement is trivial, since we must have $|\rho_i - \cos\varphi^*_i| = 0$. This is the only case in which we can have
\[
\frac{1-\rho_i}{1 - \cos\varphi_i} = \frac{1+\rho_i}{1+ \cos\varphi_i} = 1,
\]

meaning that when the $d$-cycle is incompatible, then either $\max_{i \in [d]}\max\{g(\varphi_i), h(\varphi_i) \} - g(\varphi_i) > 0$ or $\max_{i \in [d]}\max\{g(\varphi_i), h(\varphi_i) \} - h(\varphi_i) > 0$.  Indeed, if $R > 0$, either $\lambda_i$ or $\lambda_{d+i}$ must be equal to zero since either $g(\varphi_i)$ or $h(\varphi_i)$ has a strictly positive gap from $\max_{i \in [d]}\max\{g(\varphi_i), h(\varphi_i) \}$. If both $\lambda_i = 0$ and $\lambda_{i+d} = 0$, we would have
\[
\mathop{\sum_{|K| odd}}\limits_{i \in K} \mu_K = \mathop{\sum_{|K| odd}}\limits_{i \in K^c} \mu_K,\]

which is a contradiction due to the fact that there exists a unique $\mu_K \neq 0$. To prove the existence part, observe that if $\mu_K = 0$ for all $K \subseteq [d]$ with $|K|$ odd, then we would have
\[
\left(\frac{\lambda_i}{1-\rho_i} - \frac{\lambda_{i+d}}{1+\rho_i}\right)\sin\varphi_i = 0
\]

for all $i \in [d]$, and since there exists at least a $j$ such that $\lambda_j + \lambda_{d+j} > 0$ due to (iii), this would imply that $\varphi_j \in \{0, \pi\}$, which leads to $\theta_j \in \{0, \pi\}$, which is excluded from our analysis. To prove the uniqueness part, suppose there exists another $[d] \supseteq M \neq K$, with $|M|$ odd, such that

\[
\begin{cases}
\sum\limits_{i \in K} \varphi_i = (|K| -1 ) \pi + \sum\limits_{i \not\in K} \varphi_i \\
\sum\limits_{i \in M} \varphi_i = (|M| -1 ) \pi + \sum\limits_{i \not\in M} \varphi_i,
\end{cases}
\]

hence summing these equalities gives

\[
2\left(\sum\limits_{i \in K\cap M} \varphi_i - \sum\limits_{i \in K^c \cap M^c} \varphi_i \right) = (|K|+|M|-2)\pi.
\]

Now, if we suppose that $K^c \cap M^c = \varnothing$, meaning that $K\cup M = [d]$, it is easy to show that $2|K \cap M| \leq |K|+|M|-2$. Indeed, $|K \cap M| \leq |K| \wedge |M|$, with equality if and only if $M \subseteq K$ (or viceversa): in this case we must have $|K| \geq |M| + 2$, otherwise they would be equal, hence $2|K \cap M| \leq 2(|K|\wedge|M|) = 2|M|$ while $|K|+|M|-2 \geq |M|+2+|M|-2 = 2|M|$. If the equality is not reached, $2|K \cap M| \leq 2(|K|\wedge|M|-1) = 2|M| - 2$, while $|K|+|M|-2 \geq |M| + |M| - 2 = 2|M| - 2$. This shows that $2|K \cap M| \leq |K|+|M|-2$, which implies that the equality above can be verified only if $\varphi_i = \pi$ for all $i \in K \cap M$, which is excluded from our analysis. Furthermore, if $K^c \cap M^c \neq \varnothing$, this is even worse unless $\varphi_i = 0$ for all $i \in K^c \cap M^c$, which is again excluded from our analysis. This completes the proof of the fact that for all $i \in [d]$, if $R > 0$, exactly one between $\lambda_i$ and $\lambda_{d_i}$ is greater than zero. As a corollary, we have that the optimal $(\varphi_1^*, \ldots, \varphi_d^*)$ satisfies
\[
1 - \lambda^* = |\rho_i - \lambda^*\cos\varphi_i^*|, \text{ for all } i \in [d],
\]

as required.

(ii) The primal set is strictly feasible, hence we know that $R$ is attained in the dual set, which is enough to prove existence. As for uniqueness, suppose there exists two optimal $\Sigma_1, \Sigma_2$ such that

\[
\begin{cases}
\Sigma_{\mathbb{S}} = \lambda^*A\Sigma_1 + (1-\lambda^*)\Sigma_{\mathbb{S}}' \\
\Sigma_{\mathbb{S}} = \lambda^*A\Sigma_2 + (1-\lambda^*)\Sigma_{\mathbb{S}}''.
\end{cases}
\]

This implies that for all $\mu \in (0,1)$

\[
\Sigma_{\mathbb{S}} = \lambda^*A(\mu\Sigma_1+(1-\mu)\Sigma_2) + (1-\lambda^*)(\mu\Sigma_{\mathbb{S}}'+(1-\mu)\Sigma_{\mathbb{S}}''),
\]

meaning that $\mu\Sigma_1+(1-\mu)\Sigma_2$ is optimal. By the optimality of $\Sigma_1$ and $\Sigma_2$ we must have that $\Sigma_{\mathbb{S}}'$ and $\Sigma_{\mathbb{S}}''$ are maximally incompatible, which means they must all be singular, as stated in Example <ref>. Now, observe that if there exists $i \in [d]$ such that $\Sigma_{\{i,i+1\}}' \neq \Sigma_{\{i,i+1\}}''$,
\[
\mu\Sigma_{\{i,i+1\}}' + (1-\mu)\Sigma_{\{i,i+1\}}'' = \begin{pmatrix}
1 & \pm(2\mu - 1)\\
\pm(2\mu - 1) & 1
\end{pmatrix},
\]

which means that $\mu\Sigma_{\mathbb{S}}'+(1-\mu)\Sigma_{\mathbb{S}}''$ can never be maximally incompatible since $\mu \in (0,1)$. This implies that $\Sigma_{\mathbb{S}}' = \Sigma_{\mathbb{S}}''$, which in turn implies that $\boldsymbol{\varphi}_1^* = \boldsymbol{\varphi}_2^*$. As for the continuity of $\boldsymbol{\varphi}^*(\theta_1, \ldots, \theta_d)$, observe that $1 - \lambda^* = |\rho_j - \lambda^*\cos\varphi_j^*|, \text{ for all } j \in [d]$ in point (i) means that there exist $\{\epsilon_j = \pm 1\}_{j \in [d]}$ such that
\[
\lambda^* = \frac{1-\epsilon_j \cos\theta_j}{1-\epsilon_j \cos\varphi_j^*}, \quad \text{ for all } j \in [d].
\]

Now, let $\left\{\boldsymbol{\theta}^{(n)} = \left(\theta_{1,n}, \ldots, \theta_{d,n}\right)\right\}_{n \in \mathbb{N}} \longrightarrow \boldsymbol{\theta} = (\theta_1, \ldots, \theta_d)$, and consider the associated sequence of optimal $\left\{\boldsymbol{\varphi}_n^{*} = (\varphi_{1,n}^*, \ldots, \varphi_{d,n}^*)\right\}_{n \in \mathbb{N}}$, meaning that
\[
\lambda_n^* =  \frac{1-\epsilon_{j,n} \cos\theta_{j,n}}{1-\epsilon_{j,n} \cos\varphi_{j,n}^*}, \quad \text{ for all } j \in [d].
\]

Taking the limit on both sides, since $\lambda^*$ is continuous due to Proposition <ref> (ii), we get that

\[
\lambda^* = \frac{1 \pm \cos\theta_j}{1 \pm \cos\left(\lim_n \varphi_{j,n}^* \right)}, \quad \text{ for all } j \in [d].
\]

This shows that the limit $\lim_n \varphi_{j,n}^*$ exists, and by uniqueness (i), we can conclude that $\lim_n \varphi_{j,n}^* = \varphi_j^*$, showing that $\boldsymbol{\varphi}$ is continuous.

As for (iii), supposing without loss of generality that $\theta_1 = \max_{i \in [d]} \theta_i$, with at most $\theta_1 > \pi/2$, observe that incompatibility is equivalent to having $\theta_1 - \sum_{i=2}^d \theta_i > 0$, hence in order to make $\lambda^*$ as big as possible we should choose $\rho_j = \lambda^*\cos\varphi_j^* + (1-\lambda^*)$ for all $ j \in \{2, \ldots, d\}$, and $\rho_1 = \lambda^*\cos\varphi_1^* - (1-\lambda^*)$. This would imply that the optimal choice of signs for a general $d$-cycle is $\epsilon_d = (-1, +\boldsymbol{1}_{d-1}^T)$, and this turns out to be true indeed. To see why, start by considering the case $d=3$, and observe that from (ii) we know that there exists a unique $K \subseteq [3]$ with $|K|$ odd such that
\[
\mathop{\sum_{|K| odd}}\limits_{i \in K} \mu_K = \mathop{\sum_{|K| odd}}\limits_{i \in K^c} \mu_K.\]

The possible values of $K$ are $\{1\}, \{2\}, \{3\}$ and $\{1,2,3\}$, and these are associated to the vectors of signs $(-1,1,1)$,$ (1,-1,1)$, $(1,1,-1)$ and $(-1,-1,-1)$, respectively. Hence, in order to prove the statement it is necessary and sufficient to show that $K = \{1\}$ leads to the optimal $\lambda^*$, meaning that $\lambda^*_1 \geq \lambda^*_2$ and $\lambda^*_1 \geq \lambda^*_4$, where
\[
\lambda^*_1 = \frac{1+\cos\theta_1}{1+\cos\varphi_1^*} = \frac{1-\cos\theta_2}{1-\cos\varphi_2^*} = \frac{1-\cos\theta_3}{1-\cos(\varphi_1^*-\varphi_2^*)},
\]

\[
\lambda^*_2 = \frac{1-\cos\theta_1}{1-\cos\tilde{\varphi}_1^*} = \frac{1+\cos\theta_2}{1+\cos\tilde{\varphi}_2^*} = \frac{1-\cos\theta_3}{1-\cos(\tilde{\varphi}_2^*-\tilde{\varphi}_1^*)},
\]

\[
\lambda^*_4 = \frac{1+\cos\theta_1}{1+\cos\tilde{\varphi}_1^*} = \frac{1+\cos\theta_2}{1+\cos\tilde{\varphi}_2^*} = \frac{1+\cos\theta_3}{1+\cos(2\pi - \tilde{\varphi}_1^*-\tilde{\varphi}_2^*)}.
\]

Now, for $\lambda^*_1 < \lambda^*_2$ to be true it is necessary to have
\[
\begin{cases}
\cos(\varphi_1^*-\varphi_2^*) < \cos(\tilde{\varphi}_1^*-\tilde{\varphi}_2^*) \\
\\
\cos\tilde{\varphi}_1^* > 1 - \frac{1-\cos\theta_1}{1+\cos\theta_1}(1+\cos\varphi_1^*)\\
\\
\cos\tilde{\varphi}_2^* < -1 + \frac{1+\cos\theta_2}{1-\cos\theta_2}(1-\cos\varphi_2^*),\\
\end{cases}
\]

with $(\varphi_1^*, \varphi_2^*), (\tilde{\varphi}_1^*, \tilde{\varphi}_2^*) \in [0, \pi]^2$ that need to simultaneously satisfy

\begin{align*}
\begin{cases}
\cos\varphi_2^* = 1 - \frac{1-\cos\theta_2}{1+\cos\theta_1}(1+\cos\varphi_1^*)\\
\\
\cos\tilde{\varphi}_1^* = 1 - \frac{1-\cos\theta_1}{1+\cos\theta_2}(1+\cos\tilde{\varphi}_2^*),\\
\end{cases} & \text{ and } \quad \quad  \begin{cases}
\varphi_1^* \leq \theta_1, \quad \quad \varphi_2^* \geq \theta_2 \\
\\
\tilde{\varphi}_1^* \geq \theta_1, \quad \quad \tilde{\varphi}_2^* \leq \theta_2, \\
\end{cases}
\end{align*}

to ensure $R(\Sigma_{\mathbb{S}_3}) \in [0,1]$. This system of inequalities has no solution in $(\tilde{\varphi}_1^*, \tilde{\varphi}_2^*)$ for fixed $(\varphi_1^*, \varphi_2^*)$ and $\theta_1 > \theta_2$. The same reasoning shows that $\lambda^*_1 < \lambda^*_4$ can never be satisfied as well, showing that the optimal choice of signs for $d=3$ is indeed $\epsilon_3 = (-1, +1, +1)$. For general $d$, it is sufficient to proceed by induction: indeed, suppose that $\epsilon_j = (-1, +\boldsymbol{1}_{j-1}^T)$ for all $j \in \{3, \ldots, d-1\}$, and consider $\lambda^* = \lambda^*(\theta_d)$ as a function of $\theta_d$, for fixed $\theta_1, \ldots, \theta_{d-1}$. This function is continuous over $[0, \theta_1 - \sum_{i = 2}^{d-1}\theta_i)$, because is the restriction of $\lambda^* = 1 - R(\Sigma_{\mathbb{S}_d})$, which is continuous by Proposition <ref> (ii), onto the last coordinate. Now, $\lambda^*(\theta_d)$ uniquely identifies a vector of signs for varying $\theta_d \in [0, \theta_1 - \sum_{i = 2}^{d-1}\theta_i)$, call it $\epsilon(\theta_d)$, taking values in $\{+1, -1\}^d$. This vector is unique because we supposed the cycle to be incompatible, hence either $g(\varphi_i)$ or $h(\varphi_i)$ in the KKT conditions has a strictly positive optimal gap, so that there exists a unique $\mu_K \neq 0$. We will show that this vector is constant for all  $\theta_d \in [0, \theta_1 - \sum_{i = 2}^{d-1}\theta_i)$, that is to say that each component of $\epsilon(\theta_d)$ is continuous in  $\theta_d \in [0, \theta_1 - \sum_{i = 2}^{d-1}\theta_i)$. Indeed, consider without loss of generality the first component of $\epsilon(\theta_d)$, and suppose by contradiction that $\epsilon(\theta_d)_1$ is not continuous in $\tilde{\theta}_d$. This implies that there exists a sequence of angles $\{\theta_{d,n}\}$ converging to $\tilde{\theta}_d$ such that
\[
\lim\limits_{n \rightarrow +\infty}\epsilon(\theta_{d,n})_1  = \epsilon_{\mathrm{lim}} = -\epsilon(\tilde{\theta}_d)_1.
\]

Without loss of  generality, assume $\epsilon_{\mathrm{lim}} = +1$ and $\epsilon(\tilde{\theta}_d)_1 = -1$. But we must have by continuity
\begin{align*}
\frac{1+ \cos\theta_1}{1+\cos\varphi_1^*} & =\frac{1-\epsilon(\tilde{\theta}_d)_1\cos\theta_1}{1-\epsilon(\tilde{\theta}_d)_1\cos\varphi_1^*} = \lambda^*(\theta_d) = \lim\limits_{n \rightarrow +\infty} \lambda^*(\theta_{d,n}) = \lim\limits_{n \rightarrow +\infty} \frac{1-\epsilon(\theta_{d,n})_1\cos\theta_1}{1-\epsilon(\theta_{d,n})_1\cos\varphi_{1,n}^{*}} \\
& = \frac{1- \cos\theta_1\lim\limits_{n \rightarrow +\infty}\epsilon(\theta_{d,n})_1 }{1-\cos\left(\lim\limits_{n \rightarrow +\infty}\varphi_{1,n}^{*}\right) \lim\limits_{n \rightarrow +\infty}\epsilon(\theta_{d,n})_1 } = \frac{1-\epsilon_{\mathrm{lim}}\cos\theta_1}{1-\epsilon_{\mathrm{lim}}\cos\varphi_1^*} =  \frac{1-\cos\theta_1}{1-\cos\varphi_1^*},
\end{align*}

where $\cos\varphi_{1,n}^*$ and $\cos\varphi_1^*$ are the $(1,2)$-th entries of the optimal matrix of the dual in $\theta_{d,n}$ and $\tilde{\theta}_d$, respectively. This implies that $\lambda^*(\tilde{\theta}_d)$ admits both representations, one with the plus sign, and one with the minus sign, and this can happen only if the cycle is compatible, which cannot be the case for $\tilde{\theta}_d \in [0, \theta_1 - \sum_{i = 2}^{d-1}\theta_i)$ since $\theta_1 > \sum_{i=2}^d \theta_i$. This means that $\epsilon(\theta_d)_j$ is continuous for all $j \in [d]$ for varying $\theta_d \in [0, \theta_1 - \sum_{i = 2}^{d-1}\theta_i)$, which implies that the vector $\epsilon(\theta_d)$ is constant on $[0, \theta_1 - \sum_{i = 2}^{d-1}\theta_i)$, so that the behaviour of $\epsilon(\theta_d)$ is uniquely determined by $\epsilon(0)$. But we do know that
\[\epsilon(0) = (\epsilon_{d-1}, \epsilon(0)_d) = (-1, +\boldsymbol{1}_{d-2}^T, \epsilon(0)_d) \]

due to Proposition <ref> and the induction step: this, together with the fact that $\epsilon(0)_d = +1$ in order to make $\Sigma'_{\mathbb{S}}$ maximally incompatible, completes the proof.

We will prove the statement by induction, with base cases $d=3$, and $d=4$:

$d=3$ Suppose without loss of generality that $\theta_1, \theta_2$ are bounded away from singularity. Also, assume without loss of generality that $\theta_2, \theta_3 \leq \pi/2$, using Proposition <ref>, so that incompatibility means $\theta_1 > \theta_2 + \theta_3$. We will prove the base case
\[
R(\Sigma_{\mathbb{S}_3}) \gtrsim \theta_2 - \theta_1 -\theta_3.
\]

by showing that
\[
R(\Sigma_{\mathbb{S}_3}) \geq \frac{\theta_1-\theta_2-\theta_3}{\theta_1-\theta_2}\frac{\cos\theta_2-\cos\theta_1}{2},
\]

and since $\cos\theta_2-\cos\theta_1 \gtrsim_c \theta_1 - \theta_2$ being bounded away from singularity, the result would follow.  Now, fix arbitrary $\theta_1, \theta_2$ satisfying the hypothesis of the statement, and suppose $\theta_1-\theta_2 \leq \pi/2$. Observe that for $\theta_3 = 0$ and $\theta_3 = \theta_1-\theta_2$ the lower bound is satisfied with equality sign due to Example <ref> and Barrett's characterisation (<ref>), respectively. Now, call

\[
h = \frac{\theta_1-\theta_2-\theta_3}{\theta_1-\theta_2},
\]

and observe that the thesis is equivalent to
\[
\lambda^* = 1-R(\Sigma_{\mathbb{S}_d}) \leq 1 -   \frac{h}{2}(\cos\theta_2-\cos\theta_1),
\]

Now, thanks to the KKT representation of the optimal $\lambda^*$, in order to have $\lambda^* > 1 - h(\cos\theta_2-\cos\theta_1)/2$ we must have

\begin{align*}
\begin{cases}
\cos\theta_1 < \cos\varphi_1^* < \frac{\cos\theta_1 + h(\cos\theta_2-\cos\theta_1)/2}{1-h(\cos\theta_2-\cos\theta_1)/2} \\
\\
\cos\theta_2 > \cos\varphi_2^* > \frac{\cos\theta_2 - h(\cos\theta_2-\cos\theta_1)/2}{1-h(\cos\theta_2-\cos\theta_1)/2}\\
\\
\cos\theta_3 > \cos\varphi_3^* > \frac{\cos\theta_3 - h(\cos\theta_2-\cos\theta_1)/2}{1-h(\cos\theta_2-\cos\theta_1)/2},
\end{cases}
\end{align*}

with $\varphi^*_1 = \varphi^*_2 + \varphi^*_3$ due to Proposition <ref> (iii). We see numerically that this system of inequalities can never be satisfied for $\theta_3 \in (0, \theta_1-\theta_2)$. Finally, taking into account all the possible ways in which a generic $3$-cycle can be reduced to a $3$-cycle with at most one negative correlation, as stated in Proposition <ref>, we get
\[
R(\Sigma_{\mathbb{S}_3}) \gtrsim \max(\theta_1-\theta_2-\theta_3, \theta_2-\theta_1-\theta_3,\theta_3-\theta_1-\theta_2,\theta_1+\theta_2+\theta_3 - 2 \pi).
\]

$d=4$ Suppose without loss of generality that one of the two angles bounded away from singularity is $\theta_1$, with $\theta_1 > \theta_2 + \theta_3 + \theta_4$, and $\theta_2, \theta_3, \theta_4 \in [0, \pi/2]$. As shown in Figure <ref>, there are two possible cases: the first one (on the left) is when the two angles bounded away from singularity are adjacent, and the second one (on the right) when they are opposite to each other. We will use the following lemma:

Consider the $d$-cycle with $\mathbb{S}_d=\{\{1,2\},\ldots, \{d,1\}\}$ and $\Sigma_{\mathbb{S}_d}:= (\Sigma_{\{1,2\}}, \cdots, \Sigma_{ \{d,1\}})$. Then, for every optimal $\Sigma$ of the dual problem, i.e. $\Sigma_{\mathbb{S}_d} = \lambda^* A\Sigma + (1-\lambda^*)\Sigma_{\mathbb{S}_d}'$, and for every $d \geq 4$,

$$R(\Sigma_{\mathbb{S}_d}) \geq R(B_{\mathbb{S}_{d-1}}(\phi)) + R(E_{\mathbb{S}_3}(\phi)), \quad \forall \phi \in [\lambda^*\Sigma_{1,d-1}-R, \lambda^*\Sigma_{1,d-1}+R],$$

where $B_{\mathbb{S}_{d-1}}(\phi)= (\Sigma_{\{1,2\}}, \cdots, \Sigma_{ \{d-2,d-1\}}, \Sigma_{ \{d-1,1\}}(\phi))$, $E_{\mathbb{S}_3}(\phi)= (\Sigma_{ \{d-1, d\}}, \Sigma_{ \{d,1\}}, \Sigma_{ \{d-1,1\}}(\phi))$ and $\Sigma_{ \{d-1,1\}}(\phi)$ is the $2 \times 2$ correlation matrix with off-diagonal entries equal to $\phi$.

In the first case, suppose we add an edge between $(2,4)$ with correlation $\cos(\theta_3+\theta_4)$. We first show that this is a valid choice of $\phi$ to invoke Proposition <ref>. In this regard, observe that $R(E_{\mathbb{S}_3}(\phi)) = 0$ for all $\phi \in [\cos(\theta_{d-1} + \theta_d), \cos(\theta_{d-1} - \theta_d)]$, hence, since we proved $R(E_{\mathbb{S}_{d-1}}(\lambda^*\Sigma_{1,d-1}+R)) = 0$ in the proof of the lemma above, we must have $\cos(\theta_{d-1} + \theta_d) \leq \lambda^*\Sigma_{1,d-1}+R$. Similarly, $\cos(\theta_1 - \sum_{i = 2}^{d-2} \theta_i) \geq \lambda^*\Sigma_{1,d-1}-R$. This, together with the fact that $\cos(\theta_1 - \sum_{i = 2}^{d-2} \theta_i) \leq \cos(\theta_{d-1} + \theta_d)$ since $\theta_1 > \sum_{i = 2}^{d} \theta_i$, allows concluding that $\lambda^*\Sigma_{1,d-1}-R \leq \cos(\theta_1 - \sum_{i = 2}^{d-2} \theta_i) < \cos(\theta_{d-1} + \theta_d) \leq \lambda^*\Sigma_{1,d-1}+R$. Now, Proposition <ref> ensures that
\[R(\theta_1, \theta_2, \theta_3, \theta_4) \geq R(\theta_1, \theta_2, \theta_3 + \theta_4), \]

and since $\theta_1, \theta_2$ are bounded away from singularity, we can employ the lower bound we found for $d=3$, and conclude

\[
R(\Sigma_{\mathbb{S}_4}) \geq \frac{\theta_1 - \theta_2 - (\theta_3+\theta_4)}{\theta_1 - \theta_2}\frac{\cos\theta_2-\cos\theta_1}{2},
\]

which gives the desired result. In the second case, we can proceed in the same way as before, and get

\[
R(\Sigma_{\mathbb{S}_4}) \geq \frac{\theta_1 - \theta_2 - (\theta_3+\theta_4)}{\theta_1 - (\theta_3+\theta_4)}\frac{\cos(\theta_3+\theta_4)-\cos\theta_1}{2}.
\]

Now, if $\sin^2(\theta_3+\theta_4) \geq c$ we are done, otherwise, $\theta_4$ must be bounded away from singularity. Indeed, since $\theta_3, \theta_4 \in [0, \pi/2]$, and $\sin^2(\theta_3) \geq c$ by hypothesis, in order to have $\sin^2(\theta_3+\theta_4) < c$ we must have $\sin^2\theta_4 \geq 1-c$. Now, since we can assume that $c$ is small enough, say $c \leq 1/2$, we conclude $\sin^2\theta_4 \geq 1-c > c$. This implies that $\theta_4$ is bounded away from singularity, and since it is adjacent to $\theta_1$, we can proceed as in the first case to get the desired result.

The two possible configurations of the two angles bounded away from singularity when $d=4$. On the left, the two angles are adjacent, while on the right they are opposite to each other.

$d \geq 5$ Suppose again without loss of generality that $\theta_1$ is bounded away from singularity, and call $\theta_j$ the other one. Now, since $d \geq 5$, we can find $k \neq 1,j$ such that $\theta_k, \theta_{k+1}$ are not necessarily assumed to be bounded away from singularity. Then, proceeding as before, thanks to Proposition <ref>, we have
\[R(\theta_1, \ldots, \theta_d) \geq R(\theta_1, \ldots, \theta_{k-1}, \theta_{k}+\theta_{k+1}, \theta_{k+2}, \ldots, \theta_d), \]

so that the induction step gives immediately that
\begin{align*}
R(\theta_1, \ldots, \theta_d) &\geq R(\theta_1, \ldots, \theta_{k-1}, \theta_{k}+\theta_{k+1}, \theta_{k+2}, \ldots, \theta_d) \\
& \geq c' \left(\theta_1 -  (\theta_k + \theta_{k+1}) - \sum\limits_{i \neq 1,j,k,k+1} \theta_i\right) = c' \left(\theta_1  - \sum\limits_{i = 2}^d \theta_i\right),
\end{align*}

where $c'$ is a constant depending on $c$ only. Finally, taking into account all the possible ways in which a generic $d$-cycle can be reduced to a $d$-cycle with at most one negative correlation, as stated in Proposition <ref>, we get
\[
R(\Sigma_{\mathbb{S}_d}) \geq c' \mathop{\max\limits_{K \subseteq [d]}}\limits_{|K| \text{ odd}}\left(\sum\limits_{i \in K}\theta_i - (|K| -1) \pi - \sum\limits_{i \in K^c}\theta_i\right),
\]

where $c'>0$ depends only on $c$.

Suppose without loss of generality that $\theta_d \geq \theta_{d-1}$, and that $\theta_1 = \max_{i \in [d]} \theta_i$, with $\theta_2, \ldots, \theta_d \leq \pi/2$. Let $R \equiv R(\Sigma_{\mathbb{S}_d}) $, and let
\[
\Sigma_{\mathbb{S}_d} = (1-R)A\Sigma + R\Sigma'_{\mathbb{S}}  = \lambda^*A\Sigma + (1-\lambda^*)\Sigma'_{\mathbb{S}}
\]

be a (not necessarily unique) dual representation of $\Sigma_{\mathbb{S}_d}$, and denote by $\Sigma_{1,d-1}$ the entry $(1, d-1)$ of $\Sigma$. We will prove the statement in three steps:

* $R(B_{\mathbb{S}_{d-1}}(\lambda^*\Sigma_{1,d-1}+R)) \leq R(\Sigma_{\mathbb{S}_d})$ and $R(E_{\mathbb{S}_{3}}(\lambda^*\Sigma_{1,d-1}+R)) = 0$,

* $R(E_{\mathbb{S}_{3}}(\lambda^*\Sigma_{1,d-1}-R)) \leq R(\Sigma_{\mathbb{S}_d})$ and $R(B_{\mathbb{S}_{d-1}}(\lambda^*\Sigma_{1,d-1}-R)) = 0$,

* $\Xi(\phi) := R(B_{\mathbb{S}_{d-1}}(\phi)) + R(E_{\mathbb{S}_3}(\phi))$ is convex for all $\phi \in [-1,1]$.

* As for the fact that $R(E_{\mathbb{S}_{3}}(\lambda^*\Sigma_{1,d-1}+R)) = 0$ observe that
\begin{align*}
A^*E_{\mathbb{S}_{3}}(\lambda^*\Sigma_{1,d-1}+R) - I_3  &= \begin{pmatrix}
1 & \lambda^*\Sigma_{1,d-1} + R & \rho_d \\
\lambda^*\Sigma_{1,d-1} + R & 1 & \rho_{d-1} \\
\rho_{d} & \rho_{d-1} & 1
\end{pmatrix} = \\
1 & \lambda^*\Sigma_{1,d-1} + R & \lambda^*\Sigma_{1,d} + R \\
\lambda^*\Sigma_{1,d-1} + R & 1 & \lambda^*\Sigma_{d-1,d} + R \\
\lambda^*\Sigma_{1,d} + R & \lambda^*\Sigma_{d-1,d} + R & 1
\end{pmatrix} \\
& \quad \quad = \lambda^* \begin{pmatrix}
1 & \Sigma_{1,d-1} & \Sigma_{1,d} \\
\Sigma_{1,d-1} & 1 & \Sigma_{d-1,d} \\
\Sigma_{1,d} & \Sigma_{d-1,d} & 1
\end{pmatrix} + (1-\lambda^*)\begin{pmatrix}
1 & 1 & 1 \\
1 & 1 & 1 \\
1 & 1 & 1
\end{pmatrix},
\end{align*}

where the second equality follows from  the optimal choice of signs given in Proposition <ref>  (iii) under the hypothesis $\theta_1 = \max_{i \in [d]} \theta_i$, with $\theta_2, \ldots, \theta_d \leq \pi/2$. This implies $R(E_{\mathbb{S}_{3}}(\lambda^*\Sigma_{1,d-1}+R)) = 0$ since $A^*E_{\mathbb{S}_{3}}(\lambda^*\Sigma_{1,d-1}+R) - I_3$, which is the $3 \times 3$ correlation matrix whose $2 \times 2$ marginals are precisely those in $E_{\mathbb{S}_{3}}(\lambda^*\Sigma_{1,d-1}+R)$, is PSD being the sum of two PSD matrices. As for
$R(B_{\mathbb{S}_{d-1}}(\lambda^*\Sigma_{1,d-1}+R)) \leq R(\Sigma_{\mathbb{S}_d})$, observe that, if $\Sigma_{\mathbb{S}_d} = \lambda^* A\Sigma + (1-\lambda^*)\Sigma_{\mathbb{S}_d}'$, then

\[
B_{\mathbb{S}_{d-1}}(\lambda^*\Sigma_{1,d-1}+R) = \lambda^* A\Sigma_{|(-d)} + (1-\lambda^*)\Sigma_{B_{\mathbb{S}_{d-1}}}'',
\]

\[
\Sigma_{B_{\mathbb{S}_{d-1}}}'' = (\Sigma_{\{1,2 \}}', \ldots, \Sigma_{\{d-1,d-2\}}', \boldsymbol{1}_2 \boldsymbol{1}_2^T),
\]

which is maximally incompatible. To see why, observe that $\Sigma'_{\mathbb{S}_d}$ is maximally incompatible by definition of the dual representation, and since $\theta_1 = \max_{i \in [d]} \theta_i$, with $\theta_2, \ldots, \theta_d \leq \pi/2$, Proposition <ref>  (iii) ensures that

\[
\Sigma'_{\mathbb{S}_d} = (-\boldsymbol{1}_2 \boldsymbol{1}_2^T, +\boldsymbol{1}_2 \boldsymbol{1}_2^T, \ldots, +\boldsymbol{1}_2 \boldsymbol{1}_2^T),
\]

which leads to
\[
\Sigma_{B_{\mathbb{S}_{d-1}}}'' =  (-\boldsymbol{1}_2 \boldsymbol{1}_2^T, +\boldsymbol{1}_2 \boldsymbol{1}_2^T, \ldots, +\boldsymbol{1}_2 \boldsymbol{1}_2^T).
\]

This shows that $\Sigma_{|(-d)}$ is feasible for $B_{\mathbb{S}_{d-1}}(\lambda^*\Sigma_{1,d-1}+R)$, and implies that $R(B_{\mathbb{S}_{d-1}}(\lambda^*\Sigma_{1,d-1}+R)) \leq R(\Sigma_{\mathbb{S}_d})$.

* The arguments in the proof above can be followed mutatis mutandis to show that $R(E_{\mathbb{S}_{3}}(\lambda^*\Sigma_{1,d-1}-R)) \leq R(\Sigma_{\mathbb{S}_d})$ and $R(B_{\mathbb{S}_{d-1}}(\lambda^*\Sigma_{1,d-1}-R)) = 0$.

* In order to show that $R(\Sigma_{\mathbb{S}_d}) \geq R(B_{\mathbb{S}_{d-1}}(\phi)) + R(E_{\mathbb{S}_3}(\phi)), \forall \phi \in I,$ we will make use of the fact that $R$ is convex and continuous, as stated in Proposition <ref> (i) (ii), i.e.
\[
R\left(\mu\Sigma_\mathbb{S}^{(1)} + (1-\mu)\Sigma_\mathbb{S}^{(2)}\right) \leq \mu R\left(\Sigma_\mathbb{S}^{(1)}\right) + (1-\mu) R\left(\Sigma_\mathbb{S}^{(2)}\right), \text{ for all } \mu \in [0,1].
\]

Now, define
\[
\Xi(\phi) = R(B_{\mathbb{S}_{d-1}}(\phi)) + R(E_{\mathbb{S}_3}(\phi)), \text{ for all } \phi \in I = [-1,1].
\]

It is easy to see that $\Xi(\phi)$ is convex in $I$ since, for all $\phi_1, \phi_2 \in I$, for all $\mu \in [0,1]$,

\begin{align*}
\Xi(\mu\phi_1 + (1-\mu)\phi_2) & =  R(B_{\mathbb{S}_{d-1}}(\mu\phi_1 + (1-\mu)\phi_2) + R(E_{\mathbb{S}_3}(\mu\phi_1 + (1-\mu)\phi_2)) \\
& = R(\mu B_{\mathbb{S}_{d-1}}(\phi_1) + (1-\mu) B_{\mathbb{S}_{d-1}}(\phi_2)) + R(\mu E_{\mathbb{S}_{3}}(\phi_1) + (1-\mu) E_{\mathbb{S}_{3}}(\phi_2)) \\
& \leq \mu R(B_{\mathbb{S}_{d-1}}(\phi_1)) + (1-\mu) R(B_{\mathbb{S}_{d-1}}(\phi_2)) + \mu R(E_{\mathbb{S}_{3}}(\phi_1)) + (1-\mu) R(E_{\mathbb{S}_{3}}(\phi_2)) \\
& = \mu\Xi(\phi_1) + (1-\mu)\Xi(\phi_2).
\end{align*}

This, implies that, for all $\mu \in [0,1]$,
\begin{align*}
R & \geq \mu R(E_{\mathbb{S}_{d-1}}(\lambda^*\Sigma_{1,d-1}-R)) + (1-\mu)R(B_{\mathbb{S}_{d-1}}(\lambda^*\Sigma_{1,d-1}-R)) \\
& = \mu\Xi(\lambda^*\Sigma_{1,d-1}-R) + (1-\mu)\Xi(\lambda^*\Sigma_{1,d-1}+R) \geq \Xi(\lambda^*\Sigma_{1,d-1}+1 - 2\mu R) \\
& =: \Xi(\phi) = R(B_{\mathbb{S}_{d-1}}(\phi)) + R(E_{\mathbb{S}_3}(\phi)),
\end{align*}

for all $\phi \in [\lambda^*\Sigma_{1,d-1}-R, \lambda^*\Sigma_{1,d-1}+R]$, as claimed. For general angles $(\theta_1, \ldots, \theta_d)$, it is sufficient to perform the transformation outlined in Proposition <ref>, find $\phi$ and $I$ as above, and perform the inverse transformation.

Illustration of Proposition <ref>. We split the original $d$-cycle into two smaller cycles, adding the extra edge $\{1, d-1\}$ with associated correlation $\phi$. We end up with a $(d-1)$-cycle $B_{\mathbb{S}_{d-1}}(\phi)$ in yellow, and a $3$-cycle $E_{\mathbb{S}_{3}}(\phi)$ in blue, such that $R(\Sigma_{\mathbb{S}_d}) \geq R(B_{\mathbb{S}_{d-1}}(\phi)) + R(E_{\mathbb{S}_3}(\phi))$ for all $\phi \in [\lambda^*\Sigma_{1,d-1}-R, \lambda^*\Sigma_{1,d-1}+R]$.

As we can see from Figure <ref>, this reduction corresponds to adding an edge in correspondence to $\{1, d-1\}$, so that the $d$-cycle $\Sigma_{{\mathbb{S}}_d}$ is divided into two smaller cycles, $B_{\mathbb{S}_d}(\phi)$ of dimension $d-1$, and $E_{\mathbb{S}_d}(\phi)$ of dimension 3. The result ensures the possibility of adding a correlation $\rho_{1, d-1} = \phi$ for the edge $\{1,d-1\}$ to make $B_{\mathbb{S}_d}(\phi)$ and $E_{\mathbb{S}_d}(\phi)$ maximally compatible, or better, at least as compatible as the original $d$-cycle, since $R(\Sigma_{\mathbb{S}_d}) \geq R(B_{\mathbb{S}_d}(\phi)) + R(E_{\mathbb{S}_d}(\phi))$.

§.§ Proofs for Section <ref>

We prove the result by considering the two cases $d \geq 42$ and $d<42$ separately. For the first of these, as in the proof of Theorem <ref>, we focus on a proper subset of the testing problem: in this case, we construct distributions with consistent sequences of covariance matrices, so that our hypotheses reduce to statements about the compatibility of the associated sequences of correlation matrices. Formally, we look at

\[
H_0: R(\Sigma_\mathbb{S}) = 0 \quad \text{ vs. } \quad H_1(\rho): R(\Sigma_\mathbb{S}) > \rho,
\]

for fixed $\rho > 0$, and we aim at finding the smallest of such $\rho$'s for which we can have non-trivial power. Again, referring to the same $\mathcal{P}_\mathbb{S}(0)$ and $\mathcal{P}_\mathbb{S}(\rho)$ defined in Section <ref>, this corresponds to assuming that $\sigma^2_\mathbb{S}$ is always consistent, and constructing prior distributions just on $\{P_\mathbb{S} : R(\Sigma_\mathbb{S}) = 0\}$ and$ \{P_\mathbb{S} : R(\Sigma_\mathbb{S}) > \rho\}$. We specialise $\Sigma_{\mathbb{S}}$ to be

\[
\Sigma_{\mathbb{S}} = \Bigg\{\begin{pmatrix}
I_d & P \\
P^T & I_d
\end{pmatrix},\begin{pmatrix}
I_d & -P \\
-P^T & I_d
\end{pmatrix}, \begin{pmatrix}
I_d & \beta I_d \\
\beta I_d & I_d
\end{pmatrix}\Bigg\},
\]

and since $R(\Sigma_\mathbb{S}) \geq  \frac{3}{4d}\sum_{j = 1}^d (\sigma_j^2(P) -  \frac{1-\beta}{2})_+$ by Proposition <ref>, it is sufficient to study the testing problems

\[
H_0': \sum_{j = 1}^d (\theta_i)_+ \leq 0 \quad \text{ vs. } \quad H_1'(\rho'): \sum_{j = 1}^d (\theta_i)_+ > \rho',
\]

where $\theta_i = \sigma_j^2(P) -  \frac{1-\beta}{2}$, find the smallest $\rho'$ for which we have non-trivial power, and use the relationship $\rho = \frac{3}{4d} \rho'$. More precisely, focusing on the latter testing problem, we want to lower bound the minimax testing risk

\[
\rho^*(n_{\mathbb{S}}, \eta) := \inf\left\{\rho > 0: \exists \varphi_{\mathbb{S}} \in \Psi_{\mathbb{S}} : \sup_{P_{\mathbb{S},0} \in \mathcal{P}_{\mathbb{S}}(0)} P_{\mathbb{S},0}^{\otimes n_{\mathbb{S}}}(\varphi_{\mathbb{S}} = 1) + \sup_{P_{\mathbb{S},1} \in \mathcal{P}_{\mathbb{S}}(\rho)} P_{\mathbb{S},1}^{\otimes n_{\mathbb{S}}} (\varphi_{\mathbb{S}} = 0) \leq \eta \right\}
\]

where $\mathcal{P}_{\mathbb{S}}(0) = \{P_{\mathbb{S}} : (\operatorname{Corr}(P_{\mathbb{S}}), \operatorname{Var}(P_{\mathbb{S}})) = (\Sigma_{\mathbb{S}}, \boldsymbol{1}_\mathbb{S}) \text{ and } R(\Sigma_\mathbb{S}) = 0 \}$, $\mathcal{P}_{\mathbb{S}}(\rho) =  \{P_{\mathbb{S}} : (\operatorname{Corr}(P_{\mathbb{S}}), \operatorname{Var}(P_{\mathbb{S}})) = (\Sigma_{\mathbb{S}}, \boldsymbol{1}_\mathbb{S}) \text{ and } R(\Sigma_\mathbb{S}) > \rho \}$, and $\Psi_{\mathbb{S}}$ is the set of sequence of tests coherent with $\mathbb{S}$. To this aim, we start by defining two prior distributions $\mu_0, \mu_1$ for $P$. First, there exist two measures $\nu_0, \nu_1$ with matching moments up to the $M$-th order such that

I. $\operatorname{supp}\left(\nu_0\right) \subseteq[-b, 0], \quad \operatorname{supp}\left(\nu_1\right) \subseteq[-b, 0] \cup\left\{\frac{b}{4 M^2}\right\}$

II. $\nu_1\left(\left\{\frac{b}{4 M^2}\right\}\right) \geq \frac{1}{2}$

III. $\forall k \in\{0,1, \ldots, M\}: \int z^k \nu_0(\mathrm{~d} z)=\int z^k \nu_1(\mathrm{~d} z)$.

This is proved in [Juditsky and Nemirovski, 2002] using ideas from the theory of best polynomial approximation. A different, but closely related version, was proved in [Cai and Low, 2011] using similar techniques. Such prior distributions have been extensively used in the minimax literature in the last decade, and led to optimal, or nearly-optimal, lower bounds in many problems of interest such as optimal estimation of nonsmooth functionals [Cai and Low, 2011, Jiao et al., 2016, Thépaut and Verzelen, 2021], testing MCAR in a fully nonparametric setting [Berrett and Samworth, 2023], and testing convex hypothesis [Blanchard et al., 2018]. Let $\mathcal{U}(d)$ denote the (normalised) Haar measure over the Lie group of orthogonal matrices $SO(d) = \{ U \in \mathbb{R}^{d,d} : U^T U = UU^T = I_d\}$, and let $\nu_0, \nu_1$ the distributions with matching moments up to the order $M$ defined above. Calling $\delta_0$ the Dirac measure in zero, we define $\mu_i$ to be the distribution of $P=U^T \Lambda U$, where $U \sim \mathcal{U}(d)$, and $\Lambda = \operatorname{diag}(\sigma_{1:d})$, with $\sigma_{1:d} \sim \nu_i^{\otimes \lceil d/2 \rceil } \otimes \delta_0 ^{\otimes (d - \lceil d/2 \rceil)}$, for $i \in \{0, 1\}$. Observe now that the support of $\mu_1$ also contains elements in $(\mathcal{P}_\mathbb{S}(\rho))^C$. In order to overcome this, we will consider the conditional measure $\mu_1|\xi$, where $\xi$ is the event
\[
\xi=\left\{\sum_{i=1}^d \mathbbm{1}_{\left\{\mu_i=b/4M^2\right\}} \geq \frac{d}{3}\right\},
\]

which ensures that $\mu_1|\xi$ is supported on the alternative. Now, given $P$, we use the shorthand

\[
N_\mathbb{S}^{\otimes n_\mathbb{S}} \equiv N_\mathbb{S}^{\otimes n_\mathbb{S}}(P) = \left(N^{\otimes n_1}\left(0, \begin{pmatrix}
I_d & P \\
P^T & I_d
\end{pmatrix}\right), N^{\otimes n_2}\left(0, \begin{pmatrix}
I_d & -P \\
-P^T & I_d
\end{pmatrix}\right), N^{\otimes n_3}\left(0, \begin{pmatrix}
I_d & \beta I_d \\
\beta I_d & I_d
\end{pmatrix}\right)\right).
\]

The marginal distribution of the data when $P$ is generated according to $\mu_1|\xi$ is then given by the mixture distribution

\[
\mathbb{E}_{\mu_1|\xi}N_\mathbb{S}^{\otimes n_\mathbb{S}} = \left(\mathbb{E}_{\mu_1|\xi}N^{\otimes n_1}\left(0, \begin{pmatrix}
I_d & P \\
P^T & I_d
\end{pmatrix}\right), \mathbb{E}_{\mu_1|\xi}N^{\otimes n_2}\left(0, \begin{pmatrix}
I_d & -P \\
-P^T & I_d
\end{pmatrix}\right), N^{\otimes n_3}\left(0, \begin{pmatrix}
I_d & \beta I_d \\
\beta I_d & I_d
\end{pmatrix}\right)\right).
\]

Similarly, the marginal distribution of the data when $P$ is generated according to $\mu_i$ is then given by the mixture distribution

\[
\mathbb{E}_{\mu_i}N_\mathbb{S}^{\otimes n_\mathbb{S}} = \left(\mathbb{E}_{\mu_i}N^{\otimes n_1}\left(0, \begin{pmatrix}
I_d & P \\
P^T & I_d
\end{pmatrix}\right), \mathbb{E}_{\mu_i}N^{\otimes n_2}\left(0, \begin{pmatrix}
I_d & -P \\
-P^T & I_d
\end{pmatrix}\right), N^{\otimes n_3}\left(0, \begin{pmatrix}
I_d & \beta I_d \\
\beta I_d & I_d
\end{pmatrix}\right)\right),
\]

for $i \in \{0,1 \}$.
For every test sequence $\varphi_{\mathbb{S}} \in \Psi_{\mathbb{S}}$, and for prior distributions $\mu_0, \mu_1|\xi$, we can bound the total error probability as

\begin{align*}
\mathcal{R}(n_\mathbb{S}, \rho') &  = \sup_{P_{\mathbb{S},0} \in \mathcal{P}_{\mathbb{S}}(0)} P_{\mathbb{S},0}^{\otimes n_{\mathbb{S}}}(\varphi_{\mathbb{S}} = 1) + \sup_{P_{\mathbb{S},1} \in \mathcal{P}_{\mathbb{S}}(\rho)} P_{\mathbb{S},1}^{\otimes n_{\mathbb{S}}} (\varphi_{\mathbb{S}} = 0) \\
%& \geq \sup_{\Sigma_{\mathbb{S}} \in \mathcal{P}_{\mathbb{S}}(0)} \mathbb{P}_{N(0,\Sigma_{\mathbb{S}})} (\varphi_{\mathbb{S}} = 1) + \sup_{\Sigma_{\mathbb{S}} \in \mathcal{P}_{\mathbb{S}}(\rho)} \mathbb{P}_{N(0,\Sigma_{\mathbb{S}})} (\varphi_{\mathbb{S}} = 0) \\
& \geq \mathbb{E}_{\mu_0}N_\mathbb{S}^{\otimes n_\mathbb{S}}(\varphi_{\mathbb{S}} = 1) + \mathbb{E}_{\mu_1|\xi}N_\mathbb{S}^{\otimes n_\mathbb{S}}(\varphi_{\mathbb{S}} = 0) \\
& = \mathbb{E}_{\mu_0}N_\mathbb{S}^{\otimes n_\mathbb{S}}(\varphi_{\mathbb{S}} = 1)+ 1-\frac{\mathbb{E}_{\mu_1}N_\mathbb{S}^{\otimes n_\mathbb{S}}(\{\varphi_\mathbb{S}=1\} \cap \xi)}{\mu_1(\xi)} \\
& \geq \mathbb{E}_{\mu_0}N_\mathbb{S}^{\otimes n_\mathbb{S}}(\varphi_{\mathbb{S}} = 1) + 1-\frac{10}{9}\mathbb{E}_{\mu_1}N_\mathbb{S}^{\otimes n_\mathbb{S}}(\varphi_{\mathbb{S}} = 1) \\
& \geq \mathbb{E}_{\mu_0}N_\mathbb{S}^{\otimes n_\mathbb{S}}(\varphi_{\mathbb{S}} = 1) + \frac{10}{9}\mathbb{E}_{\mu_1}N_\mathbb{S}^{\otimes n_\mathbb{S}}(\varphi_{\mathbb{S}} = 0)-\frac{1}{9} \\
& \geq \mathbb{E}_{\mu_0}N_\mathbb{S}^{\otimes n_\mathbb{S}}(\varphi_{\mathbb{S}} = 1) + \mathbb{E}_{\mu_1}N_\mathbb{S}^{\otimes n_\mathbb{S}}(\varphi_{\mathbb{S}} = 0)-\frac{1}{9} \\
& \geq 1 - \operatorname{TV}\left(\mathbb{E}_{\mu_0}N_\mathbb{S}^{\otimes n_\mathbb{S}}, \mathbb{E}_{\mu_1}N_\mathbb{S}^{\otimes n_\mathbb{S}} \right) -\frac{1}{9}.
\end{align*}

The second inequality follows from Hoeffding's inequality, which ensures that for all $d \geq 42$,

\[
\mu_1\left(\xi\right) \geq \frac{9}{10},
\]

since $\mu_1(\{b/4M^2\}) \geq 1/2$ by II. This shows that it is now sufficient to control the total variation distance between the marginals of $N_\mathbb{S}^{\otimes n_\mathbb{S}}$ with respect to the unconditional priors $\mu_0, \mu_1$ by finding $b/4M^2$ such that $\operatorname{TV}\left(\mathbb{E}_{\mu_0}N_\mathbb{S}^{\otimes n_\mathbb{S}}, \mathbb{E}_{\mu_1}N_\mathbb{S}^{\otimes n_\mathbb{S}} \right) \leq 1/2 - 1/9$. This would imply that $\mathcal{R}(n_\mathbb{S}, \rho') \geq 1/2$, and would lead to
\[
\rho' = \frac{d}{3} \frac{b}{4M^2},\]

where the extra $d/3$ factor comes from conditioning on the event $\xi$. Hence, let us now focus on controlling $\operatorname{TV}\left(\mathbb{E}_{\mu_0}N_\mathbb{S}^{\otimes n_\mathbb{S}}, \mathbb{E}_{\mu_1}N_\mathbb{S}^{\otimes n_\mathbb{S}} \right)$. We have

\begin{align*}
\operatorname{TV}&\left(\mathbb{E}_{\mu_0}N_\mathbb{S}^{\otimes n_\mathbb{S}}, \mathbb{E}_{\mu_1}N_\mathbb{S}^{\otimes n_\mathbb{S}} \right) \\
& = \operatorname{TV}\Bigg\{\left(\mathbb{E}_{\mu_0} N^{\otimes n_1}\left(0, \begin{pmatrix}
I_d & P \\
P^T & I_d
\end{pmatrix}\right), \mathbb{E}_{\mu_0}N^{\otimes n_2}\left(0, \begin{pmatrix}
I_d & -P \\
-P^T & I_d
\end{pmatrix}\right), N^{\otimes n_3}\left(0, \begin{pmatrix}
I_d & \beta I_d \\
\beta I_d & I_d
\end{pmatrix}\right) \right), \\
& \quad \quad \quad \quad \quad  \left(\mathbb{E}_{\mu_1} N^{\otimes n_1}\left(0, \begin{pmatrix}
I_d & P \\
P^T & I_d
\end{pmatrix}\right), \mathbb{E}_{\mu_1}N^{\otimes n_2}\left(0, \begin{pmatrix}
I_d & -P \\
-P^T & I_d
\end{pmatrix}\right), N^{\otimes n_3}\left(0, \begin{pmatrix}
I_d & \beta I_d \\
\beta I_d & I_d
\end{pmatrix}\right) \right) \Bigg\} \\
& = \operatorname{TV}\Bigg\{\left(\mathbb{E}_{\mu_0} N^{\otimes n_1}\left(0, \begin{pmatrix}
I_d & P \\
P^T & I_d
\end{pmatrix}\right), \mathbb{E}_{\mu_0}N^{\otimes n_2}\left(0, \begin{pmatrix}
I_d & -P \\
-P^T & I_d
\end{pmatrix}\right) \right), \\
& \quad \quad \quad \quad \quad  \left(\mathbb{E}_{\mu_1} N^{\otimes n_1}\left(0, \begin{pmatrix}
I_d & P \\
P^T & I_d
\end{pmatrix}\right), \mathbb{E}_{\mu_1}N^{\otimes n_2}\left(0, \begin{pmatrix}
I_d & -P \\
-P^T & I_d
\end{pmatrix}\right) \right) \Bigg\} \\
& \leq \operatorname{TV}\Bigg\{\mathbb{E}_{\mu_0}N^{\otimes n_1} \left(0, \begin{pmatrix}
I_d & P \\
P^T & I_d
\end{pmatrix}\right), \mathbb{E}_{\mu_1}N^{\otimes n_1} \left(0, \begin{pmatrix}
I_d & P \\
P^T & I_d
\end{pmatrix}\right)\Bigg\} \\
& + \operatorname{TV}\Bigg\{\mathbb{E}_{\mu_0}N^{\otimes n_2} \left(0, \begin{pmatrix}
I_d & -P \\
-P^T & I_d
\end{pmatrix}\right), \mathbb{E}_{\mu_1}N^{\otimes n_2} \left(0, \begin{pmatrix}
I_d & -P \\
-P^T & I_d
\end{pmatrix}\right) \Bigg\}.
\end{align*}

Dealing with such $\mu_0, \mu_1$ is not straightforward, due to the presence of the integrals with respect to the Haar measure. Nonetheless, following similar ideas as in [Thépaut and Verzelen, 2021], we upper bound the total variance distance above using the following two lemmata, where we suppose $P$ to be symmetric.

Let $P$ be symmetric, with spectral decomposition $P = U^T \Lambda U$. Let $\mathcal{U}(d)$ denote the (normalised) Haar measure over the Lie group of orthogonal matrices $SO(d) = \{ U \in \mathbb{R}^{d,d} : U^T U = UU^T = I_d\}$, and let $\nu_0, \nu_1$ the distributions with matching moments up to the order $M$ defined above. Denote by $\mu_i$ the distribution of $U^T \Lambda U$, where $U \sim \mathcal{U}(d)$, and $\Lambda = \operatorname{diag}(\sigma_{1:d})$, with $\sigma_{1:d} \sim \nu_i^{\otimes \lceil d/2 \rceil } \otimes \delta_0 ^{\otimes (d - \lceil d/2 \rceil)}$. Then
\begin{align*}
\operatorname{TV}\Bigg\{\mathbb{E}_{\mu_0}& N^{\otimes n} \left(0, \begin{pmatrix}
I_d & P \\
P^T & I_d
\end{pmatrix}\right), \mathbb{E}_{\mu_1}N^{\otimes n} \left(0, \begin{pmatrix}
I_d & P \\
P^T & I_d
\end{pmatrix}\right)\Bigg\} \\
& \leq \lceil d/2 \rceil \operatorname{TV}\Bigg\{\mathbb{E}_{\tilde{\pi}_0}\left\{N^{\otimes n}\left(\boldsymbol{0}_{2d}, \begin{pmatrix}
I_{d} & \eta u u^T \\
\eta u u^T & I_{d}
\end{pmatrix}\right) \right\}, \mathbb{E}_{\tilde{\pi}_1}\left\{N^{\otimes n}\left(\boldsymbol{0}_{2d}, \begin{pmatrix}
I_{d} & \eta' u' u'^T \\
\eta' u' u'^T & I_{d}
\end{pmatrix}\right) \right\} \Bigg\},
\end{align*}

where $\tilde{\pi}_0$ (resp. $\tilde{\pi}_1$) is the distribution of $\eta u u^T$ (resp. $\eta' u' u'^T$), where $\eta \sim \nu_0$ (resp. $\eta' \sim \nu_1$) and $u = (u_{d'}, \boldsymbol{0}^T_{d-d'})$ (resp. $u' = (u'_{d'}, \boldsymbol{0}^T_{d-d'})$) is such that $u_{d'}$ (resp $u'_{d'}$) is a uniform sample from the $d'$-dimensional sphere $\mathcal{S}^{d'-1} = \{x \in \mathbb{R}^{d'}:\|x\|_2 = 1 \}$, with $d' = d+1-\lceil d/2 \rceil$.

With the same notation as above, then

\begin{align*}
\operatorname{TV}^2&\Bigg\{\mathbb{E}_{\tilde{\pi}_0}\left\{N^{\otimes n}\left(\boldsymbol{0}_{2d}, \begin{pmatrix}
I_d & \eta u u^T \\
\eta u u^T & I_d
\end{pmatrix}\right) \right\},  \mathbb{E}_{\tilde{\pi}_1}\left\{N^{\otimes n}\left(\boldsymbol{0}_{2d}, \begin{pmatrix}
I_d & \eta' u' u'^T \\
\eta' u' u'^T & I_d
\end{pmatrix}\right) \right\}\Bigg\} \\
& \quad \quad \quad \leq \sum\limits_{k = M +1}^\infty \binom{k+n-1}{n-1}\mathbb{E}[u_1^{2k}] \left(\int \eta^{k} [\nu_0(d\eta)-\nu_1(d\eta)] \right)^2.
\end{align*}

Applying these lemmata, it follows that

\begin{align*}
\operatorname{TV}&\Bigg\{\mathbb{E}_{\mu_0}N^{\otimes n_1} \left(0, \begin{pmatrix}
I_d & P \\
P^T & I_d
\end{pmatrix}\right), \mathbb{E}_{\mu_1}N^{\otimes n_1} \left(0, \begin{pmatrix}
I_d & P \\
P^T & I_d
\end{pmatrix}\right)\Bigg\} \ \\
& \leq \lceil d/2 \rceil \operatorname{TV}\Bigg\{\mathbb{E}_{\tilde{\pi}_0}\left\{N^{\otimes n_1}\left(\boldsymbol{0}_{2d}, \begin{pmatrix}
I_d & \eta u u^T \\
\eta u u^T & I_d
\end{pmatrix}\right) \right\}, \mathbb{E}_{\tilde{\pi}_1}\left\{N^{\otimes n_1}\left(\boldsymbol{0}_{2d}, \begin{pmatrix}
I_d & \eta' u' u'^T \\
\eta' u' u'^T & I_d
\end{pmatrix}\right) \right\}  \Bigg\} \\
& \leq \lceil d/2 \rceil \sqrt{\sum_{k = M+1}^\infty \binom{k+n_1-1}{n_1-1} \mathbb{E}[u_1^{2k}] \left(\int \eta^{k} [\nu_0(d\eta)-\nu_1(d\eta)] \right)^2} ,
\end{align*}

where the first inequality comes from Lemma <ref>, and the second from Lemma <ref>. Here $u_1$ is the first coordinate of a uniform random vector in the $d'$-dimensional unit sphere, and $\nu_0, \nu_1$ are the distributions with matching moments up the order $M$ defined above. Now, observe that $u_1^2 \overset{d}{=} Z_1^2/\sum_{i=1}^{d'} Z_i^2$ where $Z_i \overset{\text{i.i.d.}}{\sim} N(0,1)$,  due to the fact that the standard normal distribution is isotropic. Hence $u_1^2 \sim \operatorname{Beta}(\frac{d'-1}{2}, \frac{1}{2})$ since if $X \sim \chi^2(\alpha)$ and $Y \sim \chi^2(\beta)$ are independent, then $ \frac{X}{X+Y} \sim \operatorname{Beta}\left(\frac{\alpha}{2}, \frac{\beta}{2}\right)$. It follows that

\begin{align*}
\mathbb{E}[u_1^{2k}] & = \int_{-1}^{1} \frac{u^{2k}(1-u^2)^{\frac{d'-3}{2}}}{B(\frac{d'-1}{2}, \frac{1}{2})} du = \int_{0}^{1} \frac{v^{k-\frac{1}{2}}(1-v)^{\frac{d'-1}{2}-1}}{B(\frac{d'-1}{2}, \frac{1}{2})} dv \\
& = \frac{B(\frac{d'-1}{2}, k +\frac{1}{2})}{B(\frac{d'-1}{2}, \frac{1}{2})} = \frac{\Gamma(k+\frac{1}{2})}{\Gamma(\frac{1}{2})} \frac{\Gamma(\frac{d'}{2})}{\Gamma(\frac{d'}{2} +k)}.
\end{align*}

\[
\left(\int \eta^{k} [\nu_0(d\eta)-\nu_1(d\eta)] \right)^2 \leq \left(b^k\left(1+\frac{1}{4^kM^{2k}} \right)\right)^2 \leq 4b^{2k}.
\]

If we choose $b^2 = \frac{d'}{4n}$, we have

\begin{align*}
\sum_{k = M+1}^\infty \binom{k+n-1}{n-1} & \mathbb{E}[u_1^{2k}] \left(\int \eta^{k} [\nu_0(d\eta)-\nu_1(d\eta)] \right)^2 \\
& \leq 4 \sum_{k = M+1}^\infty \binom{k+n-1}{n-1} \frac{\Gamma(k+\frac{1}{2})}{\Gamma(\frac{1}{2})} \frac{\Gamma(\frac{d'}{2})}{\Gamma(\frac{d'}{2} +k)} b^{2k} \\
& = 4 \sum_{k = M+1}^\infty \frac{\Gamma(n+k)}{\Gamma(n)\Gamma(k+1)} \frac{\Gamma(k+\frac{1}{2})}{\Gamma(\frac{1}{2})} \frac{\Gamma(\frac{d'}{2})}{\Gamma(\frac{d'}{2} +k)} b^{2k} \\
& = 4 \sum_{k = M+1}^\infty \frac{\Gamma(k+\frac{1}{2})}{\Gamma(k+1)\Gamma(\frac{1}{2})} \frac{\Gamma(\frac{d'}{2})}{\Gamma(\frac{d'}{2} +k)} \frac{\Gamma(n+k)}{\Gamma(n)} \frac{(d')^k}{4^kn^k} \\
& = 4 \sum_{k = M+1}^\infty \frac{\Gamma(k+\frac{1}{2})}{\Gamma(k+1)\Gamma(\frac{1}{2})} \frac{(\frac{d'}{2})^k \Gamma(\frac{d'}{2})}{\Gamma(\frac{d'}{2} +k)} \frac{\Gamma(n+k)}{n^k \Gamma(n)} \frac{1}{2^k} \\
& \leq  4 \sum_{k = M+1}^\infty
\frac{(\frac{d'}{2})^k \Gamma(\frac{d'}{2})}{\Gamma(\frac{d'}{2} +k)} \frac{\Gamma(n+k)}{n^k \Gamma(n)} 2^{-k} \leq 4 \cdot 2^{-(M+1)} = 2^{-(M-1)}.
\end{align*}

The second inequality follows from the fact that $\frac{\Gamma(k+\frac{1}{2})}{\Gamma(k+1)\Gamma(\frac{1}{2})} \leq 1$, while the third one follows from the fact that

\[
\frac{(\frac{d}{2})^k \Gamma(\frac{d}{2})}{\Gamma(\frac{d}{2} +k)} \frac{\Gamma(n+k)}{n^k \Gamma(n)} \leq 1.
\]

Indeed, writing $\psi$ for the digamma function, the function $x \mapsto \log \frac{a^k \Gamma(a)}{\Gamma(a+k)}$ has derivative $\psi(a)-\psi(a+k)+k/a > 0$, and is therefore increasing. Thus, whenever $n \geq d/2 \geq d'/2$ the inequality follows.
Summing up, if we set $b/4M^2 = d/\{4(n_1 \wedge n_2)\}$,  we have that

\begin{align*}
\operatorname{TV}\left(\mathbb{E}_{\mu_0}N_\mathbb{S}^{\otimes n_\mathbb{S}}, \mathbb{E}_{\mu_1}N_\mathbb{S}^{\otimes n_\mathbb{S}} \right) & \leq \operatorname{TV}\Bigg\{\mathbb{E}_{\mu_0}N^{\otimes n_1} \left(0, \begin{pmatrix}
I_d & P \\
P^T & I_d
\end{pmatrix}\right), \mathbb{E}_{\mu_1}N^{\otimes n_1} \left(0, \begin{pmatrix}
I_d & P \\
P^T & I_d
\end{pmatrix}\right)\Bigg\}  \\
& + \operatorname{TV}\Bigg\{\mathbb{E}_{\mu_0}N^{\otimes n_2} \left(0, \begin{pmatrix}
I_d & -P \\
-P^T & I_d
\end{pmatrix}\right), \mathbb{E}_{\mu_1}N^{\otimes n_2} \left(0, \begin{pmatrix}
I_d & -P \\
-P^T & I_d
\end{pmatrix}\right) \Bigg\} \\
& \leq 2 \lceil d/2 \rceil 2^{-\frac{M-1}{2}} \leq (d+1)2^{-\frac{M-1}{2}},
\end{align*}

which is upper bounded by $1/2 - 1/9$ if and only if
\[
M > 2\frac{\log (d+1) - \log(1/2 - 1/9)}{\log2} + 1.
\]

Hence, this shows that
\[
\frac{b}{4M^2} \gtrsim \sqrt{\frac{d}{(n_1 \wedge n_2) \log^4 d}}
\]
is sufficient to have $\operatorname{TV}\left(\mathbb{E}_{\mu_0}N_\mathbb{S}^{\otimes n_\mathbb{S}}, \mathbb{E}_{\mu_1}N_\mathbb{S}^{\otimes n_\mathbb{S}} \right) \leq 1/2-1/9$, which implies that $\mathcal{R}(n_\mathbb{S}, \rho') =  \mathcal{R}(n_\mathbb{S}, \frac{d}{3}\frac{b}{4M^2}) \geq 1/2$. This allows us to conclude that
\[
\rho^*  \geq \frac{3}{4d}\rho' = \frac{b}{16M^2} \gtrsim \sqrt{\frac{d}{(n_1 \wedge n_2) \log^4 d}}.\]

We finally turn to the simpler case $d < 42$. It is sufficient to work as in the proof of Theorem <ref>, and show that testing the consistency of the variances represents the essential difficulty of the problem. More precisely, we will show that testing

\[
H_0: V(\Sigma_\mathbb{S}) = 0 \quad \text{ vs. } \quad H_1(\rho): V(\Sigma_\mathbb{S}) > \rho,
\]

requires at least a separation of the order $\sqrt{1/(n_1 \wedge n_2)}$, and since $T = V(\sigma^2_\mathbb{S}) + R(\Sigma_\mathbb{S})$, the statement will follow. To this aim, we bound the total error probability by choosing

\[
P_{\mathbb{S},0}^{\otimes n_\mathbb{S}} = \left(N^{\otimes n_1}(\boldsymbol{0}_{2d}, I_{2d}), N^{\otimes n_2}(\boldsymbol{0}_{2d}, I_{2d}), N^{\otimes n_3}(\boldsymbol{0}_{2d}, I_{2d}) \right) \in \mathcal{P}_{\mathbb{S}}(0),
\]

\[
P_{\mathbb{S},1}^{\otimes n_\mathbb{S}} = \left(N^{\otimes n_1}(\boldsymbol{0}_{2d},\operatorname{diag}(1+\delta, 1 \ldots, 1)), N^{\otimes n_2}(\boldsymbol{0}_{2d}, \operatorname{diag}(1-\delta, 1 \ldots, 1)), N^{\otimes n_3}(\boldsymbol{0}_{2d}, I_{2d}) \right) \in \mathcal{P}_{\mathbb{S}}(\delta).
\]

We have

\begin{align*}
\mathcal{R}(n_\mathbb{S}, \delta) & =\inf_{\varphi_\mathbb{S}} \biggl\{ \sup_{P_{\mathbb{S},0} \in \mathcal{P}_{\mathbb{S}}(0)} P_{\mathbb{S},0}^{\otimes n_{\mathbb{S}}}(\varphi-\mathbb{S} = 1)  + \sup_{P_{\mathbb{S},1} \in \mathcal{P}_{\mathbb{S}}(\delta)} P_{\mathbb{S},1}^{\otimes n_{\mathbb{S}}} (\varphi-\mathbb{S} = 0) \biggr\} \geq 1 - \operatorname{TV}\bigl( P_{\mathbb{S},0}^{\otimes n_{\mathbb{S}}} , P_{\mathbb{S},1}^{\otimes n_{\mathbb{S}}} \bigr) \\
& \geq \left( 1 - \operatorname{TV}\bigl(N^{\otimes n_1}(\boldsymbol{0}_{2d}, I_{2d}), N^{\otimes n_1}(\boldsymbol{0}_{2d},\operatorname{diag}(1+\delta, 1 \ldots, 1) \bigr)\right) - \frac{1}{2}\\
& + \left( 1 - \operatorname{TV}\bigl(N^{\otimes n_2}(\boldsymbol{0}_{2d}, I_{2d}), N^{\otimes n_2}(\boldsymbol{0}_{2d},\operatorname{diag}(1-\delta, 1 \ldots, 1) \bigr)\right) - \frac{1}{2}.
\end{align*}

Now, if $P_0 := N^{\otimes n_1}(\boldsymbol{0}_{2d}, I_{2d}), P_1 := N^{\otimes n_1}(\boldsymbol{0}_{2d},\operatorname{diag}(1+\delta, 1 \ldots, 1))$,

\begin{align*}
4 \operatorname{TV}(P_0, P_1)^2 & \leq \operatorname{\chi^2}\left(P_0, P_1 \right) = \int \left(\frac{dP_1}{dP_0}\right)^2 dP_0 - 1 \\
& = \frac{1}{(1+\delta)^{n_1}}\int \left(  \prod_{i = 1}^{n_1} \exp\left\{ \frac{\delta}{2(1+\delta)}x_{i1}^2\right\}\right)^2 dP_0 - 1\\
& = \frac{1}{(1+\delta)^{n_1}}\int  \prod_{i = 1}^{n_1} \exp\left\{ \frac{\delta}{1+\delta}x_{i1}^2\right\} dP_0 - 1 \\
& = \frac{1}{(1+\delta)^{n_1}}\int \prod_{i =1}^{n_1} (2\pi)^{-d} \exp\left\{-\frac{1}{2}x^T \operatorname{diag}\left( \frac{1-\delta}{1+\delta}, 1, \ldots, 1\right) x\right\} dx - 1 \\
& = (1-\delta^2)^{-n_1/2} - 1\leq e^{n_1\delta^2/2} - 1,
\end{align*}

from which we see that $\operatorname{TV}\left(P_0, P_1 \right) \leq 1/4$ if $\delta \leq \sqrt{2\log(5/4)/n_1}$. The same holds true for $Q_0 := N^{\otimes n_2}(\boldsymbol{0}_{2d}, I_{2d}), Q_1 := N^{\otimes n_2}(\boldsymbol{0}_{2d},\operatorname{diag}(1-\delta, 1 \ldots, 1))$, which shows that $\mathcal{R}(n_\mathbb{S}, \delta) \geq 1/2$ if $\delta=\sqrt{\frac{2\log(5/4)}{n_1 \wedge n_2}}$. The above bound on the total variation distance demonstrates that we may choose $\delta=\sqrt{2\log(5/4)/n_1 \wedge n_2}$, and hence that we have

\[
\rho^* \geq \delta = \sqrt{\frac{2\log(5/4)}{n_1 \wedge n_2}},
\]

as claimed.

Let $\varphi(z)$ denote the density of the $d$-dimensional Gaussian law with respect to the Lebesgue measure. By the triangle inequality we have that

\begin{align*}
\operatorname{TV} & \Bigg\{\mathbb{E}_{\mu_0}\left\{ N^{\otimes n}\left(\boldsymbol{0}_{2d}, \begin{pmatrix}
I_d & U^T \Lambda U \\
U^T \Lambda U & I_d
\end{pmatrix}\right) \right\}, \mathbb{E}_{\mu_1}\left\{N^{\otimes n}\left(\boldsymbol{0}_{2d}, \begin{pmatrix}
I_d & U^T \Lambda U \\
U^T \Lambda U & I_d
\end{pmatrix}\right) \right\} \Bigg\} \\
& \leq \sum_{j = 0}^{\lceil d/2 \rceil-1} \operatorname{TV}\Bigg\{\mathbb{E}_{\pi_j}\left\{N^{\otimes n}\left(\boldsymbol{0}_{2d}, \begin{pmatrix}
I_d & U^T \Lambda U \\
U^T \Lambda U & I_d
\end{pmatrix}\right) \right\}, \mathbb{E}_{\pi_{j+1}}\left\{N^{\otimes n}\left(\boldsymbol{0}_{2d}, \begin{pmatrix}
I_d & U^T \Lambda U \\
U^T \Lambda U & I_d
\end{pmatrix} \right) \right\}\Bigg\},
\end{align*}

where $\pi_j$ is distribution of $U^T \Lambda U$, where $U \sim \mathcal{U}(d)$ is common for all $\pi_j$, while $\Lambda = \operatorname{diag}(\sigma_{1:d})$, with $\sigma_{1:d} \sim \nu_0^{\otimes (\lceil d/2 \rceil -j)} \otimes \nu_1^{\otimes j} \otimes \delta_0 ^{\otimes \lfloor d/2 \rfloor}$, for $j \in \{0, \ldots, \lceil d/2 \rceil - 1\}$. Observe that $\pi_0 = \mu_0$ and $\pi_{\lceil d/2 \rceil} = \mu_1$, so that this inequality essentially interpolates $\mu_0$ and $\mu_1$ with $\lceil d/2 \rceil$ intermediate measures such that, for every $j \in \{0, \ldots, \lceil d/2 \rceil - 1\}$, $\pi_j$ differs from $\pi_{j+1}$ only for the distribution of $\sigma_j$ in $\Lambda$. Now, consider a generic $j \in \{0, \ldots, \lceil d/2 \rceil - 1\}$ and define $S:= \{1, \ldots, \lceil d/2 \rceil -j-1, \lceil d/2 \rceil -j+1, \ldots, \lceil d/2 \rceil  \}$. We will show that we can bound each term of the summation above by
\[\operatorname{TV}\Bigg\{\mathbb{E}_{\tilde{\pi}_0}\left\{N^{\otimes n}\left(\boldsymbol{0}_{2d}, \begin{pmatrix}
I_d & \eta u u^T \\
\eta u u^T & I_d
\end{pmatrix}\right) \right\}, \mathbb{E}_{\tilde{\pi}_1}\left\{N^{\otimes n}\left(\boldsymbol{0}_{2d}, \begin{pmatrix}
I_d & \eta' u' u'^T \\
\eta' u' u'^T & I_d
\end{pmatrix}\right) \right\} \Bigg\}, \]

with $\tilde{\pi}_0, \tilde{\pi}_1$ defined in the statement, and this would conclude the proof. To this aim, observe that if
\[
\begin{pmatrix}
X \\
\end{pmatrix} \sim N\left(\boldsymbol{0}_{2d}, \begin{pmatrix}
I_d & U^T \Lambda U \\
U^T \Lambda U & I_d
\end{pmatrix} \right),
\]

\[
\begin{cases}
X|Y \sim N(U^T \Lambda U Y, I_d - U^T \Lambda^2 U)\\
\\
Y \sim N(\boldsymbol{0}_{d}, I_d).
\end{cases}
\]

This allows us to write

\begin{align*}
TV_0 & := \operatorname{TV} \Bigg\{\mathbb{E}_{\pi_j}\left\{N^{\otimes n}\left(\boldsymbol{0}_{2d}, \begin{pmatrix}
I_d & U^T \Lambda U \\
U^T \Lambda U & I_d
\end{pmatrix}\right) \right\}, \mathbb{E}_{\pi_{j+1}}\left\{N^{\otimes n}\left(\boldsymbol{0}_{2d}, \begin{pmatrix}
I_d & U^T \Lambda U \\
U^T \Lambda U & I_d
\end{pmatrix} \right) \right\} \Bigg\} \\
& = \int  \prod_{i =1}^n \varphi(y_i) \bigg|\mathbb{E}_{\pi_j}\left\{\prod_{i =1}^n |I - U^T \Lambda^2 U|^{-1/2}\varphi((I - U^T \Lambda^2 U)^{-1/2}(x_i - U^T \Lambda U y_i))\right\} \\
& \quad \quad \quad \quad - \mathbb{E}_{\pi_{j+1}}\left\{\prod_{i =1}^n |I - U^T \Lambda^2 U|^{-1/2}\varphi((I - U^T \Lambda^2 U)^{-1/2}(x_i - U^T \Lambda U y_i))\right\} \bigg|  dx dy,
\end{align*}

where $dx = dx_1 \ldots dx_n$, and similarly for $dy$. Now, let $U_S$ be the restriction  of $U$ to its columns in $S$. By definition of $\pi_{j}$ (resp. $ \pi_{j+1}$), we can write $U^T \Lambda U$ as $U^T \Lambda U = \eta u u^T + U_S^T \operatorname{diag}(\sigma_{-j}) U_S$
where $\sigma_{-j} \sim \nu_0^{\otimes (\lceil d/2 \rceil -j-1)} \otimes \delta_0 \otimes \nu_1^{\otimes j} \otimes \delta_0^{\otimes d - \lceil d/2 \rceil}$, where $\delta_0$ is the Dirac measure in $0$. Write $\pi$ for the distribution of $\left(U_S, \operatorname{diag}\left(\sigma_{-j}\right)\right)$ and $f_0$ (resp. $f_1$) for the conditional distribution of $(u, \eta)$ given $\left(U_S, \operatorname{diag}\left(\sigma_{-j}\right)\right)$: this is given by $\eta \sim \nu_0$ (resp. $\nu_1$), while $u|U_S$ is sampled uniformly from $\mathcal{S}^{d-1} \cap U_S^\perp$, i.e. the intersection between the $d$-dimensional unit sphere $\mathcal{S}^{d-1}:= \{x \in \mathbb{R}^d:\|x\|_2 = 1 \}$ and the orthogonal complement of the columns spanned by $U_S$. First, observe that $\operatorname{dim}(\mathcal{S}^{d-1} \cap U_S^\perp) = d+1-\lceil d/2 \rceil$. Secondly, observe that for every measurable function $h$,
\[
\mathbb{E}h(P) = \int h(P) \pi_j(dP) = \int h(P) f_0(du, d\eta)\pi\left(dU_S, d\sigma_{-j}\right),
\]

and similarly for $\pi_{j+1}$. This allows to bound the TV distance above one step further as

\begin{multline*}
TV_0 \leq \int \prod_{i =1}^n \varphi(y_i) \bigg|\int \prod_{i =1}^n |I - U^T \Lambda^2 U|^{-1/2}\varphi((I - U^T \Lambda^2 U)^{-1/2}(x_i - U^T \Lambda U y_i) f_0(du, d\eta) \\
- \int \prod_{i =1}^n |I - U'^T \Lambda'^2 U'|^{-1/2}\varphi((I - U'^T \Lambda'^2 U')^{-1/2}(x_i - U'^T \Lambda' U' y_i) f_1(du', d\eta')\bigg| \pi\left(dU_S, d\sigma_{-j}\right) dx dy \\
= \int \prod_{i =1}^n \varphi(y_i) \bigg(\int \bigg|\int \prod_{i =1}^n |I - U^T \Lambda^2 U|^{-1/2}\varphi((I - U^T \Lambda^2 U)^{-1/2}(x_i - U^T \Lambda U y_i) f_0(du, d\eta) \\
- \int \prod_{i =1}^n |I - U'^T \Lambda'^2 U'|^{-1/2}\varphi((I - U'^T \Lambda'^2 U')^{-1/2}(x_i - U'^T \Lambda' U' y_i) f_1(du', d\eta')\bigg| dx \bigg) \pi\left(dU_S, d\sigma_{-j}\right) dy,
\end{multline*}

where in the first step we used Jensen's inequality, bringing the common $\pi$ outside the absolute value, while in the last step we used Fubini-Tonelli theorem with positive integrand. Consider now the innermost integral
\begin{align*}
\int & \bigg|\int \prod_{i =1}^n |I - U^T \Lambda^2 U|^{-1/2}\varphi((I - U^T \Lambda^2 U)^{-1/2}(x_i - U^T \Lambda U y_i) f_0(du, d\eta) \\
& \quad - \int \prod_{i =1}^n |I - U'^T \Lambda'^2 U'|^{-1/2}\varphi((I - U'^T \Lambda'^2 U')^{-1/2}(x_i - U'^T \Lambda' U' y_i) f_1(du', d\eta')\bigg| dx \\
& = \int \bigg|\int \prod_{i =1}^n |I - U^T \Lambda^2 U|^{-1/2}\varphi((I - U^T \Lambda^2 U)^{-1/2}(x_i - \eta u u^T y_i - \sum_{k \neq j}\sigma_k u_k u_k^T y_i) f_0(du, d\eta) \\
& \quad - \int \prod_{i =1}^n |I - U'^T \Lambda'^2 U'|^{-1/2}\varphi((I - U'^T \Lambda'^2 U')^{-1/2}(x_i - \eta' u' u'^T y_i - \sum_{k \neq j}\sigma_k u_k u_k^T y_i) f_1(du', d\eta')\bigg| dx
\end{align*}

for fixed $U_S, \sigma_{-j}, y$. This can be simplified to
\begin{align*}
\int & \bigg|\int \prod_{i =1}^n |I - U^T \Lambda^2 U|^{-1/2}\varphi((I - U^T \Lambda^2 U)^{-1/2}(x_i - \eta u u^T y_i)) f_0(du, d\eta) \\
& \quad - \int \prod_{i =1}^n |I - U'^T \Lambda'^2 U'|^{-1/2}\varphi((I - U'^T \Lambda'^2 U')^{-1/2}(x_i - \eta' u' u'^T y_i)) f_1(du', d\eta')\bigg| dx
\end{align*}
after the change of variable $x_i' = x_i - \sum_{k \neq j}\sigma_k u_k u_k^T y_i$, for all $i \in [n]$. Now, observe that, under $f_0$, we have
\[
(I - U^T \Lambda^2 U)^{-1/2} = \frac{1}{\sqrt{1-\eta^2}}uu^T + \sum_{i \neq j} \frac{1}{\sqrt{1-\sigma_i^2}} u_i u_i^T,
\]

which yields
\[|I - U^T \Lambda^2 U|^{-1/2} = \frac{1}{{\sqrt{1-\eta^2}} \prod\limits_{i \neq j}\sqrt{1-\sigma_i^2}};\]

similarly under for $(I - U'^T \Lambda'^2 U')^{-1/2}$ under $\pi_1$, with $\eta', u'$ in place of $\eta, u$. Perform the change of variables
\[
x_i = \left(I - \sum_{k \neq j}\sigma_k^2 u_k u_k^T\right)^{1/2}z_i,
\]

for all $i \in [n]$, whose Jacobian is
\[
\prod_{i =1}^n \left|I - \sum_{k \neq j}\sigma_k^2 u_k u_k^T\right|^{1/2} =  \prod_{i =1}^n \prod\limits_{k \neq j}\sqrt{1-\sigma_k^2}.
\]

We get

\begin{align*}
\int & \bigg|\int \prod_{i =1}^n \frac{1}{\sqrt{1-\eta^2}} \varphi\left(\left(\sum_{i \neq j} u_i u_i^T + \frac{1}{\sqrt{1-\eta^2}}uu^T \right) z_i - \frac{\eta}{\sqrt{1-\eta^2}} u u^T y_i\right) f_0(du, d\eta) \\
& \quad - \int \prod_{i =1}^n \frac{1}{\sqrt{1-\eta'^2}} \varphi\left(\left(\sum_{i \neq j} u_i u_i^T + \frac{1}{\sqrt{1-\eta'^2}}u'u'^T \right) z_i - \frac{\eta'}{\sqrt{1-\eta'^2}} u' u'^T y_i\right) f_1(du', d\eta')\bigg| dx \\
& = \int \bigg|\int \prod_{i =1}^n \frac{1}{\sqrt{1-\eta^2}} \varphi\left(\left(\sum_{i \neq j} u_i u_i^T + \frac{1}{\sqrt{1-\eta^2}}uu^T \right)(z_i - \eta u u^T y_i)\right) f_0(du, d\eta) \\
& \quad - \int \prod_{i =1}^n \frac{1}{\sqrt{1-\eta'^2}} \varphi\left(\left(\sum_{i \neq j} u_i u_i^T + \frac{1}{\sqrt{1-\eta'^2}}u'u'^T \right)(z_i - \eta' u' u'^T y_i)\right) f_1(du', d\eta')\bigg| dx \\
& = \int \bigg|\int \prod_{i =1}^n \frac{1}{\sqrt{1-\eta^2}} \varphi\left(\left(I - \eta^2 uu^T \right)^{-1/2}(z_i - \eta u u^T y_i)\right) f_0(du, d\eta) \\
& \quad - \int \prod_{i =1}^n \frac{1}{\sqrt{1-\eta'^2}} \varphi\left(\left(I - \eta'^2 u'u'^T \right)^{-1/2} (z_i - \eta' u' u'^T y_i)\right) f_1(du', d\eta')\bigg| dx \\
& = \int \bigg|\int \prod_{i =1}^n \left|I - \eta^2 uu^T \right|^{-1/2}\varphi\left(\left(I - \eta^2 uu^T \right)^{-1/2}(z_i - \eta u u^T y_i)\right) f_0(du, d\eta) \\
& \quad - \int \prod_{i =1}^n \left|I - \eta'^2 u'u'^T \right|^{-1/2} \varphi\left(\left(I - \eta'^2 u'u'^T \right)^{-1/2} (z_i - \eta' u' u'^T y_i)\right) f_1(du', d\eta')\bigg| dx \\
& = \operatorname{TV}\Bigg\{ \mathbb{E}_{f_0}\{N^{\otimes n}(\eta u u^T y, I - (\eta uu^T)(\eta uu^T)^T)\}, \mathbb{E}_{f_1}\{N^{\otimes n}(\eta' u' u'^T y, I - (\eta' u'u'^T)(\eta' u'u'^T)^T)\}\Bigg\}.
\end{align*}

Coming back to the initial TV distance we wish to bound, we get that

\begin{align*}
& \operatorname{TV} \Bigg\{\mathbb{E}_{\pi_j}\left\{N^{\otimes n}\left(\boldsymbol{0}_{2d}, \begin{pmatrix}
I_d & U^T \Lambda U \\
U^T \Lambda U & I_d
\end{pmatrix}\right) \right\}, \mathbb{E}_{\pi_{j+1}}\left\{N^{\otimes n}\left(\boldsymbol{0}_{2d}, \begin{pmatrix}
I_d & U^T \Lambda U \\
U^T \Lambda U & I_d
\end{pmatrix} \right) \right\} \Bigg\} \\
& \leq \int \operatorname{TV}\Bigg\{ \mathbb{E}_{f_0}\{N^{\otimes n}(\eta u u^T y, I - (\eta uu^T)(\eta uu^T)^T)\}, \mathbb{E}_{f_1}\{N^{\otimes n}(\eta' u' u'^T y, I - (\eta' u'u'^T)(\eta' u'u'^T)^T)\}\Bigg\} \\
& \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \varphi(y) \pi\left(dU_S, d\sigma_{-j}\right) dy \\
& = \int \operatorname{TV}\Bigg\{\mathbb{E}_{f_0}\left\{N^{\otimes n}\left(\boldsymbol{0}_{2d}, \begin{pmatrix}
I_{d} & \eta u u^T \\
\eta u u^T & I_{d}
\end{pmatrix}\right) \right\}, \mathbb{E}_{f_1}\left\{N^{\otimes n}\left(\boldsymbol{0}_{2d}, \begin{pmatrix}
I_{d} & \eta' u' u'^T \\
\eta' u' u'^T & I_{d}
\end{pmatrix}\right) \right\} \Bigg\} \pi\left(dU_S, d\sigma_{-j}\right) \\
& = \operatorname{TV}\Bigg\{\mathbb{E}_{\tilde{\pi}_0}\left\{N^{\otimes n}\left(\boldsymbol{0}_{2d}, \begin{pmatrix}
I_{d} & \eta u u^T \\
\eta u u^T & I_{d}
\end{pmatrix}\right) \right\}, \mathbb{E}_{\tilde{\pi}_1}\left\{N^{\otimes n}\left(\boldsymbol{0}_{2d}, \begin{pmatrix}
I_{d} & \eta' u' u'^T \\
\eta' u' u'^T & I_{d}
\end{pmatrix}\right) \right\} \Bigg\},
\end{align*}

where $\tilde{\pi}_0$ (resp. $\tilde{\pi}_1$) is the distribution of $\eta u u^T$ (resp. $\eta' u' u'^T$), where $\eta \sim \nu_0$ (resp. $\eta' \sim \nu_1$) and $u$ (resp. $u'$) is sampled uniformly from a $d'$-dimensional unit sphere embedded in $\mathbb{R}^d$, with $d' = d + 1 - \lceil d/2 \rceil$. Now, since the Gaussian distribution is invariant under orthogonal transformation, we might assume that $u = (u_{d'}, \boldsymbol{0}^T_{d-d'})$, with $u_{d'}$ uniformly sampled from the $d'$-dimensional sphere $\mathcal{S}^{d'-1}$, and the result follows.

\[
\int \prod_{i =1}^n \varphi(y_i) \bigg|\int \prod_{i =1}^n \frac{1}{\sqrt{1-\eta^2}} \varphi\left(\left(I - \eta^2 uu^T \right)^{-1/2}(z_i - \eta u u^T y_i)\right) [\tilde{\pi}_0(du, d\eta) - \tilde{\pi}_1(du, d\eta)]\bigg| dz dy,
\]

and observe that
\[
\left(I - \eta^2 uu^T \right)^{-1} = I + \frac{\eta^2}{1-\eta^2}uu^T.
\]

\begin{align*}
& \varphi\left(\left(I - \eta^2 uu^T \right)^{-1/2}(z_i - \eta u u^T y_i)\right) = (2\pi)^{-\frac{d}{2}} \exp\left\{-\frac{1}{2}(z_i - \eta u u^T y_i)^T \left(I + \frac{\eta^2}{1-\eta^2}uu^T \right) (z_i - \eta u u^T y_i) \right\} \\
& = (2\pi)^{-\frac{d}{2}} \exp\left\{-\frac{1}{2}z_i^T z_i - \frac{1}{2}\frac{\eta^2}{1-\eta^2} z_i^T uu^T z_i - \frac{1}{2} \eta^2 y_i^T uu^T y_i -\frac{1}{2} \frac{\eta^4}{1-\eta^2} y_i^T uu^T y_i  \right. \\
& \left. \hspace{11.1cm} + \eta z_i^T uu^T y_i + \frac{\eta^3}{1-\eta^2}z_i^T u u^T y_i \right\} \\
& = (2\pi)^{-\frac{d}{2}} \exp\left\{-\frac{1}{2}z_i^T z_i - \frac{1}{2}\frac{\eta^2}{1-\eta^2} z_i^T uu^T z_i - \frac{1}{2} \frac{\eta^2}{1-\eta^2} y_i^T uu^T y_i + \frac{\eta}{1-\eta^2}z_i^T u u^T y_i\right\} \\
& = \varphi(z_i)\exp\left\{ - \frac{1}{2}\frac{\eta^2}{1-\eta^2} z_i^T uu^T z_i - \frac{1}{2} \frac{\eta^2}{1-\eta^2} y_i^T uu^T y_i + \frac{\eta}{1-\eta^2}z_i^T u u^T y_i\right\} \\
& = \varphi(z_i)\exp \left\{ - \frac{1}{2} \langle \begin{pmatrix}
\frac{\eta^2}{1-\eta^2} uu^T & -\frac{\eta}{1-\eta^2} uu^T \\
-\frac{\eta}{1-\eta^2} uu^T & \frac{\eta^2}{1-\eta^2}uu^T
\end{pmatrix}, \begin{pmatrix}
z_i \\ y_i
\end{pmatrix}\begin{pmatrix}
z_i \\ y_i
\end{pmatrix}^T \rangle \right\} =: \varphi(z_i) g(\eta, u, z_i, y_i).
\end{align*}

\begin{align*}
TV_1 &:= \int \prod_{i =1}^n \varphi(y_i) \bigg|\int \prod_{i =1}^n \frac{1}{\sqrt{1-\eta^2}} \varphi\left(\left(I - \eta^2 uu^T \right)^{-1/2}(z_i - \eta u u^T y_i)\right) [\tilde{\pi}_0(du, d\eta) - \tilde{\pi}_1(du, d\eta)]\bigg| dx dy \\
& = \int \prod_{i =1}^n \varphi(z_i) \varphi(y_i) \bigg|\int \prod_{i =1}^n \frac{1}{\sqrt{1-\eta^2}} g(\eta, u, z_i, y_i) [\tilde{\pi}_0(du, d\eta) - \tilde{\pi}_1(du, d\eta)]\bigg| dz dy \\
& \leq \sqrt{\int \prod_{i =1}^n \varphi(z_i) \varphi(y_i) \bigg[\int \prod_{i =1}^n \frac{1}{\sqrt{1-\eta^2}} g(\eta, u, z_i, y_i) [\tilde{\pi}_0(du, d\eta) - \tilde{\pi}_1(du, d\eta)]\bigg]^2 dz dy},
\end{align*}

where we used Cauchy-Schwartz inequality in the last step. Thus, it follows that

\begin{align*}
TV_1^2 & \leq \int \prod_{i =1}^n \varphi(z_i) \varphi(y_i) \sum_{k = 0,1} \sum_{j = 0,1}(-1)^{k+j} \\
& \quad \quad \quad \left(\int \int \prod_{i =1}^n \frac{1}{\sqrt{1-\eta^2}\sqrt{1-\eta'^2}} g(\eta, u, z_i, y_i) g(\eta', u', z_i, y_i)\tilde{\pi}_k(du, d\eta)\tilde{\pi}_j(du', d\eta')\right) dz dy \\
& = \sum_{k = 0,1} \sum_{j = 0,1}(-1)^{k+j}\int \int (1-\eta^2)^{-n/2} (1-\eta'^2)^{-n/2} \\
& \quad \quad \quad \left(\int \prod_{i =1}^n g(\eta, u, z_i, y_i) g(\eta', u', z_i, y_i) \varphi(z_i) \varphi(y_i) dz dy \right)\tilde{\pi}_k(du, d\eta)\tilde{\pi}_j(du', d\eta') \\
& = \sum_{k = 0,1} \sum_{j = 0,1}(-1)^{k+j}\int \int (1-\eta^2)^{-n/2} (1-\eta'^2)^{-n/2} \\
& \quad \quad \quad \left(\prod_{i =1}^n \int  g(\eta, u, z_i, y_i) g(\eta', u', z_i, y_i) \varphi(z_i) \varphi(y_i) dz_i dy_i \right)\tilde{\pi}_k(du, d\eta)\tilde{\pi}_j(du', d\eta'),
\end{align*}

where in the second equality we used Fubini-Tonelli's theorem to change the order of integration, and Fubini's theorem to factorise independent integrands in the last one. Let us consider a generic
\[
\int g(\eta, u, z_i, y_i) g(\eta', u', z_i, y_i) \varphi(z_i) \varphi(y_i)dz_i dy_i,
\]

bearing in mind that $u = (u_{d'}, \boldsymbol{0}^T_{d-d'}), u' = (u'_{d'},\boldsymbol{0}^T_{d-d'})$, with $u_{d'}, u'_{d'}$ being independent and uniform samples from the $d'$-dimensional unit sphere, where $d' = d + 1 - \lceil d/2 \rceil$.  We have
\begin{align*}
\int & g(\eta, u, z_i, y_i) g(\eta', u', z_i, y_i) \varphi(z_i) \varphi(y_i)dz_i dy_i \\
& = \int (2\pi)^{-d} \exp \left\{ - \frac{1}{2} \langle \begin{pmatrix}
\frac{\eta^2}{1-\eta^2} uu^T & -\frac{\eta}{1-\eta^2} uu^T \\
-\frac{\eta}{1-\eta^2} uu^T & \frac{\eta^2}{1-\eta^2}uu^T
\end{pmatrix} + \right. \\
& \left. \hspace{4cm} + \begin{pmatrix}
\frac{\eta'^2}{1-\eta'^2} u'u'^T & -\frac{\eta'}{1-\eta'^2} u'u'^T \\
-\frac{\eta'}{1-\eta'^2} u'u'^T & \frac{\eta'^2}{1-\eta'^2}u'u'^T
\end{pmatrix} + \begin{pmatrix}
I_d & \boldsymbol{O}_d \\
\boldsymbol{O}_d & I_d
\end{pmatrix}, \begin{pmatrix}
z_i \\ y_i
\end{pmatrix}\begin{pmatrix}
z_i \\ y_i
\end{pmatrix}^T \rangle \right\} \\
& = \int (2\pi)^{-d} \exp \left\{ - \frac{1}{2} \langle \begin{pmatrix}
I_d + \frac{\eta^2}{1-\eta^2} uu^T + \frac{\eta'^2}{1-\eta'^2} u'u'^T & -\frac{\eta}{1-\eta^2} uu^T -\frac{\eta'}{1-\eta'^2} u'u'^T \\
-\frac{\eta}{1-\eta^2} uu^T  -\frac{\eta'}{1-\eta'^2} u'u'^T & I_d + \frac{\eta^2}{1-\eta^2}uu^T \frac{\eta'^2}{1-\eta'^2}u'u'^T
\end{pmatrix}, \begin{pmatrix}
z_i \\ y_i
\end{pmatrix}\begin{pmatrix}
z_i \\ y_i
\end{pmatrix}^T \rangle \right\} \\
& =: \int (2\pi)^{-d} \exp \left\{ - \frac{1}{2} \langle K, \begin{pmatrix}
z_i \\ y_i
\end{pmatrix}\begin{pmatrix}
z_i \\ y_i
\end{pmatrix}^T \rangle \right\} = |K|^{-1/2}.
\end{align*}

Now $K$ takes the form
\[
K = \begin{pmatrix}
I_d + \frac{\eta^2}{1-\eta^2} uu^T + \frac{\eta'^2}{1-\eta'^2} u'u'^T & -\frac{\eta}{1-\eta^2} uu^T -\frac{\eta'}{1-\eta'^2} u'u'^T \\
-\frac{\eta}{1-\eta^2} uu^T  -\frac{\eta'}{1-\eta'^2} u'u'^T & I_d + \frac{\eta^2}{1-\eta^2}uu^T \frac{\eta'^2}{1-\eta'^2}u'u'^T
\end{pmatrix}.
\]

It is straightforward to show that
\[
|K| = \frac{(1 - (u^Tu')^2 \eta \eta')^2}{(1-\eta^2)(1-\eta'^2)} \overset{d}{=} \frac{(1 - u_1^2 \eta \eta')^2}{(1-\eta^2)(1-\eta'^2)},
\]

but, since it requires some lengthy algebraic computations, we defer its proof to Lemma <ref> below. Now, it follows that

\begin{align*}
TV_1^2 & \leq \sum_{k = 0,1} \sum_{j = 0,1}(-1)^{k+j}\int \int (1-\eta^2)^{-n/2} (1-\eta'^2)^{-n/2} \\
& \quad \quad \quad \quad \left(\prod_{i =1}^n \int  g(\eta, u, z_i, y_i) g(\eta', u', z_i, y_i) \varphi(z_i) \varphi(y_i) dz_i dy_i \right)\tilde{\pi}_k(du, d\eta)\tilde{\pi}_j(du', d\eta') \\
& = \sum_{k = 0,1} \sum_{j = 0,1}(-1)^{k+j}\int \int (1-\eta^2)^{-n/2} (1-\eta'^2)^{-n/2} |K|^{-n/2}\tilde{\pi}_k(du, d\eta)\tilde{\pi}_j(du', d\eta') \\
& = \sum_{k = 0,1} \sum_{j = 0,1}(-1)^{k+j}\int \int \frac{1}{(1-u_1^2 \eta\eta')^n}\tilde{\pi}_k(du, d\eta)\tilde{\pi}_j(du', d\eta') \\
& = \sum_{h = 0}^\infty \sum_{k = 0,1} \sum_{j = 0,1}(-1)^{k+j}\int \int \binom{h +n-1}{n-1} u_1^{2h}\eta^h\eta'^h\tilde{\pi}_0(du, d\eta)\tilde{\pi}_1(du', d\eta') \\
& = \sum_{k = 0}^\infty \binom{k+n-1}{n-1}
\mathbb{E}[u_1^{2k}] \left(\int \eta^{k} [\nu_0(d\eta)-\nu_1(d\eta)] \right)^2 \\
& = \sum_{k = M+1}^\infty \binom{k+n-1}{n-1} \mathbb{E}[u_1^{2k}] \left(\int \eta^{k} [\nu_0(d\eta)-\nu_1(d\eta)] \right)^2,
\end{align*}

since $\nu_0, \nu_1$ share the first $M$ moments.

\[K = \begin{pmatrix}
I_d + \frac{\eta^2}{1-\eta^2} uu^T + \frac{\eta'^2}{1-\eta'^2} u'u'^T & -\frac{\eta}{1-\eta^2} uu^T -\frac{\eta'}{1-\eta'^2} u'u'^T \\
-\frac{\eta}{1-\eta^2} uu^T  -\frac{\eta'}{1-\eta'^2} u'u'^T & I_d + \frac{\eta^2}{1-\eta^2}uu^T \frac{\eta'^2}{1-\eta'^2}u'u'^T
\end{pmatrix},
\]

where $u,u'$ are $d$-dimensional unit vectors. Then,
\[
|K| = \frac{(1 - (u^Tu')^2 \eta \eta')^2}{(1-\eta^2)(1-\eta'^2)} %\overset{d}{=} \frac{(1 - u_1^2 \eta \eta')^2}{(1-\eta^2)(1-\eta'^2)}.
\]

Let $\alpha = \eta^2/(1-\eta^2), \alpha' = \eta'^2/(1-\eta'^2), \beta = -\eta/(1-\eta^2), \beta' = -\eta'/(1-\eta'^2)$. We aim at finding $|K|$, where
\[
K = \begin{pmatrix}
I_d + \alpha uu^T + \alpha' u'u'^T & \beta uu^T + \beta' u'u'^T \\
\beta uu^T  +\beta' u'u'^T & I_d + \alpha uu^T \alpha u'u'^T
\end{pmatrix}.
\]

First, observe that by Schur's complement

\begin{align*}
|K| &= \bigg| I_d + \alpha uu^T + \alpha' u'u'^T \bigg| \\
& \quad \quad \quad \quad \quad \times \bigg| I_d + \alpha uu^T + \alpha' u'u'^T - \left(\beta uu^T + \beta' u'u'^T\right)\left( I_d + \alpha uu^T + \alpha' u'u'^T \right)^{-1}\left(\beta uu^T + \beta' u'u'^T\right)\bigg|,
\end{align*}

and that we may assume without loss of generality that $u' = \boldsymbol{e}_1$. Indeed, let $R$ be any orthogonal matrix in $\mathbb{R}^{d,d}$, and consider $Ru, Ru'$ in place of $u,u'$ respectively. Then
\begin{align*}
\bigg| I_d + \alpha R uu^T R^T + \alpha' R u'u'^T R^T \bigg| &= \bigg| R(I_d + \alpha uu^T + \alpha' u'u'^T)R^T \bigg| = \bigg|R\bigg| \bigg|I_d + \alpha uu^T + \alpha' u'u'^T\bigg| \bigg|R^T \bigg| \\
& \bigg| I_d + \alpha uu^T + \alpha' u'u'^T \bigg|,
\end{align*}

and it is easy to check that the same happens for

\begin{align*}
\bigg| I_d & + \alpha Ruu^T R^T + \alpha' Ru'u'^TR^T \\
& - \left(\beta Ruu^TR^T + \beta' Ru'u'^TR^T\right)\left( I_d + \alpha Ruu^TR^T + \alpha'Ru'u'^T R^T\right)^{-1}\left(\beta Ruu^TR^T + \beta' Ru'u'^TR^T\right)\bigg|.
\end{align*}

This is not necessary for the proof, but it helps with the notation, and also explains why $u^Tu' \overset{d}{=} u_1$ when $u$ and $u'$ are sampled as described when we apply the result. Now, for all $\alpha, \alpha' \in \mathbb{R}$,
\begin{align*}
\left(I + \alpha u u^T + \alpha' \boldsymbol{e}_1 \boldsymbol{e}_1^T \right)^{-1} &= I - \frac{\alpha}{1+\alpha-\frac{\alpha\alpha'}{1+\alpha'}\gamma^2} uu^T - \frac{\alpha'}{1+\alpha'-\frac{\alpha\alpha'}{1+\alpha'}\gamma^2}\boldsymbol{e}_1 \boldsymbol{e}_1^T + \\
& + \gamma \frac{\alpha'}{1+\alpha'}\frac{\alpha}{1+\alpha-\frac{\alpha\alpha'}{1+\alpha'}\gamma^2}\boldsymbol{e}_1 u^T + \gamma \frac{\alpha}{1+\alpha}\frac{\alpha'}{1+\alpha'-\frac{\alpha\alpha'}{1+\alpha'}\gamma^2} u \boldsymbol{e}_1^T,
\end{align*}

where $\gamma = \boldsymbol{e}_1^T u$, and

\begin{align*}
I + \alpha u u^T + \alpha' \boldsymbol{e}_1 \boldsymbol{e}_1^T & - \left(\beta uu^T + \beta' \boldsymbol{e}_1 \boldsymbol{e}_1^T\right)\left(I + \alpha u u^T + \alpha' \boldsymbol{e}_1 \boldsymbol{e}_1^T \right)^{-1}\left(\beta uu^T + \beta' \boldsymbol{e}_1 \boldsymbol{e}_1^T\right) \\
& = I +\frac{\gamma^2 \eta^2 \eta'^2}{1-\gamma^2 \eta^2 \eta'^2}(uu^T + \boldsymbol{e}_1 \boldsymbol{e}_1^T) -\frac{\gamma \eta \eta}{1-\gamma^2 \eta^2 \eta'^2}(\boldsymbol{e}_1 u^T + u \boldsymbol{e}_1^T).
\end{align*}

Calling $x = (\gamma^2 \eta^2 \eta'^2)/(1-\gamma^2 \eta^2 \eta'^2)$ and $c = \gamma \eta \eta'$, we thus have

\begin{align*}
|K| &= \bigg| I_d + \alpha uu^T + \alpha' \boldsymbol{e}_1 \boldsymbol{e}_1^T \bigg| \bigg| I_d + x uu^T + x \boldsymbol{e}_1 \boldsymbol{e}_1^T - \frac{x}{c} \begin{pmatrix}
\vertbar & \vertbar \\
u & \boldsymbol{e}_1 \\
\vertbar & \vertbar
\end{pmatrix} \begin{pmatrix}
\horzbar & \boldsymbol{e}_1 & \horzbar \\
\horzbar & u & \horzbar
\end{pmatrix}\bigg|.
\end{align*}

In order to compute these determinants, we will repeatedly make use of the fact that, if $A$ is an invertible $n\times n$ matrix, $U,V$ are $n \times m$ matrices, then
\[
|A + uu^T| = |I_m + V^T A^{-1} U| |A|.
\]

If $A = I_n$, this is commonly referred as the Weinstein–Aronszajn identity. Now,

\[
\bigg| I_d + \alpha uu^T + \alpha' \boldsymbol{e}_1 \boldsymbol{e}_1^T \bigg| = \bigg| I_d + \alpha uu^T \bigg| \bigg|1 +  \alpha' \boldsymbol{e}^T_1(I - \alpha uu^T/(1+\alpha))\boldsymbol{e}_1 \bigg| = (1+\alpha)\left(1+\alpha'-\frac{\alpha \alpha'}{1+\alpha}\gamma^2\right),
\]

\begin{align*}
\bigg| & I_d + x uu^T + x \boldsymbol{e}_1 \boldsymbol{e}_1^T - \frac{x}{c} \begin{pmatrix}
\vertbar & \vertbar \\
u & \boldsymbol{e}_1 \\
\vertbar & \vertbar
\end{pmatrix} \begin{pmatrix}
\horzbar & \boldsymbol{e}_1 & \horzbar \\
\horzbar & u & \horzbar
\end{pmatrix}\bigg| \\
& = \bigg| I_d + x uu^T + x \boldsymbol{e}_1 \boldsymbol{e}_1^T \bigg|\bigg| I -\frac{x}{c}\begin{pmatrix}
\horzbar & \boldsymbol{e}_1 & \horzbar \\
\horzbar & u & \horzbar
\end{pmatrix}(I_d + x uu^T + x \boldsymbol{e}_1 \boldsymbol{e}_1^T)^{-1} \begin{pmatrix}
\vertbar & \vertbar \\
u & \boldsymbol{e}_1 \\
\vertbar & \vertbar
\end{pmatrix}\bigg| \\
& = (1+x)(1+x-\frac{x^2}{1+x}\gamma^2)\bigg|I -\frac{x}{c}\begin{pmatrix}
\horzbar & \boldsymbol{e}_1 & \horzbar \\
\horzbar & u & \horzbar
\end{pmatrix} \\
& \quad \times \left(I - \frac{x}{1+x-\frac{x^2}{1+x}\gamma^2} (uu^T + \boldsymbol{e}_1 \boldsymbol{e}_1^T) + \gamma \frac{x}{1+x} \frac{x}{1+x-\frac{x^2}{1+x}\gamma^2}\begin{pmatrix}
\vertbar & \vertbar \\
u & \boldsymbol{e}_1 \\
\vertbar & \vertbar
\end{pmatrix} \begin{pmatrix}
\horzbar & \boldsymbol{e}_1 & \horzbar \\
\horzbar & u & \horzbar
\end{pmatrix}\right)\begin{pmatrix}
\vertbar & \vertbar \\
u & \boldsymbol{e}_1 \\
\vertbar & \vertbar
\end{pmatrix} \bigg| \\
& = (1+x)(1+x-\frac{x^2}{1+x}\gamma^2) \left|\begin{pmatrix}
1 - \frac{x}{c}(\gamma + 2\tau_1 \gamma + \tau_2(1+\gamma^2)) & -\frac{x}{c}(1+\tau_1(1+\gamma^2)+2\tau_2\gamma) \\
-\frac{x}{c}(1+\tau_1(1+\gamma^2)+2\tau_2\gamma) &  1 - \frac{x}{c}(\gamma + 2\tau_1 \gamma + \tau_2(1+\gamma^2))
\end{pmatrix} \right|,
\end{align*}

where $\tau_1 = - x/(1+x-\frac{x^2}{1+x}\gamma^2), \tau_2  = \gamma x \tau_1/(1+x)$. Putting all the pieces together,

\begin{align*}
|K| &= (1+\alpha)\left(1+\alpha'-\frac{\alpha \alpha'}{1+\alpha}\gamma^2\right) (1+x)\left(1+x-\frac{x^2}{1+x}\gamma^2\right) \\
& \quad \quad \times \left((1 - \frac{x}{c}(\gamma + 2\tau_1 \gamma + \tau_2(1+\gamma^2)))^2 -\frac{x^2}{c^2}(1+\tau_1(1+\gamma^2)+2\tau_2\gamma))^2 \right),
\end{align*}

and substituting the expressions of $\alpha, \alpha', x, c, \tau_1, \tau_2$ as functions of $\eta, \eta', \gamma$ gives
\[
|K| = \frac{(1 - (u^Tu')^2 \eta \eta')^2}{(1-\eta^2)(1-\eta'^2)},
\]

as claimed.

We start by proving the first statement. Since $\Sigma_\mathbb{S}$ is consistent, we have that

\begin{align*}
\Sigma_\mathbb{S} \text{ is compatible } \quad  & \text{if and only if } \quad \begin{pmatrix}
I_d & P & -P \\
P^T & I_d & \beta I_d \\
-P^T & \beta I_d & I_d
\end{pmatrix} \succeq 0 \\
&  \text{if and only if } \quad  \begin{pmatrix}
I_d & \beta I_d \\
\beta I_d & I_d
\end{pmatrix} -
\begin{pmatrix}
P^T P & -P^T P \\
-P^T P & P^T P
\end{pmatrix} \succeq 0,
\end{align*}

where the second equivalence follows by standard properties of Schur complements. However, we can see that

\begin{align*}
\inf \biggl\{ \begin{pmatrix} x \\ y \end{pmatrix}^T \biggl\{ \begin{pmatrix}
I_d & \beta I_d \\
\beta I_d & I_d
\end{pmatrix} &-
\begin{pmatrix}
P^T P & -P^T P \\
-P^T P & P^T P
\end{pmatrix} \biggr\} \begin{pmatrix} x \\ y \end{pmatrix} : x, y \in \mathbb{R}^d \biggr\} \\
& = \inf \bigl\{ \|x-y\|_2^2 + 2(1+\beta)x^Ty - \|P(x-y)\|_2^2 : x, y \in \mathbb{R}^d \bigr\} \\
& = \inf \bigl\{ \|v\|_2^2 + 2(1+\beta)(v+y)^Ty - \|Pv\|_2^2 : v, y \in \mathbb{R}^d \bigr\} \\
& = \inf \biggl\{ \frac{1-\beta}{2}\|v\|_2^2 - v^TP^TPv : v  \in \mathbb{R}^d \biggr\} \\
& = \inf \biggl\{ \biggl( \frac{1-\beta}{2} - \|P\|_2^2\biggr)v^2 : v \in [0,\infty) \biggr\},
\end{align*}

where the third equality follows on noting that the minimising choice of $y$ is given by $-v/2$. It is now clear that $\Sigma_\mathbb{S}$ is compatible if and only if $\|P\|_2^2 \leq (1-\beta)/2$, as claimed.

As for the second part of the statement, let $\boldsymbol{v}_1, \ldots, \boldsymbol{v}_d$ the orthonormal eigenvectors or $P^TP$ with eigenvalues $\lambda_1 \geq \ldots \geq \lambda_d$, and let $L$ be the maximal $l$ such that $\lambda_l \geq (1-\beta)/2$. For $l \in [L]$, define

\[
X_{\mathbb{S}}^{(l)} = \frac{c}{4}\Bigg\{\begin{pmatrix}
2P\boldsymbol{v}_l\boldsymbol{v}_l^T P^T & -2P\boldsymbol{v}_l\boldsymbol{v}_l^T \\
-2\boldsymbol{v}_l\boldsymbol{v}_l^T P^T & \boldsymbol{v}_l\boldsymbol{v}_l^T/2
\end{pmatrix},\begin{pmatrix}
2P\boldsymbol{v}_l\boldsymbol{v}_l^T P^T & 2P\boldsymbol{v}_l\boldsymbol{v}_l^T \\
2\boldsymbol{v}_l\boldsymbol{v}_l^T P^T & \boldsymbol{v}_l\boldsymbol{v}_l^T/2
\end{pmatrix}, \begin{pmatrix}
\boldsymbol{v}_l\boldsymbol{v}_l^T/2 & -\boldsymbol{v}_l\boldsymbol{v}_l^T \\
-\boldsymbol{v}_l\boldsymbol{v}_l^T & \boldsymbol{v}_l\boldsymbol{v}_l^T/2
\end{pmatrix}\Bigg\},
\]

with $0< c \leq 5/6 + \sqrt{73}/6$, and define $ X_{\mathbb{S}} = \sum_{l=1}^L X_{\mathbb{S}}^{(l)}$. We first show that $X_\mathbb{S}$ is a feasible solution for our primal optimisation problem. We have

\[A^*X_{\mathbb{S}} = \frac{c}{4} \sum_{l=1}^L
\begin{pmatrix}
4P\boldsymbol{v}_l\boldsymbol{v}_l^T P^T & -2P\boldsymbol{v}_l\boldsymbol{v}_l^T & 2P\boldsymbol{v}_l\boldsymbol{v}_l^T\\
-2\boldsymbol{v}_l\boldsymbol{v}_l^T P^T & \boldsymbol{v}_l\boldsymbol{v}_l^T & - \boldsymbol{v}_l\boldsymbol{v}_l^T \\
2\boldsymbol{v}_l\boldsymbol{v}_l^T P^T & - \boldsymbol{v}_l\boldsymbol{v}_l^T &  \boldsymbol{v}_l\boldsymbol{v}_l^T
\end{pmatrix} = \frac{c}{4} \sum_{l=1}^L \begin{pmatrix}
2P\boldsymbol{v}_l \\
-\boldsymbol{v}_l \\
\boldsymbol{v}_l
\end{pmatrix}
\begin{pmatrix}
2P\boldsymbol{v}_l \\
-\boldsymbol{v}_l \\
\boldsymbol{v}_l
\end{pmatrix}^T \succeq 0,
\]

and since $X_{\mathbb{S}}^{(0)} = \frac{1}{2} (I_{2d}, I_{2d}, I_{2d})$,

\begin{align*}
X_{\mathbb{S}} + X_{\mathbb{S}}^{(0)} & = \frac{1}{2}\left(\begin{pmatrix}
I_d + cP(\sum_{l=1}^L\boldsymbol{v}_l \boldsymbol{v}_l^T) P^T & -cP(\sum_{l=1}^L\boldsymbol{v}_l \boldsymbol{v}_l^T) \\
-c(\sum_{l=1}^L\boldsymbol{v}_l \boldsymbol{v}_l^T) P^T & I_d + \frac{c}{4} \sum_{l=1}^L\boldsymbol{v}_l \boldsymbol{v}_l^T
\end{pmatrix}, \right. \\
& \left. \quad \quad  \begin{pmatrix}
I_d + cP(\sum_{l=1}^L\boldsymbol{v}_l \boldsymbol{v}_l^T) P^T & +cP(\sum_{l=1}^L\boldsymbol{v}_l \boldsymbol{v}_l^T) \\
+c(\sum_{l=1}^L\boldsymbol{v}_l \boldsymbol{v}_l^T) P^T & I_d + \frac{c}{4} \sum_{l=1}^L\boldsymbol{v}_l \boldsymbol{v}_l^T
\end{pmatrix}, \begin{pmatrix}
I_d + \frac{c}{4} \sum_{l=1}^L\boldsymbol{v}_l \boldsymbol{v}_l^T & -\frac{c}{2} \sum_{l=1}^L\boldsymbol{v}_l \boldsymbol{v}_l^T \\
-\frac{c}{2} \sum_{l=1}^L\boldsymbol{v}_l \boldsymbol{v}_l^T & I_d + \frac{c}{4} \sum_{l=1}^L\boldsymbol{v}_l \boldsymbol{v}_l^T
\end{pmatrix} \right).
\end{align*}

It remains to show that $X_{\mathbb{S}} + X_{\mathbb{S}}^{(0)} \succeq_\mathbb{S} 0$. Now, as for the first component of $X_{\mathbb{S}} + X_{\mathbb{S}}^{(0)}$, observe that the bottom-right block
\[
I_d + \frac{c}{4} \sum_{l=1}^L\boldsymbol{v}_l \boldsymbol{v}_l^T \succeq 0,
\]

and it is invertible due to the fact that $\|c \sum_{l=1}^L\boldsymbol{v}_l \boldsymbol{v}_l^T/4\|_2 \leq c/4 < 1$, since the $\boldsymbol{v}_l$'s are orthonormal. The inverse is

\begin{align*}
\left(I_d + \frac{c}{4} \sum_{l=1}^L\boldsymbol{v}_l \boldsymbol{v}_l^T \right)^{-1}  &= \left(I_d -  \left(-\frac{c}{4} \sum_{l=1}^L\boldsymbol{v}_l \boldsymbol{v}_l^T\right)\right)^{-1} = \sum_{k=0}^\infty (-1)^k \left(\frac{c}{4}\right)^k \left(\sum_{l=1}^L\boldsymbol{v}_l \boldsymbol{v}_l^T \right)^k \\
&= I_d + \sum_{k=1}^\infty (-1)^k \left(\frac{c}{4}\right)^k \left(\sum_{l=1}^L\boldsymbol{v}_l \boldsymbol{v}_l^T \right)^k = I_d + \left(\sum_{l=1}^L\boldsymbol{v}_l \boldsymbol{v}_l^T \right)\sum_{k=1}^\infty (-1)^k \left(\frac{c}{4}\right)^k \\
& = I_d + \left(\sum_{l=1}^L\boldsymbol{v}_l \boldsymbol{v}_l^T \right)\left( \frac{1}{1+c/4} - 1\right) = I_d - \frac{c}{c+4}\sum_{l=1}^L\boldsymbol{v}_l \boldsymbol{v}_l^T,
\end{align*}

where the fourth equality comes from the fact that $\sum_{l=1}^L\boldsymbol{v}_l \boldsymbol{v}_l^T$ is idempotent again by the orthonormality of the $\boldsymbol{v}_l$'s. Hence, the first component of $X_{\mathbb{S}} + X_{\mathbb{S}}^{(0)}$ is positive semidefinite if and only if
\[
I_d + cP\left(\sum_{l=1}^L\boldsymbol{v}_l \boldsymbol{v}_l^T\right) P^T \succeq c^2 P \left(\sum_{l=1}^L\boldsymbol{v}_l \boldsymbol{v}_l^T\right) \left(I_d -\frac{c}{4+c}\sum_{l=1}^L\boldsymbol{v}_l \boldsymbol{v}_l^T\right) \left(\sum_{l=1}^L\boldsymbol{v}_l \boldsymbol{v}_l^T\right) P^T,
\]

which is equivalent to
\[
I_d \succeq \left(\frac{4c^2}{4+c} - c \right)P\left(\sum_{l=1}^L\boldsymbol{v}_l \boldsymbol{v}_l^T\right)P^T = \left(\frac{4c^2}{4+c} - c \right)P\left(\sum_{l=1}^L\boldsymbol{v}_l \boldsymbol{v}_l^T\right)^2P^T,
\]

which is satisfied if and only if $4c^2/(4+c) - c \leq 1$, due to the fact that $\|P\left(\sum_{l=1}^L\boldsymbol{v}_l \boldsymbol{v}_l^T\right)^2P^T\|_2 = \|P\left(\sum_{l=1}^L\boldsymbol{v}_l \boldsymbol{v}_l^T\right)\|_2^2 \leq 1$ again by orthonormality. This implies that the first component of $X_{\mathbb{S}} + X_{\mathbb{S}}^{(0)} \succeq_\mathbb{S}$ is PSD if and only if $0< c \leq 5/6 + \sqrt{73}/6$, and of course the same is true for the second component of $X_{\mathbb{S}} + X_{\mathbb{S}}^{(0)}$. As for the third component,  using an analogous idea, it is easy to show that it is positive semidefinite if and only if
\[
I_d \succeq \left(\frac{c^2}{4+c} - \frac{c}{4} \right)  \sum_{l=1}^L\boldsymbol{v}_l \boldsymbol{v}_l^T,
\]

which is satisfied if and only if $0 < c \leq 4$. Summing up, this shows that $X_{\mathbb{S}}$ is feasible for $0< c \leq 5/6 + \sqrt{73}/6$, and leads to

\begin{align*}
R(\Sigma_\mathbb{S}) & \geq -\frac{c}{3d} \sum_{l=1}^L \begin{pmatrix}
2P\boldsymbol{v}_l \\
-\boldsymbol{v}_l \\
\boldsymbol{v}_l
\end{pmatrix}
\begin{pmatrix}
I_d & P & -P \\
P & I_d & \beta I_d \\
-P^T \beta I_d & I_d
\end{pmatrix}
\begin{pmatrix}
2P\boldsymbol{v}_l \\
-\boldsymbol{v}_l \\
\boldsymbol{v}_l
\end{pmatrix}^T \\
& = \frac{c}{3d} \sum_{l=1}^L \left(\lambda_l - \frac{1-\beta}{2}\right) = \frac{c}{3d} \sum_{l=1}^d \left(\lambda_l - \frac{1-\beta}{2}\right)_+ \\
& = \frac{c}{3d} \sum_{l=1}^d \left(\sigma^2_l(P)^2 - \frac{1-\beta}{2}\right)_+ > \frac{3}{4d} \sum_{l=1}^d \left(\sigma^2_l(P)^2 - \frac{1-\beta}{2}\right)_+,
\end{align*}

since $ 5/6 + \sqrt{73}/6 > 9/4$.

[Albert, 1972]
Arthur Albert.
Regression and the Moore-Penrose pseudoinverse.
Mathematics in science and engineering, 94, 1972.

[Aleksić, 2023]
Danijel Aleksić.
A novel test of Missing Completely at Random:
U-statistics-based approach.
arXiv preprint arXiv:2310.19189, 2023.

[Barrett et al., 1993]
Wayne Barrett, Charles R Johnson, and Pablo Tarazaga.
The real positive definite completion problem for a simple cycle.
Linear Algebra Appl., 192:0 3–31, 1993.

[Berrett and Samworth, 2023]
Thomas B Berrett and Richard J Samworth.
Optimal nonparametric testing of Missing Completely At
Random, and its connections to compatibility.
Ann. Statist., 510 (5):0 2170–2193, 2023.

[Berrett et al., 2022]
Thomas B. Berrett, Alberto Bordino, Danat Duisenbekov, Sean Jaffe, and
Richard J. Samworth.
MCARtest: Optimal nonparametric testing of Missing
Completely At Random, 2022.
R package version 1.2.

[Blanchard et al., 2018]
Gilles Blanchard, Alexandra Carpentier, and Maurilio Gutzeit.
Minimax Euclidean separation rates for testing convex hypotheses in
Electronic Journal of Statistics, 120 (2):0
3713 – 3735, 2018.
URL <https://doi.org/10.1214/18-EJS1472>.

[Blekherman et al., 2012]
Grigoriy Blekherman, Pablo A. Parrilo, and Rekha R. Thomas.
Semidefinite Optimization and Convex Algebraic Geometry.
Society for Industrial and Applied Mathematics, Philadelphia, PA,
URL <https://epubs.siam.org/doi/abs/10.1137/1.978161197229>.

[Boyd and Vandenberghe, 2004]
Stephen Boyd and Lieven Vandenberghe.
Convex Optimization.
Cambridge University Press, March 2004.
ISBN 0521833787.

[Bunea and Xiao, 2015]
Florentina Bunea and Luo Xiao.
On the sample covariance matrix estimator of reduced effective rank
population matrices, with applications to fPCA.
Bernoulli, 210 (2), may 2015.
URL <https://doi.org/10.3150

[Cai and Low, 2011]
T Tony Cai and Mark G Low.
Testing composite hypotheses, Hermite polynomials and optimal
estimation of a nonsmooth functional.
Ann. Statist., 39:0 1012–1041, 2011.

[Cai and Zhang, 2019]
T Tony Cai and Linjun Zhang.
High-dimensional linear discriminant analysis: Optimality, adaptive
algorithm, and missing data.
J. Roy. Statist. Soc. Ser. B, 810 (4):0
675–705, 2019.

[Cai et al., 2011]
Tony Cai, Weidong Liu, and Xi Luo.
A Constrained $l_1$ Minimization Approach to Sparse
Precision Matrix Estimation.
Journal of the American Statistical Association, 1060
(494):0 594–607, 2011.
ISSN 01621459.
URL <http://www.jstor.org/stable/41416395>.

[Candès and Tao, 2010]
Emmanuel J. Candès and Terence Tao.
The Power of Convex Relaxation: Near-Optimal Matrix
IEEE Transactions on Information Theory, 560
(5):0 2053–2080, 2010.

[Candès and Recht, 2009]
Emmanuel J. Candès and Benjamin Recht.
Exact Matrix Completion via Convex Optimization.
Foundations of Computational Mathematics, 90
(6):0 717–772, Dec 2009.
ISSN 1615-3375.
Funding by NSF.

[Cox, 1975]
D. R. Cox.
A note on data-splitting for the evaluation of significance levels.
Biometrika, 62:0 441–444, 1975.

[Dempster et al., 1977]
A. P. Dempster, N. M. Laird, and D. B. Rubin.
Maximum Likelihood from Incomplete Data Via the EM
Journal of the Royal Statistical Society: Series B
(Methodological), 390 (1):0 1–22, 1977.

[Elsener and van de Geer, 2018]
Andreas Elsener and Sara van de Geer.
Sparse spectral estimation with missing and corrupted measurements,
URL <https://arxiv.org/abs/1811.10443>.

[Follain et al., 2022]
Bertille Follain, Tengyao Wang, and Richard J. Samworth.
High-dimensional Changepoint Estimation with Heterogeneous
Journal of the Royal Statistical Society Series B: Statistical
Methodology, 840 (3):0 1023–1055, 07 2022.
ISSN 1369-7412.
URL <https://doi.org/10.1111/rssb.12540>.

[Fuchs, 1982]
Camil Fuchs.
Maximum likelihood estimation and model selection in contingency
tables with missing data.
J. Amer. Statist. Assoc., 77:0 270–278, 1982.

[Grone et al., 1984]
Robert Grone, Charles R. Johnson, Eduardo M. Sá, and Henry Wolkowicz.
Positive definite completions of partial Hermitian matrices.
Linear Algebra and its Applications, 58:0 109–124,
ISSN 0024-3795.

[Guo and Shah, 2023]
F Richard Guo and Rajen D Shah.
Rank-transformed subsampling: inference for multiple data splitting
and exchangeable p-values.
arXiv preprint arXiv:2301.02739, 2023.

[Han and Liu, 2017]
Fang Han and Han Liu.
Statistical analysis of latent generalized correlation matrix
estimation in transelliptical distribution.
Bernoulli, 230 (1), feb 2017.
URL <https://doi.org/10.3150

[Hawkins, 1981]
Douglas M. Hawkins.
A new test for multivariate normality and homoscedasticity.
Technometrics, 230 (1):0 105–110, 1981.
ISSN 0040-1706.

[Hofert et al., 2020]
Marius Hofert, Ivan Kojadinovic, Martin Maechler, and Jun Yan.
copula: Multivariate Dependence with Copulas, 2020.
URL <https://CRAN.R-project.org/package=copula>.
R package version 1.0-0.

[Jamshidian and Jalal, 2010]
Mortaza Jamshidian and Siavash Jalal.
Tests of homoscedasticity, normality, and missing completely at
random for incomplete multivariate data.
Psychometrika, 75:0 649–674, 2010.

[Janková et al., 2020]
Jana Janková, Rajen D. Shah, Peter Bühlmann, and Richard J. Samworth.
Goodness-of-fit Testing in High Dimensional Generalized Linear
Journal of the Royal Statistical Society Series B: Statistical
Methodology, 820 (3):0 773–795, 05 2020.
ISSN 1369-7412.
URL <https://doi.org/10.1111/rssb.12371>.

[Jiao et al., 2016]
Jiantao Jiao, Yanjun Han, and Tsachy Weissman.
Minimax Estimation of the $L_1$ Distance.
In 2016 IEEE International Symposium on Information Theory
(ISIT), pages 750–754, 2016.

[Johnson, 1989]
C.R. Johnson.
Matrix Theory and Applications.
American Mathematical Soc., 1989.
ISBN 9780821867464.
URL <https://books.google.co.uk/books?id=EOflkS9ruxcC>.

[Juditsky and Nemirovski, 2002]
Anatoli Juditsky and Arkadi Nemirovski.
On nonparametric tests of positivity/monotonicity/convexity.
The Annals of Statistics, 300 (2):0 498 –
527, 2002.
URL <https://doi.org/10.1214/aos/1021379863>.

[Kellerer, 1984]
Hans G Kellerer.
Duality theorems for marginal problems.
Z. Wahrscheinlichkeit., 67:0 399–432, 1984.

[Khachiyan and Porkolab, 1997]
L. Khachiyan and L. Porkolab.
Computing integral points in convex semi-algebraic sets.
In Proceedings 38th Annual Symposium on Foundations of Computer
Science, pages 162–171, 1997.

[Kim and Ramdas, 2024]
Ilmun Kim and Aaditya Ramdas.
Dimension-agnostic inference using cross U-statistics.
Bernoulli, 300 (1):0 683–711, 2024.
URL <https://doi.org/10.3150/23-BEJ1613>.

[Kim and Bentler, 2002]
Kevin H Kim and Peter M Bentler.
Tests of homogeneity of means and covariance matrices for
multivariate incomplete data.
Psychometrika, 67:0 609–623, 2002.

[Laurent, 2009]
Monique Laurent.
Matrix Completion Problems.
Encyclopedia of Optimization, 3:0 221–229, 2009.

[Laurent and Poljak, 1996]
Monique Laurent and Svatopluk Poljak.
On the Facial Structure of the Set of Correlation Matrices.
SIAM Journal on Matrix Analysis and Applications, 170
(3):0 530–547, 1996.
URL <https://doi.org/10.1137/0617031>.

[Lei et al., 2018]
Jing Lei, Max G’Sell, Alessandro Rinaldo, Ryan J. Tibshirani, and Larry
Distribution-Free Predictive Inference for Regression.
Journal of the American Statistical Association, 1130
(523):0 1094–1111, 2018.
URL <https://doi.org/10.1080/01621459.2017.1307116>.

[Li and Yu, 2015]
Jun Li and Yao Yu.
A nonparametric test of missing completely at random for incomplete
multivariate data.
Psychometrika, 80:0 707–726, 2015.

[Little and Rubin, 2002]
R.J.A. Little and D.B. Rubin.
Statistical analysis with missing data.
Wiley series in probability and mathematical statistics. Probability
and mathematical statistics. Wiley, 2002.
ISBN 9780471183860.
URL <http://books.google.com/books?id=aYPwAAAAMAAJ>.

[Little, 1988]
Roderick JA Little.
A test of Missing Completely at Random for multivariate data
with missing values.
J. Amer. Statist. Assoc., 83:0 1198–1202, 1988.

[Loh and Wainwright, 2012]
Po-Ling Loh and Martin J Wainwright.
High-dimensional regression with noisy and missing data: Provable
guarantees with nonconvexity.
Ann. Statist., 400 (3):0 1637–1664, 2012.

[Lounici, 2014]
Karim Lounici.
High-dimensional covariance matrix estimation with missing
Bernoulli, 200 (3):0 1029 – 1058, 2014.
URL <https://doi.org/10.3150/12-BEJ487>.

[Lovász, 2003]
L. Lovász.
Semidefinite Programs and Combinatorial Optimization, pages
Springer New York, New York, NY, 2003.
ISBN 978-0-387-22444-2.
URL <https://doi.org/10.1007/0-387-22444-0_6>.

[Lundborg et al., 2022]
Anton Rask Lundborg, Ilmun Kim, Rajen D. Shah, and Richard J. Samworth.
The Projected Covariance Measure for assumption-lean variable
significance testing, 2022.

[Meinshausen and Bühlmann, 2006]
Nicolai Meinshausen and Peter Bühlmann.
High-Dimensional Graphs and Variable Selection with the
The Annals of Statistics, 340 (3):0
1436–1462, 2006.
ISSN 00905364.
URL <http://www.jstor.org/stable/25463463>.

[Moran, 1973]
P. A. P. Moran.
Dividing a Sample into Two Parts. A Statistical Dilemma.
Sankhyā: The Indian Journal of Statistics, Series A
(1961-2002), 350 (3):0 329–333, 1973.
ISSN 0581572X.
URL <http://www.jstor.org/stable/25049883>.

[Nesterov and Nemirovskii, 1994]
Yurii Nesterov and Arkadii Nemirovskii.
Interior-Point Polynomial Algorithms in Convex Programming.
Society for Industrial and Applied Mathematics, 1994.
URL <https://epubs.siam.org/doi/abs/10.1137/1.9781611970791>.

[Oliveira, 2010]
Roberto Imbuzeiro Oliveira.
Concentration of the adjacency matrix and of the Laplacian in
random graphs with independent edges.
arXiv preprint arXiv:0911.0600, 2010.

[Polak, 2012]
Elijah Polak.
Springer Science and Business Media, 12 2012.

[Ramana, 1997]
Motakuri V. Ramana.
An exact duality theory for semidefinite programming and its
complexity implications.
Mathematical Programming, 77:0 129–162, 1997.

[Recht, 2011]
Benjamin Recht.
A Simpler Approach to Matrix Completion.
J. Mach. Learn. Res., 12:0 3413–3430, dec 2011.
ISSN 1532-4435.

[Rockafellar, 1970]
R. Tyrrell Rockafellar.
Convex analysis.
Princeton Mathematical Series. Princeton University Press, Princeton,
N. J., 1970.

[Rockel, 2020]
Tobias Rockel.
missMethods: Methods for Missing Data, 2020.
URL <https://CRAN.R-project.org/package=missMethods>.
R package version 0.2.0.

[Santos et al., 2019]
Miriam Seoane Santos, Ricardo Cardoso Pereira, Adriana Fonseca Costa,
Jastin Pompeu Soares, João Santos, and Pedro Henriques Abreu.
Generating Synthetic Missing Data: A Review by Missing
IEEE Access, 7:0 11651–11667, 2019.

[Scheidegger et al., 2022]
Cyrill Scheidegger, Julia Hörrmann, and Peter Bühlmann.
The Weighted Generalised Covariance Measure.
J. Mach. Learn. Res., 23:0 273:1–273:68, 2022.
URL <http://jmlr.org/papers/v23/21-1328.html>.

[Sell et al., 2023]
Torben Sell, Thomas B Berrett, and Timothy I Cannings.
Nonparametric classification with missing data.
arXiv preprint arXiv:2305.11672, 2023.

[Solari and Djordjilović, 2022]
Aldo Solari and Vera Djordjilović.
Multi split conformal prediction.
Statistics & Probability Letters, 1840 (C), 2022.

[Spohn et al., 2021]
Meta-Lina Spohn, Jeffrey Näf, Loris Michel, and Nicolai Meinshausen.
PKLM: A flexible MCAR test using Classification.
arXiv preprint arXiv:2109.10150, 2021.

[Stekhoven and Bühlmann, 2011]
Daniel J. Stekhoven and Peter Bühlmann.
MissForest—non-parametric missing value imputation for mixed-type
Bioinformatics, 280 (1):0 112–118, 10 2011.
ISSN 1367-4803.
URL <https://doi.org/10.1093/bioinformatics/btr597>.

[Thépaut and Verzelen, 2021]
Solène Thépaut and Nicolas Verzelen.
Optimal estimation of Schatten norms of a rectangular matrix.
arXiv preprint arXiv:2111.13551, 2021.

[van Buuren and Groothuis-Oudshoorn, 2011]
Stef van Buuren and Karin Groothuis-Oudshoorn.
mice: Multivariate imputation by chained equations in R.
Journal of Statistical Software, 45:0 1–67, 2011.

[Vandenberghe and Boyd, 1996]
Lieven Vandenberghe and Stephen Boyd.
Semidefinite programming.
SIAM Review, 380 (1):0 49–95, 1996.
URL <https://doi.org/10.1137/1038003>.

[Vershynin, 2019]
Roman Vershynin.
High-Dimensional Probability.
Cambridge University Press, 2019.
<https://www.math.uci.edu/ rvershyn/papers/HDP-book/HDP-book.pdf>.

[Waghmare and Panaretos, 2022]
Kartik G Waghmare and Victor M Panaretos.
The completion of covariance kernels.
The Annals of Statistics, 500 (6):0
3281–3306, 2022.

[Wainwright, 2019]
Martin J Wainwright.
High-dimensional Statistics: A Non-asymptotic Viewpoint.
Cambridge University Press, 2019.

[Wilks, 1946]
S. S. Wilks.
Sample Criteria for Testing Equality of Means, Equality of
Variances, and Equality of Covariances in a Normal Multivariate
The Annals of Mathematical Statistics, 170
(3):0 257 – 281, 1946.
URL <https://doi.org/10.1214/aoms/1177730940>.

[Yates, 1933]
F. Yates.
The Analysis of Replicated Experiments When the Field
Results Are Incomplete.
Empirical Journal of Experimental Agriculture 1 (2): 129–42,

[Zhu et al., 2022]
Ziwei Zhu, Tengyao Wang, and Richard J. Samworth.
High‐dimensional principal component analysis with heterogeneous
Journal of the Royal Statistical Society Series B, 840
(5):0 2000–2031, November 2022.

Appendix <ref> contains further properties of our measure of incompatibility $R$ that were not investigated in the main body of the text. Appendix <ref> contains another oracle test based on a different measure of incompatibility, which acts on covariance matrices normalised in such a way to have fixed scale. Appendix <ref> contains auxiliary results in Semi-definite Programming, while classical tail bounds are contained in Appendix <ref>.

§ FURTHER PROPERTIES OF $R(\CDOT)$

We analyse two further examples, where the missingness patterns $\mathbb{S}$ is more complex. These examples are interesting per se, but we have decided not to include them in the main body because they would have disrupted the flow of the presentation. We start from the case where we observe all possible patterns of cardinality $d-1$, and nothing else.

Consider the set of patterns $\mathbb{S} = \{S_{(-1)}, \cdots, S_{(-d)}\}$, with $d \geq 2$, where $S_{(-i)} = \{1, \ldots, i-1, i+1, \ldots, d\}$. We show how $R(\Sigma_{\mathbb{S}})$ can be lower-bounded by the maximal inconsistency, or, more precisely,
\[
R(\Sigma_{\mathbb{S}}) \geq \frac{1}{2} \max_{i > j} \mathop{\max_{k > h}}_{k,h \neq i,j} |\rho_{ij}^{(k)} - \rho_{ij}^{(h)}| =: \Theta,
\]

where $\rho_{ij}^{(k)}$ is the correlation between $X_i$ and $X_j$ for the pattern $S_{(-k)}$, for $k \in [d] \setminus \{i,j\}$.

In order to prove the statement, suppose the maximum is $|\rho_{ij}^{(k)} - \rho_{ij}^{(h)}|$, and consider $X_{\mathbb{S}} = dY_{\mathbb{S}} - X_{\mathbb{S}}^{(0)}$, where $X_{\mathbb{S}}^{(0)} = \frac{1}{d-1}(I_{d-1}, \ldots, I_{d-1})$ and
\[
Y_{\mathbb{S}} = (0, \ldots, \underbrace{A_1}_{h}, 0, \ldots, 0, \underbrace{A_2}_{k}, 0, \ldots, 0),
\]

\[
(A_1)_{\tilde{i}, \tilde{j}} = \begin{cases}
1/4 \quad \text{ if } (\tilde{i}, \tilde{j}) \in \{(i,i), (j,j), (i,j), (j,i)\} \\
0 \quad \text{ otherwise},
\end{cases}
\]

\[
(A_2)_{\tilde{i}, \tilde{j}} = \begin{cases}
1/4 \quad \text{ if } (\tilde{i}, \tilde{j}) \in \{(i,i), (j,j) \} \\
-1/4 \quad \text{ if } (\tilde{i}, \tilde{j}) \in \{(i,j), (j,i) \} \\
0 \quad \text{ otherwise}.
\end{cases}
\]

Then, provided $X_{\mathbb{S}}$ is feasible, we get precisely that

\[
R(\Sigma_{\mathbb{S}}) \geq -\frac{1}{d}\langle X_{\mathbb{S}}, \Sigma_{\mathbb{S}}\rangle_{\mathbb{S}} = \frac{1}{2} \max_{i > j} \mathop{\max_{k > h}}_{k,h \neq i,j} |\rho_{ij}^{(k)} - \rho_{ij}^{(h)}|.
\]

All is left to prove is that $X_{\mathbb{S}}$ is indeed feasible: $X_{\mathbb{S}} + X_{\mathbb{S}}^{(0)} = dY_{\mathbb{S}} \succeq_{\mathbb{S}} 0$, and $A^*X_{\mathbb{S}}$ is diagonal with trace zero, hence we can choose $Y = -A^*X_{\mathbb{S}}  \in \mathcal{Y}$ in the primal characterisation so that $A^*X_{\mathbb{S}} + Y = \boldsymbol{O} \succeq 0$.

Observe that the same is true in the case where we also have a complete case pattern, i.e. $\mathbb{S} = \{[d], S_{(-1)}, \cdots, S_{(-d)}\}$, with $d \geq 2$, meaning that using the same strategy we can control $R$ with the maximal inconsistency. Related to this, it would be interesting to know if there is a case in which the incompatibility value $\Theta$ controls $R(\Sigma_{\mathbb{S}})$ both from above and below, meaning that $\Theta$ fully characterises $R(\Sigma_{\mathbb{S}})$.  In this regard, we have the following: