Schemat stowarzyszenia

Teoria schematów asocjacyjnych powstała w statystyce , w teorii projektowania eksperymentalnego do analizy wariancji . W matematyce schematy asocjacyjne należą zarówno do algebry , jak i kombinatoryki . W kombinatoryce algebraicznej schematy asocjacyjne zapewniają ujednolicone podejście do wielu tematów, na przykład projektów kombinatorycznych i teorii kodowania . W algebrze schematy asocjacyjne uogólniają grupy , a teoria schematów asocjacyjnych uogólnia teorię charakterów liniowych reprezentacji grup .

Definicja

₀ Schemat asocjacji klasy n składa się ze zbioru X wraz z podziałem S z X × X na n + 1 relacji binarnych , R , R ₁ , ..., R _n , które spełniają:

• ${\ Displaystyle R_ {0} = \ {(x, x): x \ w X \}}$ i nazywa się relacją tożsamości .
• ${\ Displaystyle R ^ {*}: = \ {(x, y): (y, x) \ w R \}$ ∗ , jeśli R w S , to R* w S
• Jeśli ${\ Displaystyle (x, y) \ w R_ {k}}$ , liczba ${\ Displaystyle z \ w X}$ taka, że $(x, z) \ w R_ {i}}$${ \$$,$ i ${\ Displaystyle (z, y) \ w R_ {j}}$ jest stałą ${\ Displaystyle p_ {$${\ displaystyle i}$ jot { $y}$$displaystyle j}$ , ${\ displaystyle k},$ od konkretnego wyboru i $displaystyle$ .

Schemat skojarzeń jest przemienny , jeśli ${\ Displaystyle p_ {ij} ^ {k} = p_ {ji} ^ {k}}$ dla wszystkich ${\ Displaystyle i}$ , ${\ Displaystyle j }$ i ${\ displaystyle k}$ . Większość autorów przyjmuje tę właściwość.

Schemat $asocjacji$ symetrycznej to taki w którym każdy relacją symetryczną . To jest:

• jeśli ( x , y ) ∈ R _ja , to ( y , x ) ∈ R _ja . (Lub równoważnie R * = R .)

Każdy symetryczny schemat skojarzeń jest przemienny.

Należy jednak zauważyć, że podczas gdy pojęcie schematu asocjacyjnego uogólnia pojęcie grupy, pojęcie schematu asocjacyjnego uogólnia jedynie pojęcie grupy przemiennej .

Dwa punkty x i y nazywane są i- tymi współpracownikami, jeśli ${\ Displaystyle (x, y) \ in R_ {i}}$ . Definicja mówi, że jeśli x i y są i -tymi asocjacjami, to także y i x . Każda para punktów jest i- tymi współpracownikami dla dokładnie jednego ${\ displaystyle i}$ . Każdy punkt jest swoim własnym zerowym współpracownikiem, podczas gdy różne punkty nigdy nie są zerowymi współpracownikami. Jeśli x i y są k- tymi towarzyszami, to liczba punktów $które$$są$ zarówno i $,$ tymi towarzyszami jak i j -tymi towarzyszami jest stałą ${\ displaystyle p_ {ij} ^ {k}}$ .

Interpretacja grafów i macierze sąsiedztwa

Symetryczny schemat asocjacji można zwizualizować jako pełny wykres z oznaczonymi krawędziami. Wykres ma ${$ , po jednym dla każdego punktu , a wierzchołki łączące krawędzie i y $y}$$displaystyle$$są$ , $\ displaystyle i}$${\ displaystyle x}$ i ${\ displaystyle y$$}$ są . $\ displaystyle p_ {ij} ^ {k}}$ unikalną etykietę, a liczba trójkątów ze stałą podstawą oznaczoną $oznaczoną$ innymi krawędziami $i$ jest $stałą$ p , w zależności od ${\ displaystyle i, j, k},$ ale nie od wyboru podstawy. W szczególności każdy wierzchołek występuje dokładnie z krawędziami oznaczonymi $}$$\ displaystyle p_ {ii} ^ {0} = v_ {i}$ ; $i}}$ { jest wartościowością relacji ${\ displaystyle R_ {i}}$ . Istnieją również $.$$oznaczone$ na $wierzchołku$ , odpowiadające

Relacje są opisane przez ich macierze sąsiedztwa . $}$$i$$}$ Displaystyle macierzą dla jest v × macierz z wierszami i kolumnami oznaczonymi punktami ${\ displaystyle X}$ .

${\ Displaystyle \ lewo (A_ {i} \ prawo) _ {x, y} = {\ rozpocząć {przypadki} 1 i {\ mbox {jeśli}} (x, y) \ w R_ {i} ,\\0,&{\mbox{inaczej.}}\end{przypadki}}\qquad (1)}$

Definicja symetrycznego schematu asocjacji jest równoznaczna ze stwierdzeniem, że macierze , które spełniają, są v × v (0,1) ZA $i}}$

I. $II$ ,

