Let $\Sigma$ be a $d\times d$ semi-definite 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.


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_3-i\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 0-1 matrices in Cp, pp 50-55, 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 at 14:45
  • $\begingroup$ Beware, this is not THE famous Grothendieck theorem, it is more a lemma. $\endgroup$ Jun 8 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 at 15:34
  • $\begingroup$ @guillaumelecue No, this is not little GT, but rather Proposition 3.3 in that same reference. $\endgroup$ Jun 8 at 19:28
  • 1
    $\begingroup$ Thanks for the reference. Yes, the max over all $\Sigma$ would be great. $\endgroup$ Jun 9 at 9:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.