Föreningsordning

Teorin om associationsscheman uppstod i statistiken , i teorin om experimentell design för variansanalys . Inom matematiken tillhör associationsscheman både algebra och kombinatorik . I algebraisk kombinatorik ger associationsscheman ett enhetligt förhållningssätt till många ämnen, till exempel kombinatoriska mönster och kodningsteori . I algebra generaliserar associationsscheman grupper och teorin om associationsscheman generaliserar karaktärsteorin för linjära representationer av grupper .

Definition

₀ Ett n -klass associationsschema består av en mängd X tillsammans med en partition S av X × X i n + 1 binära relationer , R , R ₁ , ..., R _n som uppfyller:

• $R_{0}=\{(x,x):x\in X\}$ och kallas identitetsrelationen .
• Definiera $R^{*}:=\{(x,y):(y,x)\in R\}$ , om R i S , då R* i S
• Om $(x,y)\in R_{k}$ , antalet $z\in X$ så att ${ \displaystyle (x,z)\in R_{i}}$ och $(z,y)\in R_{j}$ är en konstant $p_{ ij}^{k}$ beroende på $i$ , $j$ , $k$ men inte på det speciella valet av $x$ och $y$ .

Ett associationsschema är kommutativt om $p_{ij}^{k}=p_{ji}^{k}$ för alla $i$ , $j$ och $k$ . De flesta författare antar denna egenskap.

Ett symmetriskt associationsschema är ett där varje $R_{i}$ är en symmetrisk relation . Det är:

• om ( x , y ) ∈ R _i , då ( y , x ) ∈ R _i . (Eller motsvarande, R * = R .)

Varje symmetriskt associationsschema är kommutativt.

Observera dock att medan begreppet ett associationsschema generaliserar begreppet en grupp, generaliserar begreppet ett kommutativt associationsschema bara begreppet en kommutativ grupp .

Två punkter x och y kallas i :e associerade om $(x,y)\in R_{i}$ . Definitionen säger att om x och y är i :e associerade så är y och x det också . Varje par av punkter är i :te associerade för exakt en $i$ . Varje punkt är sin egen nollassocierade medan distinkta punkter aldrig är nollassocierade. Om x och y är k:te associeringar så är antalet punkter $z$ som är både i :te associeringarna till $x$ och j: te associerade till $y$ en konstant $p_{ij}^{k}$ .

Graftolkning och närliggande matriser

Ett symmetriskt associationsschema kan visualiseras som en komplett graf med märkta kanter. Grafen har $v$ hörn, en för varje punkt i $X$ , och kanten som sammanfogar hörn $x$ och $y$ är märkta $i$ om $x$ och $y$ är $i$ :e associerade. Varje kant har en unik etikett, och antalet trianglar med en fast bas märkt $k$ med de andra kanterna märkta $i$ och $j$ är en konstant ${\ displaystyle p_{ij}^{k}}$ , beroende på $i,j,k$ men inte på valet av bas. I synnerhet är varje vertex infallande med exakt $p_{ii}^{0}=v_{i}$ kanter märkta $i$ ; $v_{i}$ är valensen för relationen $R_{i}$ . Det finns också slingor märkta $0$ vid varje vertex $x$ , motsvarande $R_{0}$ .

Relationerna beskrivs av deras närliggande matriser . $A_{i}$ är närliggande matris för $R_{i}$ för $i=0,\ldots ,n$ och är en v × v matris med rader och kolumner märkta med punkterna $X$ .

$\left(A_{i}\right)_{x,y}={\begin{cases}1,&{\mbox{if }}(x,y)\in R_{i} ,\\0,&{\mbox{annars.}}\end{cases}}\qquad (1)$

Definitionen av ett symmetriskt associationsschema motsvarar att säga att $A_{i}$ är v × v (0,1)-matriser som uppfyller

I. $A_{i}$ är symmetrisk,

II. $\sum _{i=0}^{n}A_{i}=J$ (all-one-matrisen),

III. $A_{0}=I$ ,

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

