Rank decomposition under combinatorial constraints

被引：3

作者：

Johnson, CR ^{[1
]}

Miller, J ^{[1
]}

机构：

[1] RANDOLPH MACON COLL,DEPT MATH,ASHLAND,VA 23005

来源：

LINEAR ALGEBRA AND ITS APPLICATIONS | 1997年 / 251卷

基金：

美国国家科学基金会;

关键词：

D O I：

10.1016/0024-3795(95)00548-X

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

A matrix is subordinate to a bipartite graph if the graph has an edge corresponding to every position in which the matrix has a nonzero entry. Which graphs have the property that every rank k matrix subordinate to the graph can be expressed as the sum of k rank 1 matrices, each of which is also subordinate to the graph? It is classical that the complete bipartite graph has this property, and more recently it has been shown that the graphs of block triangular, not necessarily square, matrices have this property. We show that the bipartite chordal graphs constitute the full answer. This fact may then be used to show that the bipartite chordal graphs constitute a case of equality in the general inequality (minimum rank) less than or equal to (biclique cover number). (C) Elsevier Science Inc., 1997

引用

页码：97 / 104

页数：8