完璧なマトリックス

数学において、完全行列とは、以下の条件を満たすk行k列の部分行列Kが存在しないm行n 列の2元行列である。 ^[1]

• k > 3
• Kの行と列の合計はそれぞれbに等しい（b ≥ 2）
• Kに含まれない行で構成される( m  −  k )行k列の部分行列の行の合計がbを超える行は存在しない。

以下は、 k = 5、b = 2 のKサブマトリックスの例です。

${\displaystyle {\begin{bmatrix}1&1&0&0&0\\0&1&1&0&0\\0&0&1&0&0\\0&0&1&1&0\\1&0&0&0&1\\1&0&0&1\end{bmatrix}}.}$

参考文献

1. DM Ryan、BA Foster、「整数計画法によるスケジューリングへのアプローチ」、p.274、オークランド大学、1981年。