Biclique decompositions and Hermitian rank Original Research Article

The 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)greater-or-equal, slantedmax{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 image, while if G is the complement of a cycle then image or image.