Matrices in $\mathcal{A}(R,S)$ with minimum $t$-term ranks

Abstract

Let $R$ and $S$ be two sequences of nonnegative integers in nonincreasing order and with the same sum, and let $\mathcal{A}(R,S)$ be the class of all $(0,1)$-matrices having row sum $R$ and column sum $S$. For a positive integer $t$, the $t$-term rank of a $(0,1)$-matrix $A$ is defined as the maximum number of $1$'s in $A$ with at most one $1$ in each column, and at most $t$ $1$'s in each row. In this paper, we address conditions for the existence of a matrix in a class $\mathcal{A}(R,S)$ that realizes all the minimum $t$-term ranks, for $t\ge 1$.

24 pages