Cycles of Nonzero Elements in Low Rank Matrices

Dedicated to the memory of Paul Erdős We consider the problem of finding some structure in the zero-nonzero pattern of a low rank matrix. This problem has strong motivation from theoretical computer science. Firstly, the well-known problem on rigidity of matrices, proposed by Valiant as a means to prove lower bounds on some algebraic circuits, is of this type. Secondly, several problems in communication complexity are also of this type. The special case of this problem, where one considers positive semidefinite matrices, is equivalent to the question of arrangements of vectors in euclidean space so that some condition on orthogonality holds. The latter question has been considered by several authors in combinatorics 1, 4]. Furthermore, we can think of this problem as a kind of Ramsey problem, where we study the tradeoff between the rank of the adjacency matrix and, say, the size of a largest complete subgraph. In this paper we show that for an real matrix with nonzero elements on the main diagonal, if the rank is o(n), the graph of the nonzero elements of the matrix contains certain cycles. We get more information for positive semidefinite matrices. Received September 9, 1999 RID="*" ID="*" Partially supported by grant A1019901 of the Academy of Sciences of the Czech Republic and by a cooperative research grant INT-9600919/ME-103 from the NSF (USA) and the MŠMT (Czech Republic).