ラテン方陣 | 直交を置換群の置換を使って考える【直交する最大個数を上から評価】

2023年9月4日

n次の " ラテン方陣 “に、n次の「置換群」を作用させることを通し、n次の直交ラテン方陣の最大個数を評価します。

この図のように、n 次のラテン方陣は、異なる n 個の文字を、1 つの文字につき n 個使い、各行各列に重複がないように n 次正方行列に配置したものです。

この n 次のラテン方陣の各成分の値を、n 次の置換群（対称群）で置換することを考えます。

A が n 次のラテン方陣、σが n 次の置換群 S_n の元のとき、
σ(A) = (σ(a_ij)) と定義します。

σ(A) は n 次の正方行列ですが、ラテン方陣であることを確認するために、各行各列に重複がないかを確認します。

上の例だと、A の 1 行目、2 行目、3 行目に 3 が 1 つずつ配置されています。

σ(A) の各行には、3 の σ による像 1 が 1 つずつ配置されています。

σ は単射なので、これ以上の 1 は σ(A) には出てきません。

σ(A) について、他の数字 2 も各行に 1 個ずつ 合計 3 個、3 も各行に 1 個ずつ合計 3 個です。

{1, … , n} = X とし、X の各元につき、n 個を n 次正方行列に各行各列に重複なく配置をします。X 上の置換群 S_n は、X から X への全単射全体で、写像の合成を積としています。

ラテン方陣 :作用が定義できるか確認

A が n 次のラテン方陣のとき、e を S_n の恒等置換とすると、
e(A) = (e(a_ij)) = (a_ij) = A なので、
e(A) はラテン方陣となっています。

任意の f, g∈S_n に対して、
(fg)(A) = (f(g(a_ij))) = f(g(A)) が、合成写像の定義から成立しています。

ただ、f(A) が、ラテン方陣となっているのかを確認しておく必要があります。

f(A) の定義から、k∈X について、A の各行に k が 1 個だけ配置されています。

k₁, k₂∈X を異なる元とすると、
k₁ と k₂ は、各行に 1 個ずつ配置されています。

つまり、1 ≦ i ≦ n のとき、
A の i 行目に k₁ と k₂ が 1 個ずつ配置されています。

f は単射なので、
f(k₁) ≠ f(k₂) です。

そのため、f(A) の i 行目には、
f(k₁) と f(k₂) が 1 個ずつ配置されています。

したがって、f が全単射なので、
f(k)∈f(X) = X が、f(A) の各行に 1 個だけ配置されていることになります。

各行について見ると、f(k₁) ≠ f(k₂) だったので、重複はありません。

各行について見ましたが、各列についても同様に重複がないことが確認できます。

t₁, t₂∈X が t₁ ≠ t₂ のとき、
j 列には、t₁ と t₂ が、それぞれ 1 個ずつ配置されています。
（1 ≦ j ≦ n です。）

f は単射なので、
f(t₁) ≠ f(t₂) です。

f(A) の定義から、
f(A) の j 列に、f(t₁), f(t₂) が、それぞれ 1 個ずつ配置されています。

そのため、f(A) には、f(X) = X の各数字、一つの数字につき n 個を使って、重複なく n² 個の成分の位置に配置されています。

作用の定義を確認

Ω を X の元を配置した n 次のラテン方陣全体とします。

先ほどの考察から、任意の f∈S_n, A∈Ω に対して、
f(A)∈Ω となっています。

可解群の群準同型像も可解群というように、n 次ラテン方陣の n 次の置換による像は n 次ラテン方陣と覚えやすい結果となっています。

そのため、
(f, A)∈S_n×Ω に対して、
f(A)∈Ω が対応しています。

そして、e∈S_n について e(A) = A でした。

合成置換の定義から、
f, g∈Sn に対して、
(fg)(A) = f(g(A)) となっています。

これで、n 次の置換群（対称群）S_n が、n 次のラテン方陣全体 Ω に作用していることが分かりました。

ラテン方陣 :直交と置換作用について

【直交の定義】

A, B∈Ω を n 次のラテン方陣とします。