Den ( x , y )-te ingången på vänster sida av (IV) är antalet vägar med längd två mellan x och y med beteckningarna i och j i grafen. Observera att raderna och kolumnerna i $A_{i}$ innehåller $v_{i}$$1$ :s:

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

Terminologi

• Siffrorna $p_{ij}^{k}$ kallas schemats parametrar . De kallas också för de strukturella konstanterna .

Historia

Termen association scheme beror på ( Bose & Shimamoto 1952 ) men konceptet är redan inneboende i ( Bose & Nair 1939) . Dessa författare studerade vad statistiker har kallat partiellt balanserade ofullständiga blockdesigner (PBIBDs). Ämnet blev ett objekt av algebraiskt intresse med publiceringen av ( Bose & Mesner 1959 ) och införandet av Bose–Mesner algebra . Det viktigaste bidraget till teorin var avhandlingen av P. Delsarte ( Delsarte 1973 ) som erkände och till fullo använde sambanden med kodningsteori och designteori. Generaliseringar har studerats av GD Higman (koherenta konfigurationer) och B. Weisfeiler ( avståndsregelbundna grafer) .

Grundläggande fakta

• $p_{00}^{0}=1$ , dvs om $(x,y)\in R_{0}$ då $x=y$ och den enda $z$ så att $(x,z)\in R_{0}$ är $z=x$ .
• ${\displaystyle \sum _{i=0}^{k}p_{ii}^{0}=|X|},$ detta beror på att ${\displaystyle R_{i}}-$ partitionen $X$ .

Bose-Mesner algebra

Närliggande matriser $A_{i}$ i graferna ( $\displaystyle \left(X,R_{i}\right)}$ genererar en kommutativ och associativ algebra ${\ matematisk {A}}$ (över de reella eller komplexa talen ) både för matrisprodukten och den punktvisa produkten . Denna associativa, kommutativa algebra kallas för associeringsschemats Bose–Mesner-algebra .

Eftersom matriserna i ${\mathcal {A}}$ är symmetriska och pendlar med varandra, kan de diagonaliseras samtidigt. Därför är ${\mathcal {A}}$ semi-enkel och har en unik grund av primitiva idempotenter $J_{0},\ldots ,J_{n}$ ,

Det finns en annan algebra av $(n+1)\times (n+1)$ matriser som är isomorf till ${\mathcal {A}}$ , och är ofta lättare att arbeta med.

Exempel

• Johnson -schemat , betecknat J ( v , k ), definieras enligt följande. Låt S vara en mängd med v element. Punkterna i schemat J ( v , k ) är ${v \choose k}$ delmängder av S med k element. Två k -element delmängder A , B av S är i :e associerade när deras skärningspunkt har storleken k − i .
• Hamming -schemat , betecknat H ( n , q ), definieras enligt följande. Punkterna för H ( n , q ) är de q ⁿ -ordnade n - tuplarna över en uppsättning av storleken q . Två n -tupler x , y sägs vara i :e associerade om de inte är överens i exakt i- koordinater. T.ex. om x = (1,0,1,1), y = (1,1,1,1), z = (0,0,1,1), då är x och y första associerade, x och z är 1:a associerade och y och z är 2:a associerade i H (4,2).
• En avstånd-reguljär graf , G , bildar ett associationsschema genom att definiera två hörn som i associerade om deras avstånd är i .
• ₀ En finit grupp G ger ett associationsschema på ${\displaystyle X=G} ,$ med en klass R _g för varje gruppelement, enligt följande: för varje $g\in G$ låt $R_{g}=\{(x,y)\mid x=g*y\}$ där ∗ $\displaystyle *}$ är gruppoperationen . Klassen för gruppidentiteten är R . Detta associationsschema är kommutativt om och endast om G är abelskt .
• Ett specifikt 3-klass associeringsschema:

Låt A (3) vara följande associationsschema med tre associerade klasser i mängden X = {1,2,3,4,5,6}. ( i , j )-posten är s om elementen i och j står i _relation Rs .

	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

