Schéma přidružení - Association scheme

Tento článek je hlavní část nemusí adekvátně shrnout jeho obsah. V souladu s požadavky Wikipedie pokyny pro hlavní sekci, prosím zvažte upravující vést k poskytnout přístupný přehled klíčových bodů článku takovým způsobem, aby mohl obstát sám jako stručná verze článku. (Březen 2013)

Teorie asociační schémata vznikly ve statistice, v teorii experimentální design pro analýza rozptylu.^[1][2][3] v matematika, asociační schémata patří oběma algebra a kombinatorika. Opravdu, v algebraická kombinatorika, asociační schémata například poskytují jednotný přístup k mnoha tématům kombinatorické vzory a teorie kódování.^[4][5] V algebře se asociační schémata zobecňují skupiny a teorie asociačních schémat zobecňuje teorie znaků z lineární reprezentace skupin.^[6][7][8]

Definice

Schéma přidružení třídy n se skládá z a soubor X společně s a rozdělit S z X × X do n + 1 binární vztahy, R.₀, R.₁, ..., R._n které splňují:

• ${ displaystyle R_ {0} = {(x, x): x v X }}$ a nazývá se vztah identity.
• Definování ${ displaystyle R ^ {*}: = {(x, y) :( y, x) v R }}$, pokud R v S, pak R * v S
• Li ${ displaystyle (x, y) v R_ ​​{k}}$, počet ${ displaystyle z v X}$ takhle ${ displaystyle (x, z) v R_ ​​{i}}$ a ${ displaystyle (z, y) v R_ ​​{j}}$ je konstanta ${ displaystyle p_ {ij} ^ {k}}$ záleží na ${ displaystyle i}$, ${ displaystyle j}$, ${ displaystyle k}$ ale ne na konkrétní volbu ${ displaystyle x}$ a ${ displaystyle y}$.

Schéma přidružení je komutativní -li ${ displaystyle p_ {ij} ^ {k} = p_ {ji} ^ {k}}$ pro všechny ${ displaystyle i}$, ${ displaystyle j}$ a ${ displaystyle k}$. Většina autorů předpokládá tuto vlastnost.

A symetrický asociační schéma je takové, ve kterém každý vztah ${ displaystyle R_ {i}}$ je symetrický vztah. To je:

• pokud (X,y) ∈ R_i, pak (y,X) ∈ R_i . (Nebo ekvivalentně, R* = R.)

Každé schéma symetrické asociace je komutativní.

Všimněte si však, že zatímco pojem asociačního schématu zevšeobecňuje pojem skupiny, pojem komutativní asociační schéma zobecňuje pouze pojem komutativní skupiny.

Dva body X a y jsou nazývány i th přidruží, pokud ${ displaystyle (x, y) v R_ ​​{i}}$. Definice uvádí, že pokud X a y jsou i takoví spolupracovníci jsou y a X. Každá dvojice bodů je i th přidruží právě jednoho ${ displaystyle i}$. Každý bod je svým vlastním nulovým spolupracovníkem, zatímco odlišné body nejsou nikdy nulovými spolupracovníky. Li X a y jsou k th přidruží pak počet bodů ${ displaystyle z}$ které jsou oba i th spolupracovníci ${ displaystyle x}$ a j th spolupracovníci ${ displaystyle y}$ je konstanta ${ displaystyle p_ {ij} ^ {k}}$.

Grafové interpretace a matice sousedství

Symetrické asociační schéma lze vizualizovat jako kompletní graf s označenými okraji. Graf má ${ displaystyle v}$ vrcholy, jeden pro každý bod ${ displaystyle X}$a hrana spojující vrcholy ${ displaystyle x}$ a ${ displaystyle y}$ je označen ${ displaystyle i}$ -li ${ displaystyle x}$ a ${ displaystyle y}$ jsou ${ displaystyle i}$ th spolupracovníci. Každá hrana má jedinečný štítek a je označen počet trojúhelníků s pevnou základnou ${ displaystyle k}$ s označením ostatních okrajů ${ displaystyle i}$ a ${ displaystyle j}$ je konstanta ${ displaystyle p_ {ij} ^ {k}}$, záleží na ${ displaystyle i, j, k}$ ale ne na výběru základny. Zejména každý vrchol je přesně shodný ${ displaystyle p_ {ii} ^ {0} = v_ {i}}$ hrany označené ${ displaystyle i}$; ${ displaystyle v_ {i}}$ je mocenství z vztah ${ displaystyle R_ {i}}$. Jsou zde také označeny smyčky ${ displaystyle 0}$ na každém vrcholu ${ displaystyle x}$, souhlasí s ${ displaystyle R_ {0}}$.

The vztahy jsou popsány jejich matice sousedství. ${ displaystyle A_ {i}}$ je matice sousedství z ${ displaystyle R_ {i}}$ pro ${ displaystyle i = 0, ldots, n}$ a je proti × proti matice s řádky a sloupci označenými body ${ displaystyle X}$.

