07.05.06 · representation-theory / symmetric

Association schemes, the Bose-Mesner algebra, and Krawtchouk/Hahn polynomials

shipped3 tiersLean: none

Anchor (Master): Delsarte 1973 An Algebraic Approach to the Association Schemes of Coding Theory (Philips Research Reports Suppl. 10); Bannai-Ito 1984 Ch. 3; Diaconis 1988 Ch. 3F

Intuition Beginner

An association scheme is a way of sorting all pairs of points in a finite set into a few "distance types." On a cube, two corners are either the same, neighbours, two steps apart, or opposite. That sorting into four types is a scheme. The surprise is that this combinatorial bookkeeping carries a hidden algebra: stack each type into a square table of 0s and 1s, and these tables multiply among themselves in a closed, well-behaved way.

That algebra of tables is the Bose-Mesner algebra. Because the tables all commute, they share one common set of eigenvectors, and the eigenvalues line up into a small grid of numbers.

Why does this matter? Those eigenvalues turn out to be values of classical orthogonal polynomials, the same ones that diagonalise many random walks. A combinatorial symmetry algebra whose eigenvalues are classical orthogonal polynomials becomes the engine for analysing distance-regular structures and random walks on them.

Visual Beginner

Picture the points of a small set drawn as dots, with every pair of dots coloured by its "distance class." Same point is colour 0, nearest pairs colour 1, next-nearest colour 2, and so on. Each colour becomes one square table of 0s and 1s, and the tables sum to the all-ones table.

Reading the picture: the loops give the identity table, the edges give the "neighbour" table, the diagonals give the "opposite" table. Their sum fills every cell with a 1, because every pair of dots lands in exactly one class.

Worked example Beginner

Take a square with corners labelled $1, 2, 3, 4$ in a cycle. Sort pairs into three classes: class 0 is "same corner," class 1 is "joined by an edge," class 2 is "across a diagonal." Corner 1 is joined by edges to 2 and 4, and sits across the diagonal from 3.

Build the neighbour table $A_{1}$ : put a 1 in row $i$ , column $j$ when $i$ and $j$ are edge-joined. Row 1 has 1s in columns 2 and 4. Every row has exactly two 1s, because every corner has two edge-neighbours.

Now multiply $A_{1}$ by itself. Entry $(1, 3)$ of $A_{1} A_{1}$ counts the corners that neighbour both 1 and 3: those are 2 and 4, giving the value 2. Entry $(1, 1)$ counts corners neighbouring 1 twice over, giving 2 as well. Working out the whole product, $A_{1} A_{1} = 2 A_{0} + 2 A_{2}$ , a clean combination of the other tables.

The lesson: the product of two scheme tables is again a sum of scheme tables, with whole-number coefficients. Those coefficients (here 2 and 2) are the intersection numbers, and they are the entire data of the scheme.

Check your understanding Beginner

Formal definition Intermediate+

Let $X$ be a finite set of size $n$ . A (symmetric) association scheme with $d$ classes is a partition of $X \times X$ into relations $R_{0}, R_{1}, \dots, R_{d}$ such that:

$R_{0} = {(x, x) : x \in X}$ is the diagonal;
each $R_{i}$ is symmetric: $(x, y) \in R_{i} ⟺ (y, x) \in R_{i}$ ;
there exist intersection numbers $p_{ij}^{k}$ such that for any $(x, y) \in R_{k}$ , the count of $z \in X$ with $(x, z) \in R_{i}$ and $(z, y) \in R_{j}$ equals $p_{ij}^{k}$ , independent of the chosen pair $(x, y) \in R_{k}$ .

Encode each relation by its adjacency matrix $A_{i} \in {0, 1}^{X \times X}$ , with $(A_{i})_{x y} = 1$ exactly when $(x, y) \in R_{i}$ . The axioms translate to: $A_{0} = I$ ; $\sum_{i = 0}^{d} A_{i} = J$ (the all-ones matrix); each $A_{i} = A_{i}^{⊤}$ ; and

A_{i} A_{j} = k = 0 \sum d p_{ij}^{k} A_{k} .

