Coherent configurations

A. E. Brouwer

Abstract

Definition and a few examples.

0.1 Relations

A coherent configuration is a finite set X (of points) together with a collection R = {R_{i} | i ∈ I} of nonempty binary relations on X, satisfying the following four conditions:

(i) R is a partition of X × X, that is, any ordered pair of points is in a unique relation R_{i}.

(ii) There is a subset H of the index set I such that {R_{h} | h ∈ H} is a partition of the diagonal {(x, x) | x ∈ X}.

(iii) For each R_{i}, its converse {(y, x) | (x, y) ∈ R_{i}} is also one of the relations in R, say, R_{i′}.

(iv) For i, j, k ∈ I and (x, y) ∈ R_{k}, the number of z ∈ X such that (x, z) ∈ R_{i} and (z, y) ∈ R_{j} is a constant p_{ij}^{k} that does not depend on the choice of x, y.

Coherent configurations were introduced by Higman in order to ‘do group theory without groups’, see example (ii) below.

The number |I| of relations is called the rank of the coherent configuration.

From (ii) we get a partition of X into sets X_{h} (h ∈ H) called fibers, defined by R_{h} = {(x, x) | x ∈ X_{h}} for h ∈ H. It follows from (iv) that for any i ∈ I we have R_{i} ⊆ X_{s} × X_{t} for certain fibers X_{s}, X_{t}. Consequently, any subset H_{0} of H determines a sub-cc with point set ⋃_{h∈H_{0}} X_{h}.

0.2 Matrices

Let A_{i} be the adjacency matrix of R_{i}, defined by (A_{i})_{xy} = 1 if (x, y) ∈ R_{i} and (A_{i})_{xy} = 0 otherwise. In terms of the A_{i} the above definition becomes: The A_{i} (i ∈ I) are nonzero 0-1 matrices with rows and columns indexed by X such that

(i) ∑_{i∈I} A_{i} = J, where J is the all-1 matrix.

(ii) ∑_{h∈H} A_{h} = I, where I is the identity matrix.

(iii) (A_{i})^{⊤} = A_{i′} for i ∈ I.

(iv) A_{i}A_{j} = ∑_{k} p_{ij}^{k}A_{k}.

0.3 The adjacency algebra

By (iv) above, the matrices A_{i} form the basis for an |I|-dimensional algebra A (over an arbitrary field F) called the (F -)adjacency algebra. The algebra A is closed for both matrix multiplication and Hadamard (entrywise) multiplication.

If F = ℂ, the algebra A is closed for taking the conjugate transpose M^{∗} = \overline{M} ^{⊤} of a matrix M, and A is a C*-algebra.

By (iii), the real or complex adjacency algebra A is semisimple. (Its radical contains together with a matrix M also M^{⊤}M or M^{∗}M, but these matrices can be diagonalized and are nilpotent so are zero. Hence rad A = 0.) It follows that A is the direct sum of simple two-sided ideals: A = ∑_{k} I_{k} where the I_{k} annihilate each other. Take F = ℂ, then each I_{k} is isomorphic to a matrix algebra M_{n_{k}}(ℂ) of matrices of order n_{k} over ℂ. We see that dim A = ∑_{k} n_{k}^{2}.

Since M_{n}(ℂ) has a basis of matrices e_{ij} (with a 1 entry at the (i, j)-position and 0 elsewhere) that multiply according to e_{ij}e_{kl} = e_{il} if j = k, and e_{ij}e_{kl} = 0 otherwise, we can find matrices E_{h} in A, n_{k}^{2} in each ideal I_{k}, where the E_{h} in I_{k} ≅ M_{n_{k}}(ℂ) multiply like the e_{ij} (taken in some order). Let E_{h′} = E_{h}^{∗}.

Now A has two bases, namely that of the A_{i} and that of the E_{j}, and we can express each basis in terms of the other. Define constants P_{ij} and Q_{ij} by A_{i} = ∑ P_{ji}E_{j} and E_{j} = \frac{1}{|X|} ∑ Q_{ij}A_{i}. (The order of indices, and the factor \frac{1}{|X|} are traditional.)

