Association scheme
Encyclopedia
The theory of association schemes arose in statistics, in the theory of experimental design
for the analysis of variance
. 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
. In algebra, association schemes generalize group
s, and the theory of association schemes generalizes the character theory of linear representations
of groups.
(i.e. a relation on X) which satisfy:
Some authors assume commutativity in the definition:
Note, however, that the notion of association scheme generlizes the notion of a group, while the notion of a commutative association scheme only generalizes the notion of a commutative group.
Two points x and y are called ith associates if
. The definition states that if x and y are ith associates so are y and x. Every pair of points are ith associates for exactly one 
. Each point is its own zeroth associate while distinct points are never zeroth associates. If x and y are kth associates then the number of points 
which are both 
-th associates of 
and 
-th associates of 
is a constant 
.
with labeled edges. The graph has
vertices, one for each point of 
, and the edge joining vertices 
and 
is labeled 
if 
and 
are 
-th associates. Each edge has a unique label, and the number of triangles with a fixed base labeled 
having the other edges labeled 
and 
is a constant 
, depending on 
but not on the choice of the base. In particular, each vertex is incident with exactly 
edges labeled 
; 
is the valency of the relation
. There are also loops labeled 
at each vertex 
, corresponding to 
.
The relations
are described by their adjacency matrices
.
is the adjacency matrix
of
for 
and is a 
matrix
with rows and columns labeled by the points of
.
The definition of an association scheme is equivalent to saying that the
are 
-matrices
which satisfy
The
-th entry of the left side of (IV) is the number of paths in the graph. Note that the rows and columns of 
contain 
's:
on a set 
can be thought of as subset
of
.
A k-class association scheme is a set of points, X, along with k + 1 binary relation
s
which partition
and 
(i.e. 
is the identity relation), such that the following holds:
There exist
non-negative integer
s
with 
and for any 
there
are exactly
elements 
such that 
and 
An association scheme is "commutative" if
for all 
, 
and 
. Most authors
assume this property.
A symmetric association scheme is one in which each relation
is a symmetric relation
. Every symmetric association scheme is commutative.
of the graphs
generate a commutative
and associative algebra
(over the real or complex number
s) both for the matrix product and the pointwise product
. 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 diagonalized
simultaneously. Therefore
is semi-simple and has a unique basis of primitive idempotents 
.
There is another algebra
of
matrices
which is isomorphic to
, and is often easier to work with.
and the Johnson scheme are of major significance in classical coding theory
.
In coding theory
, association scheme theory is mainly concerned with the distance
of a code
. The linear programming
method produces upper bounds for the size of a code
with given minimum distance
, and lower bounds for the size of a 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 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 matrices
of the Hamming scheme
.
Design of experiments
In general usage, design of experiments or experimental design is the design of any information-gathering exercises where variation is present, whether under the full control of the experimenter or not. However, in statistics, these terms are usually used for controlled experiments...
for the analysis of variance
Analysis of variance
In statistics, analysis of variance is a collection of statistical models, and their associated procedures, in which the observed variance in a particular variable is partitioned into components attributable to different sources of variation...
. In mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, association schemes belong to both algebra
Algebra
Algebra is the branch of mathematics concerning the study of the rules of operations and relations, and the constructions and concepts arising from them, including terms, polynomials, equations and algebraic structures...
and combinatorics
Combinatorics
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...
. Indeed, in algebraic combinatorics
Algebraic combinatorics
Algebraic combinatorics is an area of mathematics that employs methods of abstract algebra, notably group theory and representation theory, in various combinatorial contexts and, conversely, applies combinatorial techniques to problems in algebra....
, association schemes provide a unified approach to many topics, for example combinatorial design
Combinatorial design
Combinatorial design theory is the part of combinatorial mathematics that deals with the existence and construction of systems of finite sets whose intersections have specified numerical properties....
s and coding theory
Coding theory
Coding theory is the study of the properties of codes and their fitness for a specific application. Codes are used for data compression, cryptography, error-correction and more recently also for network coding...
. In algebra, association schemes generalize group
Group (mathematics)
In mathematics, a group is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element. To qualify as a group, the set and the operation must satisfy a few conditions called group axioms, namely closure, associativity, identity...
s, and the theory of association schemes generalizes the character theory of linear representations
Group representation
In the mathematical field of representation theory, group representations describe abstract groups in terms of linear transformations of vector spaces; in particular, they can be used to represent group elements as matrices so that the group operation can be represented by matrix multiplication...
of groups.
Definition
An association scheme consists of a set X together with a partition S of (i.e. a relation on X) which satisfy:- For every x, y ∈ X, (x, y) ∈ Ri for exactly one Ri in S.
is an element of S, called the identity relationRelation (mathematics)In set theory and logic, a relation is a property that assigns truth values to k-tuples of individuals. Typically, the property describes a possible connection between the components of a k-tuple...
.- Defining
, if R in S, then R* in S - If
, the number of 
such that 
and 
is a constant 
depending on 
, 
, 
but not on the particular choice of 
and 
.
Some authors assume commutativity in the definition:
- if (x,y) ∈ Ri, then (y,x) ∈ Ri . (Or equivalently, R*=R.)
Note, however, that the notion of association scheme generlizes the notion of a group, while the notion of a commutative association scheme only generalizes the notion of a commutative group.
Two points x and y are called ith associates if
. The definition states that if x and y are ith associates so are y and x. Every pair of points are ith associates for exactly one . Each point is its own zeroth associate while distinct points are never zeroth associates. If x and y are kth associates then the number of points which are both -th associates of and -th associates of is a constant .Graph interpretation and adjacency matrices
An association scheme is visualized as a complete graphComplete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:...
with labeled edges. The graph has
vertices, one for each point of , and the edge joining vertices and is labeled if and are -th associates. Each edge has a unique label, and the number of triangles with a fixed base labeled having the other edges labeled and is a constant , depending on but not on the choice of the base. In particular, each vertex is incident with exactly edges labeled ; is the valency of the relationRelation (mathematics)
In set theory and logic, a relation is a property that assigns truth values to k-tuples of individuals. Typically, the property describes a possible connection between the components of a k-tuple...
. There are also loops labeled at each vertex , corresponding to .The relations
Relation (mathematics)
In set theory and logic, a relation is a property that assigns truth values to k-tuples of individuals. Typically, the property describes a possible connection between the components of a k-tuple...
are described by their adjacency matrices
Adjacency matrix
In mathematics and computer science, an adjacency matrix is a means of representing which vertices of a graph are adjacent to which other vertices...
.
is the adjacency matrixAdjacency matrix
In mathematics and computer science, an adjacency matrix is a means of representing which vertices of a graph are adjacent to which other vertices...
of
for and is a matrixMatrix (mathematics)
In mathematics, a matrix is a rectangular array of numbers, symbols, or expressions. The individual items in a matrix are called its elements or entries. An example of a matrix with six elements isMatrices of the same size can be added or subtracted element by element...
with rows and columns labeled by the points of
.The definition of an association scheme is equivalent to saying that the
are -matricesMatrix (mathematics)
In mathematics, a matrix is a rectangular array of numbers, symbols, or expressions. The individual items in a matrix are called its elements or entries. An example of a matrix with six elements isMatrices of the same size can be added or subtracted element by element...
which satisfy
- I.
is symmetric, - II.
, - III.
, - IV.
.
The
-th entry of the left side of (IV) is the number of paths in the graph. Note that the rows and columns of contain 's:A more technical definition
Recall that a binary relationBinary relation
In mathematics, a binary relation on a set A is a collection of ordered pairs of elements of A. In other words, it is a subset of the Cartesian product A2 = . More generally, a binary relation between two sets A and B is a subset of...
on a set can be thought of as subsetSubset
In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...
of
.A k-class association scheme is a set of points, X, along with k + 1 binary relation
Binary relation
In mathematics, a binary relation on a set A is a collection of ordered pairs of elements of A. In other words, it is a subset of the Cartesian product A2 = . More generally, a binary relation between two sets A and B is a subset of...
s
which partition
and (i.e. is the identity relation), such that the following holds:There exist
non-negative integerInteger
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
s
with and for any thereare exactly
elements such that and An association scheme is "commutative" if
for all , and . Most authorsassume this property.
A symmetric association scheme is one in which each relation
is a symmetric relationSymmetric relation
In mathematics, a binary relation R over a set X is symmetric if it holds for all a and b in X that if a is related to b then b is related to a.In mathematical notation, this is:...
. Every symmetric association scheme is commutative.
Terminology
- If
we say that 
and 
are ith associates. - The numbers
are called the parameters of the scheme.
Basic facts
, i.e. if 
then 
and the only 
such that 
is 
, this is because the 
partition 
.
The Bose–Mesner algebra
The adjacency matricesAdjacency matrix
In mathematics and computer science, an adjacency matrix is a means of representing which vertices of a graph are adjacent to which other vertices...
of the graphsGraph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
generate a commutativeCommutativity
In mathematics an operation is commutative if changing the order of the operands does not change the end result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it...
and associative algebra
Algebra
Algebra is the branch of mathematics concerning the study of the rules of operations and relations, and the constructions and concepts arising from them, including terms, polynomials, equations and algebraic structures...
(over the real or complex numberComplex number
A complex number is a number consisting of a real part and an imaginary part. Complex numbers extend the idea of the one-dimensional number line to the two-dimensional complex plane by using the number line for the real part and adding a vertical axis to plot the imaginary part...
s) both for the matrix product and the pointwise product
Pointwise product
The pointwise product of two functions is another function, obtained by multiplying the image of the two functions at each value in the domain...
. This associative
Associative algebra
In mathematics, an associative algebra A is an associative ring that has a compatible structure of a vector space over a certain field K or, more generally, of a module over a commutative ring R...
, commutative algebra
Commutative algebra
Commutative algebra is the branch of abstract algebra that studies commutative rings, their ideals, and modules over such rings. Both algebraic geometry and algebraic number theory build on commutative algebra...
is called the Bose–Mesner algebra
Bose–Mesner algebra
In mathematics, a Bose–Mesner algebra is a set of matrices, together with set of rules for combining those matrices, such that certain conditions apply...
of the association scheme.
Since the matrices
Matrix (mathematics)
In mathematics, a matrix is a rectangular array of numbers, symbols, or expressions. The individual items in a matrix are called its elements or entries. An example of a matrix with six elements isMatrices of the same size can be added or subtracted element by element...
in
are symmetric and commuteCommutativity
In mathematics an operation is commutative if changing the order of the operands does not change the end result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it...
with each other, they can be diagonalized
Diagonal matrix
In linear algebra, a diagonal matrix is a matrix in which the entries outside the main diagonal are all zero. The diagonal entries themselves may or may not be zero...
simultaneously. Therefore
is semi-simple and has a unique basis of primitive idempotents .There is another algebra
Algebra
Algebra is the branch of mathematics concerning the study of the rules of operations and relations, and the constructions and concepts arising from them, including terms, polynomials, equations and algebraic structures...
of
matricesMatrix (mathematics)
In mathematics, a matrix is a rectangular array of numbers, symbols, or expressions. The individual items in a matrix are called its elements or entries. An example of a matrix with six elements isMatrices of the same size can be added or subtracted element by element...
which is isomorphic to
, 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
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 schemeHamming schemeThe Hamming scheme, named after Richard Hamming, is also known as the hyper-cubic association scheme, and it is the most important example for coding theory...
, denoted H(n,q), is defined as follows. The points of H(n,q) are the qn ordered n-tupleTupleIn mathematics and computer science, a tuple is an ordered list of elements. In set theory, an n-tuple is a sequence of n elements, where n is a positive integer. There is also one 0-tuple, an empty sequence. An n-tuple is defined inductively using the construction of an ordered pair...
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 graphDistance-regular graphIn mathematics, a distance-regular graph is a regular graph such that for any two vertices v and w at distance i the number of vertices adjacent to w and at distance j from v is the same. Every distance-transitive graph is distance-regular...
, G, forms an association scheme by defining two vertices to be i th associates if their distance is i.
- A finite groupFinite groupIn mathematics and abstract algebra, a finite group is a group whose underlying set G has finitely many elements. During the twentieth century, mathematicians investigated certain aspects of the theory of finite groups in great depth, especially the local theory of finite groups, and the theory of...
G yields an association scheme on
, with a class Rg for each group element, as follows: for each 
let 
where 
is the group operationOperation (mathematics)The general operation as explained on this page should not be confused with the more specific operators on vector spaces. For a notion in elementary mathematics, see arithmetic operation....
. The class of the group identity is R0. This association scheme is commutative if and only if G is abelianAbelian groupIn abstract algebra, an abelian group, also called a commutative group, is a group in which the result of applying the group operation to two group elements does not depend on their order . Abelian groups generalize the arithmetic of addition of integers...
.
Coding theory
The Hamming schemeHamming scheme
The Hamming scheme, named after Richard Hamming, is also known as the hyper-cubic association scheme, and it is the most important example for coding theory...
and the Johnson scheme are of major significance in classical coding theory
Coding theory
Coding theory is the study of the properties of codes and their fitness for a specific application. Codes are used for data compression, cryptography, error-correction and more recently also for network coding...
.
In coding theory
Coding theory
Coding theory is the study of the properties of codes and their fitness for a specific application. Codes are used for data compression, cryptography, error-correction and more recently also for network coding...
, association scheme theory is mainly concerned with the distance
Hamming distance
In information theory, the Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different...
of a code
Code
A code is a rule for converting a piece of information into another form or representation , not necessarily of the same type....
. The linear programming
Linear programming
Linear programming is a mathematical method for determining a way to achieve the best outcome in a given mathematical model for some list of requirements represented as linear relationships...
method produces upper bounds for the size of a code
Code
A code is a rule for converting a piece of information into another form or representation , not necessarily of the same type....
with given minimum distance
Hamming distance
In information theory, the Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different...
, and lower bounds for the size of a design
T-design
In combinatorial mathematics, a block design is a set together with a family of subsets whose members are chosen to satisfy some set of properties that are deemed useful for a particular application. These applications come from many areas, including experimental design, finite geometry, software...
with a given strength. The most specific results are obtained in the case where the underlying association scheme satisfies certain polynomial
Polynomial
In mathematics, a polynomial is an expression of finite length constructed from variables and constants, using only the operations of addition, subtraction, multiplication, and non-negative integer exponents...
properties; this leads one into the realm of orthogonal polynomials
Orthogonal polynomials
In mathematics, the classical orthogonal polynomials are the most widely used orthogonal polynomials, and consist of the Hermite polynomials, the Laguerre polynomials, the Jacobi polynomials together with their special cases the ultraspherical polynomials, the Chebyshev polynomials, and the...
. In particular, some universal bounds are derived for code
Code
A code is a rule for converting a piece of information into another form or representation , not necessarily of the same type....
s and designs
T-design
In combinatorial mathematics, a block design is a set together with a family of subsets whose members are chosen to satisfy some set of properties that are deemed useful for a particular application. These applications come from many areas, including experimental design, finite geometry, software...
in polynomial-type association schemes.
In classical coding theory
Coding theory
Coding theory is the study of the properties of codes and their fitness for a specific application. Codes are used for data compression, cryptography, error-correction and more recently also for network coding...
, dealing with code
Code
A code is a rule for converting a piece of information into another form or representation , not necessarily of the same type....
s in a Hamming scheme
Hamming scheme
The Hamming scheme, named after Richard Hamming, is also known as the hyper-cubic association scheme, and it is the most important example for coding theory...
, the MacWilliams transform involves a family of orthogonal polynomials known as the Krawtchouk polynomials. These polynomials give the eigenvalues of the distance relation matrices
Matrix (mathematics)
In mathematics, a matrix is a rectangular array of numbers, symbols, or expressions. The individual items in a matrix are called its elements or entries. An example of a matrix with six elements isMatrices of the same size can be added or subtracted element by element...
of the Hamming scheme
Hamming scheme
The Hamming scheme, named after Richard Hamming, is also known as the hyper-cubic association scheme, and it is the most important example for coding theory...
.
See also
- Block design
- Bose-Mesner algebra
- Combinatorial designCombinatorial designCombinatorial design theory is the part of combinatorial mathematics that deals with the existence and construction of systems of finite sets whose intersections have specified numerical properties....
- Randomized block designRandomized block designIn the statistical theory of the design of experiments, blocking is the arranging of experimental units in groups that are similar to one another. Typically, a blocking factor is a source of variability that is not of primary interest to the experimenter...
- Spherical designSpherical designA spherical design, part of combinatorial design theory in mathematics, is a finite set of N points on the d-dimensional unit hypersphere Sd such that the average value of any polynomial f of degree t or less on the set equals the average value of f on the whole sphere...