2
大学数学基礎解説
文献あり

Steinerシステム - Fisher不等式

147
0
$$$$

  1. Fisher不等式

  2. 自己同型群

  3. アフィン平面

  4. Steinerトリプルシステム

    1. STSの直積


  5. Mathieu群 $M_{11}$$M_{12}$

    1. S(2,3,9)の性質

    2. S(3,4,10)の構成


構成したSteinerシステム

(2,3,7)NEW

シュタイナーシステム, フィッシャー不等式, ファノ平面

定義

Steinerシステム

$v$点集合$\Omega=\lbrace\alpha_1,\alpha_2,\cdots,\alpha_v\rbrace$とその部分集合族$\mathcal{B}=\lbrace B_1,B_2,\cdots,B_b\rbrace$の組$(\Omega,\mathcal{B})$であって, 条件

  • 任意の$1\leq i\leq b$に対して, $|B_i|=k$
  • $\Omega$の任意の$t$$\alpha_{p_1},\alpha_{p_2},\cdots,\alpha_{p_t}$を取ったとき, $\alpha_{p_1},\alpha_{p_2},\cdots,\alpha_{p_t}\in B_i$となる$B_i\in\mathcal{B}$が存在して一意

を満たすものをSteinerシステムと呼び, $S(t,k,v)=S(\Omega,\mathcal{B})$のように表記する.
$\mathcal{B}$の元をブロックといい, 以下では$0< t< k< v$を仮定する.

 すぐに明らかになることだが, Steinerシステムに関するいくつかのパラメータは$t,k,v$によって表されるため, この3組を明示する.


 定義に従って$F=S(\Omega,\mathcal{B})=S(2,3,7)$を構成する.

構成法1.

 $\Omega=\lbrace 1,2,3,4,5,6,7\rbrace$として, 起点となる3つ組を$(1,2,3)$とする. $(1,n)$の組を網羅するために, $(1,4,7)$$(1,5,6)$を取る. 次に$(2,n)$の組を入れるために, $4,5,6,7$の組み合わせが重複しないように$(2,4,6),(2,5,7)$を取る. 同様にして$(3,4,5),(3,6,7)$を取れば,
\begin{eqnarray} \mathcal{B}=\lbrace(1,2,3),(1,4,7),(1,5,6),(2,4,6),(2,5,7),(3,4,5),(3,6,7)\rbrace \end{eqnarray}
と組み上げられる.

構成法2.

 $4,5,6,7$を2つの組に分ける方法は$\lbrace(4,7),(5,6)\rbrace,\hspace{3mm}\lbrace(4,6),(5,7)\rbrace,\hspace{3mm}\lbrace(4,5),(6,7)\rbrace$の3通り.
各々を$1,2,3$と組み合わせれば,
$(1,4,7),(1,5,6)$
$(2,4,6),(2,5,7)$
$(3,4,5),(3,6,7)$
となり, 最後に$(1,2,3)$を付け足せば同様の結果が得られる.

構成法3.

 $S(2,3,7)$の場合, Fano平面と呼ばれる図形で可視化ができる.
 
 線分も円も広義での直線と捉えれば, 直線がブロックを成していて, Steinerシステムの定義も満足していることが確認できる.
\begin{eqnarray} \mathcal{B}=\lbrace(1,2,3),(1,4,7),(1,5,6),(2,4,6),(2,5,7),(3,4,5),(3,6,7)\rbrace \end{eqnarray}

基本的な性質

 一般のSteinerシステムの性質をいくつか見た後, ブロックの個数$b$$t,k,v$の関係式を導く.

$\Omega$において, $\alpha$を含むような$t$元の選び方は$\begin{pmatrix}v-1\\t-1\end{pmatrix}$通り.
$\mathcal{B}$において, $\alpha$を含むブロックとして$B_i$を取る. $B_i$$k$個の元から$\alpha$を含むような$t$元の選び方は$\begin{pmatrix}k-1\\t-1\end{pmatrix}$通り.
いま, $\alpha$を含むブロックの個数を$r$としているのだから, $\alpha$を含む$t$元の選び方は$r\begin{pmatrix}k-1\\t-1\end{pmatrix}$通り.
したがって,
\begin{eqnarray} r\begin{pmatrix}k-1\\t-1\end{pmatrix}&=&\begin{pmatrix}k-1\\t-1\end{pmatrix}\\ \iff r&=&\frac{\begin{pmatrix}v-1\\t-1\end{pmatrix}}{\begin{pmatrix}k-1\\t-1\end{pmatrix}} \end{eqnarray}

 これは以下のように一般化できる.

$S=S(t,k,v)=S(\Omega,\mathcal{B})$をSteinerシステムとする. $1\leq i\leq t$として, $\Omega$のある$i$元部分集合を含むブロックの個数$\lambda_i$$\dfrac{\begin{pmatrix}v-i\\t-i\end{pmatrix}}{\begin{pmatrix}k-i\\t-i\end{pmatrix}}$.

定理1と同様.

