協会制度

連想スキーム 理論は、統計学、分散分析のための実験計画理論において生まれた。[ 1 ] [ 2 ] [ 3 ]数学において、連想スキームは代数学と組合せ論の両方に属する。代数的組合せ論において、連想スキームは、例えば組合せ設計や誤り訂正符号の理論など、多くのトピックに対する統一的なアプローチを提供する。[ 4 ] [ 5 ]代数学において、連想スキーム理論は、群の線型表現の指標理論を一般化する。[ 6 ] [ 7 ] [ 8 ]

意味

nクラスの関連付けスキームは、集合Xと 、X × X を次の条件を満たすn + 1 個 のバイナリ関係R 0、R 1、 ...、R nに分割したパーティションSで構成されます。

  • R0＝{（×、×）:×∈X}{\displaystyle R_{0}=\{(x,x):x\in X\}}; これは恒等関係と呼ばれます。
  • を定義すると、R がSに含まれる場合、R* がSに含まれることになります。R∗:={（×、y）:（y、×）∈R}{\displaystyle R^{*}:=\{(x,y):(y,x)\in R\}}
  • の場合、および となるの数は、によって決まりますが、およびの特定の選択には依存しません。（×、y）∈Rけ{\displaystyle (x,y)\in R_{k}}z∈X{\displaystyle z\in X}（×、z）∈R私{\displaystyle (x,z)\in R_{i}}（z、y）∈Rj{\displaystyle (z,y)\in R_{j}}p私jけ{\displaystyle p_{ij}^{k}}私{\displaystyle i}j{\displaystyle j}け{\displaystyle k}×{\displaystyle x}y{\displaystyle y}

すべての、 、に対してが成り立つとき、関連スキームは可換である。多くの著者はこの性質を前提としている。ただし、関連スキームの概念は群の概念を一般化するのに対し、可換関連スキームの概念は可換群の概念のみを一般化する点に注意する必要がある。 p私jけ＝pj私け{\displaystyle p_{ij}^{k}=p_{ji}^{k}}私{\displaystyle i}j{\displaystyle j}け{\displaystyle k}

対称的な関連スキームとは、それぞれが対称的な関係にあるスキームです。つまり、 R私{\displaystyle R_{i}}

  • ( x , y ) ∈ R iならば、 ( y , x ) ∈ R iです。（あるいは、R * = Rと等価です。）

すべての対称的な関連付けスキームは可換です。

2点xとyは、 のi番目の関連付けと呼ばれます。定義によれば、xとyがi番目の関連付けであれば、とxもi番目の関連付けとなります。すべての点のペアは、ちょうど1つのに対してi番目の関連付けとなります。各点はそれ自身の0番目の関連付けとなりますが、異なる点が0番目の関連付けとなることはありません。xとyがk番目の関連付けである場合、のi番目の関連付けであり、かつ のj番目の関連付けでもある点の数は定数 です。 （×、y）∈R私{\displaystyle (x,y)\in R_{i}}私{\displaystyle i}z{\displaystyle z}×{\displaystyle x}y{\displaystyle y}p私jけ{\displaystyle p_{ij}^{k}}

グラフ解釈と隣接行列

対称的な関連スキームは、ラベル付きの辺を持つ完全グラフとして視覚化できます。グラフには、 の各点に1つずつ頂点があり、頂点 と を結ぶ辺は、と が番目の関連である場合にラベルが付けられます。各辺には一意のラベルが付けられ、固定底辺にラベルが付けられ、他の辺に と のラベルが付けられた三角形の数は定数 で、底辺の選択に依存しますが、選択には依存しません。特に、各頂点は のラベルが付けられた辺と正確に接続されます。は関係の原子価です。また、各頂点には に対応する のラベルが付けられたループがあります。 v{\displaystyle v}X{\displaystyle X}×{\displaystyle x}y{\displaystyle y}私{\displaystyle i}×{\displaystyle x}y{\displaystyle y}私{\displaystyle i}け{\displaystyle k}私{\displaystyle i}j{\displaystyle j}p私jけ{\displaystyle p_{ij}^{k}}私、j、け{\displaystyle i,j,k}p私私0＝v私{\displaystyle p_{ii}^{0}=v_{i}}私{\displaystyle i}v私{\displaystyle v_{i}}R私{\displaystyle R_{i}}0{\displaystyle 0}×{\displaystyle x}R0{\displaystyle R_{0}}

