All Rights Reserved by Academic Press, New York and London
Reprinted from JOURNAL OF COMBINATORIAL THEORY. Series B

Vol. 35, No.2, October 1983
Printed in Belgium

NoteIntersection Numbers for Coherent Configurations
and the Spectrum of a Graph
COLIN D. WALTER
Department of Mathematics, University College, Belfield, Dublin 4. Ireland
Communicated by Norman L. Biggs
Received August 4, 1983
It is shown that the intersection numbers of a coherent configuration are closely related
to the determinant of a generic matrix for the corresponding adjacency algebra. This isimportant as both concepts provide isomorphism invariants for graphs.

The coherent configurations studied by Higman in [1] are of interest in graphtheory because invariants for the isomorphism class of a graph are obtained in theintersection numbers of the unique minimal coherent configuration generated by thepartition of V×V induced by the edge set E and the diagonal set V of the vertices of thegraph.
If A is the adjacency matrix of a labelled, directed graph Γ with vertex set V, one
constructs the smallest algebra 8 over C containing A, AT and the characteristic
matrices of sets S ⊂ V×V which are maximal with respect to(i, j) and (k, l) ∈ S implies aij = akl for all (ars) ∈ 8(1)These sets S form the partition of V×V which define a coherent configuration for Γand their characteristic matrices (the 0,1-adjacency matrices of the graphs with edgesets S) generate 8 as a module over C. Let A1, A2, ..., Ar be these matrices. Suppose X= ΣxiAi and Y = ΣyjAj are two generic matrices of 8. Then the intersection numbers
are defined by
XY = Σ aijkxiyjAk(2)They are clearly independent of the vertex numbering and so are isomorphism classinvariants. The same is true of the characteristic polynomial det(xI−A) and also of det
X, which certainly provides at least as much information as det(xI−A). The object of
this paper is to show that the intersection numbers give a finer classification of graphs
than does the spectrum or indeed det X, and to investigate how much weaker is the201

0095-8956/83 S3.00
Copyright @ 1983 by Academic Press, IncAll rights of reproduction in any form reserved.

202

COLIN D. WAL TER

classification using det X.
Suppose that Ai corresponds to Si ⊂ V×V. One may reasonably suppose that thenumbers aijk are provided together with the partition of the sets Si into diagonal andoff-diagonal subsets. From (2) if Sd is a diagonal class with corresponding vertices Vd,then S ∩ Vd×Vd = Si or ∅ according as aidi = 1 = adii or not. Let Jd = Σ’Ai where thesum is restricted to those i with Si ⊂ Vd×Vd. This is the matrix with 1’s in the block
Vd×Vd and 0’s elsewhere. Hence Jd2 = |Sd|Jd. Equating coefficients of Ad using (2)yields the order of Sd as Σ’aijd, where i, j satisfy Si, Sj ⊂ Vd×Vd. Using (2) again one
can inductively obtain the coefficients wdt of each Ad for the powers X t (t ≤ |V|). Nowtrace(Xi) = Σdwdt|Sd | for the sum over the diagonal classes. Newton’s formulae applied
to the generic eigenvalues of X consequently yield det X.
THEOREM. The intersection numbers determine the determinant of a genericmatrix in the adjacency algebra.
Conversely, assume that det X is given together with, as before, the partition intodiagonal and off-diagonal sets. Let 9 be the algebra over C generated by Bi = AiT for1 ≤ i ≤ r. This is the algebra of the graph Γ T with adjacency matrix B = AT. Itsintersection numbers satisfy bijk = ajik and its generic matrix is Y = ΣxiB i = XT.
Because det Y = det X, the determinant cannot distinguish aijk from ajik. However, it
will be shown that aijk+ajik is determined by det X.
Let {Sd | d∈D} be the collection of diagonal sets with corresponding partition V =∪d∈D Vd. We will treat det X as a polynomial in the variables xd (d∈D). The uniqueterm z of highest degree has the form Πd∈D xd rd and yields |Sd| = rd for d∈D. For X =(xrs), the coefficient of zxi−1xj−1 for i, j ∈ D is −2−δΣr∈ViΣs∈V xrsxsr = −1Σkδijk |Sk| xk xk’where Sk’ = SkT = {(r,s) | (s,r)∈Sk} defines k’, δ = l or 0 according as i = j or not, andδijk = l or 0 according as Sk ⊂ (Vi×Vj) ∪ (Vj×Vi) or not. This pairs Sk with SkT,establishes when Sk = SkT and so yields |Sk| for all k.
The block of Sk is nearly determined: either Vi×Vj or Vj×Vi for i, j as above. Makean arbitrary choice of Sk ⊂ Vi×Vj for one such triple (i,j,k) with i ≠ j. This fixes theprecise block of all other classes as follows: The action of X on C|V| = C[v∈V] induces
an action on the subspace Cr (r= |D|) with basis {Σv∈Vdv | d∈D} which is described bythe matrix X with entries x de = |Ve|−1Σr∈VdΣs∈Ve xrs. Because the variables in eachblock are distinct, det X is an irreducible factor of det X with degree r. Set xs = 0 if Ss∩ Vd×Vd = ∅ for all d∈D, and xs = 1 if Ss ⊂ Vd×Vd for some d∈D but s∉D. Then det
X specialises to Πd∈D(xd−1)|Vd|−1 (xd + |Vd | −1) and det X can be recognised as thatfactor which specialises to Πd∈D(xd + |Vd | −1). Now Ss ⊂ Vi×V ∪ V×Vj if, and only if,

