Cycles of Nonzero Elements in Low Rank Matrices
Cycles of Nonzero Elements in Low Rank Matrices
复制标题
低秩矩阵中非零元素的循环
DOI：
--
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
P. Pudlák
中科院分区：
文献类型：
--
作者：
P. Pudlák
致力于内存的保罗Erdwords我们考虑的问题，找到一些结构中的零非零模式的低秩矩阵。这个问题有很强的理论计算机科学的动机。首先，著名的矩阵刚性问题，Valiant作为证明某些代数电路下界的一种手段而提出的，就是这种类型。其次，通信复杂性中的几个问题也属于这种类型。这个问题的特殊情况，其中一个考虑半正定矩阵，是等价于问题的安排向量在欧几里德空间，使一些条件正交举行。后一个问题已经考虑了几个作者在组合[1，4]。此外，我们可以把这个问题看作是一种Ramsey问题，在这里我们研究邻接矩阵的秩和最大完全子图的大小之间的权衡。本文证明了对于主对角线上具有非零元素的真实的矩阵，如果秩为o（n），则矩阵的非零元素的图包含某些圈。我们得到了更多关于半正定矩阵的信息。
Dedicated to the memory of Paul ErdősWe 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.