Perfect matrix

{{Short description|Type of binary matrix}}

In mathematics, a perfect matrix is an m-by-n binary matrix that has no possible k-by-k submatrix K that satisfies the following conditions:D. M. Ryan, B. A. Foster, [http://www2.imm.dtu.dk/courses/02735/ryanfoster.pdf An Integer Programming Approach to Scheduling], p.274, University of Auckland, 1981.

• k > 3
• the row and column sums of K are each equal to b, where b ≥ 2
• there exists no row of the (m − k)-by-k submatrix formed by the rows not included in K with a row sum greater than b.

The following is an example of a K submatrix where k = 5 and b = 2:

::$$

\begin{bmatrix}

1 & 1 & 0 & 0 & 0 \\

0 & 1 & 1 & 0 & 0 \\

0 & 0 & 1 & 1 & 0 \\

0 & 0 & 0 & 1 & 1 \\

1 & 0 & 0 & 0 & 1

\end{bmatrix}.