INTRODUCTION TO ASSOCIATION SCHEMES

J.J. Seidel Fakulteit Wiskunde en Informatica Techn. Univ. Eindhoven NL-5644 HK Eindhoven The Netherlands

Abstract The present paper gives an introduction to the theory of association schemes, following Bose-Mesner (1959), Biggs (1974), Delsarte (1973), Bannai-Ito (1984) and Brouwer-Cohen-Neumaier (1989). Apart from definitions and many examples, also several proofs and some problems are included. The paragraphs have the following titles:

1. Introduction 5. Representations

2. Distance regular graphs 6. Root lattices

3. Minimal idempotents 7. Generalizations

4. A-modules 8. References

§1. Introduction An ordinary graph on n vertices (symmetric relation Γ on an n-set Ω) is described by its symmetric n × n adjacency matrix A. We paint the edges of the complete graph on n vertices in s colours:

J − I = A_{1} + A_{2} + ... + A_{s} ,

and require that the vector space

A = ⟨A_{0} = I, A_{1}, A_{2}, ..., A_{s}⟩_{ℝ}

is a symmetric algebra w.r.t. matrix multiplication, that is,

A_{i}A_{j} = A_{j}A_{i} = ∑_{k=0}^{s} a_{ij}^{k}A_{k} ; i, j = 0, 1, ..., s .

We call this algebra the Bose-Mesner algebra of the s-association scheme (Ω,{id,Γ_{1}, Γ_{2}, ..., Γ_{s}}), where colour i corresponds to relation (graph) Γ_{i} and adjacency matrix A_{i}. The intersection numbers a_{ij}^{k} and the valencies v_{i} = a_{ii}^{0} have the following interpretation:

[figure: ∘; w; ∘; w’; Γ_{k}; Γ_{i}; Γ_{j}; ♯a_{ij}^{k}; ∘; w; Γ_{i}; ♯v_{i}]

These notions go back to Bose and Mesner (1959).

\underline{Example 1}. A strongly regular graph is a 2-association scheme, where A_{1} and A_{2} denote the adjacency matrices of the graph and its complement.

In the next example we use the distance ∂(u, v) of the vertices u and v of a graph, and the relations Γ_{i}, defined by {u, v} ∈ Γ_{i} iff ∂(u, v) = i, for i = 0, 1, ..., d = diameter.

\underline{Example 2}. The hexagon

[figure: ∘; 1; ∘; 4; ∘; 6; ∘; 2; ∘; 5; ∘; 3]

gives rise to a 3-association scheme, since the distance i matrices A_{i} read:

A_{1} = [ \begin{matrix}0 & J − I \\ J − I & 0 \end{matrix} ] , A_{2} = [ \begin{matrix}J − I & 0 \\ 0 & J − I \end{matrix} ] , A_{3} = [ \begin{matrix}0 & I \\ I & 0 \end{matrix} ] .

\underline{Problem}. Prove that the distance relations in the cube graph form a 3-association scheme. Determine the valencies and the intersection numbers.

\underline{Example 3} Hamming scheme H(v, 𝔽_{2}). Consider Ω := (𝔽_{2})^{v} with Hamming distance ∂_{H}(x, y), that is, the number of coordinates in which x and y ∈ Ω differ. Denote by Γ_{i} the relation

{x, y} ∈ Γ_{i} iff ∂_{H}(x, y) = i .

Then we have a v-association scheme with

n = 2^{v} , v_{i} = ( \begin{matrix}v \\ i \end{matrix} ) , a_{ij}^{k} = ( \begin{matrix}k \\ \frac{1}{2} (i − j + k) \end{matrix} ) ( \begin{matrix}v − k \\ \frac{1}{2} (i + j − k) \end{matrix} ) .

\underline{Example 4} Johnson scheme J(v, k). Take Ω the set of all k-subsets of a v-set, and {w, w′} ∈ Γ_{i} iff |w ∩ w′| = k − i. Then

n = ( \begin{matrix}v \\ k \end{matrix} ) , v_{i} = ( \begin{matrix}k \\ i \end{matrix} ) ( \begin{matrix}v − k \\ i \end{matrix} ) .

In an association scheme (Ω, {Γ_{i}}) we will be interested in special subsets X ⊂ Ω, for instance:

– blue cliques X : only blue edges in X,

– blue cocliques X : no blue edges in X,

