Bose–Mesner algebra

In mathematics, a Bose–Mesner algebra is a special set of matrices which arise from a combinatorial structure known as an association scheme, together with the usual set of rules for combining (forming the products of) those matrices, such that they form an associative algebra, or, more precisely, a unitary commutative algebra. Among these rules are:

  • the result of a product is also within the set of matrices,
  • there is an identity matrix in the set, and
  • taking products is commutative.

Bose–Mesner algebras have applications in physics to spin models, and in statistics to the design of experiments. They are named for R. C. Bose and Dale Marsh Mesner.[1]

DefinitionEdit

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

  • given an  , the number of   such that   depends only on i (and not on x). This number will be denoted by vi, and
  • given   with  , the number of   such that   and   depends only on i,j and k (and not on x and y). This number will be denoted by  .

This structure is enhanced by adding all pairs of repeated elements of X and collecting them in a subset R0. 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.[2] 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 Di defined by:

 

Let   be the vector space consisting of all matrices  , with   complex.[3][4]

The definition of an association scheme is equivalent to saying that the   are v × v (0,1)-matrices which satisfy

  1.   is symmetric,
  2.   (the all-ones matrix),
  3.  
  4.  

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   contain   1s:

 

From 1., these matrices are symmetric. From 2.,   are linearly independent, and the dimension of   is  . From 4.,   is closed under multiplication, and multiplication is always associative. This associative commutative algebra   is called the Bose–Mesner algebra of the association scheme. Since the matrices in   are symmetric and commute with each other, they can be simultaneously diagonalized. This means that there is a matrix   such that to each   there is a diagonal matrix   with  . This means that   is semi-simple and has a unique basis of primitive idempotents  . These are complex n × n matrices satisfying

 
 
 

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

 

and

 

The p-numbers  , and the q-numbers  , play a prominent role in the theory.[5] They satisfy well-defined orthogonality relations. The p-numbers are the eigenvalues of the adjacency matrix  .

TheoremEdit

The eigenvalues of   and  , satisfy the orthogonality conditions:

 
 

Also

 

In matrix notation, these are

 
 

where  

Proof of theoremEdit

The eigenvalues of   are   with multiplicities  . This implies that

 

which proves Equation   and Equation  ,

 

which gives Equations  ,   and  . 

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  -th Cartesian power   of a set   on which a basic association scheme   is defined. A first association scheme defined on   is called the  -th Kronecker power   of  . Next the extension is defined on the same set   by gathering classes of  . The Kronecker power corresponds to the polynomial ring   first defined on a field  , 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.[6][7][8]

See alsoEdit

NotesEdit

ReferencesEdit

  • Bailey, Rosemary A. (2004), Association schemes: Designed experiments, algebra and combinatorics, Cambridge Studies in Advanced Mathematics, 84, Cambridge University Press, p. 387, ISBN 978-0-521-82446-0, MR 2047311CS1 maint: ref=harv (link)
  • Bannai, Eiichi; Ito, Tatsuro (1984), Algebraic combinatorics I: Association schemes, Menlo Park, CA: The Benjamin/Cummings Publishing Co., Inc., pp. xxiv+425, ISBN 0-8053-0490-8, MR 0882540
  • Bannai, Etsuko (2001), "Bose–Mesner algebras associated with four-weight spin models", Graphs and Combinatorics, 17 (4): 589–598, doi:10.1007/PL00007251
  • Bose, R. C.; Mesner, D. M. (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 2237117, MR 0102157
  • Cameron, P. J.; van Lint, J. H. (1991), Designs, Graphs, Codes and their Links, Cambridge: Cambridge University Press, ISBN 0-521-42385-6
  • Camion, P. (1998), "Codes and association schemes: Basic properties of association schemes relevant to coding", in Pless, V. S.; Huffman, W. C. (eds.), Handbook of coding theory, The Netherlands: Elsevier
  • Delsarte, P.; Levenshtein, V. I. (1998), "Association schemes and coding theory", IEEE Transactions on Information Theory, 44 (6): 2477–2504, doi:10.1109/18.720545
  • MacWilliams, F. J.; Sloane, N. J. A. (1978), The theory of error-correcting codes, New York: Elsevier
  • Nomura, K. (1997), "An algebra associated with a spin model", Journal of Algebraic Combinatorics, 6 (1): 53–58, doi:10.1023/A:1008644201287