Consider the bilinear form on A given by (M, N) = tr M^{∗}N. This form is nondegenerate, and the A_{i} are mutually orthogonal, and the E_{j} are, too. It follows that if M is an arbitrary matrix of order v = |X|, the projection πM of M on A is given by πM = ∑_{i} \frac{(A_{i},M)}{(A_{i},A_{i})}A_{i} = ∑_{j} \frac{(E_{j},M)}{(E_{j},E_{j})}E_{j}. For M = yx^{∗} of rank 1, we find

∑_{i} \frac{x^{∗}A_{i′}y}{(A_{i}, A_{i})}A_{i} = ∑_{j} \frac{x^{∗}E_{j′}y}{(E_{j}, E_{j})}E_{j}

for all x, y ∈ V. (This is a form of Roos’ identity.)

For M = xx^{∗}, which is symmetric and positive semidefinite, the projection πM is also symmetric and positive semidefinite, and we find Hobart’s result that ∑_{i} \frac{1}{(A_{i},A_{i})}(x^{∗}A_{i}x)A_{i} is psd. (This is a form of Delsarte’s LP bound.)

One has (A_{i}, A_{i}) = k_{i}|X_{g}| when R_{i} ⊆ X_{g} × X_{h} and A_{i} has row sums k_{i} (= p_{ii}^{g}). One has (E_{i}, E_{i}) = m_{i} when the standard module V = ℂ^{X} contains m_{i} copies of the I_{k} corresponding to E_{i}. Computing (A_{i}, E_{j}) in two ways, we find (A_{i}, E_{j}) = \frac{1}{|X|}Q_{ij}(A_{i}, A_{i}) = \frac{1}{|X|}Q_{ij}k_{i}|X_{g}| and (A_{i}, E_{j}) = \overline{P_{ji}} (E_{j}, E_{j}) = \overline{P_{ji}} m_{j}.

0.4 Association schemes

A coherent configuration (cc) is called homogeneous if I_{0} consists of a single element, which then is written 0.

A cc is called commutative when A_{i}A_{j} = A_{j}A_{i} for all i, j ∈ I (or, equivalently, when p_{ij}^{k} = p_{ji}^{k} for all i, j, k ∈ I).

A cc is called symmetric when A_{i}^{⊤} = A_{i} for all i ∈ I (or, equivalently, when i′ = i for all i ∈ I).

Every symmetric cc is commutative. Every nonempty commutative cc is homogeneous. Every homogeneous cc of rank at most 5 is commutative. A nonempty symmetric cc is called a (symmetric) association scheme. (For most authors association schemes are by definition symmetric, but Delsarte used the term more generally for homogeneous commutative coherent configurations, so one often adds ‘symmetric’ to avoid ambiguity.) For association schemes the adjacency algebra is also known as the Bose-Mesner algebra.

0.5 Examples

(i) The empty coherent configuration has X = ∅. It has R = ∅ and is symmetric but not homogeneous, and not an association scheme.

(ii) Let G be a permutation group acting on the set X. Then X together with the partition R of X × X into orbits of G (acting on X × X via g(x, y) = (gx, gy)) is a coherent configuration. A coherent configuration obtained in this way is called Schurian. This coherent configuration is homogeneous when G has precisely 1 orbit, i.e., when X is nonempty and G is transitive on X.

(iii) Let S be an arbitrary collection of relations on X. Then there is a unique coarsest R such that (X, R) is a coherent configuration and all elements of S are unions of relations in R. (Proof: Consider the algebra generated by the matrices I, J and the 0-1 adjacency matrices for the elements of S under taking ordinary and Hadamard products. It has a basis of minimal idempotents for Hadamard multiplication, and this yields R.) In particular, a graph Γ (directed or not) determines a coherent configuration cc(Γ).