– code X at min. distance δ : no Γ_{1}, Γ_{2}, ..., Γ_{δ−1} in X,

– few-distance sets X in ℝ^{d}, etc., etc.

The problem then will be to find bounds for the cardinality |X| of the special subsets X ⊂ Ω, and to investigate the case of equality.

§2. Distance-regular graphs In a graph Γ = (Ω, E) of diameter d we define:

distance ∂(u, v) = length of shortest path between u, v ∈ Ω ,

Γ_{i}(u) := {x ∈ Ω : ∂(x, u) = i} , |Γ_{i}(u)| =: k_{i} .

\underline{Definition}. A graph Γ is distance regular if for all u ∈ Ω, for i = 0, 1, 2, ..., d,

each v ∈ Γ_{i}(u) has c_{i} neighbours in Γ_{i−1}(u) ,
has b_{i} neighbours in Γ_{i+1}(u) ,
has a_{i} neighbours in Γ_{i}(u) .

[figure: k; k_{2}; k_{i−1}; k_{i}; k_{i+1}; k_{d}; λ; a_{2}; a_{i−1}; a_{i}; a_{i+1}; a_{d}; Γ_{1}(u); Γ_{2}(u); Γ_{i−1}(u); Γ_{i}(u); Γ_{i+1}(u); Γ_{d}(u); b_{1}; b_{2}; b_{i−1}; b_{i}; b_{i+1}; 1; c_{2}; c_{i−1}; c_{i}; c_{i+1}; c_{d}; u; ∘; …; …]

Then

a_{i} + b_{i} + c_{i} = k , k_{i+1}c_{i+1} = k_{i}b_{i} , b_{0} = k , c_{1} = 1 , a_{1} = λ .

So the independent parameters are

{k = b_{0}, b_{1}, b_{2}, ..., b_{d−1} ; 1 = c_{1}, c_{2}, ..., c_{d}} .

It is convenient to arrange the parameters into the (d + 1) × (d + 1) tridiagonal matrix T:

T := [ \begin{matrix}0 & k \\ c_{1} & a_{1} & b_{1} \\ & c_{2} & a_{2} & b_{2} \\ & & c_{3} & a_{3} & ... \\ & & & c_{4} & ... \\ . & . & . \\ & & & & & ... & b_{d−1} \\ & & & & & c_{d} & a_{d} \end{matrix} ] .

The definition of distance-regularity translates in terms of the n × n distance i matrices A_{i}, which are defined by

A_{i}(x, y) = 1 if ∂(x, y) = i , = 0 otherwise. (So A_{1} = A, A_{0} = I.)

\underline{Theorem}. Γ is distance regular iff, for 1 ≤ i ≤ d − 1,

AA_{i} = b_{i−1}A_{i−1} + a_{i}A_{i} + c_{i+1}A_{i+1} .

\underline{Proof}.

(AA_{i})(x, y) = # {z ∈ Ω : ∂(x, z) = 1, ∂(y, z) = i} .

There are such z only if ∂(x, y) = i − 1, i, i + 1 , and their numbers are b_{i−1}, a_{i}, c_{i+1}, respectively. □

\underline{Corollary}. In a distance regular graph the distance i matrices A_{i} are polynomials p_{i} of degree i in the adjacency matrix A, for i = 0, 1, ..., d.

\underline{Proof}. By recursive application of the theorem. □

\underline{Corollary}. For a distance regular graph of diameter d, the distance i relations constitute a d-association scheme.

\underline{Proof}. Conversely to A_{i} = p_{i}(A), deg p_{i} = i, the powers I, A, A^{2}, ..., A^{d} are linear combinations of A_{0}, A_{1}, ..., A_{d}. This implies that ⟨A_{0} = I, A_{1} = A, A_{2}, ..., A_{d}⟩_{ℝ} is a Bose-Mesner algebra. □

\underline{Example}. The distance 1 relation in the Hamming scheme H(d, 𝔽_{2}) defines a distance regular graph. The vertices are the vectors of 𝔽_{2}^{d}, two vertices being adjacent whenever they differ in one coordinate. Hence

k = d , c_{i} = i , b_{i} = d − i , k_{i} = ( \begin{matrix}d \\ i \end{matrix} ) .

\underline{Problem}. Find the parameters b_{i} and c_{i} for the distance regular graph formed by the d-subsets of an n-set, n ≥ 2d, adjacency whenever two d-subsets differ in one element.