A = (a_ij), B = (b_ij) に対して、
1 以上 n 以下の自然数 s, t について、
(a_st, b_st) を A と B の (s, t) 成分同士の組という言い方をすることにします。

これら n² 個の成分同士の組が、どの二つも相異なるときに、n 次ラテン方陣 A と B が直交しているといいます。

A と B が直交していないということは、
ある 1 以上 n 以下の自然数 p, q, r, s が存在して、
(p, q) ≠ (r, s) だけれでも、
(a_pq, b_pq) = (a_rs, b_rs) ということになります。

(p, q) ≠ (r, s) だけれでも、
A と B の (p, q) 成分同士の組と、
(r, s) 成分同士の組が一致してしまっているときに、直交ではないということです。

n = 2 のときは、2 次のラテン方陣が直交しないことを見てみます。

2次のラテン方陣は直交しない

X = {1, 2} を 2 次正方行列の位置に配置してラテン方陣を考えます。

(1, 1) 成分に 1 を配置すると、ラテン方陣の定義から、
(1, 2) 成分は 2 です。

列についても共通の数字が表れないため、
(2, 1) 成分は 2 となります。

残りの (2, 2) 成分は、2 行目と 2 列目に同じ数字が配置できないために、1 となります。

この 2 次ラテン方陣を A とします。

今度は、(1, 1) 成分に 2 を配置する場合を考えます。

(1, 2) 成分と (2, 1) 成分は 1 となり、
(2, 2) 成分は 2 となります。

このラテン方陣を B とします。

A と B について、
(1, 1) 成分同士の組は (1, 2),
(1, 2) 成分同士の組は (2, 1),
(2, 1) 成分同士の組は (2, 1),
(2, 2) 成分同士の組は (1, 2) となります。

2² 個の成分同士の組について、重複が起きているので、二つのラテン方陣は直交していません。

B と A で考えても、やはり B と A は直交していません。

よって、n = 2 のとき、2 次のラテン方陣で直交するものは存在しません。

ここで、自然な命題が考えられます。

A, B∈Ω が直交であるとき、任意の f, g∈S_n に対して、
f(A) と f(B) は直交しているのかということです。

f(A), f(B)∈Ω ということは、既に確かめましたが、直交しているという関係を保存することをこれから説明します。

直交するラテン方陣を置換すると

【命題】

n 次のラテン方陣を
A = (a_ij), B = (b_ij) とし、
f と g を任意の S_n の置換とする。

このとき、f(A) と f(B) は直交するラテン方陣である。

＜証明＞

上で確認したように、
f(A) と g(B) は n 次のラテン方陣です。

仮定より、A と B の n² 個の成分同士の組は、どの二つも重複していません。

この状況で、背理法を用いて、f(A) と g(B) が直交していることを示します。

f(A) と g(B) が直交していないと仮定します。

すると、1 以上 n 以下の自然数 p, q, r, s が存在して、
(p, q) ≠ (r, s) だけれでも、
(f(a_pq), g(b_pq)) = (f(a_rs), g(b_rs)) となります。

つまり、
f(a_pq) = f(a_rs), g(b_pq) = g(b_rs) となっています。