関係は、隣接行列によって記述されます。は、の隣接行列であり、 は、行と列が の点でラベル付けされたv × v行列です。 あ私{\displaystyle A_{i}}R私{\displaystyle R_{i}}私＝0、…、n{\displaystyle i=0,\ldots ,n}X{\displaystyle X}

（あ私）×、y＝{1、もし （×、y）∈R私、0、さもないと。（1）{\displaystyle \left(A_{i}\right)_{x,y}={\begin{cases}1,&{\mbox{if }}(x,y)\in R_{i},\\0,&{\mbox{otherwise.}}\end{cases}}\qquad (1)}

対称結合スキームの定義は、 v × v (0,1)行列が次の式を満たすとする ことと等しい。あ私{\displaystyle A_{i}}

I.対称的である、あ私{\displaystyle A_{i}}
II. （オールワンマトリックス）∑私＝0nあ私＝J{\displaystyle \sum _{i=0}^{n}A_{i}=J}
III. 、あ0＝私{\displaystyle A_{0}=I}
IV. .あ私あj＝∑け＝0np私jけあけ＝あjあ私、私、j＝0、…、n{\displaystyle A_{i}A_{j}=\sum _{k=0}^{n}p_{ij}^{k}A_{k}=A_{j}A_{i},i,j=0,\ldots ,n}

(IV) の左辺の( x , y ) 番目の要素は、グラフ中のラベルiとjを持つ、長さ 2 のxとy間のパスの数です。 の行と列には が含まれていることに注意してください。 あ私{\displaystyle A_{i}}v私{\displaystyle v_{i}}1{\displaystyle 1}

あ私J＝Jあ私＝v私J。（2）{\displaystyle A_{i}J=JA_{i}=v_{i}J.\qquad (2)}

用語

  • これらの数値は、スキームのパラメータと呼ばれます。また、構造定数とも呼ばれます。p私jけ{\displaystyle p_{ij}^{k}}

歴史

アソシエーション・スキームという用語は（ Bose & Shimamoto 1952 ）に由来するが、その概念は（Bose & Nair 1939）に既に存在していた。[ 9 ]これらの著者は、統計学者が部分的バランス型不完全ブロック設計（PBIBD）と呼ぶものを研究していた。このテーマは、（ Bose & Mesner 1959 ）の出版とボーズ・メスナー代数の導入によって代数的な関心の対象となった。この理論への最も重要な貢献は、符号理論と設計理論との関連性を認識し、それを十分に活用したデルサルト博士の論文（Delsarte 1973）であった。[ 10 ]

コヒーレント構成と呼ばれる一般化は、DG Higman によって研究されてきました。

基本的な事実

  • p000＝1{\displaystyle p_{00}^{0}=1}つまり、の場合、となり、 となる唯一の条件が満たされる。（×、y）∈R0{\displaystyle (x,y)\in R_{0}}×＝y{\displaystyle x=y}z{\displaystyle z}（×、z）∈R0{\displaystyle (x,z)\in R_{0}}z＝×{\displaystyle z=x}
  • ∑私＝0けp私私0＝|X|{\displaystyle \sum _{i=0}^{k}p_{ii}^{0}=|X|}; これはパーティションのためです。R私{\displaystyle R_{i}}X{\displaystyle X}

ボーズ・メスナー代数

グラフの隣接行列は、行列積とアダマール積（エントリワイズ）の両方に対して、実数または複素数上の可換かつ結合的な代数を生成する。行列積で形成される代数は、結合スキームの ボーズ・メスナー代数と呼ばれる。あ私{\displaystyle A_{i}}（X、R私）{\displaystyle \left(X,R_{i}\right)}あ{\displaystyle {\mathcal {A}}}

の行列は対称かつ互いに可換であるため、同時に対角化することができる。したがって、は半単純であり、原始冪等性の唯一の基底を持つ。 あ{\displaystyle {\mathcal {A}}}あ{\displaystyle {\mathcal {A}}}J0、…、Jn{\displaystyle J_{0},\ldots ,J_{n}}

に同型な別の行列代数が存在し、こちらの方が扱いやすい場合が多いです。 （n+1）×（n+1）{\displaystyle (n+1)\times (n+1)}あ{\displaystyle {\mathcal {A}}}

例

  • ジョンソンスキーム（ J ( v , k )と表記）は次のように定義される。Sをv個の要素を持つ集合とする。スキームJ ( v , k )の点は、 S のk個の要素を持つ部分集合である。S の 2 つのk個の要素を持つ部分集合A、Bは、それらの交差の大きさがk  −  iであるとき、i番目の関連である。（vけ）{\displaystyle {v \choose k}}
  • ハミング方式はH ( n , q )と表記され、以下のように定義されます。H ( n , q )の点は、サイズqの集合上のq n順序のn組です。2つのn組x、y は、 i番目の座標で一致しない場合、 i番目の対応関係にあると言われます。例えば、x = (1,0,1,1)、y = (1,1,1,1)、z = (0,0,1,1)の場合、 xとyはH (4,2)において1番目の対応関係、1番目の対応関係、yとzは2番目の対応関係になります。
  • 距離正規グラフGは、 2 つの頂点の距離がiである場合に、それらの頂点をi番目の関連点として定義することによって、関連スキームを形成します。
  • 有限群Gは 上の連想スキームを生成し、各群元に対してクラスR gが与えられます。これは次のように定義されます。各に対して、は群演算です。群単位元のクラスはR 0です。この連想スキームは、Gがアーベル である場合に限り、可換です。X＝G{\displaystyle X=G}グラム∈G{\displaystyle g\in G}Rグラム＝{（×、y）∣×＝グラム∗y}{\displaystyle R_{g}=\{(x,y)\mid x=g*y\}}∗{\displaystyle *}
  • 具体的な3クラス関連付けスキーム：[ 11 ]
A (3)を、集合X = {1,2,3,4,5,6} 上の3つの関連クラスを持つ次の関連スキームとする。要素iとjが関係R sにある場合、( i , j ) の要素はs となる。
 123456
1  0   1   1   2   3   3 
2  1   0   1   3   2   3 
3  1   1   0   3   3   2 
4  2   3   3   0   1   1 
5  3   2   3   1   0   1 
6  3   3   2   1   1   0 

符号理論

ハミング方式とジョンソン方式は古典的な符号理論において重要な意味を持っています。

符号理論において、連想スキーム理論は主に符号の距離を扱う。線形計画法は、与えられた最小距離を持つ符号のサイズの上限と、与えられた強度を持つ設計のサイズの下限を生成する。最も具体的な結果は、基礎となる連想スキームが特定の多項式特性を満たす場合に得られる。これは直交多項式の領域につながる。特に、多項式型連想スキームにおける符号と設計に対して、いくつかの普遍的な境界が導出される。

ハミング方式の符号を扱う古典的な符号理論において、マクウィリアムズ変換はクロフチューク多項式として知られる直交多項式の族を伴う。これらの多項式は、ハミング方式の距離関係行列の固有値を与える。

参照

注記

参考文献

「 https://en.wikipedia.org/w/index.php?title=Association_scheme&oldid=1336850938」より取得