INTERSECTION NUMBERS203

det X does not contain a term with the product xsxk for i, j, k as chosen above. Acouple of applications of this produces the block of every class Ss subject to thechoice mentioned.
For the intersection numbers auvw where u or v∈D and w∉D it is clear that aiww =awjw = 1 for Sw ⊂ Vi×Vj and auvw = 0 otherwise; and if k∈D, then auu’k = |Su||Sk|−1 for Su⊂ Vk×V with auvk = 0 otherwise. Anyother intersection numbers contribute to thecoefficient of z(xixjxk)−1 in det X for some i, j, k ∈ D. This coefficient is obtained bylooking at 3 × 3 submatrices of X which include the three diagonal elements xi, xj, xkand equals(4−p)!−1∑∑∑Su ⊂Vi ×V j S v ⊂V j ×Vk S w ⊂Vk ×Vi|Sw|(auvw’ xuxvxw + au’v’w xu’ xv’ xw’ )(3)

where p is the number of distinct indices among i, j, k; the sums are restricted to offdiagonal classes (i.e., u, v, w ∉ D); and St’ = SiT defines u’, v’, and w’. Symmetry in (3)for u, v, w ensures that
|Su|avwu’ = |Sv|awuv’ = |Sw|auvw’ and auvw = au’v’w’(4)

For p>1 the blocks Vi×Vj, Vj×Vk and Vk×Vi are distinct and so z(xixjxk)−1xuxvxw has
coefficient |Sw|auvw’. This determines the intersection numbers except on diagonal
blocks because those auvw not satisfying Su ⊂ Vi×Vj Sv ⊂ Vj×Vk and Sw ⊂ Vk×Vi forsome i, j, k ∈ D with u, v, w ∉ D are necessarily zero.
Taking p = 1 in (3) and letting q be the number of distinct indices among u, v, w
yields the coefficient(4−q)!−1 |Sw|(auvw’ + avuw’)(5)

for zxi−3xuxvxw by virtue of (4). The intersection numbers for the diagonal blocks
obtained via (5) are the only ones that cannot be individually ascertained once thechoice of block for one off-diagonal Ss is made. If the alternative choice holds so that
all the classes Ss have been associated with the transpose of their correct block, thenauvw and avuw have to be interchanged throughout. However, in either case auvw + avuw
is known.
THEOREM. The determinant of a generic matrix in the adjacency algebra
determines the sums aijk + ajik of pairs of intersection numbers.
Let 8 d be the algebra given by the block Vd×Vd. Then 8 d is commutative if, andonly if, auvw = avuw for all relevant u, v, w. In particular, this is the case when the rank

204

COLIN D. WAL TER

or number of classes Ss ⊂ Vd×Vd is sufficiently small. Whenever 8 itself iscommutative, the auvw can therefore all be found. Thus the intersection numbers anddet X determine each other. For the important case when Γ is a regular (unlabelled)graph, 8 is simply the algebra generated by the adjacency matrix A and the all 1’smatrix J. So 8 is commutative and det X yields the same class of graphs as do theintersection numbers.
REFERENCE
1. D. G. HIGMAN, Coherent configurations, Geom. Dedicata 4 (1975), 1-32.

Printed by the St. Catherine Press Ltd., Tempelhof 41, Bruges, BelgiumW