Minimax Condorcet

2013-11-06T04:05:14Z

128.12.253.4: Made short description at the top much clearer. The explanation below still explains in great detail.

{{Inadequate lead|date=March 2013}}
{{Use dmy dates|date=September 2011}}
The theory of '''association schemes''' arose in statistics, in the theory of [[design of experiments|experimental design]] for the [[analysis of variance]].<ref>{{harvnb|Bailey|2004|loc=pg. 387}}</ref><ref>{{harvnb|Bose|Mesner|1959}}</ref><ref>{{harvnb|Bose|Nair|1939}}</ref> In [[mathematics]], association schemes belong to both [[algebra]] and [[combinatorics]]. Indeed, in [[algebraic combinatorics]], association schemes provide a unified approach to many topics, for example [[combinatorial design]]s and [[coding theory]].<ref>{{harvnb|Bannai|Ito|1984}}</ref><ref>{{harvnb|Godsil|1993}}</ref> In algebra, association schemes generalize [[group (mathematics)|group]]s, and the theory of association schemes generalizes the [[group character|character theory]] of [[group representation|linear representations]] of groups.<ref>{{harvnb|Bailey|2004|loc=pg. 387}}</ref><ref>{{harvnb|Zieschang|2005b}}</ref><ref>{{harvnb|Zieschang|2005a}}</ref>

==Definition==

An n-class association scheme consists of a [[Set (mathematics)|set]] ''X'' together with a [[partition of a set|partition]] ''S'' of ''X'' × ''X'' into n + 1 [[binary relation]]s, R0, R1, ..., Rn which satisfy:

*<math>R_{0}=\{(x,x):x\in X\}</math> and is called the [[Identity relation]].
*Defining <math> R^* :=\{(x,y) | (y,x)\in R\}</math>, if ''R'' in ''S'', then ''R*'' in ''S''
*If <math>(x,y)\in R_{k}</math>, the number of <math>z\in X</math> such that <math>(x,z)\in R_{i}</math> and <math>(z,y)\in R_{j}</math> is a constant <math>p^k_{ij}</math> depending on <math>i</math>, <math>j</math>, <math>k</math> but not on the particular choice of <math>x</math> and <math>y</math>.

An association scheme is ''commutative'' if <math>p_{ij}^k=p_{ji}^k</math> for all <math>i</math>, <math>j</math> and <math>k</math>. Most authors assume this property.

A ''symmetric'' association scheme is one in which each relation <math>R_i</math> is a [[symmetric relation]]. That is:

* if (''x'',''y'') ∈ ''R''''i'', then (''y'',''x'') ∈ ''R''''i'' . (Or equivalently, ''R''* = ''R''.)

Every symmetric association scheme is commutative.

Note, however, that while the notion of an association scheme generalizes the notion of a group, the notion of a commutative association scheme only generalizes the notion of a commutative group.

Two points ''x'' and ''y'' are called ''i'' th associates if <math>(x,y)\in R_{i}</math>. The definition states that if ''x'' and ''y'' are ''i'' th associates so are ''y'' and ''x''. Every pair of points are ''i'' th associates for exactly one <math>i</math>. Each point is its own zeroth associate while distinct points are never zeroth associates. If ''x'' and ''y'' are ''k'' th associates then the number of points <math>z</math> which are both ''i'' th associates of <math>x</math> and ''j'' th associates of <math>y</math> is a constant <math>p^k_{ij}</math>.

===Graph interpretation and adjacency matrices===

An association scheme can be visualized as a [[complete graph]] with labeled edges. The graph has <math>v</math> vertices, one for each point of <math>X</math>, and the edge joining vertices <math>x</math> and <math>y</math> is labeled <math>i</math> if <math>x</math> and <math>y</math> are <math>i</math> th associates. Each edge has a unique label, and the number of triangles with a fixed base labeled <math>k</math> having the other edges labeled <math>i</math> and <math>j</math> is a constant <math>p^k_{ij}</math>, depending on <math>i,j,k</math> but not on the choice of the base. In particular, each vertex is incident with exactly <math>p^0_{ii}=v_{i}</math> edges labeled <math>i</math>; <math>v_{i}</math> is the [[Adjacency relation|valency]] of the [[Relation (mathematics)|relation]] <math>R_{i}</math>. There are also loops labeled <math>0</math> at each vertex <math>x</math>, corresponding to <math>R_{0}</math>.