(iiia) The discrete coherent configuration on a set X is the unique coherent configuration in which all singletons are fibers. It has rank |X|^{2} and is the finest coherent configuration on X.

(iiib) The indiscrete coherent configuration on a set X is the coherent configuration determined by the complete graph on X. It is the coarsest coherent configuration on X. If |X| > 1 it has rank 2.

(iv) Up to isomorphism, there are four coherent configurations on 3 points. The indiscrete one is cc(K_{3}) and is an association scheme of rank 2. The coherent configuration determined by the cyclically directed triangle is commutative and homogeneous and has rank 3. The path P_{3} of length 2 determines cc(P_{3}) of rank 5. The discrete cc has rank 9.

Let us give very explicit details.

a) The indiscrete scheme cc(K_{3}) has adjacency algebra A = ⟨I, J − I⟩ with idempotents \frac{1}{3}J and I − \frac{1}{3}J and P = [ \begin{matrix}1 & 2 \\ 1 & −1 \end{matrix} ].

b) The cyclically directed triangle has adjacency algebra A = ⟨I, A, A^{2}⟩, where A = [ \begin{matrix}0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{matrix} ] with idempotents \frac{1}{3}(I + ρA + ρ^{2}A^{2}) for ρ = 1, ω, ω^{2}, where

ω is a primitive cube root of unity, and P = [ \begin{matrix}1 & 1 & 1 \\ 1 & \overline{ω} & ω \\ 1 & ω & \overline{ω} \end{matrix} ].

c) The scheme cc(P_{3}) has adjacency algebra

A = ⟨[ \begin{matrix}1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{matrix} ] , [ \begin{matrix}0 & 1 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{matrix} ] , [ \begin{matrix}0 & 0 & 0 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \end{matrix} ] , [ \begin{matrix}0 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix} ] , [ \begin{matrix}0 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{matrix} ]⟩.

Here A is the sum of the three minimal left ideals of dimensions 2, 2, 1 generated

by the idempotents [ \begin{matrix}1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{matrix} ] , \frac{1}{2} [ \begin{matrix}0 & 0 & 0 \\ 0 & 1 & 1 \\ 0 & 1 & 1 \end{matrix} ] , \frac{1}{2} [ \begin{matrix}0 & 0 & 0 \\ 0 & 1 & −1 \\ 0 & −1 & 1 \end{matrix} ]. The sum of the first two is

a two-sided ideal of dimension 4 isomorphic to M_{2}(ℂ), the third is isomorphic to M_{1}(ℂ). The basis of the E_{j} can be taken as

\{[ \begin{matrix}1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{matrix} ] , \frac{1}{\sqrt{2}} [ \begin{matrix}0 & 1 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{matrix} ] , \frac{1}{\sqrt{2}} [ \begin{matrix}0 & 0 & 0 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \end{matrix} ] , \frac{1}{2} [ \begin{matrix}0 & 0 & 0 \\ 0 & 1 & 1 \\ 0 & 1 & 1 \end{matrix} ] , \frac{1}{2} [ \begin{matrix}0 & 0 & 0 \\ 0 & 1 & −1 \\ 0 & −1 & 1 \end{matrix} ]\}.

Now P = [ \begin{matrix}1 & 0 & 0 & 0 & 0 \\ 0 & \sqrt{2} & 0 & 0 & 0 \\ 0 & 0 & \sqrt{2} & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & −1 \end{matrix} ]. The isomorphism of A with M_{2}(ℂ) ⊕ M_{1}(ℂ) sends

the adjacency matrix A = [ \begin{matrix}0 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \end{matrix} ] of the path P_{3} to \sqrt{2} [ \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} ] + [^{0} ], so that A

has eigenvalues \sqrt{2}, 0, −\sqrt{2}.

d) The discrete cc on 3 points has adjacency algebra A = M_{3}(ℂ), and both the 9 matrices A_{i} and the 9 matrices E_{j} are the 9 matrices e_{ij} with a single 1.