If \(u\) is a column vector in \(\mathbb C^d\) and \(A\) a \(d \times d\) matrix, we denote by \(u^*\) its Hermitian transpose, by \(\| u \|\) the Euclidean norm of \(x\), and by \(\| A\|\) the operator norm of \(A\). The identity matrix is denoted by \(I\).
A. Marcus, D. A. Spielman and N. Srivastava [“Interlacing families II: Mixed characteristic polynomials and the Kadison-Singer problem”, Preprint, arXiv:1306.3969] proved the following result:
Fix \(\varepsilon > 0\) and let \(u_1, \dots,u_m\) be column vectors in \(\mathbb C^d\) such that \(\sum_{k=1}^m u_k u_k^* = I\) and \(\| u_k \| ^2 \leq \varepsilon\) for all \(k \in \{ 1, \dots, m\}\). Then there exists a partition of \(\{1, \dots,m\}\) into disjoint sets \(S_1\) and \(S_2\) such that, for \(j \in \{1,2\}\), \[ \left \| \sum_{k \in S_j} u_k u_k^* \right \| \leq \frac 12 + O(\sqrt{\varepsilon}). \] Using a reduction due to J. Anderson [Trans. Am. Math. Soc. 249, 303–329 (1979; Zbl 0408.46049)], this result implies a positive solution to the Kadison-Singer problem. This problem had been open for 54 years, see [P. G. Casazza and J. C. Tremain, Proc. Natl. Acad. Sci. USA 103, No. 7, 2032–2039 (2006; Zbl 1160.46333)] for more information.
The aforementioned result can be interpreted in the following way. If we have a set of small multiples of rank 1 projections that sum up to the identity matrix, then we can partition this set into two subsets each of which sums up to approximately half the identity matrix. The authors now study the question which other matrices can be approximated in this way and prove the following:
Fix \(\varepsilon > 0\) and let \(u_1, \dots,u_m\) be column vectors in \(\mathbb C^d\) such that \(\sum_{k=1}^m u_k u_k^* = I\) and \(\| u_k \| ^2 \leq \varepsilon\) for all \(k \in \{ 1, \dots, m\}\). Suppose \(0 \leq t_k \leq 1\) for \(k \in \{1, \dots,m\}\). Then there exists a set of indices \(S \subset \{1,\dots,m\}\) such that \[ \left \| \sum_{k \in S} u_k u_k^* - \sum_{k=1}^m t_k u_k u_k^*\right \| \leq O(\varepsilon^\frac 18). \]