f^-1, g^-1∈S_n で、
f(a_pq), g(b_pq, f(a_rs), g(b_rs) は 1 以上 n 以下の自然数なのです。

そのため、逆置換で移すと、
a_pq = a_rs, b_pq = b_rs となります。

ゆえに、A と B の (p, q) 成分同士の組である
(a_pq, b_pq) と、A と B の (r, s) 成分同士の組である (a_rs, b_rs) について、
(a_pq, b_pq) = (a_rs, b_rs) ということです。

これは、A と B の n² 個の成分同士の組は、どの二つも重複していないことに矛盾です。

よって、背理法より、
f(A) と g(B) は直交しています。 ■

ここまでの内容を踏まえて、三つ以上の n 次のラテン方陣についての直交について考えます。

A₁, A₂, … , A_r と n 次のラテン方陣が r 個あったとします。

これらが全て相異なるとき、r 個のラテン方陣が互いに直交しているといいます。

n が大きくなると、n 次のラテン方陣の個数は、とても多くなりますが、直交する n 次のラテン方陣の個数は、必ずこの数以下ということを示します。

ラテン方陣 : n次の互いに直交する最大個数

【定理】

n を 2 以上の自然数とする。

n 次ラテン方陣の互いに直交する最大個数を r とする。

つまり、A₁, … , A_r を n 次ラテン方陣で互いに直交している r 個とする。（ただし、r が 0 個ということもある。）

このとき、r ≦ n－1 である。

＜証明＞

r = 0, 1 のときは、
1 ≦ n－1 と成立しているので、r が 2 以上の場合を考えます。

1 ≦ t ≦ r について、
A_t の (i, j) 成分を _ta_ij と表すことにします。

A_t の 1 行目について、
ラテン方陣なので、
_ta₁₁, _ta₁₂, … , _ta_1n は、相異なる n 個の自然数が並んでいます。

各 t について、次の f_t という写像は、S_n の元です。

このことから、
f₁(A₁), … , f_r(A_r) の 1 行目は、
1, 2, … , n と左から数字が並んでいることになります。

ここで、【命題】より、
f₁(A₁), … , f_r(A_r) は、どの二つも直交する n 次のラテン方陣です。

ここで、自然数 i, j を、
1 ≦ i < j ≦ r とします。

今、f_i(A_i), f_j(A_j) の 1 行目について、
(1, 1) 成分同士の組 (1, 1),
(1, 2) 成分同士の組 (2, 2),
・・・
(1, n) 成分同士の組 (n, n) … ★となっています。

f_i(A_i), f_j(A_j) の (1, 1) 成分の値は 1 なので、ラテン方陣だから、1 列目の 2 行目以降に 1 は現れません。

そのため、f_i(A_i), f_j(A_j) の (1, 2) 成分の値は、 1 以外ということになります。

ここで、f_i(A_i), f_j(A_j) の (1, 2) 成分の値が一致していると、次のように矛盾が発生します。

f_i(A_i), f_j(A_j) の (1, 2) 成分の値が m という n 以下の自然数とします。

すると、(1, 2) 成分同士の組が、
(m , m) となります。

しかし、★より、(m, m) は、
(1, m) 成分同士の組と一致します。

これは、f_i(A_i) と f_j(A_j) が直交していることに矛盾です。

このことから、
f_i(A_i), f_j(A_j) の (1, 2) 成分の値は異なるということになります。

以上より、
f₁(A₁), … , f_r(A_r) の (1, 2) 成分には、2 以上 n 以下の相異なる r 個の値が現れています。

2 以上 n 以下の範囲にある自然数は n－1 個なので、
r ≦ n－1 です。 ■

これで、n 次ラテン方陣の最大個数を上から評価することがあります。

n = 2 のときは、上で確認したように、最大個数が 0 です。

ここまで、ほぼ集合論の入門内容で議論を進めることができましたが、この【定理】の等号が成立するのかどうかということや、直交する最大個数が 0 となる n は存在するのかといった内容になると、難しい問題となります。

36士官問題

実は、あの有名なオイラーが提示した 36士官問題というものがありました。

簡単に内容を述べると、
6 次ラテン方陣で直交することは起こり得ないという予想でした。

この内容は、確か 1900年くらいに、存在しないことが証明されました。

さすが天才オイラーに関連する内容です。

n = 2 だと手書きですぐに解決ですが、6 次となると人の手で書き出すというわけにもいきません。

時が流れて 20 世紀以降の数学の研究となると、先ほどの【定理】で等号が成立するのはどんなときかといったレベルになります。

さすがに、こういう内容は代数学入門の内容を超えるので、このあたりで今回の記事を終了することにします。

ちなみに、オイラーの多面体定理のついでに、
正十二面体と正二十面体の頂点の置換について、一つ前の記事で解説しています。

また、複素指数関数という記事で、オイラーの公式について説明をしています。

これで今回の記事を終了します。

読んで頂き、ありがとうございました。