Bose–Mesner algebra

Let X be a set of v elements. Consider a partition of the 2-element subsets of X into n non-empty subsets, R₁, ..., R_n such that:

• given an $x\; \backslash in\; X$, the number of $y\; \backslash in\; X$ such that $\backslash \{x,y\backslash \}\; \backslash in\; R\_i$ depends only on i (and not on x). This number will be denoted by v_i, and
• given $x,y\; \backslash in\; X$ with $\backslash \{x,y\backslash \}\; \backslash in\; R\_k$, the number of $z\; \backslash in\; X$ such that $\backslash \{x,z\backslash \}\; \backslash in\; R\_i$ and $\backslash \{z,y\backslash \}\; \backslash in\; R\_j$ depends only on i,j and k (and not on x and y). This number will be denoted by $p^k\_\{ij\}$.

This structure is enhanced by adding all pairs of repeated elements of X and collecting them in a subset R₀. This enhancement permits the parameters i, j, and k to take on the value of zero, and lets some of x,y or z be equal.

A set with such an enhanced partition is called an association scheme.{{harvnb|Cameron|van Lint|1991|loc=pp.197–198}} One may view an association scheme as a partition of the edges of a complete graph (with vertex set X) into n classes, often thought of as color classes. In this representation, there is a loop at each vertex and all the loops receive the same 0th color.

The association scheme can also be represented algebraically. Consider the matrices D_i defined by:

: $(D\_i)\_\{x,y\}\; =\; \backslash begin\{cases\}$

1,& \text{if } \left(x,y\right)\in R_{i},\\

0,& \text{otherwise.} \end{cases} \qquad (1)

Let $\backslash mathcal\{A\}$ be the vector space consisting of all matrices $\backslash sideset\{\}\{\_\{i=0\}^\{n\}\}\backslash sum\; a\_\{i\}D\_\{i\}$, with $a\_\{i\}$ complex.{{harvnb|Camion|1998}}{{harvnb|Delsarte|Levenshtein|1998}}

The definition of an association scheme is equivalent to saying that the $D\_\{i\}$ are v × v (0,1)-matrices which satisfy

1. $D\_i$ is symmetric,
2. $\backslash sum\_\{i=0\}^n\; D\_\{i\}=J$ (the all-ones matrix),
3. $D\_0=I,$
4. $D\_i\; D\_j\; =\; \backslash sum\_\{k=0\}^n\; p^k\_\{ij\}\; D\_k\; =\; D\_j\; D\_i,\backslash qquad\; i,j=0,\backslash ldots,n.$

The (x,y)-th entry of the left side of 4. is the number of two colored paths of length two joining x and y (using "colors" i and j) in the graph. Note that the rows and columns of $D\_i$ contain $v\_i$ 1s:

: $D\_i\; J=J\; D\_i\; =\; v\_i\; J.\; \backslash qquad\; (2)$

From 1., these matrices are symmetric. From 2., $D\_\{0\},\backslash ldots,D\_\{n\}$ are linearly independent, and the dimension of $\backslash mathcal\{A\}$ is $n+1$. From 4., $\backslash mathcal\{A\}$ is closed under multiplication, and multiplication is always associative. This associative commutative algebra $\backslash mathcal\{A\}$ is called the Bose–Mesner algebra of the association scheme. Since the matrices in $\backslash mathcal\{A\}$ are symmetric and commute with each other, they can be simultaneously diagonalized. This means that there is a matrix $S$ such that to each $A\backslash in\backslash mathcal\{A\}$ there is a diagonal matrix $\backslash Lambda\_\{A\}$ with $S^\{-1\}A\; S=\backslash Lambda\_\{A\}$. This means that $\backslash mathcal\{A\}$ is semi-simple and has a unique basis of primitive idempotents $J\_\{0\},\backslash ldots,J\_\{n\}$. These are complex n × n matrices satisfying

: $$

J_i^2 =J_i, i=0,\ldots,n, \qquad (3)

: $$

J_i J_k=0, i\neq k, \qquad (4)

: $$

\sum_{i=0}^n J_i = I. \qquad (5)

The Bose–Mesner algebra has two distinguished bases: the basis consisting of the adjacency matrices $D\_i$, and the basis consisting of the irreducible idempotent matrices $J\_k$. By definition, there exist well-defined complex numbers such that

: $D\_\{i\}=\backslash sum\_\{k=0\}^n\; p\_i\; (k)\; J\_k,\; \backslash qquad\; (6)$

and

: $$

|X|J_{k}=\sum_{i=0}^n q_k\left(i\right)D_i. \qquad (7)

The p-numbers $p\_i\; (k)$, and the q-numbers $q\_k(i)$, play a prominent role in the theory.{{harvnb|Camion|1998}} They satisfy well-defined orthogonality relations. The p-numbers are the eigenvalues of the adjacency matrix $D\_i$.

The eigenvalues of $p\_i(k)$ and $q\_k(i)$, satisfy the orthogonality conditions:

: $$

\sum_{k=0}^n \mu_i p_i (k)p_\ell (k)=v v_i \delta_{i \ell}, \quad(8)

: $$

\sum_{k=0}^n \mu_i q_k (i) q_\ell (i)=v \mu_k \delta_{k \ell}. \quad(9)

Also

: $$

\mu_j p_i (j) = v_i q_ j (i),\quad i,j=0,\ldots,n. \quad(10)

