On Linear spaces of matrices of bounded rank

Abstract Motivated by questions in theoretical computer science and quantum information theory, we address the classical problem of determining linear spaces of matrices of bounded rank. Spaces of bounded rank three were classified in 1983, and it has been a longstanding problem to classify spaces of bounded rank four. Before our study, no non-classical example of such a space was known. We exhibit two non-classical examples of such spaces and give the full classification of basic spaces of bounded rank four. There are exactly four such up to isomorphism. We also take steps to bring together the methods used to study spaces of bounded rank from the linear algebra and algebraic geometry communities. A linear space of matrices has an associated tensor. We discuss the geometry of the tensors associated to the new examples and consequences for complexity theory.