Existence of Strict Inequalities Between the Various Matrix Ranks of Tournament Matrices

摘要

The biclique cover and partition numbers of bipartite graphs and digraphs are related to several matrix ranks. These matrix ranks include the boolean rank, nonnegative integer rank, term rank, and real rank. D. De Caen has shown that the real rank of an n-tournament matrix is n or n - 1. This result, together with other known basic relationships between the various matrix ranks, greatly restricts the possible values of the ranks of adjacency matrices corresponding to tournaments. These restrictions lead naturally to the problem of finding examples of tournaments or classes of tournaments where the ranks of the corresponding adjacency matrices are not equal. In this paper, classes of tournament matrices that satisfy various inequality relationships between the matrix ranks are given and several open problems are presented.