バランスのとれたマトリックス

数学において、バランスのとれた行列とは、すべての行の合計とすべての列の合計が 2 になる奇数次の 正方行列を含まない0-1行列(すべてのエントリが 0 または 1 である行列) です。

バランスのとれた行列は線形計画法で研究されています。バランスのとれた行列の重要性は、係数の行列がバランスがとれていて、その右辺または目的ベクトルがすべて 1 のベクトルである場合に、線形計画問題の解が積分であるという事実に由来します。^{[1] [2]}特に、この種の線形計画の積分解を探す場合、整数線形計画を明示的に解く必要はなく、線形計画自体の最適な頂点解を見つけるだけで十分です。

たとえば、次の行列はバランスの取れた行列です。

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

定義と同様に、0-1行列がバランスしているのは、奇数サイクル（奇数次のサイクルグラフ）の接続行列である部分行列を含まない場合のみです。 ^[2]

したがって、バランスが取れていない唯一の 3 x 3 の 0-1 行列は (行と列の順列を除いて)、次数 3 のサイクル グラフの接続行列です。

${\displaystyle C_{3}={\begin{bmatrix}1&0&1\\1&1&0\\0&1&1\\\end{bmatrix}}}$

次の行列は、次数 5 のサイクル グラフの接続行列です。

${\displaystyle C_{5}={\begin{bmatrix}1&0&0&0&1\\1&1&0&0&0\\0&1&1&0&0\\0&1&1&0&0\\0&0&0&1&1\\\end{bmatrix}}}$

上記の特徴は、または(または他の奇数サイクルの接続行列) を部分行列として含む行列はバランスが取れていないことを意味します。 ${\displaystyle C_{3}}$${\displaystyle C_{5}}$

バランスの取れたマトリックスはすべて完全なマトリックスです。

バランスのとれた行列という概念よりもさらに制限的なのが、完全にバランスのとれた行列という概念です。0-1 行列は、重複する列がなく、すべての行の合計とすべての列の合計が 2 に等しい正方行列を含まない場合、完全にバランスがとれていると呼ばれます。同様に、行列が完全にバランスがとれているのは、サイクルの接続行列である部分行列を含まない場合のみです (奇数次か偶数次かは関係ありません)。この特徴から、完全にバランスのとれた行列はすべてバランスがとれていることがすぐにわかります。^[3]

さらに、完全にユニモジュラな0-1 行列もバランスが取れています。次の行列は、奇数サイクルの接続行列である部分行列を含まないため、バランスの取れた行列です。

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

この行列は完全にユニモジュラではない（行列式は-2）ため、0-1完全にユニモジュラな行列はバランスの取れた行列の適切な部分集合である。^[2]

例えば、バランス行列は集合分割問題の特殊なケースにおける係数行列として現れる。^[4]

バランスの取れた行列を識別する別の方法は、部分列カウントを利用することである。ここで、行列Aの任意の行の部分列カウントSCは、

SC = |{ t | [ a _sj  = 1, a _ij  = 0（s  <  i  <  tの場合、a _tj  = 1]、j  = 1、...、  n }|

0-1行列Aがすべての行s  = 1, ...,  mに対してSC( s )≤1である場合、Aは一意の部分列を持ち、完全にユニモジュラ^{[4]であり、したがってバランスが取れています。この条件は}Aがバランスしているために十分ですが、必要ではないことに注意してください。言い換えると、すべての行s  = 1, ...,  mに対してSC( s )≤1である0-1行列は、バランスの取れた行列の集合の適切な部分集合です。

より一般的な概念として、すべての要素が0、1、-1のいずれかである行列は、行と列ごとに2つの非ゼロ要素を持つすべての部分行列で要素の合計が4の倍数である場合にバランスが取れていると呼ばれます。^[5]