Let $e_1,...,e_r$ be the first $r$ standard basis of $\mathbb{R}^n, r<n$. Let $u_1,...,u_n$ be another orthonormal basis of $\mathbb{R}^n$. Let $\otimes$ be the tensor product on $\mathbb{R}^n$ and define a subspace of $\mathbb{R}^{n\times n}$ as $$S = span\{e_1\otimes e_1,...,e_r\otimes e_r\}$$ $\mathbb{R}^{n\times n}$, as a Hilbert space, is also equipped with the usual matrix inner product $\langle,\rangle$ and the induced norm $\|\|$ (which is the Frobenius norm).

Take any $\Lambda\in S$ with $\|\Lambda\|=1$. Is the following conjecture true?

There exists a constant $C\geq1$, if $u_1,...,u_n$ are chosen such that $$1 -\delta\leq\sum_{i=1}^n\left|\langle\Lambda,u_i\otimes u_i\rangle\right|^2$$ for some very small $\delta>0$ (for example $0<\delta<\frac{1}{rn}$), then there exists a set $T\subset\{1,2,...,n\}$ with $|T| = r$ satisfying $$1-C\delta\leq\sum_{i\in T}\left|\langle\Lambda,u_i\otimes u_i\rangle\right|^2$$

The conjecture can be verified when $r=1$. Note that $C$ cannot depend on $\delta$, which means the conjecture states that there is a $C>0$ to make the assertion true for all $\delta$ small enough. For example, $C$ can be taken as 2 when $r=1$.

  • 1
    $\begingroup$ Sure. Let $C = 1$ and $T = \{1, \ldots, n\}.$ $\endgroup$ – Vít Tuček Aug 15 '19 at 12:37
  • 3
    $\begingroup$ @VítTuček: they said $r < n$. $\endgroup$ – Nik Weaver Aug 15 '19 at 13:40
  • 1
    $\begingroup$ looks to be true for r=1 $\endgroup$ – Paata Ivanishvili Aug 15 '19 at 17:07
  • $\begingroup$ Take $C$ large enough to make $1-C\delta$ negative! $\endgroup$ – Meisam Soleimani Malekan Aug 16 '19 at 4:02
  • $\begingroup$ @MeisamSoleimaniMalekan C should be a constant not depending on $\delta$... I'll make this clearer in the post. $\endgroup$ – neverevernever Aug 16 '19 at 12:29

Without loss of generality, $u_1,\dots,u_n$ can be taken to be the standard basis of ${\bf R}^n$ (so $e_1,\dots,e_r$ is just some arbitrary orthonormal system). We can view $\Lambda$ as a real symmetric $n \times n$ matrix of Frobenius norm $1$ and rank at most $r$. (Conversely, every such matrix has a representation of the desired form for some $e_1,\dots,e_r$ by the spectral theorem, so this reformulation has not lost any information.) If $D = \sum_{i=1}^n \langle \Lambda, u_i \otimes u_i \rangle u_i \otimes u_i$ is the diagonal component of $\Lambda$, the hypothesis is then $\|D\|^2 \geq 1-\delta$.

Let $\lambda = \mathrm{diag}(\lambda_1,\dots,\lambda_r,0,\dots,0)$ be the diagonalisation of $\Lambda$ (the ordering of the eigenvalues is irrelevant), thus $\lambda$ is a unit vector supported on a set of $r$ indices in $\{1,\dots,n\}$. By the Schur-Horn theorem, $D$ is a convex combination of the permutations $\sigma(\lambda)$ of $\lambda$, $\sigma \in S_n$, where the symmetric group $S_n$ acts on diagonal matrices in the obvious manner, thus $$ D = \sum_{\sigma \in S_n} c_\sigma \sigma(\lambda)$$ for some non-negative coefficients $c_\sigma$ summing to $1$. (Again, the Schur-Horn theorem is an if-and-only-if statement, so we have still not lost any information so far.)

Now we exploit the uniform convexity of the Frobenius norm. We take the norm square $$ 1-\delta \leq \|D\|^2 = \sum_{\sigma,\sigma' \in S_n} c_\sigma c_{\sigma'} \langle \sigma(\lambda), \sigma'(\lambda) \rangle$$ and then apply the cosine rule to conclude $$ \sum_{\sigma,\sigma' \in S_n} c_\sigma c_{\sigma'} \| \sigma(\lambda) - \sigma'(\lambda)\|^2 \leq 2\delta$$ hence by pigeonholing there exists $\sigma_0 \in S_n$ such that $$ \sum_{\sigma \in S_n} c_\sigma \| \sigma(\lambda) - \sigma_0(\lambda)\|^2 \leq 2\delta$$ hence by Cauchy-Schwarz $$ \sum_{\sigma \in S_n} c_\sigma \| \sigma(\lambda) - \sigma_0(\lambda)\| \leq \sqrt{2\delta}$$ hence by the triangle inequality $$ \| \sum_{\sigma \in S_n} c_\sigma \sigma(\lambda) - \sigma_0(\lambda)\| \leq \sqrt{2\delta}$$ thus $$ \| D - \sigma_0(\lambda) \| \leq \sqrt{2\delta}.$$ The diagonal matrix $\sigma_0(\lambda)$ is supported on a set $T \subset \{1,\dots,n\}$ of cardinality $r$, and the above inequality implies that the Frobenius norm of $D$ outside of $T$ is at most $\sqrt{2\delta}$. Thus $$ \sum_{i \not \in T} |\langle \Lambda, u_i \otimes u_i \rangle|^2 \leq 2\delta$$ so that $$ \sum_{i \in T} |\langle \Lambda, u_i \otimes u_i \rangle|^2 \geq 1-3\delta$$ as required.

  • $\begingroup$ This proof is ingenious. Thank you Terry! $\endgroup$ – neverevernever Aug 16 '19 at 16:53

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.