Perfect matrix explained
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:[1]
- 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}.
Notes and References
- D. M. Ryan, B. A. Foster, An Integer Programming Approach to Scheduling, p.274, University of Auckland, 1981.
