Extending partial permutation matrices

Abstract:

Let ${M_1},\;{M_2}, \cdots ,\;{M_s}$ be $n \times n$ arrays such that in each ${M_i}$, each cell is either empty or occupied by a $1$. It is shown that if ${M_1} + {M_2} + \cdots + {M_s}$ contains only $1$’s, the totality of $1$’s is less than or equal to $n - 1$, and the $1$’s are in different rows and columns, then the ${M_i}$’s can be completed to permutation matrices $M_1’ , \cdots ,M_s’$ so that $M_1’ + \cdots + M_s’$ is a $(0,\;1)$-matrix.