While mimicking the union bound in quantum systems, we land on the following conjecture but don't know how to prove this. Given any complex-valued $n\times m$ matrix $A$. A sub-matrix of $A$ is defined by two index subsets $I \subseteq [n], J \subseteq [m]$, $$ (A\vert_{I, J})_{i j} := \begin{cases} A_{ij} \quad\text{ if }i\in I, j\in J \\ 0 \quad \text{ otherwise. } \end{cases} $$ Now there are $k$ index sets pairs $I_t\subset [n], J_t\subset [m]$ for $1\le t\le k$. Suppose that for any $i\in [n], j\in [m]$, there always exists some $t$ such that $i\in I_t, j\in J_t$. (Notice that $t$ might not be unique.)

Does the following inequality always hold? $$ \|A\|_{\mathrm{op}} \le \sum_{1\le t\le k}\big\|A\vert_{I_t, J_t}\big\|_{\mathrm{op}} $$ where $\|\cdot\|_{\mathrm{op}}$ is the operator 2-norm, or equivalently, the maximum singular value.

(We posted the question in Math Stackexchange, but then realized that this should be a research level question. Thus we have deleted the old post and re-post here.)


Assume we work with the operator 2-norm. We have $$\|A\|_2^2 = \sup_{\|x\|=1} \|Ax\|_2^2=\sup_{\|x\|=1} \sum_{j=1}^{m}(\sum_{i=1}^{n}a_{ji}x_i)^2.$$ Let $I_t=\{i^t_{1}, \dots i^t_{p(t)}\}$ and $J_t=\{j^t_{1}, \dots j^t_{r(t)}\}$. Hence \begin{equation} \sum_{1 \leq t \leq k} \|A_{I_t,J_t}\|_2^2=\sum_{1 \leq t \leq k}\ \sup_{\|x\|=1}\|A_{I_t,J_t}x\|^2_2= \sup_{\|x\|=1}\ \sum_{1 \leq t \leq k} \sum_{k=1}^{r(t)} (\sum_{l=1}^{p(t)}a_{j^t_k i^t_l}x_i)^2. \end{equation} Now since for any $i \in [n],\ j \in [m]$ there is a $t$ such that $i \in I_t,\ j \in J_t$, the triple sum must contain all terms $(a_{ji}x_i)$ for $i \in [n],\ j \in [m]$ at least once. There could be some extra terms, which are non negative, so we have $$\|A\|_2^2 \leq \sum_{1 \leq t \leq k} \|A_{I_t,J_t}\|_2^2 \leq \bigg({\sum_{1 \leq t \leq k} \|A_{I_t,J_t}\|_2 }\bigg)^2.$$ Now $\sqrt{\cdot}$ is monotone, thus by taking the square root we get the desired inequality.

  • $\begingroup$ The first equation is in general wrong since it should be $$ \sup_{\Vert x\Vert=1}\sum_{j=1}^m\left|\sum_{i=1}^na_{ji}x_i\right|^2 $$ $\endgroup$ Aug 22 '19 at 11:22
  • $\begingroup$ You are right, but as far as I see the same argument still holds. $\endgroup$
    – dioniz
    Aug 22 '19 at 11:33
  • 2
    $\begingroup$ No, the argument does not hold. even if the triple sum contains all terms $(A_{ji}x_i)$, it does the square of not necessarily be greater. Since extra terms might cancel out with original terms. $\endgroup$ Aug 22 '19 at 13:32

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.