The tridiagonal matrix T, of size d + 1, is useful for eigenvalues.

\underline{Lemma}. The eigenvalues of A are those of T (not counting multiplicities).

\underline{Proof}. Let λ be an eigenvalue of A. Then A_{i} = p_{i}(A) has the eigenvalue p_{i}(λ).

The theorem implies

λp_{i}(λ) = b_{i−1}p_{i−1}(λ) + a_{i}p_{i}(λ) + c_{i+1}p_{i+1}(λ) .

But this reads

T^{t}\underline{p}(λ) = λ\underline{p}(λ) , for \underline{p}(λ) := (p_{0}(λ), p_{1}(λ), ..., p_{d}(λ)) .

and λ is an eigenvalue of T^{t}, hence of T. There are d + 1 distinct eigenvalues of A, hence of T. □

Although T and T^{t} have the same eigenvalues, they do not have the same eigenvectors. We shall denote by \underline{u}(ϑ) the eigenvector of T corresponding to the eigenvalue ϑ:

T^{t}\underline{p}(λ) = λ\underline{p}(λ) ; T \underline{u}(ϑ) = ϑ\underline{u}(ϑ) ; u_{0} = p_{0} = 1 ,

hence

c_{i}u_{i−1} + a_{i}u_{i} + b_{i}u_{i+1} = ϑu_{i} ; i = 1, ..., d − 1 .

\underline{Lemma}.

(\underline{u}(ϑ), \underline{p}(λ)) = 0 , for ϑ ≠ λ .

\underline{Proof}.

ϑ(\underline{u}(ϑ), \underline{p}(λ)) = (T \underline{u}(ϑ), \underline{p}(λ)) = (\underline{u}(ϑ), T^{t}\underline{p}(λ)) = λ(\underline{u}(ϑ), \underline{p}(λ)) . □

\underline{Theorem}. Let the adjacency matrix A of a distance regular graph have the eigenvalue ϑ of multiplicity f. Let the tridiagonal T have eigenvector \underline{u}(ϑ). Then

L := \frac{f}{n} (I + u_{1}A_{1} + u_{2}A_{2} + ... + u_{d}A_{d})

is an idempotent matrix of rank f.

\underline{Proof}. If λ is any other eigenvalue of A, then the corresponding eigenvalue of L equals

\frac{f}{n} ∑_{i=0}^{d} u_{i}(ϑ)p_{i}(λ) = \frac{f}{n} (\underline{u}(ϑ), \underline{p}(λ)) = δ_{ϑ,λ} .

Indeed, the lemma gives 0 for λ ≠ ϑ. For λ = ϑ the corresponding eigenvalue of L, which also has multiplicity f, equals 1, since trace L = f. □

\underline{Remark}. The theory in this section goes back to Biggs (1974). By the present theorem a distance regular graph may be viewed as a set of vectors at equal length in ℝ^{f}, at cosines u_{i}. For certain classes of DRG this paves the way to characterization, by use of root lattices, cf. BCN (1989) and §6.

§3. Minimal idempotents We return to the general case of an association scheme with Bose-Mesner algebra

A = ⟨A_{0} = I, A_{1}, A_{2}, ..., A_{s}⟩_{ℝ} .

The commuting A_{i} are simultaneously diagonalizable, hence there exists a basis of minimal orthogonal idempotents:

A = ⟨E_{0} = \frac{1}{n} J, E_{1}, ..., E_{s}⟩_{ℝ} .

\underline{Example}. s = 2, spec A = (k^{1}, r^{f}, s^{g}).

E_{1} = \frac{1}{r − s} (A − sI − \frac{k − s}{n} J) , of rank f ,

E_{2} = \frac{1}{r − s} (rI − A + \frac{k − r}{n} J) , of rank g .

The algebra A is closed with respect to matrix multiplication. It is also closed with respect to Schur (= entry-wise) multiplication with idempotents A_{0}, A_{1}, ..., A_{s}. We have:

Matrix multiplication ·  , Schur multiplication ∘
E_{i}E_{j} = δ_{ij}E_{i}  ,  A_{i} ∘ A_{j} = δ_{ij}A_{i}
A_{i}A_{j} = ∑_{k=0}^{s} a_{ij}^{k}A_{k}  , E_{i} ∘ E_{j} = ∑_{k=0}^{s} b_{ij}^{k}E_{k}
intersection numbers a_{ij}^{k} ∈ ℕ , Krein parameters b_{ij}^{k} ≥ 0

