8.7. ラテン方陣

Frobenius のマッチング定理 (命題 8.6.7) が持つ様々な応用の一つに、ラテン方陣の数学的理論がある。ラテン方陣は次のように定義される:

定義 8.7.1

\(n\) を自然数とする。\(n\) 次のラテン方陣 (Latin square of order \(n\)) とは、次の条件を満たす \(n\times n\) 行列 \(M\) を意味する:

\(M\) の要素は整数 \(1,2,\ldots,n\) であり、それぞれちょうど \(n\) 回ずつ現れる。
\(M\) の各行の要素は全て異なる。
\(M\) の各列の要素は全て異なる。

例 8.7.2

\(5\) 次のラテン方陣を次に示す:

\[ \begin{pmatrix} 1 & 2 & 3 & 4 & 5\\ 2 & 3 & 4 & 5 & 1\\ 3 & 4 & 5 & 1 & 2\\ 4 & 5 & 1 & 2 & 3\\ 5 & 1 & 2 & 3 & 4 \end{pmatrix} \]

この形をしたラテン方陣は一般化できる: \(c_{k}\) を次のように定めるとき、任意の自然数 \(n\) に対して行列 \(\left( c_{i+j-1}\right) _{1\leq i\leq n,\ 1\leq j\leq n}\) は \(n\) 次のラテン方陣である:

\[ c_{k}= \begin{cases} k & (k\leq n \text{ のとき})\\ k-n & (\text{それ以外のとき}) \end{cases} \]

ラテン方陣の有名な利用例として数独と呼ばれるパズルがある。数独では、上述の三つの条件に加えて、\(3 \times 3\) の小行列に関する制約も満たす数字の配置を見つけることがパズルの目的となる。ラテン方陣について詳しくは Wikipedia や書籍 [LayMul98] を参照してほしい。

例 8.7.2 に示したラテン方陣はあまり面白くない。どのようなアルゴリズムを使えば、一般的なラテン方陣を構築できるだろうか？

試しに、次の再帰的なアルゴリズムを考えてみよう: 最初に第 \(1\) 行を埋め、次に第 \(2\) 行を埋め、以降も同様に行ごとに埋めていく。当然、各行を埋めるときはその行がラテン方陣の一部となるように (定義 8.7.1 の条件 (b) と (c) が満たされるように) 埋める。

例 8.7.3

このアルゴリズムを使って \(5\) 次のラテン方陣を構築してみよう。第 \(1\) 行を (例えば) 次のように定めたとする:

\[ \begin{pmatrix} 3 & 1 & 4 & 2 & 5 \end{pmatrix} \]

このとき、第 \(2\) 行として \({\begin{pmatrix} 2 & 4 & 1 & 5 & 3 \end{pmatrix}}\) を付け足すことができる: この行は異なる要素からなり、各要素は第 \(1\) 行の同じ位置にある要素と異なる (ここでも第 \(2\) 行として選べる行は他にも多くある)。これで最初の二行が決定した:

\[ \begin{pmatrix} 3 & 1 & 4 & 2 & 5\\ 2 & 4 & 1 & 5 & 3 \end{pmatrix} \]

同様の処理を続ければ、次のようなラテン方陣が得られる:

\[ \begin{pmatrix} 3 & 1 & 4 & 2 & 5\\ 2 & 4 & 1 & 5 & 3\\ 1 & 5 & 2 & 3 & 4\\ 5 & 2 & 3 & 4 & 1\\ 4 & 3 & 5 & 1 & 2 \end{pmatrix} \]

[もちろん、これは今考えているアルゴリズムを使って得られるラテン方陣の一例に過ぎない。]

このアルゴリズムは必ずラテン方陣を生成するだろうか？

数学的に厳密になるなら、このアルゴリズムは完全に定義できていない。各行を埋める自明ではない操作の詳細が説明されていないからである。ただ、一旦アルゴリズムが定義できたと仮定しよう (定義できない可能性もある)。このとき、自然な疑問として「アルゴリズムは常に完全なラテン方陣を生成するのか、それともどこかで行き詰まる可能性があるのか？」がある。ここで「行き詰まる」とは、第 \(k + 1\) 行 (\(k < n\)) の生成が不可能になることを意味する。

実は、このアルゴリズムが行き詰まることはない。言い換えれば、次の命題が成り立つ:

命題 8.7.4

\(n \in \mathbb{N}\), \(k\in\left\{ 0,1,\ldots ,n-1\right\} \) を任意に取る。このとき、任意の \(k\times n\) ラテン長方形 (Latin rectangle, 要素に \(1,2,\ldots,n\) をそれぞれ \(k\) 個ずつ持ち、定義 8.7.1 の条件 (b) と (c) を満たす任意の行列) は、適切に選択された行を下部に付け足すことで \(\left( k+1\right) \times n\) ラテン長方形に拡張できる。

[証明] \(k \times n\) ラテン長方形を \(M\) とする¹。\(M\) の下部に追加すると \(\left( k+1\right) \times n\) ラテン長方形が得られるような行を見つけたい。

この新しい行は \(1,2,\ldots,n\) を含む必要があり、さらに任意の \(i\in\left\{ 1,2,\ldots,n\right\} \) に対して新しい行の第 \(i\) 要素は \(M\) の第 \(i\) 列の要素と一致してはいけない。この条件を満たす行をどうすれば見つけられるだろうか？

\(X=\left\{ 1,2,\ldots,n\right\} \) および \(Y=\left\{ -1,-2,\ldots ,-n\right\} \) と定め、単純グラフ \(G\) を次のように定義する: \(G\) の頂点集合は \(X \cup Y\) であり、頂点 \(i \in X\) と頂点 \(-j \in Y\) は \(j\) が \(M\) の第 \(i\) 列に存在しないとき、かつそのときに限って隣接する。これ以外に隣接する二頂点は存在しない。

このとき \(\left( G,X,Y\right) \) は二部グラフである。さらに、グラフ \(G\) が \(\left( n-k\right) \)-正則だと示すのも難しくない²。よって Frobenius のマッチング定理 (命題 8.6.7) より、\(G\) は完全マッチングを持つ。この完全マッチングを

\[ \left\{ \left\{ 1,\ -a_{1}\right\} ,\ \left\{ 2,\ -a_{2}\right\} ,\ \ldots,\ \left\{ n,\ -a_{n}\right\} \right\} \]

とする。このマッチングに属する辺は端点を共有しないので、\(a_{1},a_{2},\ldots,a_{n}\) は相異なる。さらに、\(\left\{ i,\ -a_{i}\right\} \) が \(G\) の辺のとき、\(a_{i}\) は \(M\) の第 \(i\) 列に含まれない。よって、\(M\) の下部に新しい行

\[ \begin{pmatrix} a_{1} & a_{2} & \cdots & a_{n} \end{pmatrix} \]

を付け足せば \(\left( k+1\right) \times n\) ラテン長方形が得られる。以上で命題 8.7.4 は証明された。□

命題 8.7.4 は Marshall Hall [Hall45] (Hall の結婚定理を発見した Philip Hall とは別人) によって 1945 年に証明された。ここに示したのは彼の証明と全く同じ議論である。

例えば \(n=5\) と \(k=3\) のときは

\[ \begin{pmatrix} 3 & 1 & 4 & 2 & 5\\ 2 & 4 & 1 & 5 & 3\\ 1 & 5 & 2 & 3 & 4 \end{pmatrix} \]

が \(M\) となれる。 ↩︎
証明: \(M\) の第 \(i\) 列には \(\left\{ 1,2,\ldots,n\right\} \) に属する \(k\) 個の相異なる値があるので、\(\left\{ 1,2,\ldots,n\right\} \) に属して \(M\) の第 \(i\) 列に属さない値は \(n - k\) 個ある。よって任意の頂点 \(i \in X\) は \(n-k\) の次数を持つ。後は任意の頂点 \(-j \in Y\) が次数 \(n-k\) を持つと示せばよい。頂点 \(-j \in Y\) を任意に取る。条件 (b) より、\(M\) の各行は \(j\) を一つずつ含む。よって \(j\) は \(M\) に全部で \(k\) 個含まれる。さらに、条件 (c) より各行で \(j\) が含まれる位置は全て異なる。ここから、\(j\) を含む \(M\) の列は \(k\) 個あると分かる。よって \(j\) を含まない \(M\) の列は \(n-k\) 個ある。言い換えれば、頂点 \(-j \in Y\) は \(n-k\) の次数を持つ。 ↩︎