The [[Relation (mathematics)|relations]] are described by their [[Adjacency matrix|adjacency matrices]]. <math>A_{i}</math> is the [[adjacency matrix]] of <math>R_{i}</math> for <math>i=0,\ldots,n</math> and is a ''v'' × ''v'' [[Matrix (mathematics)|matrix]] with rows and columns labeled by the points of <math>X</math>.
:<math>\left(A_{i}\right)_{x,y}=\left\{\begin{matrix}
1, & \mbox{if } \left(x,y\right)\in R_{i},\\
0, & \mbox{otherwise.} \end{matrix}\right. \qquad(1)</math>

The definition of an association scheme is equivalent to saying that the <math>A_{i}</math> are ''v'' × ''v'' (0,1)-[[Matrix (mathematics)|matrices]] which satisfy
:I. <math>A_{i} \,</math> is symmetric,
:II. <math>\sum_{i=0}^{n}A_{i}=J</math> (the all-ones matrix),
:III. <math>A_{0}=I \,</math>,
:IV. <math>A_{i}A_{j}=\sum_{k=0}^{n} p^k_{ij}A_{k}=A_{j}A_{i}, i,j=0,\ldots,n</math>.

The (''x'', ''y'')-th entry of the left side of (IV) is the number of paths of length two between ''x'' and ''y'' with labels i and j in the graph. Note that the rows and columns of <math>A_{i}</math> contain <math>v_{i}</math> <math>1</math>'s:

<math>A_{i} J=J A_{i}=v_{i} J. \qquad(2)</math>

===Terminology===
*The numbers <math>p_{ij}^k</math> are called the ''parameters'' of the scheme. They are also referred to as the ''structural constants''.

==History==
The term ''association scheme'' is due to {{harv|Bose|Shimamoto|1952}} but the concept is already inherent in {{harv|Bose|Nair|1939}}.<ref>{{harvnb|Dembowski|1968|loc=pg. 281, footnote 1}}</ref> These authors were studying what statisticians have called ''partially balanced incomplete block designs'' (PBIBDs). The subject became an object of algebraic interest with the publication of {{harv|Bose|Mesner|1959}} and the introduction of the Bose–Mesner algebra. The most important contribution to the theory was the thesis of P. Delsarte {{harv|Delsarte|1973}} who recognized and fully used the connections with coding theory and design theory.<ref>{{harvnb|Bannai|Ito|1984|loc=pg. vii}}</ref> Generalizations have been studied by D. G. Higman (coherent configurations) and B. Weisfeiler (distance regular graphs).

==Basic facts==

*<math>p_{00}^0 = 1</math>, i.e. if <math>(x,y) \in R_0</math> then <math>x = y</math> and the only <math>z</math> such that <math>(x,z) \in R_0</math> is <math>z=x</math>
*<math>\sum_{i=0}^{k} p_{ii}^0 = |X|</math>, this is because the <math>R_i</math> partition <math>X</math>.

==The Bose–Mesner algebra==

The [[Adjacency matrix|adjacency matrices]] <math>A_i</math> of the [[Graph (mathematics)|graphs]] <math>\left(X,R_{i}\right)</math> generate a [[Commutativity|commutative]] and [[associative]] [[algebra]] <math>\mathcal{A}</math> (over the real or [[complex number]]s) both for the [[matrix product]] and the [[pointwise product]]. This [[Associative algebra|associative]], [[commutative algebra]] is called the [[Bose–Mesner algebra]] of the association scheme.

Since the [[Matrix (mathematics)|matrices]] in <math>\mathcal{A}</math> are [[Symmetric matrix|symmetric]] and [[Commutativity|commute]] with each other, they can be [[Diagonal matrix|diagonalized]] simultaneously. Therefore <math>\mathcal{A}</math> is [[Semisimple operator|semi-simple]] and has a unique basis of primitive [[idempotent]]s <math>J_{0},\ldots,J_{n}</math>.

There is another [[algebra]] of <math>\left(n+1\right)\times\left(n+1\right)</math> [[Matrix (mathematics)|matrices]] which is [[isomorphic]] to <math>\mathcal{A}</math>, and is often easier to work with.

==Examples==

*The [[Johnson scheme]], denoted ''J''(''v,k''), is defined as follows. Let ''S'' be a set with ''v'' elements. The points of the scheme ''J''(''v'',''k'') are the <math>{v \choose k}</math> subsets of S with ''k'' elements. Two ''k''-element subsets ''A'', ''B'' of ''S'' are ''i'' th associates when their intersection has size ''k'' − ''i''.

*The [[Hamming scheme]], denoted ''H''(''n'',''q''), is defined as follows. The points of ''H''(''n'',''q'') are the ''qn'' ordered ''n''-[[tuple]]s over a set of size ''q''. Two ''n''-tuples ''x'', ''y'' are said to be ''i'' th associates if they disagree in exactly ''i'' coordinates. E.g., if ''x'' = (1,0,1,1), ''y'' = (1,1,1,1), ''z'' = (0,0,1,1), then ''x'' and ''y'' are 1st associates, ''x'' and ''z'' are 1st associates and ''y'' and ''z'' are 2nd associates in ''H(4,2)''.

*A [[distance-regular graph]], ''G'', forms an association scheme by defining two vertices to be ''i'' th associates if their distance is ''i''.

*A [[finite group]] ''G'' yields an association scheme on <math>X=G</math>, with a class ''R''''g'' for each group element, as follows: for each <math>g \in G</math> let <math>R_g=\{(x,y) | x=g*y\}</math> where <math>*</math> is the group [[operation (mathematics)|operation]]. The class of the group identity is ''R''0. This association scheme is commutative if and only if ''G'' is [[Abelian group|abelian]].

*A specific 3-class association scheme:<ref>{{harvnb|Street|Street|1987|loc=pg. 238}}</ref>
:Let ''A''(3) be the following association scheme with three associate classes on the set ''X'' = {1,2,3,4,5,6}. The (''i'',''j'') entry is ''s'' if elements ''i'' and ''j'' are in relation Rs.
<center>
{| class="wikitable"
|-
!  !! 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 
|}
</center>

==Coding theory==

The [[Hamming scheme]] and the [[Johnson scheme]] are of major significance in classical [[coding theory]].

In [[coding theory]], association scheme theory is mainly concerned with the [[Hamming distance|distance]] of a [[code]]. The [[linear programming]] method produces upper bounds for the size of a [[code]] with given minimum [[Hamming distance|distance]], and lower bounds for the size of a [[T-design|design]] with a given strength. The most specific results are obtained in the case where the underlying association scheme satisfies certain [[polynomial]] properties; this leads one into the realm of [[orthogonal polynomials]]. In particular, some universal bounds are derived for [[code]]s and [[T-design|designs]] in polynomial-type association schemes.

In classical [[coding theory]], dealing with [[code]]s in a [[Hamming scheme]], the MacWilliams transform involves a family of orthogonal polynomials known as the [[Krawtchouk polynomials]]. These polynomials give the [[eigenvalues]] of the distance relation [[Matrix (mathematics)|matrices]] of the [[Hamming scheme]].

==See also==

* [[Block design]]
* [[Bose–Mesner algebra]]
* [[Combinatorial design]]

==Notes==
{{Reflist}}

==References==

* {{citation| first=Rosemary A.| last=Bailey | authorlink=Rosemary A. Bailey | url=http://www.maths.qmul.ac.uk/~rab/Asbook | title=Association Schemes: Designed Experiments, Algebra and Combinatorics|publisher=Cambridge University Press|year=2004|isbn=978-0-521-82446-0| mr=2047311}}. (Chapters from preliminary draft are [http://www.maths.qmw.ac.uk/~rab available on-line].)

* {{citation| last1=Bannai | first1=Eiichi | last2=Ito | first2=Tatsuro | title=Algebraic combinatorics I: Association schemes | publisher=The Benjamin/Cummings Publishing Co., Inc. | location=Menlo Park, CA | year=1984 | pages=xxiv+425 | isbn=0-8053-0490-8 | mr=0882540 | unused_data= }}

* {{citation| last1=Bose|first1=R. C.| authorlink1=R. C. Bose| last2=Mesner|first2=D. M.|year=1959|title=On linear associative algebras corresponding to association schemes of partially balanced designs|journal=[[Annals of Mathematical Statistics]]|volume=30|issue=1|pages=21–38| url=http://projecteuclid.org/euclid.aoms/1177706356 | doi=10.1214/aoms/1177706356 | mr = 102157 | jstor = 2237117}}

* {{citation| last1=Bose|first1=R. C.|authorlink1=R. C. Bose|first2= K. R.|last2= Nair|title= Partially balanced incomplete block designs|journal= [[Sankhya (journal)|Sankhyā]]|volume= 4|year=1939|pages= 337–372}}

* {{citation|last=Bose|first=R. C.|last2=Shimamoto|first2=T.|title=Classification and analysis of partially balanced incomplete block designs with two associate classes|journal=Journal of the American Statistical Association|year=1952|volume=47|pages=151–184|authorlink=R. C. Bose}}

* P. Camion (1998), Codes and Association Schemes: Basic Properties of Association Schemes Relevant to Coding, in ''Handbook of Coding Theory'', V. S. Pless and W. C. Huffman, Eds., Elsevier, The Netherlands.

* {{citation|last=Delsarte |first= P.|year=1973 |title= An Algebraic Approach to the Association Schemes of Coding Theory|journal= Philips Research Reports, Supplement No. 10}}

* {{cite journal | last1 = Delsarte | first1 = P. | last2 = Levenshtein | first2 = V. I. | year = 1998 | title = Association schemes and coding theory | url = | journal = IEEE Transactions on Information Theory | volume = 44 | issue = 6| pages = 2477–2504 }}

*{{citation|last=Dembowski|first=P.|title=Finite Geometry|publisher=Springer-Verlag|location=Berlin|year=1968}}

* {{citation|first=C. D.| last=Godsil|authorlink = Chris Godsil|title=Algebraic Combinatorics|publisher=Chapman and Hall|year=1993|location=New York|isbn=0-412-04131-6 | mr=1220704 }}

* F. J. MacWilliams and N. J. A. Sloane, ''The Theory of Error-Correcting Codes'', Elsevier, New York, 1978.

*{{cite book
|author=Street, Anne Penfold and Street, Deborah J.
|title=Combinatorics of Experimental Design
|publisher=Oxford U. P. [Clarendon]
|year=1987
|pages=400+xiv
|isbn=0-19-853256-3
}}

* van Lint, J.H., and Wilson, R.M. (1992), ''A Course in Combinatorics''. Cambridge, Eng.: Cambridge University Press. ISBN 0-521-00601-5

* {{citation|doi=10.1090/S0273-0979-05-01077-3|url=http://www.ams.org/bull/2006-43-02/S0273-0979-05-01077-3/S0273-0979-05-01077-3.pdf|title=''Association Schemes: Designed Experiments, Algebra and Combinatorics'' by Rosemary A. Bailey, Review|first= Paul-Hermann|last=Zieschang|journal=Bulletin of the American Mathematical Society|volume=43|year=2005a|issue=02|pages=249–253}}

* {{citation| last=Zieschang | first=Paul-Hermann | title=Theory of association schemes | publisher=Springer | year=2005b | pages=xii+283 | isbn=3-540-26136-2 }}

* {{citation | last1=Zieschang | first1=Paul-Hermann | title=The exchange condition for association schemes | doi=10.1007/BF02777367 | mr=2214129 | year=2006 | journal=Israel Journal of Mathematics | issn=0021-2172 | volume=151 | issue=3 | pages=357–380}}

{{Experimental design|state=collapsed}}
{{Statistics|collection|state=collapsed}}

[[Category:Articles with inconsistent citation formats]]
[[Category:Design of experiments]]
[[Category:Analysis of variance]]
[[Category:Algebraic combinatorics]]
[[Category:Representation theory]]

formulasearchengine - User contributions [en]

Minimax Condorcet