Rank decomposition under combinatorial constraints Original Research Article

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) ≤ (biclique cover number).