Definition (Bose-Mesner algebra). The complex span $A = ⟨ A_{0}, \dots, A_{d} ⟩$ is the Bose-Mesner algebra of the scheme. The product relation above shows $A$ is closed under ordinary matrix multiplication; since the $A_{i}$ are symmetric 0/1 matrices summing to $J$ , $A$ is also closed under the entrywise Hadamard product $\circ$ , with $A_{i} \circ A_{j} = δ_{ij} A_{i}$ . The algebra is commutative when (and we assume) $p_{ij}^{k} = p_{j i}^{k}$ .

Because the $A_{i}$ are commuting symmetric real matrices, they are simultaneously diagonalisable. The common eigenspaces give a second basis of $A$ : the primitive idempotents $E_{0}, E_{1}, \dots, E_{d}$ , with $E_{0} = \frac{1}{n} J$ , $E_{j} E_{k} = δ_{j k} E_{j}$ , and $\sum_{j} E_{j} = I$ .

Definition (eigenmatrices). The two bases are related by the first eigenmatrix $P$ and second eigenmatrix $Q$ :

A_{i} = j = 0 \sum d P_{j i} E_{j}, E_{j} = \frac{1}{n} i = 0 \sum d Q_{ij} A_{i}, P Q = QP = n I .

The entry $P_{j i}$ is the eigenvalue of $A_{i}$ on the $j$ -th eigenspace.

Counterexamples to common slips

Not every partition is a scheme. The regularity axiom (3) is a strong constraint; a random partition of $X \times X$ has no constant intersection numbers and generates no closed algebra.
Commutative does not mean ordinary = Hadamard. The two products coincide only on the diagonal idempotent basis. The $A_{i}$ are idempotent under $\circ$ but not under ordinary multiplication, and vice versa for the $E_{j}$ .
$P$ -polynomial is extra structure. A scheme is $P$ -polynomial (metric) only when one can order the classes so that $A_{i} = v_{i} (A_{1})$ for a degree- $i$ polynomial $v_{i}$ . Most schemes are not $P$ -polynomial.

Key theorem with proof Intermediate+

Theorem (Krawtchouk eigenvalues of the Hamming scheme). Let $X = {0, 1, \dots, q - 1}^{n}$ and let $(x, y) \in R_{i}$ when $x$ and $y$ differ in exactly $i$ coordinates (Hamming distance $i$ ). This is the Hamming scheme $H (n, q)$ . It is $P$ -polynomial, and the eigenvalue of $A_{i}$ on the $j$ -th eigenspace is

P_{j i} = K_{i} (j) := ℓ = 0 \sum i (- 1)^{ℓ} (q - 1)^{i - ℓ} (ℓ j) (i - ℓ n - j),

the Krawtchouk polynomial of degree $i$ evaluated at $j$ .

Proof. The scheme $H (n, q)$ is the $n$ -fold tensor product of the one-class scheme on ${0, \dots, q - 1}$ . For the single coordinate, the additive characters of the abelian group $(Z / q)$ (for $q$ prime; in general the characters of any abelian group of order $q$ ) diagonalise the two relations "equal" and "different." Concretely, write the characters as $χ_{a} (x) = ω^{a x}$ with $ω = e^{2 π i / q}$ . The difference relation $A_{1}^{(1)} = J_{q} - I_{q}$ acts on $χ_{a}$ with eigenvalue $- 1$ for $a \neq = 0$ and $q - 1$ for $a = 0$ , by character orthogonality (see 07.01.04).

Tensoring $n$ copies, a joint eigenvector is indexed by a word $a \in {0, \dots, q - 1}^{n}$ , and its eigenspace depends only on the weight $j = ∣ {m : a_{m} \neq = 0} ∣$ . The eigenvalue of the distance- $i$ matrix $A_{i}$ is the coefficient extracted by counting how many ways $i$ coordinates can be chosen to differ, split by whether each falls on a zero or non-zero character index. Expanding the generating identity

i = 0 \sum n P_{j i} z^{i} = (1 - z)^{j} (1 + (q - 1) z)^{n - j}