Transition between the two bases of A:

A_{k} = ∑_{i=1}^{s} p_{ik}E_{i}  ,  E_{i} = \frac{1}{n} ∑_{k=0}^{s} q_{ki}A_{k}
A_{k}E_{i} = p_{ik}E_{i}  ,  E_{i} ∘ A_{k} = \frac{1}{n} q_{ki}A_{k}
valency v_{k} = p_{ok}  ,  multiplicity f_{i} = q_{oi}
Δ_{v} := diag(v_{k})  ,  Δ_{f} := diag(f_{i})
P = [p_{ik}], the character table , Q from P Q = nI = QP .

\underline{Theorem}.

Δ_{f}P = Q^{t}Δ_{v} .

\underline{Proof}.

f_{i}p_{ik} = p_{ik} tr E_{i} = tr A_{k}E_{i} = ∑ E_{i} ∘ A_{k} = \frac{1}{n} q_{ki} ∑ A_{k} = q_{ki}v_{k} ,

with trace MN^{t} = ∑_{elts} M ∘ N. □

\underline{Problem}. Prove the Krein inequalities b_{ij}^{k} ≥ 0, by considering E_{i} ∘ E_{j} and E_{i} ⊗ E_{j}, and by using that, for fixed i, j, the matrix E_{i} ∘ E_{j} has the eigenvalues b_{ij}^{k}.

\underline{Remark}. For strongly regular graphs the vanishing of the Krein parameter b_{11}^{1} allows the following combinatorial interpretation.

Let Γ be a strongly regular graph having b_{11}^{1} = 0. Then, for every vertex x, the subconstituents Γ(x) and Δ(x) are both strongly regular.

[figure: Γ(x); Δ(x); Γ; x; ∘]

Essentially, also the converse holds (under the assumption that Γ, Γ(x), Δ(x) are strongly regular for some vertex x). Such graphs are called Smith graphs. For r = 1, 2 they are the following unique graphs, with order and eigenvalues (n, k, r, s):

\begin{matrix}(16, 5, 1, −3) & , & (27, 10, 1, −5) & , & (100, 22, 2, −8) & , \\ (112, 30, 2, −10) & , & (162, 56, 2, −16) & , & (275, 112, 2, −28) & . \end{matrix}

The automorphism groups of these graphs are well-known groups, such as the 27 lines-group, the Higman-Sims group on 100, the McLaughlin group on 275 vertices, cf. BCN (1989).

\underline{Example}. Elimination of Q from Δ_{f}P = Q^{t}Δ_{v}, P Q = QP = nI yields

P^{t}Δ_{f}P = nΔ_{v} , ∑_{z=0}^{s} f_{z}p_{zk}p_{zl} = nv_{k}δ_{k,l} .

In the case of distance regular graphs, the

p_{zi} are (degree i)-polynomials in p_{z1} (0 ≤ i ≤ s) .

From the equations above it follows that the p_{zi} form a family of orthogonal polynomials with weights f_{z}. For the Hamming scheme H(v, 𝔽_{2}) these are the Krawchouk polynomials, for the Johnson scheme J(v, l) the dual Hahn polynomials, cf. Delsarte (1973).

\underline{Remark}. Similarly, elimination of P leads to Q-polynomial association schemes, cf. the classification theorems in Bannai-Ito (1984).

§4. The A-module V Let A be the Bose-Mesner algebra of an association scheme on Ω. Consider the vector space

V = ℝΩ = {x = ∑_{w∈Ω} x(w)w} = {f : Ω → ℝ} ,

provided with the inner product (x, y) = ∑_{w∈Ω} x(w)y(w).

A acts on V, with simultaneous eigenspaces

V = V_{0} ⊥ V_{1} ⊥ ... ⊥ V_{s} ; π_{i} : V → V_{i} ;
A_{k}V_{i} = p_{ik}V_{i} , E_{i} = Gram {π_{i}w : w ∈ Ω} .

A subset X = {w_{1}, ..., w_{m}} ⊂ {w_{1}, ..., w_{n}} = Ω is represented by its characteristic vector

x = (111..100..0) ∈ ℝΩ .

Then |X| = (x, x), |X ∩ Y | = (x, y), and the average valency of A_{k} over S is

a_{k} := \frac{(x, A_{k}x)}{(x, x)} , k = 0, 1, ..., s .

