Let $\Sigma$ be a $d\times d$ semidefinite positive matrix (SDP). Let $I\subset\{1,\ldots, d\}\times \{1, \ldots, d\}$ be a symmetric subset of indices (i.e. if $(p,q)\in I$ then $(q,p)\in I$). We denote by $._{op}$ the operator norm over $\mathbb{R}^{d\times d}$. Is it possible to find an absolute constant $c$ (independent of $d$ and $\Sigma$) such that $$\Sigma_I_{op}\leq c \Sigma_{op}$$ where $\Sigma_I$ is the symmetric matrices with entries equal to $\Sigma_{pq}$ when $(p,q)\in I$ and $0$ everywhere else.
1 Answer
No, no such constant exists. For example, if $I = \{(i,j) \mid i<j\}$, then $\Sigma\mapsto \Sigma_I$ is the usual triangular projection, and the norm is of order $\log n$, see for example Norm of the upper triangular part of symmetric matrix (the fact that you restrict to positive definite matrices does not change much, see below).
Of course, this $I$ is not symmetric, but it can be made symmetric by a standard $2$by$2$ matrix trick. Namely, if $I \subset \{1,\dots,2d\}\times \{1,\dots,2d\}$ is defined by $\{(i,d+j) \mid i<j\leq d\}\cup \{(j+d,i)\mid i<j\leq d\}$ then the norm of $\Sigma \mapsto \Sigma_I$ is of order $\log n$.
Actually, an old theorem by Grothendieck allows to compute almost exactly the best constant $c$. Almost, because Grothendieck's theorem allows to compute exactly the norm of $\Sigma\mapsto \Sigma_I$ on the space of all matrices (real or complex). But, writing any matrix as a sum $\Sigma=\Sigma_1\Sigma_2+i\Sigma_3i\Sigma_4$ with $\\Sigma_k\_{op} \leq \\Sigma\_{op}$, one sees that the norm of the restriction to positive definite matrices is, up to a factor $4$, equivalent to the norm.
Grothendieck's theorem says that the norm of $\Sigma\mapsto \Sigma_I$ is equal to the infimum of $\max_{i,j} \v_i\ \w_j\$ over all euclidean spaces $H$ and vectors $v_1,\dots,v_d,w_1,\dots,w_d \in H$ such that $$\langle v_i,w_j\rangle = \begin{cases} 1 & if\ (i,j)\in I\\ 0 & \textrm{otherwise}\end{cases}$$
The same formula holds similarly if you replace the indicator function of $I$ by an arbitrary function $\varphi:\{1,\dots,d\}\times \{1,\dots,d\}\to \mathbf{C}$, and the map $\Sigma\mapsto \Sigma_I$ by $\Sigma\mapsto (\varphi(i,j)\Sigma_{i,j})$ (a Schur multiplier).
See for example Chapter 5 in Pisier's book Similarity problems and completely bounded maps.
Added on June 9 The best constant $c=c(d)$ such that $\\Sigma_I\_{op} \leq c(d) \\Sigma\_{op}$ for every positive definite $d \times d$ matrix $\Sigma$ and every symmetric $I \subset \{1,\dots,d\} \times \{1,\dots,d\}$ is of order $\sqrt{d}$. The inequality $c(d) \leq \sqrt{d}$ is easy from Grothendieck's characterization, and the reverse inequality $c(d) \geq \sqrt{t}/100$ follows by considering for $\Sigma$ a Hadamard unitary. All this is explained in section 2 of
Doust, I., Norms of 01 matrices in Cp, pp 5055, Proc. Centre Math. Appl. Austral. Nat. Univ., 39, Austral. Nat. Univ., Canberra, 2001.
available on the author's webpage.

$\begingroup$ Thanks a lot Mikael ! I did not see Grothendieck theorem applying here. $\endgroup$ Jun 8, 2021 at 14:45

$\begingroup$ Beware, this is not THE famous Grothendieck theorem, it is more a lemma. $\endgroup$ Jun 8, 2021 at 15:28

$\begingroup$ Ok, is it the little GT from here ? I'm actually trying to compute $$max\left(\frac{\Sigma_I_{op}}{\Sigma_{op}}:I=s \mbox{and I is symmetric}\right)$$ $\endgroup$ Jun 8, 2021 at 15:34

$\begingroup$ @guillaumelecue No, this is not little GT, but rather Proposition 3.3 in that same reference. $\endgroup$ Jun 8, 2021 at 19:28

1$\begingroup$ Thanks for the reference. Yes, the max over all $\Sigma$ would be great. $\endgroup$ Jun 9, 2021 at 9:31