Upper-bound for spectral norm of the covariance matrix of a certain Gaussian vector with correlated entries Let $n$ and $m$ be large positive integers. Let $x=(x_1,\ldots,x_n)$ be a vector of independent random variables from $N(0,1)$. It is clear that the covariance matrix of $x$ is $I_n$, the identity matrix. Form a random vector $x'$ in $\mathbb R^m$ as follows.
For $k$ from $1$ through $m$, do the following

*

*Sample a subset of indices $\{i,j\}$ from $\{1,2,\ldots,n\}$ uniformly without replacement.

*Independently of anything else, sample $t$ from $U([0, 1])$.

*Set the $k$th component of $x'$ to $tx_i + (1-t)x_j$.

Let $\Sigma'$ be the covariance matrix of $x'$.
Question. What is a good upper-bound for $\lambda_{\max}(\Sigma')$ ?
My wild guess would be something like $c$ (upto absolute constants).
 A: Here we bound the entire spectrum of $\Sigma'$, from below and above. This post is inspired by a comment of user @BrendanMcKay.

Claim. $\lambda_\max(\Sigma') = O(m/n)$ and $\lambda_\min(\Sigma') = \Omega(n/m)$.

Proof. As remarked by user @BrendanMcKay, $\Sigma' = D + E$, where $D$ is an $m \times m$ diagonal matrix with $D_k = 1/4$ for all $k \in [m]$ and $E$ is an $m \times m$ psd matrix with entries of order $O(1/n)$.
Upper-bound. Since $\Sigma'$ is symmetric, one has
\begin{eqnarray}
\begin{split}
\lambda_\max(\Sigma') = \|\Sigma'\|_{op} &\le \sqrt{\|\Sigma'\|_1\|\Sigma'\|_\infty} =  \|\Sigma'\|_\infty\\
& = \max_{1 \le k \le m}\sum_{1 \le \ell \le m}|\mathbb E\,x'_k x'_\ell|\\
& = \max_{1 \le k \le m}\sum_{1 \le \ell \le m}\begin{cases}1/4,&\mbox{ if }k = \ell,\\ O(1/n),&\mbox{ else}
\end{cases}\\
&= O(m/n).
\end{split}
\end{eqnarray}
Lower-bound. By woodbury identity, $(\Sigma')^{-1} = (D+E)^{-1} = D^{-1}-D^{-1}(I+ED^{-1})^{-1} E D^{-1}$, and so
\begin{eqnarray}
\begin{split}
\|(\Sigma')^{-1}\|_{op} &= \|(D+E)^{-1}\|_{op} = \|D^{-1}\|_{op}+\|D^{-1}\|_{op}\|(I+ED^{-1})^{-1}\|_{op}\|E\|_{op}\|D^{-1}\|_{op}\\
&= \frac{1}{4}+\frac{\|E\|_{op}}{16}\|(I+ED^{-1})^{-1}\|_{op} \le \frac{1}{4} + \frac{\|E\|_{op}}{16} = O(\|E\|_{op}).
\end{split}
\end{eqnarray}
Now, using the same argument as for the first part of the proof, it is easy to obtain $\|E\|_{op} = O(m/n)$. We deduce from the above computations that $\|(\Sigma')^{-1}\|_{op} = O(m/n)$, and so
\begin{eqnarray}
\lambda_\min(\Sigma') = \frac{1}{\|(\Sigma')^{-1}\|_{op}} = \frac{1}{O(m/n)} = \Omega(n/m).
\end{eqnarray}
