# Understanding statement about bounds of vector in the context of a RSDF ≤ₘ WOPT proof

I'm trying to follow the proof of Lemma 4 of "Strong NP-Hardness of the Quantum Separability Problem", by S. Gharibian, 2010 [1], which, roughly, states that there is a many-one reduction from the problem of Robust Semidefinite Feasability (RSDF) and the problem of Weak Optimization (WOPT), for some particular conditions.

I believe this context is not very important (and I will try to give every necessary definition below), as my problem is with a specific step of the proof, stating that

$$\lVert \hat c \rVert_2 \in O(m^{1/2} \Delta)$$

(with these symbols to be defined).

The authors state that this follows from a previously given equation and the Cauchy–Schwarz inequality, but I don't see how these connect, and would appreciate help understanding so.

## Definitions:

• $$\DeclareMathOperator\Tr{Tr}$$(d1) $$k, l \in \mathbb{Z}^+$$
• (d2) $$M = k+1$$, $$N = l(l-1)/2 + 1$$
• (d3) $$B_j$$ are $$l \times l$$ real and symmetrical matrices, with $$j=1, \dotsc, k$$
• (d4) $$A_j$$ are $$N \times N$$ matrices, where the top-left corner is set to $$B_j$$, and the rest of the entries are set to $$0$$,
• (d5) $$C$$ is an $$(MN) \times (MN)$$ block-matrix, defined as follows: $$\begin{pmatrix} 0 & A_1 & \cdots & A_{m-1} \\ A_1 & 0 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ A_{m-1} & 0 & \cdots & 0 \end{pmatrix}$$
• (d6) $$\Delta = \sqrt{2 \sum_{i=1}^k {\lVert B_i \rVert_2}^2 }$$
• (d7) $$\{\sigma_j\}_j$$ are the Hermitian generators of $$\operatorname{SU}(MN)$$ such that $$\Tr(\sigma_j \sigma_k) = 2\delta_{jk}$$
• (d8) $$\hat c$$ is an $$MN$$-entry vector, where each component is given by $$\hat c_j = 1/2 \Tr(C\sigma_j)$$
• (d9) $$r\in \mathbb{R}^{MN}$$ is a Bloch vector for $$\mathbb{C}^M \otimes \mathbb{C}^N$$ (I don't expect this to play a large role, except maybe for the properties I've written below)
• (d10) $$m = M^2N^2 - 1$$

## Identities

The following identities/properties are known:

• (i1) $$\lVert r \rVert_2 \leq \sqrt{2 (MN - 1) / MN}$$ (though not every $$r$$ satisfying this property is a Bloch vector)
• (i2) $$\{r \; \vert \; \lVert r \rVert_2 \leq \sqrt{2/MN(MN - 1)}\}$$ is a valid set of Bloch vectors
• (i3) $$\lVert C \rVert_2 \equiv \Delta$$
• (i4) $$\frac{1}{2} \sum_{i=1}^{M^2N^2 - 1} r_i \cdot \Tr(C \sigma_i) = \hat c^T r$$

## Problem

The authors state that [1, end of paragraph following eq. 8]:

Since $$\Tr(\sigma_i \sigma_j) = 2\delta_{ij}$$, it follows from [identity i4] and the C.-S. inequality that $$\lVert \hat c \rVert_2 \in O(m^{1/2} \Delta)$$.

I don't understand how to arrive at this conclusion.

• You are using the physicist's convention where "generators of $\operatorname{SU}(MN)$" really means "elements of a[n implicit, fixed] basis of $\mathfrak{su}(MN)$", right? Commented Jan 6, 2022 at 22:44
• @LSpice My lack of awareness means probably, yes. I think I have an answer but I still haven't used orthogonality (at least explicitly). Please see below. By the way of your edit: are thanks against the rules? Commented Jan 6, 2022 at 22:50
• I'd say that it's not universal, but that there is some consensus that one should not have "thanks" in one's posts. However, it is just a general "house style"; as with all edits, if you disagree with it, then feel free to restore it. Commented Jan 6, 2022 at 22:57
• I'm fine with it :) It was just for future reference. (Also thanks for the LaTeX fixes.) Commented Jan 6, 2022 at 22:58

$$\def\Tr{\mathop{\text{Tr}}}$$ Let $$\langle \cdot, \cdot \rangle_F$$ be the Frobenius inner product.

$$C$$ is symmetric and real, so $$C^\dagger \equiv C$$, then writing out $$\lVert \hat c \rVert_2$$, and with $$(\Tr C\sigma_i)^2 \equiv \lvert \Tr C \sigma_i\rvert^2$$:

$$\lVert \hat c \rVert_2 = \sqrt{\frac{1}{2} \sum_{i=1}^{M^2N^2-1} (\Tr C\sigma_i)^2} = \sqrt{\frac{1}{2} \sum_{i=1}^{M^2N^2-1} {\langle C, \sigma_i \rangle_F}^2} \overset{\text{C.-S.}}{\leq} \sqrt{\sum_{i=1}^{M^2N^2-1} \lVert C \rVert^2 \lVert \sigma_i \rVert^2} = \lVert C \rVert \sqrt{\sum_{i=1}^{M^2N^2-1} \lVert \sigma_i \rVert^2} = \Delta \sqrt{\sum_{i=1}^{M^2N^2-1} \lVert \sigma_i \rVert^2}$$

Thus remains to prove that $$\sqrt{\sum_{i=1}^{M^2N^2-1} \lVert \sigma_i \rVert^2} = O(m^{1/2})$$:

$$\sigma_i$$ are unitary, so $$\lVert \sigma_i \rVert = \sqrt{\langle \sigma_i , \sigma_i \rangle_F} = \sqrt{\sum_{jk} (\sigma_i^\dagger \sigma_i)_{jk}} = \sqrt{\sum_{jk} (\mathbb{I}_{MN})_{jk}} = \sqrt{MN}$$.

Now, recalling that $$m := M^2N^2 - 1$$, one easily finds that $$\sqrt{\sum_i^{M^2N^2-1} \lVert \sigma_i \rVert^2} = (m^2 + m)^{1/4} = O(m^{1/2})$$.

• (Part of this answer was given by ddb in tilde.chat's #math channel, thanks to him.) Commented Jan 6, 2022 at 23:12