and reading off the coefficient of $z^{i}$ gives exactly $K_{i} (j)$ . The right-hand factorisation is the product over coordinates: each of the $j$ non-zero positions contributes $(1 - z)$ (eigenvalue $- 1$ on the difference relation), each of the $n - j$ zero positions contributes $1 + (q - 1) z$ (eigenvalue $q - 1$ ). $□$

Bridge. This theorem builds toward the spectral analysis of urn-model walks and appears again in 07.05.15, where the Ehrenfest urn is the walk on $H (n, 2)$ and its relaxation time is read straight off $K_{1} (j) = n - 2 j$ . The foundational reason the Krawtchouk polynomials appear is that the Bose-Mesner algebra of $H (n, q)$ is exactly the commutant of the permutation action of the wreath-product symmetry group, so its eigenvalue table is the table of zonal spherical functions; this is exactly the abelian, commutative-product counterpart of the Gelfand-pair spherical functions of 07.05.13. The central insight, putting these together, is that diagonalising a combinatorial distance algebra and diagonalising a reversible random walk are the same computation: the bridge is the dictionary "eigenvalue of $A_{i}$ = value of an orthogonal polynomial = decaying Fourier mode," which generalises the non-abelian Fourier analysis of 07.01.09 to the metric setting.

Exercises Intermediate+

Exercise 6 (hard, symbolic).

