Matrices of zeros and ones with the maximum jump number Original Research Article

Let A = (aij) be an m × n matrix. There is a natural way to associate a poset PA with A. Let x1, …, xm and y1, …, yn disjoint sets of m and n elements, respectively, and define xi < yj if and only if aij ≠ 0. A jump in a linear extension of PA is a pair of consecutive elements which are incomparable in P. The maximum jump number over a class of n × n matrices of zeros and ones with constant row and column sum k, M(n,k), has been investigated [R.A. Brualdi, H.C. Jung, Linear Algebra Appl. 172 (1992) 261–282]. In this paper, matrices with M(n,k) are characterized, and a conjecture appearing in Brualdi and Jung, Linear Algebra Appl. 172 (1992) 261–282, is proved.