アソシエーションスキーム
概要
アソシエーションスキーム（association scheme）とは、有限集合 $X$ の元の対の全体を、対角とそれ以外のいくつかの対称な関係 $R_0,\dots,R_d$ に分け、$(x,y)\in R_k$ のとき $(x,z)\in R_i$ かつ $(z,y)\in R_j$ となる $z$ の個数が $i,j,k$ だけで決まるようにしたものである。強正則グラフ、距離正則グラフ、Hamming スキーム、Johnson スキームが例である。関係の隣接行列は、行列の積と成分ごとの積について閉じた可換な代数（Bose–Mesner 代数）を張り、互いに直交する冪等行列の基底をもつ。2 つの基底を結ぶ固有値行列から、部分集合の大きさの上界を与える Delsarte の線形計画限界が得られる。
アソシエーションスキーム（association scheme）とは、有限集合 $X$ の元の対を、いくつかの「関係」に分け、2 つの元を経由する元の数え方が関係の種類だけで決まるようにしたものである。強正則グラフ（関係が「隣接」と「非隣接」の 2 種類）や 距離正則グラフ（関係が「距離 $i$」）を一般化した対象である。定義は Bose と Shimamoto により、隣接行列の代数は Bose と Mesner が調べ、Delsarte はこれを部分構造の大きさの上界に応用した（BH11 pp. 163–166）。
関係ごとの隣接行列が張る空間は、行列の積についても成分ごとの積についても閉じた可換な代数になる（Bose–Mesner 代数）。この代数は互いに直交する冪等行列の基底をもち、2 つの基底を結ぶ行列（固有値行列）がスキームの固有値と重複度をまとめて記録する。これを使うと、部分集合の大きさに線形計画法で上界を与えられる（Delsarte の線形計画限界）。
この記事では、Bose–Mesner 代数の構造、固有値行列の直交関係、Delsarte の線形計画限界、群作用と距離正則グラフからスキームが得られることを完全に証明する。
定義
有限集合 $X$ と、$X\times X$ の空でない部分集合 $R_0,R_1,\dots,R_d$ の組が $d$ クラスのアソシエーションスキーム であるとは、次をみたすことをいう。
- $R_0,\dots,R_d$ は $X\times X$ の分割である。
- $R_0=\{(x,x):x\in X\}$ である。
- 各 $i$ について、$(x,y)\in R_i$ なら $(y,x)\in R_i$ である。
- 各 $i,j,k$ について、$(x,y)\in R_k$ のとき
$$ p^k_{ij}:=\#\{z\in X:(x,z)\in R_i,\ (z,y)\in R_j\} $$
は $(x,y)\in R_k$ の選び方によらない。
$p^k_{ij}$ を 交差数 という。$n:=\lvert X\rvert$、$n_i:=p^0_{ii}$ とおく。$n_i$ は $x$ と関係 $R_i$ にある元の個数で、$x$ によらない。この定義は Bose と Shimamoto によるもので、Delsarte の流儀では 対称 なアソシエーションスキームという。より一般には 3 を「各 $i$ に $R_i$ の転置がどれかの $R_j$ に等しい」に弱めたものも考え、さらに $p^k_{ij}=p^k_{ji}$ を課したものを 可換 なスキームという（BH11 p. 163）。この記事では対称なものだけを扱う。
$R_i$ の隣接行列 $A_i$（行と列を $X$ で添字づけ、$(x,y)\in R_i$ なら $(x,y)$ 成分が $1$、そうでなければ $0$）を使うと、条件は次のように書ける（$I$ は単位行列、$J$ はすべての成分が $1$ の行列）。
$$
\sum_{i=0}^dA_i=J,\qquad A_0=I,\qquad A_i^{\mathsf T}=A_i,\qquad A_iA_j=\sum_{k=0}^dp^k_{ij}A_k.
$$
最後の式は、$(A_iA_j)_{xy}$ が $(x,z)\in R_i$、$(z,y)\in R_j$ となる $z$ の個数であることと、$A_k$ の台が互いに交わらないことからわかる。各 $i\ge1$ について $(X,R_i)$ は $n_i$ 正則な単純グラフである。
- $p^k_{ij}=p^k_{ji}$。
- $\sum_{i=0}^dp^k_{ij}=n_j$、$\sum_{j=0}^dn_j=n$。
- $n_k\,p^k_{ij}=n_i\,p^i_{kj}$。
1． $(x,y)\in R_k$ とする。条件 3 から $(y,x)\in R_k$ なので、$p^k_{ij}=\#\{z:(y,z)\in R_i,\ (z,x)\in R_j\}$ である。関係はどれも対称なので、これは $\#\{z:(x,z)\in R_j,\ (z,y)\in R_i\}=p^k_{ji}$ に等しい。
2． $(x,y)\in R_k$ を固定する。$(z,y)\in R_j$ となる $z$ は $n_j$ 個で、各 $z$ について $(x,z)$ はただ 1 つの $R_i$ に入るので、$i$ について和をとると $n_j$ である。後半は、$x$ を固定して $X$ を $(x,z)$ の関係で分ければよい。
3． $(x,y)\in R_k$、$(x,z)\in R_i$、$(z,y)\in R_j$ をみたす $(x,y,z)$ の個数を 2 通りに数える。$(x,y)$ ごとに数えると $nn_kp^k_{ij}$ である。$(x,z)\in R_i$（$nn_i$ 組）ごとに、$(x,y)\in R_k$ かつ $(y,z)\in R_j$ となる $y$ の個数は $p^i_{kj}$ なので、$nn_ip^i_{kj}$ である。$\square$
例
- 2 クラスのスキーム：$\mathrm{srg}(v,k,\lambda,\mu)$ の隣接関係を $R_1$、隣接しない相異なる対を $R_2$ とすると 2 クラスのスキームで、$p^1_{11}=\lambda$、$p^2_{11}=\mu$ である。逆に 2 クラスのスキームでは、$(X,R_1)$ は $n_1$ 正則で、隣接する 2 頂点の共通の隣接頂点は $p^1_{11}$ 個、隣接しない 2 頂点では $p^2_{11}$ 個で、$R_1,R_2$ は空でないので完全グラフでも辺のないグラフでもなく、強正則グラフである（BH11 p. 164）。$\mathrm{srg}$ からスキームが得られることは、prop-as-identities の 1・2 の数え上げを各 $(x,y)$ で行うと、残りの交差数が $p^k_{11}$ と $n_1,n_2$ で表されることによる。
- 距離正則グラフ：直径 $d$ の距離正則グラフで $R_i$ を「距離 $i$」とするとスキームになる（次の prop-as-drg）。
$\Gamma$ を直径 $d$ の距離正則グラフ、$R_i:=\{(x,y):d(x,y)=i\}$ とすると、$(X,R_0,\dots,R_d)$ は $d$ クラスのアソシエーションスキームである。
1〜3 は距離の性質から明らかで、$R_i$ は直径の定義により空でない。$A_i$ を距離 $i$ の行列、$A=A_1$ とし、$\mathcal{A}:=\operatorname{span}(A_0,\dots,A_d)$ とおく。距離正則グラフ の補題「三項漸化式」により $AA_i\in\mathcal{A}$ なので、$\mathcal{A}$ は左から $A$ を掛ける操作で閉じ、したがって任意の多項式 $f$ について $f(A)\mathcal{A}\subset\mathcal{A}$ である。同じ漸化式から $A_i=p_i(A)$ となる多項式 $p_i$ がある（同記事の補題のあとの注意）ので、$A_iA_j=p_i(A)A_j\in\mathcal{A}$ である。$A_iA_j=\sum_kc_kA_k$ と書くと、$A_k$ の台は互いに交わらないので、$(x,y)\in R_k$ のとき $(A_iA_j)_{xy}=c_k$ は $(x,y)$ によらない。これが条件 4 である。$\square$
群作用からも多くのスキームが得られる。有限群 $G$ が有限集合 $X$ に作用し、任意の $x,y\in X$ について $gx=y$、$gy=x$ となる $g\in G$ があるとき、作用は 寛大に推移的（generously transitive）であるという。とくに推移的である。
$G$ の $X$ への作用が寛大に推移的なら、$G$ の $X\times X$ への対角的な作用 $g(x,y)=(gx,gy)$ の軌道全体はアソシエーションスキームをなす。
軌道は $X\times X$ の分割である。作用は推移的なので、対角 $\{(x,x)\}$ は 1 つの軌道である（$(x,x)$ を $(y,y)$ に移すには $gx=y$ となる $g$ をとればよい）。$(x,y)$ と $(y,x)$ は、$gx=y$、$gy=x$ となる $g$ で移り合うので同じ軌道にあり、条件 3 が成り立つ。$(x,y)$ と $(x',y')$ が同じ軌道 $R_k$ にあり $g(x,y)=(x',y')$ とすると、$z\mapsto gz$ は $\{z:(x,z)\in R_i,(z,y)\in R_j\}$ から $\{z':(x',z')\in R_i,(z',y')\in R_j\}$ への全単射である（軌道は $G$ で保たれる）。よって条件 4 が成り立つ。$\square$
- Hamming スキーム $H(d,q)$：$F$ を $q$ 元集合（$q\ge2$）、$X=F^d$ とし、$R_i$ を「ちょうど $i$ 個の座標で異なる」（Hamming 距離 $i$）とする。座標の置換と、各座標ごとの $F$ の置換からなる群 $G$ を考える。$x,y$ について、$x_m\ne y_m$ の座標 $m$ で $x_m$ と $y_m$ を入れ替える置換をとれば $x,y$ が入れ替わるので、作用は寛大に推移的である。Hamming 距離の等しい 2 組 $(x,y)$、$(x',y')$ は、座標の置換で異なる座標の位置をそろえ、各座標の置換で値をそろえれば移り合い、$G$ は距離を保つので、軌道はちょうど $R_0,\dots,R_d$ である。よって $H(d,q)$ は $d$ クラスのスキームである。
- Johnson スキーム $J(v,k)$：$X$ を $v$ 元集合の $k$ 元部分集合の全体（$k\le v/2$）とし、$R_i$ を $\lvert A\cap B\rvert=k-i$（$0\le i\le k$）とする。対称群 $S_v$ の作用は、$A\setminus B$ と $B\setminus A$ の元を 1 対 1 に入れ替える置換で $A,B$ を交換するので寛大に推移的で、同様に軌道は交わりの大きさで決まる。よって $J(v,k)$ は $k$ クラスのスキームである。$J(v,2)$ の $R_1$ は三角グラフである。
主定理：Bose–Mesner 代数
以下、$(X,R_0,\dots,R_d)$ を $d$ クラスのアソシエーションスキームとし、$\mathcal{A}:=\operatorname{span}_{\mathbb{R}}(A_0,\dots,A_d)$ とおく。行列 $M,N$ の成分ごとの積（Hadamard 積）を $M\circ N$ と書く。
- $\mathcal{A}$ は $d+1$ 次元で、$I$ と $J$ を含み、行列の積について閉じた可換な代数である。$\mathcal{A}$ の元は対称行列である。
- $\mathcal{A}$ は Hadamard 積についても閉じ、$A_i\circ A_j=\delta_{ij}A_i$ である。
- $\mathcal{A}$ の基底 $E_0,\dots,E_d$ で、$E_iE_j=\delta_{ij}E_i$、$\sum_iE_i=I$、$E_0=\tfrac1nJ$ となるものがある。各 $E_i$ は $\mathbb{R}^X$ のある部分空間 $V_i$ への直交射影で、$\mathbb{R}^X=V_0\oplus\dots\oplus V_d$ は直交直和、$V_0$ は $\mathbf{1}$（すべての成分が $1$ のベクトル）で張られる。この基底は順序を除いて一意である。
1． $A_i$ は空でない互いに交わらない台をもつ $0,1$ 行列なので線形独立で、$\dim\mathcal{A}=d+1$ である。$I=A_0$、$J=\sum_iA_i$ である。$A_iA_j=\sum_kp^k_{ij}A_k\in\mathcal{A}$ なので積で閉じ、prop-as-identities の 1 から $A_iA_j=A_jA_i$ である。$A_i$ は対称なので、その線形結合も対称である。
2． 台が交わらないことから $A_i\circ A_j=\delta_{ij}A_i$ で、双線形性により $\mathcal{A}$ は Hadamard 積で閉じる。
3． 同時固有空間。 実数の組 $\lambda=(\lambda_0,\dots,\lambda_d)$ について $V_\lambda:=\{v\in\mathbb{R}^X:A_iv=\lambda_iv\ (\forall i)\}$ とおき、$V_\lambda\ne0$ となる $\lambda$ の集合を $\Lambda$ とする。可換な実対称行列 $A_0,\dots,A_d$ について、$\mathbb{R}^X=\bigoplus_{\lambda\in\Lambda}V_\lambda$（直交直和）であることを、行列の個数についての帰納法で示す。$A_0,\dots,A_{m-1}$ の同時固有空間 $W$ は、$A_m$ と可換なので $A_m$ で保たれ、$A_m$ の $W$ への制限は対称なので、スペクトル定理 により $W$ は $A_m$ の固有空間の直交直和に分かれる。異なる $\lambda$ の $V_\lambda$ は、ある $A_i$ の異なる固有値の固有空間に含まれるので直交する。
射影が $\mathcal{A}$ に入ること。 $E_\lambda$ を $V_\lambda$ への直交射影とする。$\lambda\ne\mu$ ($\lambda,\mu\in\Lambda$) について $\lambda_{i}\ne\mu_{i}$ となる添字 $i=i(\lambda,\mu)$ を 1 つ選び、
$$
F_\lambda:=\prod_{\mu\in\Lambda,\ \mu\ne\lambda}\frac{A_{i(\lambda,\mu)}-\mu_{i(\lambda,\mu)}I}{\lambda_{i(\lambda,\mu)}-\mu_{i(\lambda,\mu)}}
$$
とおくと、$F_\lambda\in\mathcal{A}$（1 により $\mathcal{A}$ は積で閉じ $I$ を含む）で、$F_\lambda$ は $V_\lambda$ の上で $1$、$V_\nu$（$\nu\ne\lambda$）の上で $0$（$\mu=\nu$ の因子が $0$）である。よって $F_\lambda=E_\lambda\in\mathcal{A}$ である。
個数。 $E_\lambda$（$\lambda\in\Lambda$）は互いに直交する $0$ でない射影なので線形独立である。$M\in\mathcal{A}$ は各 $V_\lambda$ の上でスカラー $M_\lambda$ 倍なので $M=\sum_\lambda M_\lambda E_\lambda$ で、$E_\lambda$ は $\mathcal{A}$ を張る。よって $\lvert\Lambda\rvert=d+1$ で、番号を付けて $E_0,\dots,E_d$ とする。$E_iE_j=\delta_{ij}E_i$、$\sum E_i=I$ は直交直和から従う。
$E_0$。 $A_i\mathbf{1}=n_i\mathbf{1}$ なので $\mathbf{1}$ はある $V_\lambda$ に入る。その $V_\lambda$ の元 $v$ は $Jv=\sum_iA_iv=(\sum_in_i)v=nv$ をみたし、$Jv$ は $\mathbf{1}$ の定数倍なので、$V_\lambda=\mathbb{R}\mathbf{1}$ である。この射影は $\tfrac1nJ$ である。
一意性。 $F_0,\dots,F_d$ が同じ性質の基底なら、各 $F_j=\sum_ic_{ij}E_i$ で $F_j^2=F_j$ から $c_{ij}\in\{0,1\}$ である。$F_jF_{j'}=0$（$j\ne j'$）と $\sum_jF_j=I$ から、各 $i$ について $c_{ij}=1$ となる $j$ はちょうど 1 つで、$d+1$ 個の $F_j$ がどれも $0$ でないので、$j\mapsto\{i:c_{ij}=1\}$ は 1 元集合への全単射である。$\square$
$\mathcal{A}$ を Bose–Mesner 代数、$E_0,\dots,E_d$ を 原始冪等元 という（BH11 §11.2、pp. 164–165）。$m_i:=\operatorname{rank}E_i=\dim V_i$ を 重複度 という。2 つの基底を
$$
A_j=\sum_{i=0}^dP_{ij}E_i,\qquad E_j=\frac1n\sum_{i=0}^dQ_{ij}A_i
$$
で結ぶ $(d+1)$ 次正方行列 $P$、$Q$ を 固有値行列（第 1・第 2 固有値行列）という。$A_jE_i=P_{ij}E_i$ なので、$P_{ij}$ は $A_j$ の $V_i$ での固有値である。一方の式を他方に代入して $A_0,\dots,A_d$ の線形独立性を使うと $QP=nI$ を得て、正方行列なので $PQ=nI$ でもある。$A_0=I$ から $P_{i0}=1$、$A_j\mathbf{1}=n_j\mathbf{1}$ と $V_0=\mathbb{R}\mathbf{1}$ から $P_{0j}=n_j$ である。$E_j$ の対角成分は $A_0$ の係数 $\frac1nQ_{0j}$ だけから来るので、$m_j=\operatorname{tr}E_j=Q_{0j}$ である。
- $\displaystyle\sum_{i=0}^dm_iP_{ij}P_{ik}=n\,n_j\,\delta_{jk}$。
- $m_iP_{ij}=n_jQ_{ji}$。
1． $A_jA_k=\sum_iP_{ij}P_{ik}E_i$ で $\operatorname{tr}E_i=m_i$ なので、$\operatorname{tr}(A_jA_k)=\sum_im_iP_{ij}P_{ik}$ である。一方、$A_k$ は対称なので $\operatorname{tr}(A_jA_k)=\sum_{x,y}(A_j)_{xy}(A_k)_{xy}$ は、$j=k$ なら $\lvert R_j\rvert=nn_j$、$j\ne k$ なら $0$ である。
2． $\operatorname{tr}(A_jE_i)=P_{ij}m_i$ である。一方 $E_i=\frac1n\sum_lQ_{li}A_l$ と 1 の計算から $\operatorname{tr}(A_jE_i)=\frac1n\sum_lQ_{li}\operatorname{tr}(A_jA_l)=\frac1nQ_{ji}\,nn_j=n_jQ_{ji}$ である。$\square$
$X=\{0,1\}^3$（$n=8$）、$R_i$ を Hamming 距離 $i$ とする。$A_1$ は立方体の隣接行列で、固有値は $3,1,-1,-3$、重複度は $1,3,3,1$ である。各固有空間での $A_0,\dots,A_3$ の固有値を並べると
$$
P=\begin{pmatrix}1&3&3&1\\1&1&-1&-1\\1&-1&-1&1\\1&-3&3&-1\end{pmatrix}
$$
で（行は $A_1$ の固有値 $3,1,-1,-3$ の順）、$P^2=8I$ なので $Q=8P^{-1}=P$ である。たとえば prop-as-orthogonality の 1 で $j=k=1$ とすると $1\cdot9+3\cdot1+3\cdot1+1\cdot9=24=8\cdot3$ である。
Delsarte の線形計画限界
空でない部分集合 $Y\subset X$ について、$a_i:=\lvert(Y\times Y)\cap R_i\rvert/\lvert Y\rvert$ を $Y$ の 内部分布 という。$a_i$ は $Y$ の元 1 つあたり、それと関係 $R_i$ にある $Y$ の元の平均個数で、$a_0=1$、$\sum_ia_i=\lvert Y\rvert$ である。
空でない $Y\subset X$ の内部分布 $a=(a_0,\dots,a_d)$ は、すべての $j$ について
$$
\sum_{i=0}^da_iQ_{ij}\ \ge\ 0
$$
をみたす。
$\chi\in\mathbb{R}^X$ を $Y$ の特性ベクトルとすると、$\chi^{\mathsf T}A_i\chi$ は $(x,y)\in(Y\times Y)\cap R_i$ の個数なので $\lvert Y\rvert a_i$ である。よって
$$
\lvert Y\rvert\sum_ia_iQ_{ij}=\sum_iQ_{ij}\,\chi^{\mathsf T}A_i\chi=n\,\chi^{\mathsf T}E_j\chi=n\,\| E_j\chi\|^2\ge0
$$
である（$E_j$ は直交射影なので $E_j^{\mathsf T}=E_j=E_j^2$）。$\square$
これは BH11 Theorem 11.3.1（p. 166）である。$Y$ に課す条件（たとえば「関係 $R_1$ にある 2 元を含まない」なら $a_1=0$）と合わせて、$\sum_ia_i=\lvert Y\rvert$ を最大にする線形計画問題を解くと、$\lvert Y\rvert$ の上界が得られる。
$H(3,2)$ で、どの 2 元も Hamming 距離が $2$ 以上の $Y$（最小距離 $2$ の符号）を考える。$a=(1,0,a_2,a_3)$ で、ex-as-h32 の $Q=P$ の第 1 列から
$$
\sum_ia_iQ_{i1}=3-a_2-3a_3\ge0
$$
である。$a_3\ge0$ なので $a_2+a_3\le3-2a_3\le3$、すなわち $\lvert Y\rvert=1+a_2+a_3\le4$ である。偶数個の $1$ をもつ 4 元 $\{000,011,101,110\}$ はどの 2 元も距離 $2$ なので、上界 $4$ は達成される。この $Y$ では $a=(1,0,3,0)$、$aQ=(4,0,0,4)$ である。
Krein 条件と多項式スキーム
$\mathcal{A}$ は Hadamard 積でも閉じるので、$E_i\circ E_j=\frac1n\sum_kq^k_{ij}E_k$ と展開できる。係数 $q^k_{ij}$ を Krein パラメータ という。交差数 $p^k_{ij}$ が非負の整数であるのと対照的に、$q^k_{ij}$ は一般に整数ではないが、負にはならない（Scott による Krein 条件。BH11 Theorem 11.4.2、p. 168。この記事では証明しない）。Krein 条件と、重複度 $m_i$ が整数であること（有理性条件、同 p. 166）は、与えられた交差数をもつスキームが存在しないことを示すのに使われる。
関係に順序を付けて、$i,j,k$ のどれか 1 つが残り 2 つの和より大きいとき $p^k_{ij}=0$ で、$k=i+j$ のとき $p^k_{ij}>0$ となるなら、スキームは 計量的（metric）であるという。計量的なスキームは本質的に距離正則グラフと同じものである（BH11 p. 170、Chapter 12 の冒頭 p. 173）。Delsarte は、スキームが計量的であることと、$P_{ik}=f_k(P_{i1})$ となる $k$ 次多項式 $f_k$ がある（$P$ 多項式的）ことが同値であることを示した（BH11 Theorem 11.6.1、p. 170）。$Q$ について同じ性質をもつものを $Q$ 多項式的 という。Hamming スキームは計量的である。グラフ $(X,R_1)$ では 1 歩で 1 つの座標だけを変えられるので、グラフの距離が Hamming 距離に等しく、prop-as-drg の形のスキームになり、三角不等式から $i,j,k$ のどれかが残り 2 つの和より大きいとき $p^k_{ij}=0$、距離 $i+j$ の 2 点の間には最短路の途中に両方から距離 $i$・$j$ の点があるので $p^{i+j}_{ij}>0$ となるからである。
反例
各行は、上の定義・命題の条件を 1 つだけ外したものである。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 交差数が一定（定義の 4） | 3 頂点の道 $1-2-3$ で $R_1$＝辺、$R_2$＝隣接しない相異なる対 | $\operatorname{span}(A_0,A_1,A_2)$ が積で閉じる |
| 関係が対称（定義の 3） | $\mathbb{Z}/3\mathbb{Z}$ で $R_1=\{(x,x+1)\}$、$R_2=\{(x,x+2)\}$ | $\mathcal{A}$ の元が対称で、固有値が実数 |
| 寛大に推移的（prop-as-orbital） | $\mathbb{Z}/3\mathbb{Z}$ の自分自身への平行移動の作用 | 軌道が（対称な）スキームをなす |
各行の確認を開く
1 行目：関係 1〜3 は成り立つ。$A_1^2$ の対角成分は頂点の次数 $1,2,1$ で、$R_0$ の上で一定でないので、$A_1^2$ は $A_0,A_1,A_2$ の線形結合でない（$p^0_{11}$ が定まらない）。
2 行目：$(x,y)\in R_k$ ごとの数え上げは一定で（$A_1A_1=A_2$、$A_1A_2=A_0$ など）、条件 1・2・4 は成り立つが、$A_1$ は巡回置換行列で対称でなく、固有値は $1$ の 3 乗根 $1,\omega,\omega^2$（$\omega=e^{2\pi i/3}$）で実数でないものを含む。
3 行目：作用は推移的だが、$(0,1)$ を $(1,0)$ に移す平行移動はないので寛大に推移的でない。$X\times X$ の軌道は 2 行目の $R_0,R_1,R_2$ で、$R_1$ は対称でない。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