\underline{Example}. For a code X in the Hamming scheme: a_{1} = a_{2} = ... = a_{δ−1} = 0.

\underline{Theorem}.

∑_{k=0}^{s} \frac{(x, A_{k}x)}{v_{k}} A_{k} = ∑_{i=0}^{s} \frac{(x, E_{i}x)}{f_{i}} nE_{i} .

\underline{Proof}. Apply §3, then

left = ∑_{k,i,j} (x, E_{i}x)E_{j}p_{ik}p_{jk}/v_{k} = ∑_{k,i,j} (x, E_{i}x)E_{j}p_{ik}q_{kj}/f_{j} = right . □

\underline{Corollary}.

Q^{t}\underline{a} ≥ 0 , for \underline{a} = (1, a_{1}, a_{2}, ..., a_{s}) .

\underline{Proof}. Multiply the theorem by E_{i}, then

(x, x) ∑_{k=0}^{s} a_{k}q_{ki} = n(x, E_{i}x) ≥ 0 .

\underline{Remark}. The constraints Q^{t}\underline{a} ≥ 0, \underline{a} ≥ \underline{0}, and |X| = 1 + a_{1} + a_{2} + ... + a_{s}, provide a setting for the application of linear programming, cf. Delsarte (1973).

A further application is the following Code-Clique theorem.

Let T = {1, 2, ..., t} ⊂ S = {1, 2, ..., s} .

X ⊂ Ω is called a T -clique if only T -relations in X, Y ⊂ Ω is called a T -code if no T -relations in Y: (x, A_{k}x) = 0 for t < k ≤ s; (y, A_{k}y) = 0 for 1 ≤ k ≤ t .

\underline{Theorem}. |X| · |Y | ≤ |Ω| and equality iff |X ∩ Y | = 1.

\underline{Proof}.

n(x, x)(y, y) = n ∑_{k=0}^{s} (x, A_{k}x)(y, A_{k}y)/v_{k} =

= n^{2} ∑_{i=0}^{s} (x, E_{i}x)(y, E_{i}y)/f_{i} ≥ n^{2}(x, E_{0}x)(y, E_{0}y) =

= |X|^{2}|Y |^{2} .  □

\underline{Problem}. Handle the case of equality.

§5. Representations Combinatorial objects are represented as sets X of vectors in Euclidean space ℝ^{d}. The set X can be investigated by means of its Gram matrix. Another way is to confront L(X) and L(ℝ^{d}), where L denotes a linear space of certain test functions.

\underline{Theorem}. Any real symmetric semidefinite marix of rank m is the Gram matrix of n vectors in Euclidean space ℝ^{m}.

\underline{Proof}. Use diagonalization of symmetric matrices:

sym  Λ^{+} 0 0 0 n n  n  m =  =

As an \underline{example} we consider a graph Γ on n vertices, say regular of valency k, whose adjacency matrix A has smallest eigenvalue s of multiplicity n − d − 1. From A the following matrix G is constructed:

AJ = kJ , G := c(A − sI − \frac{k − s}{n} J) = [ \begin{matrix}1 & & & & α/β \\ & . & . & . \\ α/β & & & & 1 \end{matrix} ] .

Then G is symmetric, positive semidefinite of rank d, has constant diagonal (say 1) and two off-diagonal entries. By the theorem, G is the Gram matrix of a twodistance set X on the unit sphere S in Euclidean space ℝ^{d}. The following general geometric theorem has consequences for graph theory. \underline{Theorem}. Any 2-distance set X on the unit sphere S in Euclidean ℝ^{d} has cardinality at most

\frac{1}{2} d(d + 3).

\underline{Proof}. For any y ∈ X we define the polynomial

F_{y}(ξ) := \frac{((y, ξ) − α)((y, ξ) − β)}{(1 − α)(1 − β)} , ξ ∈ S .

The n polynomials in ξ ∈ S, thus obtained, have degree ≤ 2 and are independent, as a consequence of

F_{y}(x) = δ_{y,x} ; x, y ∈ X .

Therefore, their number n is at most the dimension of the space of all polynomials of degree ≤ 2 in d variables, restricted to S. This dimension equals

\frac{1}{2} d(d + 1) + d + 0 =

\frac{1}{2} d(d + 3). □

Only three examples are known for the case of equality, viz.

(n, d) = (5, 2) , (27, 6) , (275, 22) .

