ラテン方陣
概要
ラテン方陣（Latin square）とは、$n$ 種類の記号を $n\times n$ の表に、どの行にもどの列にも各記号がちょうど 1 回ずつ現れるように並べたものである。群や準群の演算表がその例で、Latin 長方形は Hall の結婚定理によって延長できる。2 つを重ねて記号の対がすべて 1 回ずつ現れるとき直交するといい、位数 $n\ge2$ の互いに直交するラテン方陣は $n-1$ 個以下で、$n$ が素数冪なら有限体を使って $n-1$ 個作れ、そこから位数 $n$ の射影平面が得られる。位数 $2$ と $6$ には直交する対がないが、$n>6$ ではつねに存在する（Bose–Shrikhande–Parker）。
ラテン方陣（Latin square）とは、$n$ 種類の記号を $n\times n$ の表に並べ、どの行にもどの列にも各記号がちょうど 1 回ずつ現れるようにしたものである。群の演算表はラテン方陣であり、数独の完成した盤面もラテン方陣になっている。
ラテン方陣の理論の中心は 直交 の概念である。2 つのラテン方陣を重ねたとき、記号の対がすべてちょうど 1 回ずつ現れるなら、それらは直交するという。6 つの連隊から 6 つの階級の士官を 1 人ずつ選んだ 36 人を、どの行・どの列にも各連隊・各階級が 1 人ずつ現れるように並べる問題（Euler の 36 士官問題）は、位数 $6$ の直交するラテン方陣の対を求める問題である。Euler は $n\equiv2\pmod4$ のとき位数 $n$ の直交する対は存在しないと予想した。位数 $6$ では対はないが、位数 $10$ 以上では予想は誤りで、Bose・Shrikhande・Parker が 1960 年に $n>6$ のすべての $n$ で対が存在することを示した（BSP60 p. 189、p. 202 の Theorem 10、p. 203）。
この記事では、互いに直交するラテン方陣の個数が $n-1$ 以下であること、$n$ が素数冪ならちょうど $n-1$ 個とれること、積による構成、$n-1$ 個の組から射影平面が作れること、直交するラテン方陣から強正則グラフが作れることを完全に証明する。
定義
$n\ge1$ とし、$n$ 元集合 $R$、$C$、$S$（行の添字、列の添字、記号）を固定する。ふつうは 3 つとも $\{1,\dots,n\}$ や $\mathbb{Z}/n\mathbb{Z}$ にとる。
写像 $L\colon R\times C\to S$ が 位数 $n$ のラテン方陣（$n$ 次のラテン方陣）であるとは、各 $r\in R$ について $c\mapsto L(r,c)$ が全単射で、各 $c\in C$ について $r\mapsto L(r,c)$ が全単射であることをいう。$L(r,c)$ を第 $r$ 行・第 $c$ 列に書いた表と同一視する。
$R=C=S=\{1,\dots,n\}$ で、第 1 行と第 1 列が $1,2,\dots,n$ の順に並んでいるラテン方陣を 標準形 という。どのラテン方陣も、列を並べ替えて第 1 行を $1,\dots,n$ の順にし、続いて第 2 行以下を並べ替えて第 1 列を $1,\dots,n$ の順にすれば、標準形になる。
- 巡回ラテン方陣：$R=C=S=\mathbb{Z}/n\mathbb{Z}$ で $L(x,y)=x+y$ とおく。$x$ を固定すると $y\mapsto x+y$ は全単射で、$y$ を固定しても同じなので、ラテン方陣である。$n=3$ では
$$ \begin{pmatrix}0&1&2\\1&2&0\\2&0&1\end{pmatrix} $$
である。 - 群の演算表：有限群 $G$ について $L(g,h)=gh$ はラテン方陣である。$g$ を固定すると $h\mapsto gh$ は逆写像 $h\mapsto g^{-1}h$ をもつからである（群 の命題「方程式の一意可解性と消去律」）。1 は $G=\mathbb{Z}/n\mathbb{Z}$ の場合である。
- 完全二部グラフの辺彩色：$K_{n,n}$ の頂点 $x_i,y_j$ を結ぶ辺に色 $L(i,j)$ を塗ることが辺彩色であることと、$L$ がラテン方陣であることは同値である（完全二部グラフ の例「$K_{n,n}$ の完全マッチングとラテン方陣」）。
群の演算表の一般化として、集合 $Q$ の上の二項演算 $\circ$ で、任意の $a,b\in Q$ について $a\circ x=b$ と $y\circ a=b$ がそれぞれただ 1 つの解 $x,y$ をもつものを 準群（quasigroup）という。定義をそのまま読みかえると、有限集合 $Q$ の上の二項演算が準群であることと、その演算表 $L(a,x)=a\circ x$ がラテン方陣であることは同値である（行 $a$ で $x\mapsto a\circ x$ が全単射であることが第 1 の方程式の一意可解性、列についても同様）。
存在と個数
巡回ラテン方陣により、どの $n\ge1$ についても位数 $n$ のラテン方陣がある。さらに、各行が $1,\dots,n$ の並べ替えで各列に同じ数が 2 度現れない $r\times n$ の表（Latin 長方形）は、行を 1 つずつ付け加えてラテン方陣に延長できる（Hallの結婚定理 の命題「Latin 長方形は 1 行延ばせる」）。
位数 $n$ のラテン方陣（$R=C=S=\{1,\dots,n\}$）の個数を $\Lambda_n$、そのうち標準形のものの個数を $\Lambda_n^\circ$ とする。
$\Lambda_n=n!\,(n-1)!\,\Lambda_n^\circ$ である。
要点：列の置換と第 2 行以下の置換の組で、ラテン方陣と標準形が 1 対 1 に対応する。
証明を開く
列の置換 $\sigma$（$\{1,\dots,n\}$ の置換）と、第 2 行以下の行の置換 $\tau$（$\{2,\dots,n\}$ の置換）の組 $(\sigma,\tau)$ は $n!(n-1)!$ 個ある。ラテン方陣 $L$ が与えられると、第 1 行を $1,\dots,n$ の順にする列の置換 $\sigma$ はただ 1 つで、その後の第 1 列の第 1 成分は $1$ なので、第 2 行以下を並べ替えて第 1 列を $1,\dots,n$ の順にする $\tau$ もただ 1 つである。逆に、標準形 $L^\circ$ と $(\sigma,\tau)$ から、置換を逆にたどって $L$ がただ 1 つ得られる。こうして $L\mapsto(\sigma,\tau,L^\circ)$ は全単射である。$\square$
位数 $3$ の標準形は、第 1 行が $(1,2,3)$、第 1 列が $(1,2,3)^{\mathsf T}$ と決まると、第 2 行の残り 2 成分は $(3,1)$ しかなく（第 2 列に $2$、第 3 列に $3$ が既にあるので第 2 行は $(2,3,1)$）、第 3 行も $(3,1,2)$ と決まる。よって $\Lambda_3^\circ=1$、$\Lambda_3=3!\cdot2!\cdot1=12$ である。すべての表を書き出して数えると、
$$
(\Lambda_1^\circ,\Lambda_2^\circ,\Lambda_3^\circ,\Lambda_4^\circ)=(1,1,1,4),\qquad (\Lambda_1,\Lambda_2,\Lambda_3,\Lambda_4)=(1,2,12,576)
$$
である。
直交ラテン方陣
同じ $R,C$ の上の位数 $n$ のラテン方陣 $L_1\colon R\times C\to S_1$、$L_2\colon R\times C\to S_2$ が 直交する とは、
$$
R\times C\to S_1\times S_2,\qquad (r,c)\mapsto\bigl(L_1(r,c),L_2(r,c)\bigr)
$$
が全単射であること、すなわち重ねた表に記号の対が各 1 回ずつ現れることをいう。どの 2 つも直交するラテン方陣の組を 互いに直交するラテン方陣（mutually orthogonal Latin squares）の組という。$n\ge2$ について、その組の大きさの最大値を $N(n)$ と書く。
記号の名前を付け替えても（$S$ の全単射を合成しても）、ラテン方陣であることと直交性は保たれる。$n\ge2$ では $L$ と $L$ 自身は直交しない（対 $(s,s)$ しか現れない）。
$n\ge2$ なら $N(n)\le n-1$ である。
$L_1,\dots,L_t$ を互いに直交するラテン方陣とし、記号を $\{1,\dots,n\}$ とする。第 1 行を $r_1$、列を $c_1,\dots,c_n$ と番号付ける。各 $L_i$ の記号を付け替えて、$L_i(r_1,c_s)=s$（$s=1,\dots,n$）としてよい。$n\ge2$ なので第 1 行と異なる行 $r_2$ がある。マス $(r_2,c_1)$ を考えると、第 1 列には第 1 行に $1$ があるので $L_i(r_2,c_1)\ne1$ である。$i\ne j$ で $L_i(r_2,c_1)=L_j(r_2,c_1)=s$ なら、対 $(s,s)$ が $(L_i,L_j)$ を重ねた表のマス $(r_2,c_1)$ と $(r_1,c_s)$ の 2 か所に現れ（行が異なるので別のマス）、直交性に反する。よって $L_1(r_2,c_1),\dots,L_t(r_2,c_1)$ は $\{2,\dots,n\}$ の相異なる元で、$t\le n-1$ である。$\square$
$q$ を素数冪、$\mathbb{F}_q$ を $q$ 元の有限体とする。$a\in\mathbb{F}_q^\times$ について
$$
L_a\colon\mathbb{F}_q\times\mathbb{F}_q\to\mathbb{F}_q,\qquad L_a(x,y)=ax+y
$$
とおくと、$L_a$（$a\ne0$）は互いに直交する $q-1$ 個のラテン方陣である。とくに $q\ge2$ について $N(q)=q-1$ である。
$x$ を固定すると $y\mapsto ax+y$ は全単射である。$y$ を固定すると、$a\ne0$ なので $x\mapsto ax+y$ は逆写像 $z\mapsto a^{-1}(z-y)$ をもつ全単射である。よって $L_a$ はラテン方陣である。$a\ne b$ とし、$(s,t)\in\mathbb{F}_q^2$ を与えると、連立方程式 $ax+y=s$、$bx+y=t$ は、差をとって $(a-b)x=s-t$ から $x=(a-b)^{-1}(s-t)$、ついで $y=s-ax$ とただ 1 組の解をもつ（$a-b\ne0$ は体で可逆）。したがって $L_a$ と $L_b$ は直交する。$N(q)\ge q-1$ と thm-ls-bound から $N(q)=q-1$ である。$\square$
- $q=3$：$L_1(x,y)=x+y$ と $L_2(x,y)=2x+y$（$\mathbb{Z}/3\mathbb{Z}$ 上）は
$$ \begin{pmatrix}0&1&2\\1&2&0\\2&0&1\end{pmatrix},\qquad\begin{pmatrix}0&1&2\\2&0&1\\1&2&0\end{pmatrix} $$
で、重ねると $(0,0),(1,1),(2,2),(1,2),(2,0),(0,1),(2,1),(0,2),(1,0)$ の $9$ 対がすべて異なる。 - $q=4$：$\mathbb{F}_4=\{0,1,\omega,\omega^2\}$（$\omega^2=\omega+1$）の元を $0,1,2,3$ と書くと（$2=\omega$、$3=\omega^2$。加法は 2 進数の各桁の排他的論理和）、$a=1,\omega,\omega^2$ の $L_a$ は
$$ \begin{pmatrix}0&1&2&3\\1&0&3&2\\2&3&0&1\\3&2&1&0\end{pmatrix},\quad \begin{pmatrix}0&1&2&3\\2&3&0&1\\3&2&1&0\\1&0&3&2\end{pmatrix},\quad \begin{pmatrix}0&1&2&3\\3&2&1&0\\1&0&3&2\\2&3&0&1\end{pmatrix} $$
で、どの 2 つも直交する。$N(4)=3$ である。 - $n=2$：位数 $2$ のラテン方陣は $\begin{pmatrix}1&2\\2&1\end{pmatrix}$ と $\begin{pmatrix}2&1\\1&2\end{pmatrix}$ の 2 つだけで、どの 2 つを重ねても現れる対は 2 種類なので直交しない。$N(2)=1$ で、thm-ls-bound の等号が成り立つ。
積による構成
$L_1,\dots,L_t$ を位数 $m$ の互いに直交するラテン方陣（行・列・記号の集合 $R,C,S$）、$M_1,\dots,M_t$ を位数 $n$ の互いに直交するラテン方陣（$R',C',S'$）とする。
$$
(L_i\otimes M_i)\bigl((r,r'),(c,c')\bigr):=\bigl(L_i(r,c),\,M_i(r',c')\bigr)
$$
とおくと、$L_1\otimes M_1,\dots,L_t\otimes M_t$ は位数 $mn$ の互いに直交するラテン方陣（行・列・記号の集合 $R\times R'$、$C\times C'$、$S\times S'$）である。とくに $N(mn)\ge\min\{N(m),N(n)\}$ である。
行 $(r,r')$ を固定すると、$(c,c')\mapsto(L_i(r,c),M_i(r',c'))$ は 2 つの全単射 $c\mapsto L_i(r,c)$、$c'\mapsto M_i(r',c')$ の直積なので全単射である。列を固定しても同様である。$i\ne j$ について、重ねた表の写像
$$
\bigl((r,r'),(c,c')\bigr)\mapsto\Bigl(\bigl(L_i(r,c),M_i(r',c')\bigr),\bigl(L_j(r,c),M_j(r',c')\bigr)\Bigr)
$$
は、成分を並べ替えれば、全単射 $(r,c)\mapsto(L_i(r,c),L_j(r,c))$ と $(r',c')\mapsto(M_i(r',c'),M_j(r',c'))$ の直積である。したがって全単射で、2 つは直交する。$t=\min\{N(m),N(n)\}$ にとれば最後の主張を得る。$\square$
$n\ge2$ を素因数分解して $n=p_1^{e_1}\cdots p_s^{e_s}$ とすると、$N(n)\ge\min_i p_i^{e_i}-1$ である。とくに $n\not\equiv2\pmod4$ なら $N(n)\ge2$、すなわち位数 $n$ の直交するラテン方陣の対がある。
thm-ls-field により $N(p_i^{e_i})=p_i^{e_i}-1$ で、thm-ls-product を繰り返し使えばよい。$n\ge2$ で $n\not\equiv2\pmod4$ なら、$n$ が奇数のときどの素数冪因子も $3$ 以上で、$4\mid n$ のとき $2$ の冪の因子は $4$ 以上、奇素数の冪の因子は $3$ 以上なので、最小値は $3$ 以上である。$\square$
この下界は MacNeish と Mann による（BSP60 p. 189）。MacNeish は $N(n)$ がこの下界に等しいと予想したが、これは成り立たない（同所）。
Euler の 36 士官問題
Euler の問題は、連隊と階級をそれぞれ記号とする位数 $6$ の直交するラテン方陣の対が存在するかを問う。下界 cor-ls-macneish は $n\equiv2\pmod4$ では $N(n)\ge1$ しか与えない。Euler はこの場合に対は存在しないと予想した（BSP60 p. 189）。
$n>6$ なら、位数 $n$ の直交するラテン方陣の対が存在する（$N(n)\ge2$）。
BSP60 p. 202 の Theorem 10 による。$n\not\equiv2\pmod4$ の場合は cor-ls-macneish で済み、残りの $n\equiv2\pmod4$ の場合が、ブロックデザイン（pairwise balanced design など）と差の方法による構成で示される。この記事では証明しない。同所（p. 203）は、$n>2$ で直交する対が存在しない位数は $6$ だけであると結論している。$n=2$ に対がないことは ex-ls-order23 の 3 で確かめた。位数 $6$ に対がないことはこの記事では証明しない。
射影平面との関係
$n\ge2$ とし、位数 $n$ の互いに直交するラテン方陣 $L_1,\dots,L_{n-1}$ があるとする。このとき位数 $n$ の有限射影平面が存在する。
要点：マスを点、行・列・各 $L_k$ の同じ記号のマスの集合を直線とすると、どの 2 マスもちょうど 1 本の直線に乗る（アフィン平面）。各平行類に無限遠点を 1 つずつ足し、無限遠直線を加える。
証明を開く
$\mathcal{K}:=\{0,1,\dots,n\}$ とおき、$P_0(r,c):=r$、$P_n(r,c):=c$、$1\le k\le n-1$ では $P_k:=L_k$ とする。$k\in\mathcal{K}$ と値 $s$ について、マスの集合 $\ell_{k,s}:=\{(r,c):P_k(r,c)=s\}$ を考える。各 $\ell_{k,s}$ はちょうど $n$ マスからなり、$k$ を固定すると $n$ 本の $\ell_{k,s}$ はマス全体の分割である。$k\ne k'$ なら、$\ell_{k,s}$ と $\ell_{k',s'}$ はちょうど 1 マスを共有する（$P_k,P_{k'}$ がともにラテン方陣なら直交性から。一方が行か列なら、他方がラテン方陣であることか、行と列が 1 マスで交わることから）。
点を、$n^2$ 個のマスと、$n+1$ 個の新しい点 $\infty_k$（$k\in\mathcal{K}$）とする。直線を、$\ell_{k,s}\cup\{\infty_k\}$（$n(n+1)$ 本）と $\ell_\infty:=\{\infty_k:k\in\mathcal{K}\}$ とする。射影平面 の公理「射影平面の公理」を確かめる。
(i) 異なる 2 点を通る直線がただ 1 本あること。2 マス $Q\ne Q'$ について、$Q$ を通る各 $k$ の直線 $\ell_{k,P_k(Q)}$ のうち 2 本は $Q$ 以外に共有マスをもたない（上の性質）ので、$Q$ を通る $n+1$ 本の直線上の $Q$ 以外のマスは合わせて $(n+1)(n-1)=n^2-1$ 個で互いに異なり、$Q$ 以外のマス全体と一致する。よって $Q'$ を通る直線はちょうど 1 本である。マス $Q$ と $\infty_k$ を通る直線は、$k$ の分割で $Q$ を含む $\ell_{k,s}\cup\{\infty_k\}$ だけである。$\infty_k$ と $\infty_{k'}$ を通るのは $\ell_\infty$ だけである。
(ii) 異なる 2 直線がただ 1 点を共有すること。同じ $k$ の 2 本は $\infty_k$ だけを共有する。$k\ne k'$ の 2 本は、上の性質によりちょうど 1 マスを共有し、無限遠点は共有しない。$\ell_{k,s}\cup\{\infty_k\}$ と $\ell_\infty$ は $\infty_k$ だけを共有する。
(iii) 4 マス $(r_1,c_1),(r_1,c_2),(r_2,c_1),(r_2,c_2)$（$r_1\ne r_2$、$c_1\ne c_2$）のうちどの 3 つにも、同じ行か同じ列の 2 マスが含まれ、その 2 マスを通る直線はその行か列だけで、残りの 1 マスを含まない。よってどの 3 つも共線でない。
各直線には $n+1$ 個の点があるので、位数は $n$ である（射影平面 の定理「有限射影平面の位数」）。$\square$
thm-ls-field と合わせると、素数冪 $q$ について位数 $q$ の射影平面が得られる。これは有限体の上の射影平面 $\mathbb{P}^2(\mathbb{F}_q)$ と同じ位数である（射影平面 の例「Fano 平面」のあとの注意）。
直交配列とラテン方陣グラフ
位数 $n$ の互いに直交するラテン方陣 $L_1,\dots,L_{g-2}$（$g\ge2$）に「行の番号」「列の番号」を加えた $g$ 個の写像は、$g$ 行 $n^2$ 列の表で、どの 2 行を取り出しても、記号の対のそれぞれがちょうど 1 つの列に現れるものを与える。これを 直交配列 といい、逆に直交配列から互いに直交する $g-2$ 個のラテン方陣が得られる（BH11 §9.1.12、pp. 120–121）。
$n\ge2$、$1\le g\le n$ とし、位数 $n$ の互いに直交するラテン方陣 $L_1,\dots,L_{g-2}$（$g\le2$ のときは 0 個）を考える。$n^2$ 個のマスを頂点とし、2 マスが同じ行・同じ列、または $g\ge3$ のときある $L_i$ で同じ記号をもつとき辺で結ぶ。ただし $g=1$ のときは同じ行だけで結ぶ。このグラフは強正則グラフ $\mathrm{srg}\bigl(n^2,\ g(n-1),\ n-2+(g-1)(g-2),\ g(g-1)\bigr)$ である。
要点：各マスは $g$ 本の「線」（prf-thm-ls-plane の $\ell_{k,s}$ のうち使う $g$ 種類）にちょうど 1 本ずつ乗り、種類の異なる線はちょうど 1 マスで交わる。
証明を開く
使う $g$ 種類の線の族を $\mathcal{K}'$ とする。prf-thm-ls-plane と同じ理由で、各種類の線はマスの分割で各線は $n$ マス、種類の異なる 2 本はちょうど 1 マスを共有し、異なる 2 マスを含む線は高々 1 本である。2 マスが隣接することは、ある線を共有することである。
次数：マス $x$ を通る $g$ 本の線は $x$ 以外に共有マスをもたないので、隣接するマスは $g(n-1)$ 個である。
$\lambda$：$x,y$ が線 $\ell$（種類 $k$）を共有するとき、共通の隣接マスは $\ell$ 上の他の $n-2$ マスと、$\ell$ の外にあるものである。後者 $z$ は $x$ を通る種類 $a$ の線と $y$ を通る種類 $b$ の線の交点で、$a,b\ne k$ である（$z\notin\ell$ で、$x,z$ を含む線はただ 1 本）。$a=b$ なら、$x$ を通る線と $y$ を通る線は同じ種類で異なる（同じなら $x,y$ が 2 本の線を共有する）ので交わらない。$a\ne b$ なら交点はちょうど 1 つで、それは $x,y$ でも $\ell$ 上でもない（$\ell$ 上なら $x$ とその点が 2 本の線を共有する）。$z$ から $(a,b)$ は決まるので、こうしたマスは $(g-1)(g-2)$ 個で、$\lambda=n-2+(g-1)(g-2)$ である。
$\mu$：$x\ne y$ が隣接しないとき、共通の隣接マスは $x$ を通る種類 $a$ の線と $y$ を通る種類 $b$ の線（$a\ne b$）の交点で、上と同じ理由で $(a,b)$ ごとに 1 つずつ異なり、$x,y$ とは異なる。よって $\mu=g(g-1)$ である。
$g\le n$ なので次数 $g(n-1)$ は $n^2-1$ より小さく、グラフは完全グラフでも辺のないグラフでもない。$\square$
$g=2$ のグラフは $n\times n$ の盤の上で同じ行か列にあるマスを結んだもので、$g=3$ のグラフを ラテン方陣グラフ という。$n=3$、$g=3$ では $\mathrm{srg}(9,6,3,6)$ である。パラメータは BH11 §9.1.12（p. 121）と一致する。
反例
各行は、上の定理の仮定を 1 つだけ外したものである。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| $q$ が素数冪（thm-ls-field） | $n=6$ | $N(n)=n-1$ |
| 係数が体（thm-ls-field） | $\mathbb{Z}/4\mathbb{Z}$ で $L(x,y)=2x+y$ | $L$ がラテン方陣 |
| $a\ne0$（thm-ls-field） | $a=0$ の $L(x,y)=y$ | $L$ がラテン方陣 |
| $n\not\equiv2\pmod4$（cor-ls-macneish） | $n=2$ | 直交する対がある |
各行の確認を開く
1 行目：rem-ls-bsp のとおり位数 $6$ の直交する対はなく $N(6)=1\ne5$ である（この記事では証明しない事実による）。$6$ は素数冪でない。
2 行目：$x=0$ と $x=2$ の行はどちらも $(0,1,2,3)$ になり、各列に同じ記号が 2 回現れる。$\mathbb{Z}/4\mathbb{Z}$ では $2$ が可逆でないので、prf-thm-ls-field の $a^{-1}$ がとれない。係数 $2\ne0$ なので、外れているのは体であることだけである。
3 行目：$a=0$ のとき $L(x,y)=y$ は各列が定数なので、列方向に全単射でない。
4 行目：$n=2\ge2$ で、外れているのは $n\not\equiv2\pmod4$ だけである。ex-ls-order23 の 3 により直交する対はない。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