. ${\ Displaystyle \ suma _ {i = 0} ^ {n} A_ {i} = J}$ (macierz wszystkich jedynek),

III. ${\ Displaystyle A_ {0} = I}$ ,

IV. $Displaystyle A_ {i} A_ {j} = \ suma _ {k = 0} ^ {n}p_{ij}^{k}A_{k}=A_{j}A_{i},i,j=0,\ldots,n}$ .

( x , y ) -ta pozycja po lewej stronie (IV) to liczba ścieżek o długości dwa między x i y z etykietami i oraz j na wykresie. Zauważ, że wiersze i kolumny zawierają 's: $za$$\ displaystyle v_ {i}}$$}$

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

Terminologia

• Liczby $_$ . _ _ Nazywa się je również stałymi strukturalnymi .

Historia

Termin schemat skojarzeń wynika ( Bose i Shimamoto 1952 ), ale koncepcja ta jest już nieodłączna ( Bose i Nair 1939 ). Autorzy ci badali to, co statystycy nazwali częściowo zrównoważonymi niekompletnymi projektami bloków (PBIBD). Temat stał się przedmiotem zainteresowania algebraicznego wraz z publikacją ( Bose i Mesner 1959 ) oraz wprowadzeniem algebry Bosego – Mesnera . Najważniejszym wkładem do teorii była teza P. Delsarte ( Delsarte 1973 ), który rozpoznał iw pełni wykorzystał powiązania z teorią kodowania i teorią projektowania. Uogólnienia badali DG Higman (konfiguracje spójne) i B. Weisfeiler ( wykresy regularne odległości ).

Podstawowe fakty

• ${\ Displaystyle p_ {00} ^ {0} = 1}$ , czyli jeśli ${\ Displaystyle (x, y) \ w R_ {0}}$ to ${\ Displaystyle x = y}$$i$ jedynym , że ${\ Displaystyle (x, z) \ w R_ {0}}$ jest ${\ Displaystyle z = x}$ .
• ${\ Displaystyle \ suma _ {i = 0} ^ {k} p_ {ii} ^ {0} = | X |}$ , to dlatego, że partycja ${\ Displaystyle R_ {i}}$${\ Displaystyle X}$ .

Algebra Bosego-Mesnera

Macierze sąsiedztwa wykresów ${\ Displaystyle \ lewo (X, R_ {i} \ prawej)}$$ja$ algebrę i ZA ja { $Displaystyle {\ mathcal {A}}}$ (na liczbach rzeczywistych lub zespolonych ) zarówno dla iloczynu macierzowego , jak i iloczynu punktowego . Ta asocjacyjna, przemienna algebra nazywana jest algebrą Bosego-Mesnera schematu asocjacyjnego.

Ponieważ macierze w $do$ symetryczne i dojeżdżają pracy ze sobą, można je diagonalizować jednocześnie. Dlatego $półprosty$ i $_$ unikalną idempotentów _ _

Istnieje inna algebra macierzy ${\ Displaystyle (n + 1) \ razy (n + 1)},$ która jest izomorficzna z , ${\ Displaystyle {\ mathcal {A}}}$ i często łatwiej się z nim pracuje.

Przykłady