In matrix notation, these are

: $$

P^T \Delta_\mu P=v\Delta_v, \quad(11)

: $$

Q^T \Delta_v Q=v\Delta_\mu, \quad(12)

where $\backslash Delta\_v\; =\; \backslash operatorname\{diag\}\; \backslash \{v\_0,v\_1,\backslash ldots,v\_n\backslash \},\backslash qquad\; \backslash Delta\_\backslash mu\; =\; \backslash operatorname\{diag\}\; \backslash \{\backslash mu\_0,\backslash mu\_1,\backslash ldots,\backslash mu\_n\backslash \}.$

The eigenvalues of $D\_i\; D\_\backslash ell$ are $p\_i\; (k)p\_\backslash ell\; (k)$ with multiplicities $\backslash mu\_k$. This implies that

: $$

v v_i \delta_{i\ell} = \operatorname{trace}D_i D_\ell = \sum_{k=0}^n \mu_i p_i(k) p_\ell (k), \quad(13)

which proves Equation $\backslash left(8\backslash right)$ and Equation $\backslash left(11\backslash right)$,

: $$

Q = v P^{-1} = \Delta_v^{-1} P^T \Delta_\mu, \quad(14)

which gives Equations $(9)$, $(10)$ and $(12)$.$\backslash Box$

There is an analogy between extensions of association schemes and extensions of finite fields. The cases we are most interested in are those where the extended schemes are defined on the $n$-th Cartesian power $X=\backslash mathcal\{F\}^\{n\}$ of a set $\backslash mathcal\{F\}$ on which a basic association scheme $\backslash left(\backslash mathcal\{F\},K\backslash right)$ is defined. A first association scheme defined on $X=\backslash mathcal\{F\}^\{n\}$ is called the $n$-th Kronecker power $\backslash left(\backslash mathcal\{F\},K\backslash right)\_\{\backslash otimes\}^\{n\}$ of $\backslash left(\backslash mathcal\{F\},K\backslash right)$. Next the extension is defined on the same set $X=\backslash mathcal\{F\}^\{n\}$ by gathering classes of $\backslash left(\backslash mathcal\{F\},K\backslash right)\_\{\backslash otimes\}^\{n\}$. The Kronecker power corresponds to the polynomial ring $F\backslash left[X\backslash right]$ first defined on a field $\backslash mathbb\{F\}$, while the extension scheme corresponds to the extension field obtained as a quotient. An example of such an extended scheme is the Hamming scheme.

Association schemes may be merged, but merging them leads to non-symmetric association schemes, whereas all usual codes are subgroups in symmetric Abelian schemes.{{harvnb|Delsarte|Levenshtein|1998}}{{harvnb|Camion|1998}}{{harvnb|MacWilliams|Sloane|1978}}

• Association scheme

{{More footnotes|date=September 2010}}

{{Reflist}}

• {{citation|first=Rosemary A.|last=Bailey|author-link=Rosemary A. Bailey|url=http://www.maths.qmul.ac.uk/~rab/Asbook |title=Association schemes: Designed experiments, algebra and combinatorics|series=Cambridge Studies in Advanced Mathematics|volume=84|publisher=Cambridge University Press|year=2004|pages=387|isbn=978-0-521-82446-0| mr=2047311}}
• {{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}}
• {{citation | last1=Bannai | first1=Etsuko |year=2001 |title=Bose–Mesner algebras associated with four-weight spin models|journal=Graphs and Combinatorics|volume=17|issue=4|pages=589–598|doi=10.1007/PL00007251| s2cid=41255028 }}
• {{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|doi-access=free}}
• {{citation|last1=Cameron|first1=P. J.|last2=van Lint|first2=J. H.|title=Designs, Graphs, Codes and their Links|year=1991|publisher=Cambridge University Press|location=Cambridge|isbn=0-521-42385-6|url-access=registration|url=https://archive.org/details/designsgraphscod0000came}}
• {{citation|last1= Camion|first1=P.|authorlink1=Paul Camion|chapter=Codes and association schemes: Basic properties of association schemes relevant to coding| title=Handbook of coding theory|editor1-last= Pless|editor1-first=V. S.|editor1-link=Vera Pless|editor2-last=Huffman|editor2-first=W. C.|publisher=Elsevier|place= The Netherlands|year= 1998}}
• {{citation|last1=Delsarte|first1=P.|last2=Levenshtein|first2=V. I.|authorlink2=Vladimir Levenshtein|title=Association schemes and coding theory|journal=IEEE Transactions on Information Theory| volume= 44| issue= 6|pages= 2477–2504|year= 1998|doi=10.1109/18.720545}}
• {{citation| first1=F. J.|last1= MacWilliams|first2=N. J. A.|last2= Sloane|authorlink2=Neil J. A. Sloane|title=The theory of error-correcting codes|publisher= Elsevier|place= New York|year= 1978}}
• {{citation|last=Nomura|first= K.|year=1997|title=An algebra associated with a spin model|journal=Journal of Algebraic Combinatorics|volume=6|issue=1|pages= 53–58|doi=10.1023/A:1008644201287|doi-access=free}}

{{Experimental design|state=expanded}}

{{DEFAULTSORT:Bose-Mesner Algebra}}

Category:Algebraic combinatorics

Category:Design of experiments

Category:Analysis of variance

Category:Representation theory

Category:Algebra