Ідеальна матриця

Ідеальна матриця — це m-by-n двійкова матриця, яка не має k x k підматриць K, що задовольняють таким умовам:

• k > 3
• Суми елементів рядків та колонок K дорівнюють b, де b ≥ 2
• Не існує жодного рядка (m − k) x k підматриці, яка утворена з рядків, що не були включені в K, із сумою елементів рядка, що більша за b.

Наступна матриця є прикладом підматриці K, де k = 5 і b = 2:

${\displaystyle {\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}}.}$

Примітки

1. D. M. Ryan, B. A. Foster, An Integer Programming Approach to Scheduling [ 8 березня 2012 у Wayback Machine.], p.274, University of Auckland, 1981.