Prove the orthogonality relation for the eigenmatrices: $\sum_{i = 0}^{d} \frac{1}{k _{i}} P_{j i} P_{j^{'} i} \cdot \frac{k _{i}}{m _{j}}$ collapses, and more directly that $P Q = n I$ encodes $\sum_{i} Q_{ij} P_{j^{'} i} = n δ_{j j^{'}}$ . Use $E_{j} A_{i}$ to relate $P$ and $Q$ .

Hint

Compute $E_{j^{'}} A_{i} = P_{j^{'} i} E_{j^{'}}$ two ways: directly, and by expanding $A_{i} = \sum_{j} P_{j i} E_{j}$ and $E_{j^{'}} = \frac{1}{n} \sum_{i} Q_{i j^{'}} A_{i}$ .

Answer

From $A_{i} = \sum_{j} P_{j i} E_{j}$ and $E_{j} E_{j^{'}} = δ_{j j^{'}} E_{j}$ , we get $E_{j^{'}} A_{i} = P_{j^{'} i} E_{j^{'}}$ . Now expand $E_{j^{'}} = \frac{1}{n} \sum_{i} Q_{i j^{'}} A_{i}$ and apply $\sum_{i} P_{j i} (\cdot)$ : substituting $E_{j^{'}} = \frac{1}{n} \sum_{i} Q_{i j^{'}} A_{i}$ into $A_{i^{'}} = \sum_{j} P_{j i^{'}} E_{j}$ and matching coefficients of the linearly independent $E_{j}$ forces $\frac{1}{n} \sum_{i} Q_{i j^{'}} P_{j i} = δ_{j j^{'}}$ , i.e. $QP$ has entries $(QP)_{j j^{'}} = \sum_{i} Q_{i j^{'}} P_{j i} = n δ_{j j^{'}}$ . Hence $QP = n I$ , and by symmetry of the construction $P Q = n I$ . The multiplicity $m_{j} = rank E_{j} = Q_{0 j}$ and valency $k_{i} = P_{0 i}$ appear as the first row/column entries, giving the weighted orthogonality $\sum_{i} k_{i}^{- 1} P_{j i} P_{j^{'} i} = n m_{j}^{- 1} δ_{j j^{'}}$ .

Advanced results Master

Theorem 1 (Bose-Mesner = commutant of a multiplicity-free action). Let a finite group $G$ act transitively on $X$ , and let the permutation representation $C [X]$ decompose without repeated irreducible constituents (a multiplicity-free action; equivalently $(G, G_{x})$ is a Gelfand pair). Then the orbitals of $G$ on $X \times X$ form a commutative association scheme whose Bose-Mesner algebra equals $End_{G} (C [X])$ , and the primitive idempotents $E_{j}$ are the projections onto the irreducible constituents. The eigenmatrix entries $P_{j i} / k_{i}$ are the zonal spherical functions of the Gelfand pair. This is the commutative-scheme face of the theory developed for $(S_{n}, S_{k} \times S_{n - k})$ in 07.05.13.

Theorem 2 (Johnson scheme and Hahn polynomials). Let $X = (k [ n ])$ , the $k$ -subsets of an $n$ -set, with $(A, B) \in R_{i}$ when $∣ A \cap B ∣ = k - i$ . This is the Johnson scheme $J (n, k)$ , the orbital scheme of the Gelfand pair $(S_{n}, S_{k} \times S_{n - k})$ . It is both $P$ -polynomial and $Q$ -polynomial; its eigenvalues are Eberlein polynomials and its dual eigenvalues are dual-Hahn polynomials, with the Hahn polynomials arising as the spherical functions. These polynomials are the discrete-orthogonal-polynomial spherical functions whose continuous shadow is the Jacobi polynomials.

Theorem 3 (Delsarte's linear-programming bound). For a code $C \subseteq X$ in a $P$ -polynomial scheme, the inner distribution $a_{i} = ∣ C ∣^{- 1} ∣ C^{2} \cap R_{i} ∣$ satisfies $a_{i} \geq 0$ , $a_{0} = 1$ , and the dual constraints $\sum_{i} a_{i} Q_{ij} \geq 0$ for all $j$ (the $Q_{ij}$ being the second-eigenmatrix entries). Maximising $\sum_{i} a_{i} = ∣ C ∣$ subject to these linear inequalities yields the Delsarte LP bound on $∣ C ∣$ . Specialised to $H (n, 2)$ this reproduces the classical bounds of coding theory; the dual constraints are precisely positivity of the Krawtchouk transform.

Theorem 4 (eigenvalues bound mixing). If a reversible random walk on $X$ has transition matrix $M = \sum_{i} c_{i} A_{i}$ lying in the Bose-Mesner algebra (constant transition probability within each relation), then $M$ is diagonalised by the $E_{j}$ , with eigenvalue $β_{j} = \sum_{i} c_{i} P_{j i}$ . Convergence to uniform is governed by $max_{j \neq = 0} ∣ β_{j} ∣$ , an explicit polynomial value. For the Ehrenfest urn this is $K_{1} (j) / n = 1 - 2 j / n$ ; for Bernoulli-Laplace it is a dual-Hahn value.

Synthesis. The central insight is that an association scheme packages a finite metric symmetry as a commutative algebra, and its two bases — the $A_{i}$ for ordinary multiplication, the $E_{j}$ for the Hadamard product — are exchanged by a duality that is exactly the discrete Fourier transform of the scheme. This is the foundational reason the same orthogonal polynomials recur: putting these together, the eigenvalue table $P$ for the Hamming scheme is the Krawtchouk array and for the Johnson scheme the Eberlein/Hahn array, and each table is simultaneously a list of spherical functions, a list of random-walk eigenvalues, and the kernel of Delsarte's LP bound. The Bose-Mesner-as-commutant picture is dual to the Gelfand-pair construction of 07.05.13: where that unit reads spherical functions off the double-coset algebra, here we read them off the orbital scheme, and the bridge between them is multiplicity-freeness. This generalises the non-abelian Fourier programme of 07.01.09 to the metric setting and builds toward the urn-diffusion mixing analysis of 07.05.15, where these polynomial eigenvalues become sharp cutoff times.

Full proof set Master

Proposition 1 (the Bose-Mesner algebra is commutative and semisimple). For a symmetric association scheme, $A = ⟨ A_{0}, \dots, A_{d} ⟩$ is a commutative algebra of dimension $d + 1$ that is closed under conjugate transpose, hence semisimple, and admits a basis of orthogonal primitive idempotents.

Proof. Each $A_{i}$ is a real symmetric matrix, so $A_{i}^{*} = A_{i}$ and $A$ is closed under the adjoint. The products $A_{i} A_{j} = \sum_{k} p_{ij}^{k} A_{k}$ stay in $A$ , so it is an algebra; the $A_{i}$ are linearly independent because their supports $R_{i}$ partition $X \times X$ , giving $dim A = d + 1$ . Symmetry of the scheme gives $A_{i} A_{j} = A_{j} A_{i}$ , so $A$ is commutative. A commutative algebra of normal matrices closed under adjoint is simultaneously unitarily diagonalisable; the common eigenprojections $E_{0}, \dots, E_{d}$ are Hermitian idempotents with $E_{j} E_{k} = δ_{j k} E_{j}$ and $\sum_{j} E_{j} = I$ . They lie in $A$ because each is a polynomial in the commuting $A_{i}$ . Counting dimensions, there are exactly $d + 1$ of them, forming the second basis. $□$

Proposition 2 (multiplicities and valencies via the eigenmatrices). Let $k_{i} = P_{0 i}$ be the valency of class $i$ and $m_{j} = rank E_{j}$ the multiplicity of eigenspace $j$ . Then $m_{j} = Q_{0 j}$ and $\sum_{j} m_{j} = n = \sum_{i} k_{i}$ , and the eigenmatrices satisfy $m_{j} P_{j i} = k_{i} \overline{Q_{ij}}$ .

Proof. Take traces in $A_{i} = \sum_{j} P_{j i} E_{j}$ : since $tr A_{i} = 0$ for $i \neq = 0$ (no fixed points off the diagonal) and $tr E_{j} = m_{j}$ , we get $\sum_{j} P_{j i} m_{j} = 0$ for $i \neq = 0$ and $\sum_{j} m_{j} = tr A_{0} = n$ . Dually, taking the Hadamard-diagonal of $E_{j} = \frac{1}{n} \sum_{i} Q_{ij} A_{i}$ at the diagonal cells gives $m_{j} = (E_{j})_{trace} = \frac{1}{n} Q_{0 j} \cdot n = Q_{0 j}$ . The relation $m_{j} P_{j i} = k_{i} \overline{Q_{ij}}$ follows by equating the two expressions for the $(x, y)$ -entry of $E_{j}$ on a pair in $R_{i}$ and using that $E_{j}$ is Hermitian: $\frac{1}{n} Q_{ij}$ is the constant value of $E_{j}$ on $R_{i}$ , while $P_{j i}$ is the eigenvalue of $A_{i}$ on the $j$ -eigenspace of dimension $m_{j}$ , and the inner product $⟨ A_{i} E_{j} 1_{x}, 1_{x} ⟩$ computed two ways yields the stated identity. $□$

Connections Master

Non-abelian Fourier transform 07.01.09. The simultaneous diagonalisation of the Bose-Mesner algebra is the metric-scheme instance of the Fourier transform on a finite group. When the scheme is the orbital scheme of a group action, the primitive idempotents $E_{j}$ are exactly the isotypic projections that 07.01.09 builds from irreducible representations, and the eigenmatrix $P$ is the table of Fourier coefficients of the relations.
Character orthogonality 07.01.04. The eigenvalues of the Hamming-scheme relations are computed by character orthogonality on the underlying abelian group: the difference relation has eigenvalue $q - 1$ on the principal character and $- 1$ on every other, and tensoring these is the engine that produces the Krawtchouk polynomials. The orthogonality relations of $P$ and $Q$ are the scheme-level shadow of character orthogonality.
Models for partially ranked data 07.05.13. That unit develops the Gelfand pair $(S_{n}, S_{k} \times S_{n - k})$ and its zonal spherical functions through the double-coset algebra; this unit produces the same spherical functions as the eigenvalues of the Johnson scheme $J (n, k)$ , the orbital scheme of that pair. The Bose-Mesner-as-commutant theorem is the precise bridge: this is the commutative, association-scheme presentation of the non-commutative Gelfand-pair theory there, with Hahn polynomials on both sides.

Historical & philosophical context Master

Association schemes entered statistics through the design of experiments: Bose and Mesner introduced the linear associative algebra of a partially balanced incomplete block design in 1959 ^{[Bose-Mesner 1959]}, abstracting the combinatorial regularity that makes such designs analysable. The algebra they named was rediscovered as the natural home for distance-regular graphs and, decisively, for coding theory when Delsarte's 1973 thesis ^{[Delsarte 1973]} recast the central problems of error-correcting codes as a linear program over the eigenmatrix of the Hamming scheme, with the Krawtchouk polynomials as its kernel. Bannai and Ito's 1984 treatise systematised the $P$ - and $Q$ -polynomial theory and exposed the deep parallel with orthogonal polynomials and Lie theory.

Diaconis brought the circle back to probability: in Chapter 3F of his 1988 monograph ^{[Diaconis 1988]} he observed that the spherical functions diagonalising reversible walks on symmetric finite structures are precisely these scheme eigenvalues, so the Krawtchouk and Hahn polynomials are at once the harmonic analysis of the cube, the engine of coding bounds, and the spectral data of the Ehrenfest and Bernoulli-Laplace urns. The philosophical lesson is one of convergent abstraction: a bookkeeping device for agricultural field trials turned out to be the commutant of a representation, and its eigenvalues turned out to be the classical orthogonal polynomials that physicists and probabilists had been computing independently for a century.

Bibliography Master

@article{BoseMesner1959,
  author = {Bose, R. C. and Mesner, Dale M.},
  title = {On linear associative algebras corresponding to association schemes of partially balanced designs},
  journal = {Annals of Mathematical Statistics},
  volume = {30},
  year = {1959},
  pages = {21--38},
}

@phdthesis{Delsarte1973,
  author = {Delsarte, Philippe},
  title = {An algebraic approach to the association schemes of coding theory},
  school = {Universit\'e Catholique de Louvain},
  year = {1973},
  note = {Philips Research Reports Supplements No. 10},
}

@book{BannaiIto1984,
  author = {Bannai, Eiichi and Ito, Tatsuro},
  title = {Algebraic Combinatorics I: Association Schemes},
  publisher = {Benjamin/Cummings},
  year = {1984},
}

@book{Diaconis1988,
  author = {Diaconis, Persi},
  title = {Group Representations in Probability and Statistics},
  publisher = {Institute of Mathematical Statistics},
  year = {1988},
  series = {IMS Lecture Notes--Monograph Series},
  volume = {11},
}

@book{BrouwerCohenNeumaier1989,
  author = {Brouwer, A. E. and Cohen, A. M. and Neumaier, A.},
  title = {Distance-Regular Graphs},
  publisher = {Springer},
  year = {1989},
}

@book{Godsil1993,
  author = {Godsil, C. D.},
  title = {Algebraic Combinatorics},
  publisher = {Chapman \& Hall},
  year = {1993},
}

Prerequisites

07.01.09
07.01.04
07.05.13

Tier anchors

beginner: Diaconis 1988 Group Representations in Probability and Statistics (IMS) Ch. 3F, informal scheme picture; Brouwer-Cohen-Neumaier 1989 Distance-Regular Graphs (Springer) Ch. 2 worked tables
intermediate: Bannai-Ito 1984 Algebraic Combinatorics I: Association Schemes (Benjamin/Cummings) Ch. 2; Godsil 1993 Algebraic Combinatorics (Chapman & Hall) Ch. 11-12
master: Delsarte 1973 An Algebraic Approach to the Association Schemes of Coding Theory (Philips Research Reports Suppl. 10); Bannai-Ito 1984 Ch. 3; Diaconis 1988 Ch. 3F

References

Bose, R. C. and Mesner, D. M. — On linear associative algebras corresponding to association schemes of partially balanced designs · Ann. Math. Statist. 30 (1959), 21-38
Delsarte, P. — An algebraic approach to the association schemes of coding theory · Philips Research Reports Supplements No. 10 (1973)
Bannai, E. and Ito, T. — Algebraic Combinatorics I: Association Schemes · Benjamin/Cummings (1984), Chapters 2-3
Diaconis, P. — Group Representations in Probability and Statistics · IMS Lecture Notes Vol. 11 (1988), Ch. 3F

Estimated time

beginner: 18m
intermediate: 45m
master: 85m