4
$\begingroup$

Given $N$ linearly independent matrices in $C^{n\times n}$, is there a lower bound known for $N$ as a function of $n$ such that the linear span of those $N$ matrices is guaranteed to contain a rank 1 matrix?

$\endgroup$
0

1 Answer 1

7
$\begingroup$

The set of rank $1$ matrices is a projective variety of dimension $2n-2$ inside the projective space over $C^{n \times n}$, which has dimension $n^2-1$. By the projective dimension theorem, it must intersect every projective variety of dimension $k$ whenever $2n-2+k > n^2-1$. The linear span of $N$ linearly independent matrices is a projective variety of dimension $k=N-1$. Therefore, if $N > (n-1)^2$, your span contains a rank $1$ matrix.

This is sharp: a generic subspace of dimension $(n-1)^2$ does not contain a rank $1$ matrix.

This question is fundamental in quantum information theory, where we want to find subspaces of $\mathbf{C}^n \otimes \mathbf{C}^n$ where every element is (very) entangled. See for example Chapter 8.1 of our book.

Aubrun, Guillaume; Szarek, Stanisław J., Alice and Bob meet Banach. The interface of asymptotic geometric analysis and quantum information theory, Mathematical Surveys and Monographs 223. Providence, RI: American Mathematical Society (AMS) (ISBN 978-1-4704-3468-7/hbk; 978-1-4704-4172-2/ebook). xxi, 414 p. (2017). ZBL1402.46001.

$\endgroup$
5
  • $\begingroup$ HI Guillaume ! Amazingly, this problem arises also, but replacing the complex field $\mathbb C$ by the real one $\mathbb R$, in Calculus of Variations, when one applies the technique of Compensated Compactness. One of my first papers was about that : Formes quadratiques et calcul des varaiations, J. Maths Pures & Appl. 62 (1983), pp 177-196. $\endgroup$ Jun 16, 2021 at 7:27
  • $\begingroup$ Hi Denis! Interesting. Let $N_{\mathbb{K}}(n)$ is the largest dimension of a subspace of $\mathbb{K}^{n \times n}$ not containing a rang $1$ matrix. We have $N_{\mathbb{R}}(n) \geq N_{\mathbb{C}}(n)$ since the lower bound arguments work for $\mathbb{R}$ as well. Also, $2=N_\mathbb{R}(2)>N_\mathbb{C}(2)=1$. Is the value of $N_{\mathbb{R}}(n)$ known ? $\endgroup$ Jun 16, 2021 at 7:38
  • $\begingroup$ thanks a lot Guillaume, this is exactly what I was looking for! I guess it is not constructive though, i.e. do you know of an algorithm which is guaranteed to find a rank 1 matrix? $\endgroup$
    – user40076
    Jun 16, 2021 at 8:30
  • $\begingroup$ I have no idea. There is an area of research called numerical algebraic geometry which may be related to what you ask, see e.g. Chapter 13 in the book "A.J. Sommese and C.W. Wampler, II,The Numerical Solution of Systems of Polynomials Arising in Engineering and Science" $\endgroup$ Jun 16, 2021 at 10:08
  • 1
    $\begingroup$ @user40076 - There are algorithms that are guaranteed to find a rank-1 matrix if it exists (you can use the Parillo sum-of-squares SDP heirarchy, for example). However, the problem is extremely similar to problems that are known to be NP-hard (and it may well be known to be NP-hard), so I doubt there is an efficient algorithm. $\endgroup$ Jun 17, 2021 at 1:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.