Biclique decompositions and Hermitian rank

AbstractThe Hermitian rank, h(A), of a Hermitian matrix A is defined and shown to equal max{n+(A),n−(A)}, the maximum of the numbers of positive and negative eigenvalues of A. Properties of Hermitian rank are developed and used to obtain results on the minimum number, b(G), of complete bipartite subgraphs needed to partition the edge set of a graph G. Witsenhausen's inequality b(G)⩾max{n+(G),n−(G)} is reproved and conditions necessary for equality to hold are given. The results are then used to estimate b(G) for several classes of graphs. For example, if G is the complement of a path then b(G)=⌊23(n−1)⌋, while if G is the complement of a cycle then b(G)=2⌊13(n−1)⌋ or ⌊13(2n−1)⌋