# Quantum inspired matrix inequality

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.
• 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$$ – Taylor Huang Aug 22 '19 at 11:22
• 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. – Taylor Huang Aug 22 '19 at 13:32