These 2-distance sets correspond to the pentagon graph, and the graphs of Schäfli, and McLaughlin, respectively. We illustrate the second case.

\underline{Example}. The 28 vectors (3^{2}, (−1)^{6}) in 7-space span 28 lines which are equiangular at cos φ = 1/3. Select a unit vector z along any line, then the 27 unit vectors along the other lines at cos φ = −1/3 with z determine a 2-distance set in 6-space at

cos α = 1/4 , cos β = −1/2 .

\underline{Problem}. From the Johnson scheme J(8, 2) find the Schäfli graph on 27 vertices (which corresponds to the 2-distance set just constructed). Find the parameters of the Schäfli graph.

We now turn to representation in eigenspaces. Let the real symmetric n×n matrix A have an eigenvalue ϑ of multiplicity m, and a corresponding eigenmatrix U of size n × m:

AU = ϑU , U^{t}U = I_{m} , UU^{t} = E .

Then the n × n matrix E is idempotent of rank m. The n row vectors u_{i} ∈ ℝ^{m} of the matrix U have E as their Gram matrix. Now let A be the adjacency matrix of a graph Γ = (V, A) on n vertices. Then U defines a representation of the graph in ℝ^{m}:

u : Γ → ℝ^{m} : V → U : i ↦ u_{i} .

For distance regular graphs the inner products (u_{i}, u_{j}) are determined by the distance ∂(i, j) =: r, hence

(u_{i}, u_{i}) = constant , w_{r} := \frac{(u_{i}, u_{j})}{(u_{i}, u_{i})} = cos φ_{ij} .

The adjacencies imply

ϑu_{i} = ∑_{j∼i} u_{j} , ϑ = ∑_{j∼i} \frac{(u_{i}, u_{j})}{(u_{i}, u_{i})} = kw_{1}

and the first cosines are

w_{0} = 1 , w_{1}(ϑ) = ϑ/k , w_{2}(ϑ) = (ϑ^{2} − a_{1}ϑ − k)/kb_{1} .

\underline{Theorem}. Let m > 2 denote the multiplicity of an eigenvalue of a distance regular graph. Then the valency k and the diameter d satisfy Godsil’s bound

k ≤ (m − 1)(m + 2)/2 , (d ≤ 3m − 4) .

\underline{Proof}. For any vector p of a distance regular graph let K denote the set of the neighbours of p. For any i, j ∈ K their distance ∂(i, j) equals 1 or 2, hence u(K) is a 2-distance set of k vectors in ℝ^{m−1}. Now apply the bound above to obtain the inequality for k. □

\underline{Problem}. Prove Godsil’s diameter bound.

§6. Euclidean root lattices A lattice is a free Abelian subgroup of rank d in Euclidean ℝ^{d}. The lattice is integral if the inner products of its vectors are integral, and even if its vectors have even norm (x, x). A root is a vector of norm 2. A root lattice is a lattice generated by roots. A root lattice is invariant under the reflection in the hyperplane perpendicular to any root r:

x ↦ x − 2\frac{(x, r)}{(r, r)} r = x − (x, r)r .

The Weyl group of the root lattice is the group generated by the reflections on the roots.

\underline{Theorem} (Witt). The only irreducible root lattices in ℝ^{d} are those of type A_{d}, D_{d}, E_{6}, E_{7}, E_{8}.

To explain the root systems of type D_{d} and E_{8} (which contain the others: A_{d} ⊂ D_{d+1}; E_{6}, E_{7} ⊂ E_{8}), we select an orthonormal basis e_{1}, e_{2}, ..., e_{d} in ℝ^{d}.

D_{d} := {x ∈ ℝ^{d} : x_{i} ∈ ℤ, ∑_{1}^{d} x_{i} ∈ 2ℤ} ;

the root system consists of the 2d(d − 1) vectors ± e_{i} ± e_{j} (i ≠ j), and is situated on d(d − 1) lines at 60^{∘} and 90^{∘} in ℝ^{d}.

E_{8} := ⟨D_{8}, \frac{1}{2} (e_{1} + e_{2} + ... + e_{8})⟩_{ℤ} ;

the root system consists of the 240 = 112+128 vectors ±e_{i}±e_{j} and \frac{1}{2} (± e_{1} ± e_{2} ± ... ± e_{8}) , even number of minusses, on 120 lines at 60^{∘}, 90^{∘} in ℝ^{8}.