Kodningsteori

Hamming -schemat och Johnson-schemat är av stor betydelse i klassisk kodningsteori .

I kodningsteori handlar associationsschemateori huvudsakligen om avståndet till en kod . Den linjära programmeringsmetoden producerar övre gränser för storleken på en kod med givet minimiavstånd och nedre gränser för storleken på en design med en given styrka. De mest specifika resultaten erhålls i fallet där det underliggande associationsschemat uppfyller vissa polynomegenskaper ; detta leder en in i riket av ortogonala polynom . Speciellt härleds vissa universella gränser för koder och mönster i associationsscheman av polynomtyp.

I klassisk kodningsteori , som handlar om koder i ett Hamming-schema , involverar MacWilliams-transformen en familj av ortogonala polynom som kallas Krawtchouk-polynomen . Dessa polynom ger egenvärdena för avståndsrelationsmatriserna i Hamming-schemat .

Se även

• Blockdesign
• Bose–Mesner algebra
• Kombinatorisk design

Anteckningar

•    Bailey, Rosemary A. (2004), Association Schemes: Designed Experiments, Algebra and Combinatorics , Cambridge University Press, ISBN 978-0-521-82446-0 , MR 2047311 . (Kapitel från preliminärt utkast finns tillgängliga online .)
•    Bannai, Eiichi; Ito, Tatsuro (1984), Algebraisk kombinatorik I: Associationsscheman , Menlo Park, CA: Benjamin/Cummings, ISBN 0-8053-0490-8 , MR 0882540
•   Bose, RC ; Mesner, DM (1959), "On linear associative algebras corresponding to association schemes of partially balanced designs" , Annals of Mathematical Statistics , 30 ( 1) : 21–38, doi : 10.1214/aoms/ 1177706356 , JSTOR 7237  
•   Bose, R.C .; Nair, K. R. (1939), "Partially balanced incomplete block designs", Sankhyā , 4 (3): 337–372, JSTOR 40383923
• Bose, R.C .; Shimamoto, T. (1952), "Klassificering och analys av partiellt balanserade ofullständiga blockdesigner med två associerade klasser", Journal of the American Statistical Association , 47 ( 258): 151–184, doi : 10.1080/01621459.1911.6105
•   Camion, P. (1998), "18. Koder och associationsscheman: grundläggande egenskaper hos associationsscheman som är relevanta för kodning", i Pless, VS; Huffman, WC; Brualdi, RA (red.), Handbook of Coding Theory , vol. 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 (Supplement nr 10), OCLC 641852316
• Delsarte, P.; Levenshtein, VI (1998). "Associationsscheman och kodningsteori". IEEE-transaktioner på informationsteori . 44 (6): 2477–2504. doi : 10.1109/18.720545 .
•   Dembowski, P. (1968), Finite Geometries , Springer, ISBN 978-3-540-61786-0
•    Godsil, CD (1993), Algebraic Combinatorics , New York: 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, vol. 16, Elsevier, ISBN 978-0-444-85010-2
•   Street, Anne Penfold ; Street, Deborah J. (1987), Combinatorics of Experimental Design , Oxford UP [Clarendon], ISBN 0-19-853256-3

•   van Lint, JH; Wilson, RM (1992), A Course in Combinatorics , Cambridge University Press, ISBN 0-521-00601-5
• Zieschang, Paul-Hermann (2005a), " Association Schemes: Designed Experiments, Algebra and Combinatorics by Rosemary A. Bailey, Review" (PDF) , Bulletin of the American Mathematical Society , 43 (2): 249–253, doi : 10.1090 /S0273-0979-05-01077-3
•   Zieschang, Paul-Hermann (2005b), Theory of association schemes , Springer, ISBN 3-540-26136-2
•    Zieschang, Paul-Hermann (2006), "The exchange condition for association schemes", Israel Journal of Mathematics , 151 (3): 357–380, doi : 10.1007/BF02777367 , MR 2214129 , S2CID 15200933