$k< v$を仮定していたのだから,$\dfrac{v-1}{k-1}>1$.
辺々$\dfrac{(v-2)(v-3)\cdots(v-t+1)}{(k-2)(k-3)\cdots(k-t+1)}>0$を掛けて,
\begin{eqnarray} r&=&\frac{v-1}{k-1}\cdot\frac{(v-2)(v-3)\cdots(v-t+1)}{(k-2)(k-3)\cdots(k-t+1)}\\ &>&\frac{(v-2)(v-3)\cdots(v-t+1)}{(k-2)(k-3)\cdots(k-t+1)}\\ &=&\lambda_2 \end{eqnarray}

 ブロックの個数$b$$t,k,v$の関係式を導く.

$\alpha\in\Omega,B\in\mathcal{B}$として, $\alpha\in B$を満たすような組$(\alpha,B)$の個数$m$を求める.
[i] ブロックの選び方は$b$通り. ブロックの位数は$k$であるから, 選んだブロックに含まれている元の選び方は$k$通り.
したがって, $m=bk$.
[ii] $\Omega$の元の選び方は$v$通り. ある元を含むブロックの個数を$r$としたため, $m=vr$.
以上より,$bk=vr$.
$r=\dfrac{(v-1)(v-2)\cdots(v-t+1)}{(k-1)(k-2)\cdots(k-t+1)}$から,
\begin{eqnarray} b&=&\frac{vr}{k}\\ &=&\frac{v(v-1)(v-2)\cdots(v-t+1)}{k(k-1)(k-2)\cdots(k-t+1)}\\ &=&\frac{\begin{pmatrix}v\\t\end{pmatrix}}{\begin{pmatrix}k\\t\end{pmatrix}} \end{eqnarray}

Fisher不等式

 Steinerシステムの接続行列を導入する.

接続行列

$\Omega=\lbrace\alpha_1,\alpha_2,\cdots,\alpha_v\rbrace,\mathcal{B}=\lbrace B_1,B_2,\cdots,B_b\rbrace$$S=S(t,k,v)=S(\Omega,\mathcal{B})$をSteinerシステムとする. $S$接続行列とは, 各成分が
\begin{eqnarray} a_{ij}=\left\{\begin{array}{ll} 1 & \alpha_i\in B_j\hspace{2mm}(1\leq i\leq v,1\leq j\leq b)\\ 0 & {\rm otherwise} \end{array}\right.\end{eqnarray}
によって定義された行列$A=\begin{bmatrix}a_{ij}\end{bmatrix}$である.

 接続行列を利用すれば, ブロックデザインの基礎的な関係式であるFisher不等式を導出できる.

$S$の接続行列を$A$, $\Omega$のある元を含むブロックの個数を$r$, ある2元部分集合を含むブロックの個数を$\lambda_2$として, $v$次正方行列$AA^\top=\begin{bmatrix}b_{ij}\end{bmatrix}$を考える.
$AA^\top$は, $A$の行同士の内積を取っていると捉えられるため,
\begin{eqnarray} b_{ij}=\left\{\begin{array}{ll} r & i=j\\ \lambda_2 & i\neq j \end{array}\right.\end{eqnarray}
と書ける.
$AA^\top$の行列式に関して,
\begin{eqnarray} {\rm det}(AA^\top)&=&\begin{vmatrix}r&\lambda_2&\cdots&\lambda_2\\\lambda_2&r&\cdots&\lambda_2\\\vdots&\vdots&\ddots&\vdots\\\lambda_2&\lambda_2&\cdots&r\end{vmatrix}\\ &=&\begin{vmatrix}r+(v-1)\lambda_2&r+(v-1)\lambda_2&\cdots&r+(v-1)\lambda_2\\\lambda_2&r&\cdots&\lambda_2\\\vdots&\vdots&\ddots&\vdots\\\lambda_2&\lambda_2&\cdots&r\end{vmatrix}\\ &=&\begin{vmatrix}r+(v-1)\lambda_2&0&\cdots&0\\\lambda_2&r-\lambda_2&\cdots&0\\\vdots&\vdots&\ddots&\vdots\\\lambda_2&0&\cdots&r-\lambda_2\end{vmatrix}\\ &=&(r-\lambda_2)^{v-1}(r+(v-1)\lambda_2) \end{eqnarray}
$r>\lambda_2$から
\begin{eqnarray} r-\lambda_2&\neq&0\\ r+(v-1)\lambda_2=r-\lambda_2+v\lambda_2&\neq&0 \end{eqnarray}
よって,
\begin{eqnarray} {\rm det}(AA^\top)&\neq&0\\ \iff {\rm rank}(AA^\top)&=&v \end{eqnarray}
行列の階数は積によって広義に減少することから$v={\rm rank}(AA^\top)\leq{\rm rank}A$.
一方, $A$$v\times b$行列であるため, ${\rm rank}A\leq b$.
以上より$v\leq b$.

$bk=vr$から
\begin{eqnarray} v&<&b\\ vk&<&bk=vr\\ k&<&r\\ k+1&\leq&r=\frac{v-1}{k-1}\\ k^2&\leq&v \end{eqnarray}

とほぼ同様のため省略.

 $S(2,q+1,q^2+q+1)$の形をしたSteinerシステムのことを特に(有限)射影平面と呼び, $q$を位数という. Fano平面$S(2,3,7)$は位数が最小の射影平面である.

参考文献

[1]
R. C. Bose, A Note on Fisher's Inequality for Balanced Incomplete Block Designs, Annals of Mathematical Statistics, 1949, 619-620
投稿日:27日前
更新日:2日前
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

有限群論 好きな群は6次対称群

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中