Witt’s theorem plays a role in the proof of the following theorems, cf. CGSS (1976), Terw (1986), Neu (1985), BCN (1989).

\underline{Theorem}. All graphs having smallest eigenvalue −2 are represented in the root systems of types D_{d} and E_{8}.

\underline{Theorem}. The Hamming graphs H(d, q) for q ≠ 4, and the Johnson graphs J(d, k) for (d, k) ≠ (8, 2) are characterized by their parameters.

In order to illustrate this, we mention an ingredient used by Terwilliger:

E_{1} = \frac{1}{n} ∑_{i=0}^{d} q_{i1}A_{i} = ∑_{i=0}^{d} (a − bi)A_{i} = Gram(x, y, z, ... ∈ ℝ^{f}) .

Then

⟨ \frac{1}{\sqrt{b}} (x − y) : (x, y) ∈ A_{1}⟩_{ℤ} is a root lattice, etc.

An ingredient used by Neumaier:

G = I + u_{1}A_{1} + ... + u_{d}A_{d}

is an idempotent matrix; for

ϑ = k − λ − 2 , u_{i} = \frac{k}{λ + 2} − i ,

this leads to root lattices, etc.

§7. Generalizations We briefly indicate three recent developments which generalize the theory exposed in the present survey.

a. \underline{Coherent algebras}, cf. Higman (1987). These are subalgebras of the matrix algebra M_{n}(ℂ) which are closed under Schur multiplication, and contain J. No symmetry, commutativity, containment of I is presupposed. This leads to the earlier coherent configurations by the same author.

b. \underline{Association schemes on triples}, cf. Mesner, Bhattacharya (1990).

The paper deals with partitions of Ω × Ω × Ω into m + 1 relations R_{i}, and with 3-dimensional matrices satisfying

A_{i}A_{j}A_{k} = ∑_{l=0}^{m} p_{ijk}^{l}A_{l} .

Here the triple product D = ABC is the v × v × v matrix having the entries

D_{xyz} = ∑_{w∈Ω} A_{wyz}B_{xwz}C_{xyw} .

c. \underline{Polynomial spaces}, cf. Godsil (1988).

Ω :  J(n, k) S ⊂ ℝ^{n} Sym(n) O(n)
ρ(x, y) : |x ∩ y| (x, y) |fix x^{−1}y| tr(x^{t}y)

The paper deals with a general set-up involving linear inner-product spaces of polynomials defined on a set Ω provided with a distance function ρ : Ω×Ω → ℝ. The axioms are:

ρ(x, y) = ρ(y, x) , dim Pol(Ω, 1) < ∞ ,

and for the inner products:

⟨f, g⟩ = ⟨1, fg⟩

and

⟨1, f⟩ ≥ 0 for f ≥ 0 , = 0 iff f = 0 .

The polynomials are defined in terms of zonals ζ_{a}(f), defined by

(ζ_{a}(f))(x) := f(ρ(a, x)) , x ∈ Ω .

We refer to the original papers for further details.

§8. References

1959. R.C. Bose, D.M. Mesner, On linear associative algebras corresponding to association schemes of partially balanced designs, Ann. Math. Statist. \underline{30}, 21–38.

1973. P. Delsarte, An algebraic approach to the association schemes of coding theory, Philips Research Reports, Suppl. \underline{10}.

1974. N.L. Biggs, Algebraic graph theory, Cambr. Univ. Press.

1976. P.J. Cameron, J.M. Goethals, J.J. Seidel, E. Shult, Line graphs, root sys-

tems, elliptic geometry, J. Algebra \underline{43}, 305–327. 1984. E. Bannai, T. Ito, Association schemes, Benjamin. 1985. A. Neumaier, Characterization of a class of distance regular graphs, J. reine

angew. Mathem. \underline{357}, 182–192. 1986. P. Terwilliger, The Johnson graph J(d, r) is unique if (d, r) ≠ (2, 8), Discrete

Math. \underline{58}, 175–189. 1987. D.G. Higman, Coherent algebras, Lin. Alg. Appl. \underline{93}, 209–239. 1988. C.D. Godsil, Polynomial spaces, Discr. Math. \underline{73}, 71–88. 1989. A.E. Brouwer, A.M. Cohen, A. Neumaier, Distance regular graphs, Springer. 1990. D.M. Mesner, P. Bhattacharya, Association schemes on triples and a ternary

algebra, J. Combin. Theory A \underline{55}, 204–234.