${ displaystyle left (A_ {i} right) _ {x, y} = left {{ begin {matrix} 1, & { mbox {if}} left (x, y right) v R_ {i}, 0, & { mbox {jinak.}} end {matrix}} vpravo. qquad (1)}$

Definice symetrického asociačního schématu je ekvivalentní s tím, že ${ displaystyle A_ {i}}$ jsou proti × proti (0,1)-matice které uspokojí

I. ${ displaystyle A_ {i}}$ je symetrický,

II. ${ displaystyle sum _ {i = 0} ^ {n} A_ {i} = J}$ (matice všeho druhu),

III. ${ displaystyle A_ {0} = I}$,

IV. ${ displaystyle A_ {i} A_ {j} = součet _ {k = 0} ^ {n} p_ {ij} ^ {k} A_ {k} = A_ {j} A_ {i}, i, j = 0, ldots, n}$.

(X, y) -tý vstup levé strany (IV) je počet cest délky dva mezi X a y se štítky i a j v grafu. Všimněte si, že řádky a sloupce ${ displaystyle A_ {i}}$ obsahovat ${ displaystyle v_ {i}}$ ${ displaystyle 1}$:

${ displaystyle A_ {i} J = JA_ {i} = v_ {i} J. qquad (2)}$

Terminologie

• Čísla ${ displaystyle p_ {ij} ^ {k}}$ se nazývají parametry režimu. Jsou také označovány jako strukturní konstanty.

Dějiny

Termín asociační schéma je to kvůli (Bose & Shimamoto 1952 ), ale koncept je již vlastní (Bose & Nair 1939 ).^[9] Tito autoři studovali to, co statistici nazvali částečně vyvážené neúplné návrhy bloků (PBIBD). Subjekt se stal předmětem algebraického zájmu zveřejněním (Bose & Mesner 1959 ) a zavedení Bose – Mesnerova algebra. Nejdůležitějším příspěvkem k teorii byla práce P. Delsarteho (Delsarte 1973 ), kteří rozpoznali a plně využili spojení s teorií kódování a teorií designu.^[10] Zevšeobecňování studoval D. G. Higman (koherentní konfigurace) a B. Weisfeiler (vzdálenost pravidelné grafy ).

Základní fakta

• ${ displaystyle p_ {00} ^ {0} = 1}$, tj. pokud ${ displaystyle (x, y) v R_ ​​{0}}$ pak ${ displaystyle x = y}$ a jediný ${ displaystyle z}$ takhle ${ displaystyle (x, z) v R_ ​​{0}}$ je ${ displaystyle z = x}$
• ${ displaystyle sum _ {i = 0} ^ {k} p_ {ii} ^ {0} = | X |}$, je to proto, že ${ displaystyle R_ {i}}$ rozdělit ${ displaystyle X}$.

Bose – Mesnerova algebra

The matice sousedství ${ displaystyle A_ {i}}$ z grafy ${ displaystyle left (X, R_ {i} right)}$ generovat a komutativní a asociativní algebra ${ displaystyle { mathcal {A}}}$ (přes skutečný nebo komplexní čísla ) oba pro maticový produkt a bodový produkt. Tento asociativní, komutativní algebra se nazývá Bose – Mesnerova algebra systému přidružení.

Protože matice v ${ displaystyle { mathcal {A}}}$ jsou symetrický a dojíždět mezi sebou mohou být diagonalizováno zároveň. Proto, ${ displaystyle { mathcal {A}}}$ je částečně jednoduché a má jedinečný základ primitiv idempotents ${ displaystyle J_ {0}, ldots, J_ {n}}$.

Je tu další algebra z ${ Displaystyle left (n + 1 right) times left (n + 1 right)}$ matice který je izomorfní na ${ displaystyle { mathcal {A}}}$, a je často snazší s ním pracovat.

Příklady

• The Johnsonovo schéma, označeno J(v, k), je definován následovně. Nechat S být set s proti elementy. Body schématu J(proti,k) jsou ${ displaystyle {v vyberte k}}$ podmnožiny S s k elementy. Dva k-prvkové podmnožiny A, B z S jsou i th přidruží, když jejich průsečík má velikost k − i.
• The Hammingovo schéma, označeno H(n,q), je definován následovně. Body z H(n,q) jsou qⁿ objednal n-n-tice přes sadu velikostí q. Dva n- n-tice X, y se říká, že jsou i tito spolupracovníci, pokud přesně nesouhlasí i souřadnice. Např. Pokud X = (1,0,1,1), y = (1,1,1,1), z = (0,0,1,1), pak X a y jsou první spolupracovníci, X a z jsou první spolupracovníci a y a z jsou 2. spolupracovníci v H (4,2).
• A vzdálenost-pravidelný graf, G, tvoří asociační schéma definováním dvou vrcholů, které mají být i tito spolupracovníci, pokud je jejich vzdálenost i.
• A konečná skupina G poskytuje asociační schéma na ${ displaystyle X = G}$, s třídou R_G pro každý prvek skupiny takto: pro každý ${ displaystyle g v G}$ nechat ${ displaystyle R_ {g} = {(x, y) | x = g * y }}$ kde ${ displaystyle *}$ je skupina úkon. Třída skupinové identity je R₀. Toto asociační schéma je komutativní právě tehdy G je abelian.
• Specifické asociační schéma třídy 3:^[11]

Nechat A(3) být následujícím asociačním schématem se třemi přidruženými třídami v sadě X = {1,2,3,4,5,6}. (i,j) položka je s pokud prvky i a j jsou ve vztahu R_s.

Teorie kódování

The Hammingovo schéma a Johnsonovo schéma mají v klasice zásadní význam teorie kódování.

v teorie kódování, teorie asociačního schématu se týká hlavně vzdálenost a kód. The lineární programování metoda vytváří horní hranice pro velikost a kód s daným minimem vzdálenost a dolní meze pro velikost a design s danou silou. Nejkonkrétnějších výsledků se dosáhne v případě, že základní schéma přidružení splňuje určité podmínky polynomiální vlastnosti; to vede jednoho do říše ortogonální polynomy. Zejména jsou odvozeny některé univerzální hranice kódy a vzory v asociačních schématech polynomiálního typu.

V klasickém teorie kódování, jednat s kódy v Hammingovo schéma, MacWilliamova transformace zahrnuje rodinu ortogonálních polynomů známých jako Krawtchoukovy polynomy. Tyto polynomy dávají vlastní čísla vztahu vzdálenosti matice z Hammingovo schéma.

Viz také

• Blokový design
• Bose – Mesnerova algebra
• Kombinatorický design

Poznámky

Reference

• Bailey, Rosemary A. (2004), Asociační schémata: Navržené experimenty, algebra a kombinatorika, Cambridge University Press, ISBN  978-0-521-82446-0, PAN  2047311. (Kapitoly z předběžného návrhu jsou dostupný online.)
• Bannai, Eiichi; Ito, Tatsuro (1984), Algebraická kombinatorika I: Asociační schémata, Menlo Park, CA: The Benjamin / Cummings Publishing Co., Inc., str. Xxiv + 425, ISBN  0-8053-0490-8, PAN  0882540
• Bose, R. C.; Mesner, D. M. (1959), „Na lineárních asociativních algebrách odpovídajících asociačním schématům částečně vyvážených vzorů“, Annals of Mathematical Statistics, 30 (1): 21–38, doi:10.1214 / aoms / 1177706356, JSTOR  2237117, PAN  0102157
• Bose, R. C.; Nair, K. R. (1939), „Částečně vyvážené neúplné blokové vzory“, Sankhya, 4: 337–372
• Bose, R. C.; Shimamoto, T. (1952), „Klasifikace a analýza částečně vyvážených neúplných návrhů bloků se dvěma přidruženými třídami“, Journal of the American Statistical Association, 47 (258): 151–184, doi:10.1080/01621459.1952.10501161
• P. Camion (1998), Codes and Association Schemes: Basic Properties of Association Schemes Relevant to Coding, in Příručka teorie kódováníPless a W. C. Huffman, Eds., Elsevier, Nizozemsko.
• Delsarte, P. (1973), „Algebraický přístup ke asociačním schématům teorie kódování“, Výzkumné zprávy společnosti Philips, dodatek č. 10
• Delsarte, P .; Levenshtein, V. I. (1998). "Asociační schémata a teorie kódování". Transakce IEEE na teorii informací. 44 (6): 2477–2504. doi:10.1109/18.720545.
• Dembowski, P. (1968), Konečná geometrie, Berlín: Springer-Verlag
• Godsil, C. D. (1993), Algebraická kombinatorika, New York: Chapman and Hall, ISBN  0-412-04131-6, PAN  1220704
• F. J. MacWilliams a N. J. A. Sloane, Teorie kódů pro opravu chyb, Elsevier, New York, 1978.
• Ulice, Anne Penfoldová & Ulice, Deborah J. (1987). Kombinatorika experimentálního designu. Oxford U. P. [Clarendon]. ISBN  0-19-853256-3.

• van Lint, J.H. a Wilson, R.M. (1992), Kurz kombinatoriky. Cambridge, Eng .: Cambridge University Press. ISBN  0-521-00601-5
• Zieschang, Paul-Hermann (2005a), "Asociační schémata: Navržené experimenty, algebra a kombinatorika autor: Rosemary A. Bailey, recenze " (PDF), Bulletin of the American Mathematical Society, 43 (2): 249–253, doi:10.1090 / S0273-0979-05-01077-3
• Zieschang, Paul-Hermann (2005b), Teorie asociačních schémat, Springer, str. Xii + 283, ISBN  3-540-26136-2
• Zieschang, Paul-Hermann (2006), „Výměnná podmínka pro asociační programy“, Israel Journal of Mathematics, 151 (3): 357–380, doi:10.1007 / BF02777367, ISSN  0021-2172, PAN  2214129