• Schemat Johnsona , oznaczony jako J ( v , k ), jest zdefiniowany następująco. Niech S będzie zbiorem z elementami v . Punkty schematu J ( v , k $_$ to S z k Dwa k -elementowe podzbiory A , B z S są i- tymi asocjacjami, gdy ich przecięcie ma rozmiar k − i .
• Schemat Hamminga , oznaczony jako H ( n , q ), jest zdefiniowany następująco. Punkty H ( n , q ) to q ⁿ uporządkowanych n - krotek na zbiorze o rozmiarze q . Mówimy, że dwie n -krotki x , y są i- tymi współrzędnymi, jeśli nie zgadzają się co do współrzędnych dokładnie i . Np. jeśli x = (1,0,1,1), y = (1,1,1,1), z = (0,0,1,1), to x i y są pierwszymi towarzyszami, x i z są 1. towarzyszami, a y i z są 2. towarzyszami w H (4,2).
• Graf regularny odległości , G , tworzy schemat asocjacji poprzez zdefiniowanie dwóch wierzchołków jako i- tych stowarzyszonych, jeśli ich odległość wynosi i .
• ₀ Skończona grupa G daje schemat asocjacji na , ${\ Displaystyle R_ {g} = \ {(x, y) \ mid x = g * y \}}$ klasą $R$ _g dla każdego elementu grupy, w następujący sposób: dla każdego niech g = $displaystyle g \ in$ gdzie ${\ Displaystyle *} jest$ operacją grupową . Klasą tożsamości grupowej jest R . Ten schemat skojarzeń jest przemienny wtedy i tylko wtedy, gdy G jest abelowe .
• Specyficzny 3-klasowy schemat asocjacji:

Niech A (3) będzie następującym schematem asocjacji z trzema klasami stowarzyszonymi na zbiorze X = {1,2,3,4,5,6}. Wpis ( i , j ) to s , jeśli elementy i i j są w relacji R _s .

	1	2	3	4	5	6
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

Teoria kodowania

Schemat Hamminga i schemat Johnsona mają duże znaczenie w klasycznej teorii kodowania .

W teorii kodowania teoria schematu asocjacyjnego dotyczy głównie odległości kodu . Metoda programowania liniowego tworzy górne granice rozmiaru kodu przy danej minimalnej odległości i dolne granice rozmiaru projektu o danej sile. Najbardziej szczegółowe wyniki uzyskuje się w przypadku, gdy podstawowy schemat asocjacji spełnia pewne właściwości wielomianu ; prowadzi to do dziedziny wielomianów ortogonalnych . W szczególności pewne uniwersalne granice są wyprowadzane dla kodów i projektów w schematach skojarzeń typu wielomianowego.

W klasycznej teorii kodowania , zajmującej się kodami w schemacie Hamminga , transformata MacWilliamsa obejmuje rodzinę wielomianów ortogonalnych znanych jako wielomiany Krawtchouka . Te wielomiany dają wartości własne macierzy relacji odległości schematu Hamminga .

Zobacz też

• Projekt bloku
• Algebra Bosego-Mesnera
• Projekt kombinatoryczny

Notatki

•    Bailey, Rosemary A. (2004), Schematy skojarzeń: zaprojektowane eksperymenty, algebra i kombinatoryka , Cambridge University Press, ISBN 978-0-521-82446-0 , MR 2047311 . (Rozdziały ze wstępnej wersji są dostępne on-line ).
•    Bannai, Eiichi; Ito, Tatsuro (1984), kombinatoryka algebraiczna I: Schematy asocjacyjne , Menlo Park, Kalifornia: Benjamin / Cummings, ISBN 0-8053-0490-8 , MR 0882540
•    Bose, RC ; Mesner, DM (1959), „O liniowych algebrach asocjacyjnych odpowiadających schematom skojarzeń częściowo zrównoważonych projektów” , Annals of Mathematical Statistics , 30 (1): 21–38, doi : 10,1214 / aoms / 1177706356 , JSTOR 2237117 , MR 0102157
•   Bose, RC ; Nair, KR (1939), „Częściowo zrównoważone niekompletne projekty bloków”, Sankhyā , 4 (3): 337–372, JSTOR 40383923
• Bose, RC ; Shimamoto, T. (1952), „Klasyfikacja i analiza częściowo zrównoważonych niekompletnych projektów bloków z dwiema klasami stowarzyszonymi”, Journal of the American Statistical Association , 47 (258): 151–184, doi : 10.1080 / 01621459.1952.10501161
•   Camion, P. (1998), „18. Kody i schematy asocjacyjne: podstawowe właściwości schematów asocjacyjnych istotne dla kodowania”, w: Pless, VS; Huffman, WC; Brualdi, RA (red.), Handbook of Coding Theory , tom. 1, Elsevier, s. 1441–, ISBN 978-0-444-50088-5
•   Delsarte, P. (1973), „An Algebraic Approach to the Association Schemes of Coding Theory”, Philips Research Reports (Suplement nr 10), OCLC 641852316
• Delsarte, P.; Levenshtein, VI (1998). „Schematy skojarzeń i teoria kodowania”. Transakcje IEEE dotyczące teorii informacji . 44 (6): 2477–2504. doi : 10.1109/18.720545 .
•   Dembowski, P. (1968), skończone geometrie , Springer, ISBN 978-3-540-61786-0
•    Godsil, CD (1993), Kombinatoryka algebraiczna , Nowy Jork: Chapman and Hall, ISBN 0-412-04131-6 , MR 1220704
•   MacWilliams, FJ; Sloane, NJA (1977), The Theory of Error Correcting Codes , North-Holland Mathematical Library, tom. 16, Elsevier, ISBN 978-0-444-85010-2
•   Ulica, Anne Penfold ; Ulica, Deborah J. (1987), Kombinatoryka projektu eksperymentalnego , Oxford UP [Clarendon], ISBN 0-19-853256-3

•   van Lint, JH; Wilson, RM (1992), Kurs kombinatoryki , Cambridge University Press, ISBN 0-521-00601-5
• Zieschang, Paul-Hermann (2005a), „ Schematy asocjacyjne: zaprojektowane eksperymenty, algebra i kombinatoryka autorstwa Rosemary A. Bailey, przegląd” (PDF) , Biuletyn Amerykańskiego Towarzystwa Matematycznego , 43 (2): 249–253, doi : 10.1090 /S0273-0979-05-01077-3
•   Zieschang, Paul-Hermann (2005b), Teoria schematów asocjacyjnych , Springer, ISBN 3-540-26136-2
•    Zieschang, Paul-Hermann (2006), „Warunek wymiany dla schematów asocjacyjnych”, Israel Journal of Mathematics , 151 (3): 357–380, doi : 10.1007 / BF02777367 , MR 2214129 , S2CID 120009352