Article and note

A Series Learning through the MacWilliams IdentityPart 5 of 12

An Introduction to Association Schemes through the MacWilliams Identity

Among the five proof systems for the MacWilliams identity, this note focuses on the orthogonal-polynomial and association-scheme approach, and introduces relation partitions, adjacency matrices, Bose–Mesner algebras, primitive idempotents, Hamming schemes, and inner and dual distributions.

Published:: May 30, 2026
Updated:: Jun 6, 2026
Reading time:: 42 min (about 9,141 words)

Tagscoding theoryMacWilliams identityassociation schemesBose-Mesner algebraHamming schemeKrawtchouk polynomialsfinite fieldsexpository note

Download PDF

Introduction

One of the fundamental theorems in coding theory is the MacWilliams identity. Let $E$ be the coordinate set, let $n = \card{E}$ , and let $C\leq \F_{q}^{E}$ be a linear code over the finite field $\F_{q}$ . Consider its dual code

C^{\perp} = \{ u \in \F_{q}^{E} : u \cdot c = 0 \text{ for all } c \in C \}.

Here

u \cdot c = \sum_{e \in E} u_{e} c_{e}.

First, define the weight enumerator of the linear code $C$ by

W_{C}(X,Y) = \sum_{c \in C} X^{n - \wt(c)} Y^{\wt(c)}.

Also write the weight distribution as

A_{i}(C) = \card{\{ c \in C : \wt(c) = i\}} \qquad (0 \leq i\leq n).

Then

W_{C}(X, Y) = \sum_{i = 0}^{n} A_{i}(C) X^{n - i} Y^{i}.

The MacWilliams identity is the formula saying that the weight enumerator of the dual code can be computed from the weight enumerator of $C$ as follows:

W_{C^{\perp}}(X, Y) = \frac{1}{\card{C}} W_{C}\bigl( X + (q - 1)Y, X - Y \bigr).

This is the MacWilliams identity.

In this series, I use proofs of the MacWilliams identity as a guide to an introduction to neighbouring areas and concepts. Accordingly, this series is aimed at readers who already know the following basic material in coding theory:

We assume familiarity, at least at a basic level, with

what a (finite) field is,
what a linear code over a finite field is,
what the Hamming weight is,
what the dual code is.

(There is no problem if you do not know a proof of the MacWilliams identity.)

This note does not assume Parts 1–4. Krawtchouk polynomials, tensor products, and additive characters appear along the way, but the parts needed in this note are explained when they are used. If you have read Part 4, the outlook will be clearer, but the note is written so that it can be read independently.

In this series, I look at proof methods for the MacWilliams identity under the following five broad families.

Fourier, character, and Poisson methods.
Möbius inversion, lattice-theoretic, and shortening/puncturing methods.
Orthogonal-polynomial and association-scheme methods.
Matroid and Tutte-polynomial methods.
Moment and double-counting methods.

In this note, I focus on the third of these: the orthogonal-polynomial and association-scheme approach. Written using Krawtchouk polynomials, the MacWilliams identity appears as

a Krawtchouk transform of the weight distribution.

Here the Krawtchouk transform means a transform of the form

(a_{i})_{i=0}^{n} \longmapsto \left( \sum_{i = 0}^{n} a_{i} \Kraw_{j}(i) \right)_{j=0}^{n}.

Let me first say how to read the subscripts. If we write $\Kraw_{i}(w)$ , this means the eigenvalue of the distance- $i$ adjacency matrix on the $w$ -th eigenspace. On the other hand, in the MacWilliams transform we write the dual-side weight as $j$ and the original weight as $i$ , so the coefficient appears in the form $\Kraw_{j}(i)$ . It is the same Krawtchouk polynomial, but one has to read from context which subscript belongs to the distance side and which belongs to the eigenspace side. We will organise this point once more after introducing the eigenspaces of the Hamming scheme. In this note, I explain in the language of association schemes why these Krawtchouk polynomials are naturally attached to Hamming space. In other words, the aim of this note is to explain why the coefficients $\Kraw_j(i)$ naturally appear as eigenvalues of the Hamming scheme. The goal of this instalment is to use a proof of the MacWilliams identity as a guide to an introduction to association schemes, especially the Hamming scheme and the Bose–Mesner algebra.

An association scheme abstracts the situation where binary relations on a finite set are divided into several types and these relations behave in a sufficiently regular way. In Hamming space, the relation between two words $x, y \in \F_{q}^{E}$ is classified according to which of

\dist(x, y) = 0, 1, \dots, n

holds. Here $\dist(x, y) = \wt(x - y)$ is the Hamming distance. From these distance relations we form adjacency matrices; when we look at the commutative algebra spanned by them, Krawtchouk polynomials appear as its eigenvalues.

The route in this note is as follows.

relation partitions → adjacency matrices → association schemes → Bose–Mesner algebras → primitive idempotents → inner and dual distributions → the MacWilliams identity

The classical starting point for coding theory from the viewpoint of association schemes is Delsarte [Del73]. For a survey of the relation between association schemes and coding theory, including distance distributions, MacWilliams transforms, and linear programming, see Delsarte–Levenshtein [DL98]. For a systematic reference on association schemes, Bannai–Ito [BI84] is standard. For a detailed account including the relation with distance-regular graphs, see Brouwer–Cohen–Neumaier [BCN89]. For the MacWilliams identity and Krawtchouk polynomials in coding theory, MacWilliams–Sloane [MS77, Chapter 5] is also a classical standard reference. For basic material on association schemes used in coding theory, Camion [Cam98] is also useful.

Viewing Relations on a Finite Set as Matrices

Before entering association schemes, we look at how to represent relations on a finite set by matrices.

Let $\Omega$ be a finite set. If we think of the elements of $\Omega$ as vertices, then a subset $R \subseteq \Omega \times \Omega$ can be viewed as a set of directed edges. The condition $(x,y)\in R$ means that there is relation $R$ from $x$ to $y$ .

Definition 2.1.

For a relation $R\subseteq \Omega\times \Omega$ on a finite set $\Omega$ , define the matrix $\mathsf{A}_R$ , whose rows and columns are indexed by $\Omega$ , by

(\mathsf{A}_R)_{x,y} = \begin{cases} 1, & (x,y)\in R,\\ 0, & (x,y)\notin R. \end{cases}

This is called the adjacency matrix of $R$ .

This definition generalises the adjacency matrix of a graph. For an ordinary simple graph, we record by $0$ and $1$ whether two vertices are joined by an edge. Here we are simply recording, in matrix form, whether a pair belongs to the relation $R$ .

Let $\C^{\Omega}$ be the set of all complex-valued functions on $\Omega$ . Equivalently, one may view it as the complex vector space with basis vectors $e_x$ corresponding to the elements $x$ of $\Omega$ . The matrix $\mathsf{A}_R$ acts as a linear map on $\C^{\Omega}$ . For a function $f\colon \Omega\to\C$ ,

(\mathsf{A}_R f)(x) = \sum_{\substack{y\in \Omega\\(x,y)\in R}} f(y).

Thus $\mathsf{A}_R$ is the operator that “adds the values over all $y$ related to $x$ by $R$ ”.

Example 2.2 (The one-coordinate relation of a complete graph).

Let $\Omega=\F_q$ . Consider the two relations

\begin{aligned} R_{0} &= \{ (a, a) : a \in \F_{q} \},\\ R_{1} &= \{ (a, b) : a, b \in \F_{q},\, a \neq b\}. \end{aligned}

The adjacency matrix of $R_{0}$ is the identity matrix $I$ , and the adjacency matrix of $R_{1}$ is $J - I$ . Here $J$ is the matrix all of whose entries are $1$ . This is the adjacency matrix of the complete graph $K_{q}$ .

In what follows, $I$ and $J$ denote the identity matrix and the all-one matrix of the size appropriate to the space on which they act. For instance, in the example above they are $q\times q$ matrices indexed by $\F_{q}$ . On the other hand, the $I$ and $J$ which later appear as operators on $\Omega=\F_{q}^{E}$ are $q^{n}\times q^{n}$ matrices indexed by $\Omega$ . Where necessary, I will specify whether an operator acts on one coordinate or on the full multi-coordinate space.

When we treat several relations at the same time, the important case is when they partition $\Omega\times \Omega$ .

Definition 2.3.

Relations $R_{0}, R_{1}, \dots, R_{d} \subseteq \Omega \times \Omega$ on a finite set $\Omega$ form a relation partition of $\Omega\times \Omega$ if

\Omega\times \Omega=R_0\sqcup R_1\sqcup\cdots\sqcup R_d.

A relation partition corresponds to colouring the relation between any two points $x, y \in \Omega$ with exactly one colour. For this reason, association schemes are sometimes described as complete graphs with coloured edges. Strictly speaking, however, the diagonal pairs $(x, x)$ are also coloured with the colour $R_{0}$ , so it is natural to think of a complete graph with loops, whose edges have been coloured. Of course, arbitrary colouring is not enough. We require strong regularity in the colouring. That is the definition in the next section.

Association Schemes

In this note, we treat the most basic case, sufficient for coding theory: symmetric association schemes. There are non-symmetric association schemes in general, but Hamming schemes are symmetric, so it is clearest to begin with this case.

Definition 3.1.

Let $\Omega$ be a finite set, and let $R_{0}, R_{1}, \dots, R_{d} \subseteq \Omega \times \Omega$ be non-empty relations giving a relation partition

\Omega \times \Omega = R_{0} \sqcup R_{1} \sqcup \dots \sqcup R_{d}.

This partition is called a symmetric association scheme if it satisfies:

$R_{0} = \{ (x, x) : x \in \Omega \}$ .
For each $i$ , if $(x, y) \in R_{i}$ , then $(y, x) \in R_{i}$ .
For any $0 \leq i, j ,k \leq d$ , if $x, y \in \Omega$ satisfy $(x, y) \in R_{k}$ , then

$\card{\{ z \in \Omega : (x, z) \in R_{i},\ (z, y) \in R_{j} \}}$

is independent of the choice of $x$ and $y$ , and depends only on $i$ , $j$ , and $k$ .

Since each $R_{k}$ is assumed to be non-empty, there is no ambiguity in choosing $(x, y)\in R_{k}$ in condition (A3).

The number appearing in condition (A3) is written $p_{ij}^{k}$ and is called an intersection number.

In words, the definition means the following. Suppose that the relation between two points $x$ and $y$ is $R_{k}$ . Then the number of points $z$ which are in relation $R_{i}$ from the viewpoint of $x$ and in relation $R_{j}$ from the viewpoint of $y$ does not depend on the concrete choice of $x$ and $y$ , but only on the types of relations $i$ , $j$ , and $k$ . Thus we are requiring the colouring of the relations to be highly uniform.

In terms of adjacency matrices, this condition looks very natural. Write the adjacency matrix of $R_{i}$ as $\mathsf{A}_{i} \coloneqq \mathsf{A}_{R_{i}}$ . Then the $(x, y)$ entry of the matrix product $\mathsf{A}_{i}\mathsf{A}_{j}$ is

(\mathsf{A}_i\mathsf{A}_j)_{x,y} = \sum_{z\in \Omega}(\mathsf{A}_i)_{x,z}(\mathsf{A}_j)_{z,y}.

This counts the number of $z$ such that $(x, z) \in R_{i}$ and $(z, y) \in R_{j}$ . Therefore the association-scheme condition says that this product of matrices can again be written as a linear combination of the same adjacency matrices.

Theorem 3.2.

The adjacency matrices of a symmetric association scheme satisfy

\mathsf{A}_{i} \mathsf{A}_{j} = \sum_{k=0}^{d}p_{ij}^{k}\mathsf{A}_{k}.

Proof

Compare the $(x,y)$ entries of both sides. Suppose that $(x,y)\in R_{k}$ . The $(x,y)$ entry of the left-hand side is the number of $z$ satisfying $(x,z)\in R_{i}$ and $(z,y)\in R_{j}$ . By the definition of an association scheme, this is equal to $p_{ij}^{k}$ . On the other hand, since the relation containing $(x,y)$ is $R_{k}$ , the $(x,y)$ entry of the right-hand side is

\sum_{\ell=0}^{d}p_{ij}^{\ell}(\mathsf{A}_{\ell})_{x,y} = p_{ij}^{k}.

Hence the entries of the two sides agree.

Thus the intersection-number condition guarantees that the operation “follow relation $R_i$ , then follow relation $R_j$ ” can again be expressed as a linear combination of the original relations $R_0,\dots,R_d$ . For this reason, a relation partition is not merely a classification; it produces a matrix algebra formed by the adjacency matrices.

Also, because the relations partition $\Omega \times \Omega$ ,

\mathsf{A}_{0} + \mathsf{A}_{1} + \dots + \mathsf{A}_{d} = J.

Here $J$ is the all-one matrix. Moreover, since $R_0$ is the diagonal relation, $\mathsf{A}_{0} = I$ .

Bose–Mesner Algebras

The adjacency matrices of an association scheme are closed under matrix multiplication. We therefore consider the vector space spanned by these matrices.

Definition 4.1.

Let $(\Omega, \{R_{i} \}_{i = 0}^{d})$ be a symmetric association scheme, and let $\mathsf{A}_{0}, \dots, \mathsf{A}_{d}$ be its adjacency matrices. The complex vector space spanned by these matrices,

\mathcal{A} = \Span_{\C}\{\mathsf{A}_0,\mathsf{A}_1,\dots,\mathsf{A}_d\} \subseteq \Mat_{\Omega}(\C),

is called the Bose–Mesner algebra of the scheme.

By Theorem 3.2, $\mathcal{A}$ is closed under matrix multiplication. It also has an identity element, since $\mathsf{A}_0=I$ . Furthermore, since $R_0,\dots,R_d$ partition $\Omega\times \Omega$ , the matrices $\mathsf{A}_0,\dots,\mathsf{A}_d$ have $1$ 's only in disjoint positions. Therefore, if

c_{0} \mathsf{A}_{0} + \dots + c_{d}\mathsf{A}_{d} = 0,

then by looking at an entry with $(x, y) \in R_{k}$ we get $c_{k} = 0$ . Hence $\mathsf{A}_{0}, \dots, \mathsf{A}_{d}$ are linearly independent, and $\dim_{\C} \mathcal{A} = d + 1$ . For a symmetric association scheme, the matrices $\mathsf{A}_i$ are real symmetric matrices, and they also commute with one another. In general, two real symmetric matrices need not commute. The commutativity here follows because, by Theorem 3.2,

\mathsf{A}_i\mathsf{A}_j = \sum_{k=0}^{d}p_{ij}^{k}\mathsf{A}_k

is a linear combination of symmetric matrices, and is therefore symmetric. Indeed,

\mathsf{A}_i\mathsf{A}_j = (\mathsf{A}_i\mathsf{A}_j)^T = \mathsf{A}_j^T\mathsf{A}_i^T = \mathsf{A}_j\mathsf{A}_i.

Thus $\mathcal{A}$ is a commutative complex matrix algebra spanned by the real symmetric, mutually commuting adjacency matrices $\mathsf{A}_{0}, \dots, \mathsf{A}_{d}$ . These adjacency matrices can be simultaneously diagonalised in the sense of linear algebra. From this simultaneous diagonalisation one obtains another basis of the Bose–Mesner algebra: the primitive idempotents. We now verify this fact using only finite-dimensional linear algebra.

Theorem 4.2.

In the Bose–Mesner algebra $\mathcal{A}$ of a symmetric association scheme, there exist matrices $\mathsf{E}_{0}, \mathsf{E}_{1}, \dots, \mathsf{E}_{d} \in \mathcal{A}$ such that:

$\mathsf{E}_{r} \mathsf{E}_{s} = 0$ ( $r \neq s$ ).
$\mathsf{E}_{r}^{2} = \mathsf{E}_{r}$ .
$\mathsf{E}_{0} + \mathsf{E}_{1} + \dots + \mathsf{E}_{d} = I$ .
$\mathsf{E}_{0}, \mathsf{E}_{1}, \dots, \mathsf{E}_{d}$ form a basis of $\mathcal{A}$ .
Each $\mathsf{A}_{i}$ acts as a scalar multiple on the image of each $\mathsf{E}_{r}$ .
No $\mathsf{E}_{r}$ can be decomposed further, inside $\mathcal{A}$ , as a non-trivial sum of orthogonal idempotents.

These $\mathsf{E}_{r}$ are called the primitive idempotents.

Proof

As seen above, $\mathsf{A}_{0}, \dots, \mathsf{A}_{d}$ are mutually commuting real symmetric matrices. Hence, by the simultaneous diagonalisation theorem from linear algebra, $\C^{\Omega}$ decomposes as an orthogonal direct sum of their common eigenspaces.

Let $\Lambda$ denote the set of all common eigenvalue tuples. Thus an element $\lambda \in \Lambda$ is a tuple of the form

\lambda = (\lambda_{0}, \lambda_{1}, \dots, \lambda_{d}) \in \C^{d+1}

for which the corresponding common eigenspace

W_{\lambda} = \{ v \in \C^{\Omega}: \mathsf{A}_{i} v = \lambda_{i} v \text{ for all } 0 \leq i \leq d\}

is non-zero. Simultaneous diagonalisation gives the orthogonal direct-sum decomposition

\C^{\Omega} = \bigoplus_{\lambda\in\Lambda} W_{\lambda}.

For each $\lambda \in \Lambda$ , write $\mathsf{F}_{\lambda}$ for the orthogonal projection onto $W_{\lambda}$ .

Basic properties of the projections

From the orthogonal direct-sum decomposition,

\mathsf{F}_{\lambda}\mathsf{F}_{\mu} = 0 \quad(\lambda \neq \mu), \qquad \mathsf{F}_{\lambda}^{2} = \mathsf{F}_{\lambda}, \qquad \sum_{\lambda \in \Lambda} \mathsf{F}_{\lambda} = I

holds. Also, since each $\mathsf{A}_{i}$ acts as multiplication by $\lambda_{i}$ on $W_{\lambda}$ ,

\mathsf{A}_{i} = \sum_{\lambda \in \Lambda} \lambda_{i} \mathsf{F}_{\lambda}.

Next we show that each $\mathsf{F}_{\lambda}$ actually belongs to $\mathcal{A}$ .

That

\mathsf{F}_{\lambda} \in \mathcal{A}

Fix $\lambda \in \Lambda$ . If $\mu \in \Lambda$ and $\mu \neq \lambda$ , then the common eigenvalue tuples are different, so there exists an index $i = i(\mu)$ such that $\lambda_{i(\mu)} \neq \mu_{i(\mu)}$ . Consider the polynomial

p_\lambda(X_{0}, \dots, X_{d}) = \prod_{\substack{\mu \in \Lambda \\ \mu \neq \lambda}} \frac{X_{i(\mu)}-\mu_{i(\mu)}}{\lambda_{i(\mu)}-\mu_{i(\mu)}}.

Substitute the commuting matrices $\mathsf{A}_{0}, \dots, \mathsf{A}_{d}$ into this polynomial. On $W_{\lambda}$ , each $\mathsf{A}_{i}$ acts as multiplication by $\lambda_{i}$ , so $p_\lambda(\mathsf{A}_{0}, \dots, \mathsf{A}_{d})$ acts as multiplication by $1$ on $W_{\lambda}$ . On the other hand, if $\nu \neq \lambda$ , then on $W_{\nu}$ the factor corresponding to $\mu = \nu$ in the product becomes $0$ . Hence $p_\lambda(\mathsf{A}_{0}, \dots, \mathsf{A}_{d})$ acts as multiplication by $0$ on $W_{\nu}$ .

Therefore

p_\lambda(\mathsf{A}_{0}, \dots, \mathsf{A}_{d}) = \mathsf{F}_{\lambda}.

The left-hand side is built from sums and products of $\mathsf{A}_{0}, \dots, \mathsf{A}_{d}$ . Since $\mathcal{A}$ is closed under matrix multiplication, it follows that $\mathsf{F}_{\lambda} \in \mathcal{A}$ .

We next determine the number of elements of $\Lambda$ .

The number of common eigenvalue tuples is

d+1

Let $m$ be the number of elements of $\Lambda$ . First, as shown above, the $\mathsf{F}_{\lambda}$ are non-zero orthogonal idempotents belonging to $\mathcal{A}$ . In particular, they are linearly independent. Indeed, if

\sum_{\lambda \in \Lambda} c_{\lambda}\mathsf{F}_{\lambda} = 0,

then restricting both sides to $W_{\mu}$ gives $c_{\mu} = 0$ . Hence

m \leq \dim_{\C} \mathcal{A}.

We prove the opposite inequality. Any $\mathsf{M} \in \mathcal{A}$ can be written in the form

\mathsf{M} = c_{0}\mathsf{A}_{0} + \dots + c_{d}\mathsf{A}_{d}.

Then on $W_{\lambda}$ , $\mathsf{M}$ acts as multiplication by $c_{0}\lambda_{0} + \dots + c_{d}\lambda_{d}$ . Thus the action of $\mathsf{M}$ is completely determined by its eigenvalue on each $W_{\lambda}$ .

Define a map $\Phi \colon \mathcal{A} \to \C^{\Lambda}$ by

\Phi(\mathsf{M}) \coloneqq \bigl( \text{the eigenvalue of $\mathsf{M}$ on $W_\lambda$} \bigr)_{\lambda\in\Lambda}.

If $\Phi(\mathsf{M}) = 0$ , then $\mathsf{M}$ acts as $0$ on every $W_{\lambda}$ . By the orthogonal direct-sum decomposition

\C^{\Omega} = \bigoplus_{\lambda \in \Lambda} W_{\lambda},

this means that $\mathsf{M}$ is the zero matrix. Thus $\Phi$ is injective, and

\dim_{\C} \mathcal{A} \leq m.

Therefore

m = \dim_{\C} \mathcal{A}.

Since we already saw that $\mathsf{A}_{0}, \dots, \mathsf{A}_{d}$ are linearly independent,

\dim_{\C} \mathcal{A} = d + 1.

Hence $m = d + 1$ .

We can therefore number the elements of $\Lambda$ as $\lambda^{(0)}, \lambda^{(1)}, \dots, \lambda^{(d)}$ . Define

\mathsf{E}_{r} \coloneqq \mathsf{F}_{\lambda^{(r)}} \qquad (0 \leq r \leq d).

Checking the listed properties

Since $\mathsf{E}_{r}$ is an orthogonal projection, $\mathsf{E}_{r}^{2} = \mathsf{E}_{r}$ . Since these are projections onto distinct common eigenspaces,

\mathsf{E}_{r} \mathsf{E}_{s} = 0 \qquad (r \neq s)

holds. Since the common eigenspaces sum to the whole space,

\mathsf{E}_{0} + \mathsf{E}_{1} + \dots + \mathsf{E}_{d} = I

also holds.

Moreover, $\mathsf{E}_{0}, \dots, \mathsf{E}_{d}$ are $d + 1$ linearly independent elements of $\mathcal{A}$ . Since $\dim_{\C} \mathcal{A} = d + 1$ , they form a basis of $\mathcal{A}$ .

Finally, each $\mathsf{A}_{i}$ acts on $W_{\lambda^{(r)}} = \mathsf{E}_{r}(\C^{\Omega})$ as multiplication by $\lambda_{i}^{(r)}$ . Thus each $\mathsf{A}_{i}$ acts as a scalar multiple on the image of each $\mathsf{E}_{r}$ .

It remains to check that these idempotents are primitive inside $\mathcal{A}$ .

Primitivity

Suppose that for some $r$ , $\mathsf{E}_{r} = \mathsf{G} + \mathsf{H}$ is a decomposition as a sum of two orthogonal idempotents $\mathsf{G},\mathsf{H}$ belonging to $\mathcal{A}$ . Thus

\mathsf{G}^{2} = \mathsf{G}, \qquad \mathsf{H}^{2} = \mathsf{H}, \qquad \mathsf{G}\mathsf{H} = 0.

Since $\mathsf{G}$ and $\mathsf{H}$ belong to $\mathcal{A}$ , they act as scalar multiples on each common eigenspace $W_{\lambda^{(s)}}$ . Write $g_{s}$ for the eigenvalue of $\mathsf{G}$ on $W_{\lambda^{(s)}}$ , and $h_{s}$ for the eigenvalue of $\mathsf{H}$ on $W_{\lambda^{(s)}}$ . Since $\mathsf{G}$ and $\mathsf{H}$ are idempotents,

g_{s}^{2} = g_{s}, \qquad h_{s}^{2} = h_{s}.

Hence $g_{s}, h_{s} \in \{ 0, 1 \}$ .

On the other hand, $\mathsf{E}_{r} = \mathsf{G} + \mathsf{H}$ . If $s \neq r$ , then $\mathsf{E}_{r}$ acts as $0$ on $W_{\lambda^{(s)}}$ , so $g_{s} + h_{s} = 0$ . Since $g_{s}, h_{s} \in \{ 0, 1 \}$ ,

g_{s} = h_{s} = 0.

If $s = r$ , then $\mathsf{E}_{r}$ acts as $1$ on $W_{\lambda^{(r)}}$ , so $g_{r} + h_{r} = 1$ . Hence

(g_{r}, h_{r}) = (1, 0) \quad\text{or}\quad (g_{r}, h_{r}) = (0, 1).

It follows that one of $\mathsf{G}$ and $\mathsf{H}$ acts as $1$ only on $W_{\lambda^{(r)}}$ , and as $0$ on all other common eigenspaces. Thus one of them is $\mathsf{E}_{r}$ . The other acts as $0$ on every common eigenspace, and is therefore the zero matrix.

Consequently

\{ \mathsf{G}, \mathsf{H} \} = \{ \mathsf{E}_{r}, 0 \}.

Thus $\mathsf{E}_{r}$ cannot be decomposed further, inside $\mathcal{A}$ , as a non-trivial sum of orthogonal idempotents.

This proves the theorem.

First let us check that this numbering is natural. In a symmetric association scheme, every adjacency matrix $\mathsf{A}_{i}$ has constant row sum. Indeed, since $(x,x)\in R_{0}$ for $x\in\Omega$ , the definition of the intersection number $p_{ii}^{0}$ gives

p_{ii}^{0} = \card{\{z\in\Omega:(x,z)\in R_{i},\ (z,x)\in R_{i}\}}.

By symmetry, $(z,x)\in R_{i}$ is equivalent to $(x,z)\in R_{i}$ , so

p_{ii}^{0} = \card{\{z\in\Omega:(x,z)\in R_{i}\}}.

The right-hand side is the sum of the $x$ -row of $\mathsf{A}_{i}$ , and the intersection number does not depend on $x$ . Thus the row sum of $\mathsf{A}_{i}$ is constant. Therefore the space of constant functions is a common eigenspace for all the $\mathsf{A}_{i}$ .

From now on, we number the projection onto the one-dimensional space of constant functions as $\mathsf{E}_{0}$ . This projection is

\mathsf{E}_{0} = \frac{1}{\card{\Omega}}J.

Indeed, since $J$ is the matrix all of whose entries are $1$ , $\card{\Omega}^{-1}J$ is the orthogonal projection onto the space of constant functions. Also,

J= \mathsf{A}_{0} + \mathsf{A}_{1} + \dots + \mathsf{A}_{d},

so this projection also belongs to $\mathcal A$ .

An idempotent is an element whose square is itself. A general idempotent matrix represents a projection along some direct-sum decomposition. The primitive idempotents here are also real symmetric, or self-adjoint, and hence are orthogonal projections with respect to the standard inner product. Thus primitive idempotents are the orthogonal projections onto the natural eigenspaces seen by the Bose–Mesner algebra. Here “primitive” means that, inside the Bose–Mesner algebra, the idempotent cannot be decomposed further as a non-trivial sum of orthogonal idempotents. It does not mean that the matrix has rank $1$ . Indeed, common eigenspaces need not be one-dimensional in general.

The adjacency matrices and the primitive idempotents are both bases of the Bose–Mesner algebra. Therefore each can be expressed as a linear combination of the other. We will write the concrete coefficients in the section on the Hamming scheme.

Thus, in an association scheme, we move between the following two bases.

basis representing relations: $\mathsf{A}_{0}, \dots, \mathsf{A}_{d}$ ↔ basis representing projections onto eigenspaces: $\mathsf{E}_{0}, \dots, \mathsf{E}_{d}$ .

In the association-scheme proof of the MacWilliams identity, this passage between the “relation side” and the “eigenspace side” is essential. The weight distribution of a code is defined on the relation side, while the dual distribution is defined by projection onto the eigenspace side. For a readable reference on the linear-algebraic treatment of Bose–Mesner algebras and primitive idempotents discussed in this section, see also Godsil [God93].

The Hamming Scheme

We now look at the Hamming scheme, the most important association scheme appearing in coding theory.

Let $E$ be a finite coordinate set, and let $n = \card{E}$ . This is a different symbol from the primitive idempotents $\mathsf{E}_j$ which appear later; the fonts distinguish them. Let the vertex set be $\Omega \coloneqq \F_{q}^{E}$ . Thus the vertices are $q$ -ary words of length $n$ . For two words $x, y \in \Omega$ , define the Hamming distance by

\dist(x, y) \coloneqq \wt(x - y).

Definition 5.1.

For $0\leq i\leq n$ , define

R_{i} \coloneqq \{ (x, y) \in \Omega \times \Omega : \dist(x, y) = i \}.

The association scheme obtained from this relation partition is called the Hamming scheme, and is denoted by $H(n, q)$ .

Write $\mathsf{A}_{i}$ for the adjacency matrix of $R_{i}$ . Thus $\mathsf{A}_{i}$ is the matrix joining two words whose distance is $i$ .

Theorem 5.2.

$H(n,q)$ is a symmetric association scheme.

Proof

$R_{0}$ is the diagonal relation, and since the Hamming distance is symmetric, each $R_{i}$ is symmetric. Also, any two words have exactly one distance among $0, 1, \dots, n$ , so $R_{0}, \dots, R_{n}$ partition $\Omega \times \Omega$ . Each $R_{i}$ is non-empty as well. Indeed, take the zero word $0 \in \F_{q}^{E}$ and a word $y$ which is non-zero in exactly $i$ coordinates; then $\dist(0, y) = i$ .

We check the intersection-number condition. Suppose $\dist(x, y) = k$ . We want to count the number of $z\in \Omega$ satisfying

\dist(x, z) = i, \qquad \dist(z, y) = j.

Since $\dist(x, y) = k$ , there are $n - k$ coordinates with $x_{e} = y_{e}$ , and $k$ coordinates with $x_{e} \neq y_{e}$ .

The contribution at each coordinate is summarised in the following table, where $\Delta_x$ and $\Delta_y$ denote the one-coordinate contributions to $\dist(x, z)$ and $\dist(z, y)$ :

case	$(\Delta_x, \Delta_y)$	choices
$x_{e} = y_{e},\ z_{e} = x_{e} = y_{e}$	$(0, 0)$	$1$
$x_{e} = y_{e},\ z_{e} \neq x_{e}$	$(1, 1)$	$q - 1$
$x_{e} \neq y_{e},\ z_{e} = x_{e}$	$(0, 1)$	$1$
$x_{e} \neq y_{e},\ z_{e} = y_{e}$	$(1, 0)$	$1$
$x_{e} \neq y_{e},\ z_{e} \neq x_{e}, y_{e}$	$(1, 1)$	$q - 2$

Recording the contribution to $\dist(x, z)$ by $s$ and the contribution to $\dist(z, y)$ by $t$ , the first two rows show that the one-coordinate generating function for a coordinate with $x_{e} = y_{e}$ is

1 + (q - 1)st,

and the last three rows show that the one-coordinate generating function for a coordinate with $x_e\neq y_e$ is

s + t + (q - 2)st.

Since the choices at different coordinates are independent, the total number is given by the product of these one-coordinate generating functions. Here the exponent of $s$ records the contribution to $\dist(x,z)$ , and the exponent of $t$ records the contribution to $\dist(z,y)$ . Thus the number of $z$ satisfying $\dist(x,z)=i$ and $\dist(z,y)=j$ can be written, for example, as

\lbrack s^{i} t^{j} \rbrack \bigl( 1 + (q - 1)st \bigr)^{n - k} \bigl( s + t + (q - 2)st \bigr)^{k}.

Here $\lbrack s^{i} t^{j} \rbrack$ denotes extraction of the coefficient of $s^{i} t^{j}$ in the expanded polynomial. When $q = 2$ , the term $q - 2 = 0$ expresses that there is no option “different from both”. This depends only on $n$ , $q$ , $i$ , $j$ , and $k$ , not on the concrete values of $x$ and $y$ . Hence the intersection-number condition holds.

In this proof we did not use an explicit formula for the intersection numbers. The important point is that the counting is governed not by the concrete positions of the two points $x$ and $y$ , but only by their distance $k$ . This is the homogeneity of Hamming space.

The row sum of $\mathsf{A}_{i}$ is the number of words at distance $i$ from a fixed word. It is

v_{i} = \binom{n}{i}(q-1)^{i}.

This $v_{i}$ is called the valency of the relation $R_{i}$ . Indeed, there are $\binom{n}{i}$ ways to choose the coordinates at distance $i$ , and in each such coordinate there are $q - 1$ choices different from the original value.

Eigenspaces of the Hamming Scheme

To understand the Bose–Mesner algebra of the Hamming scheme, we need to simultaneously diagonalise the adjacency matrices $\mathsf{A}_{0}, \dots, \mathsf{A}_{n}$ . This is where Krawtchouk polynomials appear.

We begin with one coordinate. Let the one-coordinate function space be $U = \C^{\F_q}$ . Inside $U$ there is the one-dimensional subspace $U_{0} = \C\one$ consisting of constant functions. Also define

U_{1} = \left\{ f \in U : \sum_{a \in \F_{q}} f(a) = 0 \right\},

the subspace of functions whose values sum to $0$ . With respect to the standard inner product, we have the orthogonal decomposition $U = U_{0} \oplus U_{1}$ .

Let $N = J - I$ be the one-coordinate adjacency matrix for “moving to a different value”. This is the adjacency matrix of the complete graph $K_{q}$ . The matrix $N$ acts on $U_{0}$ with eigenvalue $q - 1$ , and on $U_{1}$ with eigenvalue $-1$ . Indeed, on constant functions, from each point there are $q - 1$ other points to go to, so the eigenvalue is $q - 1$ . On the other hand, if $f \in U_{1}$ , then

(Nf)(a) = \sum_{b \neq a} f(b) = \sum_{b \in \F_{q}}f(b) - f(a) = -f(a).

For this note, it is enough to think of the tensor product as the operation which makes a function of many variables by multiplying one-variable functions over the coordinates, and which lets one-coordinate operators act independently on each coordinate. No general theory of tensor products is needed to understand this article.

The multi-coordinate space is

\C^{\Omega} = \C^{\F_{q}^{E}} \cong \bigotimes_{e \in E} U.

If for each $e \in E$ we choose a one-coordinate function $f_{e} \in U$ , then the pure tensor $\bigotimes_{e \in E} f_{e}$ represents the function

x = (x_{e})_{e \in E} \longmapsto \prod_{e \in E} f_{e}(x_{e}).

Also, the tensor product $\bigotimes_{e \in E} T_{e}$ of one-coordinate operators $T_{e} \colon U \to U$ should be understood as applying $T_{e}$ independently to the component in the $e$ -th coordinate. For example, when $E = \{ 1, 2 \}$ , the tensor $f_{1} \otimes f_{2}$ represents the two-variable function

(a, b) \longmapsto f_{1}(a)f_{2}(b).

Also, $T_{1} \otimes T_{2}$ acts by

(T_{1} \otimes T_{2})(f_{1} \otimes f_{2}) = (T_{1} f_{1}) \otimes (T_{2} f_{2}),

so it is the operator which applies $T_{1}$ to the first coordinate and $T_{2}$ to the second coordinate. For a general $E$ , this is simply extended to all coordinates. Decomposing each coordinate as $U = U_{0} \oplus U_{1}$ gives the orthogonal decomposition

\C^{\Omega} = \bigoplus_{S\subseteq E} \left( \bigotimes_{e\in S}U_1 \otimes \bigotimes_{e\notin S}U_0 \right).

Here $S$ denotes the set of coordinates in which we have chosen the non-constant direction.

Definition 6.1.

For $0 \leq w \leq n$ , define

V_w = \bigoplus_{\substack{S\subseteq E\\ \card{S} = w}} \left( \bigotimes_{e\in S}U_1 \otimes \bigotimes_{e\notin S}U_0 \right).

Then

\C^{\Omega} = V_{0} \oplus V_{1} \oplus \dots \oplus V_{n}.

For each direct-summand component with $\card{S}=w$ , the dimension is $(\dim U_{1})^{w} = (q - 1)^{w}$ , and there are $\binom{n}{w}$ such sets $S$ . Thus

\dim V_{w} = \binom{n}{w}(q - 1)^{w}.

Intuitively, $V_{w}$ is the component with non-constant direction in $w$ coordinates. This decomposition will be the eigenspace decomposition of the Hamming scheme.

Next consider the generating function collecting the distance matrices $\mathsf{A}_j$ . The $I$ and $N$ on the right-hand side are operators on the one-coordinate space $U = \C^{\F_{q}}$ . On the other hand, the $\mathsf{A}_{j}$ on the left-hand side are operators on the multi-coordinate space $\C^{\Omega} = \C^{\F_{q}^{E}}$ . Taking a tensor product extends the one-coordinate action independently to all coordinates. In one coordinate, keeping the same value is the action $I$ , and moving to a different value is the action $N = J - I$ . Therefore, on the multi-coordinate space,

\sum_{j=0}^{n}\mathsf{A}_{j} z^{j} = \bigotimes_{e \in E}(I + zN) \tag{6.1}

holds. Indeed, when the right-hand side is expanded, the coefficient of $z^{j}$ is exactly the operator which changes the value in precisely $j$ coordinates and keeps the remaining coordinates unchanged.

Definition 6.2.

For $0 \leq w \leq n$ , define numbers $\Kraw_{0}(w), \dots, \Kraw_{n}(w)$ by

\sum_{j=0}^{n}\Kraw_{j}(w)z^{j} = \bigl( 1 + (q - 1)z \bigr)^{n - w}(1 - z)^{w}. \tag{6.2}

These are called the values of the Krawtchouk polynomials associated with the $q$ -ary Hamming scheme.

Expanding the generating function gives

\Kraw_j(w) = \sum_{\ell=0}^{j} (-1)^\ell (q-1)^{j-\ell} \binom{w}{\ell} \binom{n-w}{j-\ell}.

Here binomial coefficients outside their range are interpreted as $0$ .

This definition may look as though we are introducing Krawtchouk polynomials as polynomials defined by a generating function, but the meaning here is slightly different. Equation (6.2) is the eigenvalue generating function for the adjacency matrices of the Hamming scheme.

Theorem 6.3.

Let $0 \leq j, w \leq n$ . The adjacency matrix $\mathsf{A}_{j}$ of the Hamming scheme acts on the eigenspace $V_{w}$ as multiplication by $\Kraw_{j}(w)$ .

Proof

An element of $V_w$ is a sum of tensors which have the $U_{1}$ direction in $w$ coordinates and the $U_{0}$ direction in the remaining $n - w$ coordinates. The one-coordinate matrix $N$ acts by $q - 1$ on $U_{0}$ and by $-1$ on $U_{1}$ . Therefore $\sum_{j} \mathsf{A}_{j} z^{j}$ acts on $V_{w}$ as multiplication by

\bigl( 1 + (q - 1)z \bigr)^{n - w}(1 - z)^{w}.

Comparing the coefficient of $z^{j}$ , the eigenvalue of $\mathsf{A}_{j}$ is $\Kraw_{j}(w)$ .

This theorem gives the following interpretation of the Krawtchouk polynomials.

A Krawtchouk polynomial is the eigenvalue of the distance- $j$ adjacency matrix of the Hamming scheme on the $w$ -th eigenspace $V_{w}$ .

As mentioned earlier, let us now organise the roles of the subscripts. The subscript $i$ of $\mathsf{A}_{i}$ is the distance-side index, while the subscript $w$ of $V_{w}$ , and later of $\mathsf{E}_{w}$ , is the eigenspace-side index. Thus $\Kraw_{i}(w)$ denotes the eigenvalue of the distance- $i$ adjacency matrix $\mathsf{A}_{i}$ on the $w$ -th eigenspace $V_w$ . On the other hand, when we later write

\mathsf{E}_{j} = \frac{1}{q^{n}} \sum_{i=0}^{n} \Kraw_{j}(i) \mathsf{A}_{i},

$j$ is on the eigenspace side and $i$ is on the distance side. In the Hamming scheme, these two sides are connected by Krawtchouk polynomials.

In particular, when $j = 1$ ,

\Kraw_{1}(w) = (q - 1)(n - w) - w = (q - 1)n - qw,

which takes distinct values for $w = 0, 1, \dots, n$ . Thus $V_{0}, V_{1}, \dots, V_{n}$ are already distinguished by $\mathsf{A}_{1}$ alone. Consequently, they are the common eigenspaces for the Bose–Mesner algebra of the Hamming scheme, and the corresponding orthogonal projections are the primitive idempotents. Indeed, since the eigenvalues of $\mathsf{A}_{1}$ on $V_{0}, \dots, V_{n}$ are distinct, Lagrange interpolation gives

\mathsf{E}_{w} = \prod_{\substack{u = 0 \\ u \neq w}}^{n} \frac{\mathsf{A}_{1} - \Kraw_{1}(u)I}{\Kraw_{1}(w)-\Kraw_{1}(u)}.

This formula extracts the projection onto $V_{w}$ as a polynomial in $\mathsf{A}_{1}$ . Therefore $\mathsf{E}_{w}$ belongs to the Bose–Mesner algebra. In this sense, for the Hamming scheme, primitive idempotents can be understood explicitly without relying on the general theory of semisimple algebras.

This viewpoint is the heart of the association-scheme perspective. The polynomial does not come first; rather, when one simultaneously diagonalises the matrix algebra built from the distance relations, the Krawtchouk polynomials appear as its eigenvalues.

Writing the Primitive Idempotents Explicitly

Write $\mathsf{E}_{w}$ for the orthogonal projection onto $V_{w}$ . Then $\mathsf{E}_{0}, \mathsf{E}_{1}, \dots, \mathsf{E}_{n}$ are the primitive idempotents of the Bose–Mesner algebra of the Hamming scheme. That is,

\mathsf{E}_{r}\mathsf{E}_{s} = \delta_{r, s} \mathsf{E}_{r}, \qquad \sum_{r=0}^{n}\mathsf{E}_{r} = I,

and each $\mathsf{A}_{j}$ acts on the image of $\mathsf{E}_{w}$ as multiplication by $\Kraw_{j}(w)$ . The image is exactly $V_w$ , and

\dim \mathsf{E}_w(\C^{\Omega}) = \dim V_{w} = \binom{n}{w}(q-1)^{w}.

Thus the primitive idempotents of the Hamming scheme are also generally not of rank $1$ .

We can write this projection explicitly as a linear combination of the adjacency matrices $\mathsf{A}_i$ . For this, look at the one-coordinate projections. Let $\Pi_{0}$ be the orthogonal projection onto $U_{0}$ , and let $\Pi_{1}$ be the orthogonal projection onto $U_{1}$ . Then

\Pi_{0} = \frac{1}{q}J, \qquad \Pi_{1} = I - \frac{1}{q}J.

In components, for $a, b \in \F_{q}$ ,

\Pi_{0}(a, b) = \frac{1}{q} \qquad \Pi_{1}(a,b) = \begin{cases} \dfrac{q-1}{q}, & a = b,\\[4pt] -\dfrac{1}{q}, & a \neq b. \end{cases}

For $S\subseteq E$ , consider the projection obtained by applying $\Pi_1$ in the coordinates of $S$ and $\Pi_0$ in the remaining coordinates. Summing all such projections with $\card{S} = w$ gives $\mathsf{E}_{w}$ . When we compute its entries, Krawtchouk polynomials appear again.

Theorem 7.1.

The primitive idempotents of the Hamming scheme $H(n,q)$ can be written as

\mathsf{E}_j = \frac{1}{q^n} \sum_{i=0}^{n}\Kraw_j(i)\mathsf{A}_i. \tag{7.1}

Proof

Take $x,y\in \Omega=\F_q^E$ , and suppose $\dist(x,y)=i$ . We compute the $(x,y)$ entry of $\mathsf{E}_j$ . The projection $\mathsf{E}_j$ is the sum, over subsets $S\subseteq E$ with $\card{S}=j$ , of the projections which apply $\Pi_1$ in the coordinates of $S$ and $\Pi_0$ in the remaining coordinates.

Putting these together as a generating function,

\begin{aligned} \sum_{j=0}^{n} q^n(\mathsf{E}_j)_{x,y}z^j &= \prod_{e\in E} \left(q\Pi_0(x_e,y_e)+q\Pi_1(x_e,y_e)z\right). \end{aligned}

If $x_e=y_e$ , then

q\Pi_0(x_e,y_e)=1, \qquad q\Pi_1(x_e,y_e)=q-1.

If $x_e\neq y_e$ , then

q\Pi_0(x_e,y_e)=1, \qquad q\Pi_1(x_e,y_e)=-1.

Since $x$ and $y$ differ in $i$ coordinates and agree in $n-i$ coordinates,

\sum_{j=0}^{n} q^n(\mathsf{E}_j)_{x,y}z^j = \bigl(1+(q-1)z\bigr)^{n-i}(1-z)^i = \sum_{j=0}^{n}\Kraw_j(i)z^j.

Hence

(\mathsf{E}_j)_{x,y} = \frac{1}{q^n}\Kraw_j(i).

This means that the entry is $q^{-n}\Kraw_j(i)$ at positions of distance $i$ . On the other hand,

\frac{1}{q^n}\sum_{i=0}^{n}\Kraw_j(i)\mathsf{A}_i

is the matrix which places exactly $q^{-n}\Kraw_j(i)$ in the entries of distance $i$ , since $\mathsf{A}_i$ has $1$ exactly in positions of distance $i$ . Therefore

\mathsf{E}_j = \frac{1}{q^n}\sum_{i=0}^{n}\Kraw_j(i)\mathsf{A}_i.

All entries agree, so the matrices are equal.

This formula is very important. The left-hand side is a projection onto an eigenspace. The right-hand side is a linear combination of adjacency matrices representing distance relations. Thus the Krawtchouk polynomials are

the coefficients connecting the relation-side basis $\mathsf{A}_i$ and the eigenspace-side basis $\mathsf{E}_{j}$ .

Let us relate this to the general theory. For a general association scheme, when we write

\mathsf{A}_i = \sum_{r=0}^{d}P_r(i)\mathsf{E}_r, \qquad \mathsf{E}_r = \frac{1}{\card{\Omega}} \sum_{i=0}^{d}Q_r(i)\mathsf{A}_i,

the coefficients are called the first eigenmatrix $P$ and the second eigenmatrix $Q$ , respectively. In the notation for the Hamming scheme used in this note,

\mathsf{A}_i=\sum_{w=0}^{n}\Kraw_i(w)\mathsf{E}_w, \qquad \mathsf{E}_j=\frac{1}{q^n}\sum_{i=0}^{n}\Kraw_j(i)\mathsf{A}_i,

so this corresponds to $P_w(i)=\Kraw_i(w)$ and $Q_j(i)=\Kraw_j(i)$ .

In the Hamming scheme, the same type of Krawtchouk polynomial appears in the two directions of this change of basis. However, the simple symmetry $\Kraw_{j}(i) = \Kraw_{i}(j)$ does not hold in general. More precisely, using the valency $v_{i} = \binom{n}{i}(q-1)^{i}$ , we have the weighted symmetry

v_{i} \Kraw_{j}(i) = v_{j}\Kraw_{i}(j).

Inner Distributions: Viewing Codes from the Relation Side

We now return to codes. In an association scheme, for a subset $D\subseteq \Omega$ of the finite set $\Omega$ , we count which relations connect pairs of points inside that subset. This is the inner distribution. Inner and dual distributions are fundamental quantities in Delsarte's association-scheme approach to coding theory [Del73; Cam98].

Let us first organise some similar notation. $\mathsf{A}_i$ is the adjacency matrix for distance $i$ , $A_i(C)$ is the number of codewords of weight $i$ in a linear code $C$ , and $a_i(D)$ is the inner distribution of a subset $D$ .

Definition 8.1.

For a subset $D\subseteq \Omega$ , define its characteristic vector by

\one_D = \sum_{x\in D}e_x \in \C^{\Omega}.

We use the standard inner product

\langle f,g\rangle = \sum_{x\in \Omega}f(x)\overline{g(x)}.

Using the adjacency matrix $\mathsf{A}_i$ , the number of ordered pairs in $D$ at distance $i$ is $\langle \mathsf{A}_{i} \one_{D}, \one_{D} \rangle$ .

Definition 8.2.

Let $D\subseteq \Omega$ be a non-empty subset. The inner distribution of $D$ is defined by

a_i(D) = \frac{1}{\card{D}} \langle \mathsf{A}_i\one_D,\one_D\rangle \qquad (0\leq i\leq n).

With this normalisation, $a_0(D)=1$ . Indeed, since $\mathsf{A}_0=I$ ,

a_{0}(D) = \frac{1}{\card{D}} \langle \one_{D}, \one_{D} \rangle = 1.

Also,

\sum_{i=0}^{n}a_i(D) = \frac{1}{\card{D}} \left\langle \sum_{i=0}^{n}\mathsf{A}_i\one_D,\one_D \right\rangle = \frac{1}{\card{D}}\langle J\one_D,\one_D\rangle = \card{D},

so with this normalisation it is not a probability distribution. It is useful to think of $a_i(D)$ as the average number of points of $D$ which are in relation $R_i$ to a fixed point of $D$ . In the Hamming scheme, this reads as the average number of points of $D$ at distance $i$ .

For a linear code, the inner distribution agrees with the usual weight distribution.

Theorem 8.3.

Let $C \leq \F_{q}^{E}$ be a linear code. Write the usual weight distribution as $A_{i}(C) = \card{\{ c \in C : \wt(c) = i \}}$ . Then $a_{i}(C) = A_{i}(C)$ .

Proof

The quantity $\langle \mathsf{A}_i\one_C,\one_C\rangle$ is the number of ordered pairs $(x,y)$ satisfying

x,y\in C, \qquad \dist(x,y)=i.

Since $C$ is a linear code, the difference $y-x$ again belongs to $C$ . Also, $\dist(x,y)=\wt(y-x)$ .

Fix a codeword $d\in C$ of weight $i$ . The pairs $(x,y)\in C^2$ satisfying $y-x=d$ are obtained by choosing $x\in C$ arbitrarily and putting $y=x+d$ , so there are exactly $\card{C}$ such pairs. Since there are $A_i(C)$ codewords of weight $i$ ,

\langle \mathsf{A}_i\one_C,\one_C\rangle = \card{C}A_i(C).

Hence $a_{i}(C) = A_{i}(C)$ .

This theorem shows that the language of association schemes contains the weight distribution of coding theory. For a general subset $D\subseteq \Omega$ , $a_{i}(D)$ is the distance distribution inside $D$ . For a linear code, taking differences returns us to the usual weight distribution.

Dual Distributions: Viewing Codes from the Eigenspace Side

The inner distribution was defined using the adjacency matrices $\mathsf{A}_i$ . This is information on the relation side. In an association scheme, there is another distribution, defined using the primitive idempotents $\mathsf{E}_j$ . This is the dual distribution.

Definition 9.1.

Let $D\subseteq \Omega$ be a non-empty subset. The dual distribution of $D$ is defined by

a_j^{\ast}(D) = \frac{\card{\Omega}}{\card{D}^2} \langle \mathsf{E}_j\one_D,\one_D\rangle \qquad (0\leq j\leq n).

Here

\langle \mathsf{E}_j\one_D,\one_D\rangle = \langle \mathsf{E}_j\one_D,\mathsf{E}_j\one_D\rangle

is the squared norm of the $V_j$ component of the characteristic vector $\one_D$ . If we used this quantity as it stands, its scale would not match the weight distribution of the dual code in the case of a linear code. Thus we multiply by the factor $\displaystyle \frac{\card{\Omega}}{\card{D}^2}$ , normalising it so that $a_j^{\ast}(C)=A_j(C^\perp)$ when $D=C$ is a linear code.

With this normalisation, $a_0^{\ast}(D)=1$ . Indeed, the projection onto the space of constant functions is $\mathsf{E}_0=\card{\Omega}^{-1}J$ , so

\langle \mathsf{E}_0\one_D,\one_D\rangle = \frac{\card{D}^2}{\card{\Omega}}.

Also,

\sum_{j=0}^{n}a_j^{\ast}(D) = \frac{\card{\Omega}}{\card{D}^2} \left\langle \sum_{j=0}^{n}\mathsf{E}_j\one_D,\one_D \right\rangle = \frac{\card{\Omega}}{\card{D}}.

Therefore the dual distribution is not a probability distribution with this normalisation either. For a linear code $C$ , this corresponds to $\card{C^{\perp}}=\card{\Omega}/\card{C}$ and agrees with the sum of the weight distribution of the dual code. For a general subset $D\subseteq \Omega$ , there is no dual code $D^{\perp}$ in the usual sense. Nevertheless, the distribution $a_j^{\ast}(D)$ seen from the eigenspace side of the Bose–Mesner algebra can still be defined. Non-negativity follows from the fact that $\mathsf{E}_j$ is an orthogonal projection.

As a warning, for a general subset $D$ , the number $a_j^{\ast}(D)$ need not be an integer, and it is not directly counting the elements of anything. It is the size of the eigenspace component of the characteristic vector $\one_D$ , normalised so that, in the case of a linear code, it agrees with the weight distribution of the dual code.

This definition may look a little abstract. But its meaning is simple. We decompose the characteristic vector $\one_D$ into the eigenspaces $V_{0}, V_{1}, \dots, V_{n}$ of the Hamming scheme, and look at the size of each component. Since $\mathsf{E}_j$ is the orthogonal projection onto $V_j$ ,

\langle \mathsf{E}_j\one_D,\one_D\rangle = \langle \mathsf{E}_j\one_D,\mathsf{E}_j\one_D\rangle \geq 0.

Thus the dual distribution is non-negative.

For a general subset $D$ , $a_j^{\ast}(D)$ is the dual distribution in Delsarte's sense. For a linear code, it is genuinely the weight distribution of the dual code. This fact connects the association-scheme proof with ordinary coding theory.

In the next theorem we use additive characters just once. The purpose is to check that the dual distribution defined in the association scheme agrees, for a linear code, with the usual weight distribution of the dual code $C^\perp$ . Thus what is needed here is not the whole theory of characters, but only the basic orthogonality relation for additive characters of finite fields.

Theorem 9.2.

Let $C \leq \F_{q}^{E}$ be a linear code. Then $a_{j}^{\ast}(C) = A_{j}(C^{\perp})$ .

Proof

Fix a non-trivial additive character $\psi \colon \F_{q} \to \C^{\times}$ of the finite field. For example, when $q=p^m$ ,

\psi(a) = \exp\left(\frac{2\pi \sqrt{-1}}{p}\Tr_{\F_q/\F_p}(a)\right)

gives a non-trivial additive character. However, we will not enter the details of this construction. In what follows, we use only the basic orthogonality relation for a non-trivial additive character:

\sum_{a\in\F_q}\psi(ta) = \begin{cases} q, & t=0,\\ 0, & t\neq 0. \end{cases}

For $u\in\F_q^E$ , put

\chi_u(x)=\psi(u\cdot x) \qquad (x\in\F_q^E).

This decomposes coordinatewise as

\chi_u(x) = \psi(u\cdot x) = \prod_{e\in E}\psi(u_ex_e).

Thus, in one coordinate, if $u_e=0$ then the function lies in the constant direction, and if $u_e\neq 0$ then it is naturally seen to lie in the direction where the sum of values is $0$ . This is why, later, $\chi_u\in V_j$ corresponds to $\wt(u)=j$ . We also use the fact that additive characters have complex absolute value $1$ , so

\overline{\psi(v\cdot x)}=\psi(-v\cdot x).

After normalisation, these functions form an orthonormal basis of $\C^{\Omega}$ . Indeed, for $u,v\in\F_q^E$ ,

\begin{aligned} \langle \chi_u,\chi_v\rangle &= \sum_{x\in\F_q^E}\psi((u-v)\cdot x)\\ &= \prod_{e\in E} \sum_{x_e\in\F_q}\psi((u_e-v_e)x_e). \end{aligned}

If $u=v$ , this product is $q^n$ . If $u\neq v$ , then for some coordinate $u_e-v_e\neq 0$ , and the corresponding factor is $0$ . Hence

\{q^{-n/2}\chi_u:u\in\F_q^E\}

is an orthonormal basis of $\C^{\Omega}$ .

In one coordinate, when $u_e=0$ , the function $x_e\mapsto\psi(u_ex_e)$ is constant, and when $u_e\neq0$ , the sum of its values is $0$ . Therefore $\chi_u$ belongs to $V_j$ if and only if $\wt(u)=j$ . Thus $\mathsf{E}_j$ is the projection onto the span of the characters of weight $j$ .

We now compute the norm of the weight- $j$ component of $\one_C$ . By Parseval's identity for the orthonormal basis,

\begin{aligned} \langle \mathsf{E}_j\one_C,\one_C\rangle &= \sum_{\substack{u\in\F_q^E\\ \wt(u)=j}} \left\lvert \left\langle \one_C,q^{-n/2}\chi_u\right\rangle \right\rvert^2. \end{aligned}

Here

\left\langle \one_C,q^{-n/2}\chi_u\right\rangle = q^{-n/2}\sum_{c\in C}\overline{\psi(u\cdot c)}.

The right-hand side is $q^{-n/2}\overline{S_u}$ , where

S_u\coloneqq\sum_{c\in C}\psi(u\cdot c).

If $u\in C^{\perp}$ , then $u\cdot c=0$ for all $c\in C$ , so

S_u=\card{C}.

On the other hand, if $u\notin C^{\perp}$ , then $c \mapsto u \cdot c$ is a non-zero $\F_q$ -linear map on $C$ and is therefore surjective onto $\F_q$ . Each value occurs exactly $\card{C}/q$ times. Thus

S_u = \frac{\card{C}}{q}\sum_{a\in\F_q}\psi(a) = 0.

Therefore

\langle \mathsf{E}_j\one_C,\one_C\rangle = \frac{\card{C}^2}{q^n} \card{\{u\in C^{\perp}:\wt(u)=j\}} = \frac{\card{C}^2}{q^n}A_j(C^{\perp}).

Since $\card{\Omega}=q^n$ , the definition of the dual distribution gives

a_j^{\ast}(C) = \frac{q^n}{\card{C}^2} \langle \mathsf{E}_j\one_C,\one_C\rangle = A_j(C^{\perp}).

Characters appeared only briefly in this theorem. Their role was to check that, in the case of a linear code, the eigenspace side of the Hamming scheme is seeing the usual dual code. From the association-scheme viewpoint, $C^{\perp}$ first appears as the dual distribution. For a linear code, this dual distribution agrees with the usual weight distribution of the dual code.

The Coefficient-Level MacWilliams Identity

With the preparation so far, the MacWilliams identity is almost proved. First we write a transform formula for a general subset.

Proposition 10.1.

Let $D\subseteq \Omega$ be a non-empty subset. Then

a_j^\ast(D) = \frac{1}{\card{D}} \sum_{i=0}^{n}a_i(D)\Kraw_j(i) \tag{10.1}

holds.

Proof

By the definition of the dual distribution,

a_j^\ast(D) = \frac{\card{\Omega}}{\card{D}^2} \langle \mathsf{E}_j\one_D,\one_D\rangle.

Substituting Theorem 7.1 and using $\card{\Omega}=q^n$ , we get

\begin{aligned} a_j^\ast(D) &= \frac{q^n}{\card{D}^2} \left\langle \frac{1}{q^n}\sum_{i=0}^{n}\Kraw_j(i)\mathsf{A}_i\one_D, \one_D \right\rangle\\ &= \frac{1}{\card{D}^2} \sum_{i=0}^{n}\Kraw_j(i)\langle \mathsf{A}_i\one_D,\one_D\rangle\\ &= \frac{1}{\card{D}} \sum_{i=0}^{n}\Kraw_j(i)a_i(D). \end{aligned}

For a linear code $C$ , by Theorem 8.3 and Theorem 9.2,

a_i(C)=A_i(C), \qquad a_j^\ast(C)=A_j(C^\perp).

Thus this general formula is exactly the coefficient-level MacWilliams identity.

Theorem 10.2 (The Coefficient-Level MacWilliams Identity).

Let $C\leq\F_q^E$ be a linear code. Put $A_i=A_i(C)$ and $B_j=A_j(C^{\perp})$ . Then

B_j = \frac{1}{\card{C}} \sum_{i=0}^{n}A_i\Kraw_j(i) \tag{10.2}

holds.

Proof

Applying Proposition 10.1 to $D=C$ gives

a_j^\ast(C) = \frac{1}{\card{C}} \sum_{i=0}^{n}a_i(C)\Kraw_j(i).

By Theorem 8.3 and Theorem 9.2,

a_i(C)=A_i, \qquad a_j^\ast(C)=A_j(C^\perp)=B_j,

B_j = \frac{1}{\card{C}} \sum_{i=0}^{n}A_i\Kraw_j(i).

The structure of this proof has three stages.

The weight distribution is expressed as the relation-side quantity

$\langle \mathsf{A}_i\one_C,\one_C\rangle.$
The weight distribution of the dual code is expressed as the eigenspace-side quantity

$\langle \mathsf{E}_j\one_C,\one_C\rangle.$
Expanding $\mathsf{E}_j$ as a linear combination of the $\mathsf{A}_i$ , Krawtchouk polynomials appear as the coefficients.

Thus the MacWilliams identity appears as

the change-of-basis formula between the two bases of the Bose–Mesner algebra: the adjacency-matrix basis and the primitive-idempotent basis.

The Polynomial Form of the MacWilliams Identity

We now derive the usual polynomial form of the MacWilliams identity from the coefficient-level formula.

Theorem 11.1 (MacWilliams Identity).

Let $C\leq\F_q^E$ be a linear code. Then

W_{C^{\perp}}(X,Y) = \frac{1}{\card{C}} W_C\bigl(X+(q-1)Y,X-Y\bigr)

holds.

Proof

Put $A_i=A_i(C)$ and $B_j=A_j(C^{\perp})$ . By Theorem 10.2,

\begin{aligned} W_{C^{\perp}}(X,Y) &= \sum_{j=0}^{n}B_jX^{n-j}Y^j\\ &= \frac{1}{\card{C}} \sum_{j=0}^{n} \sum_{i=0}^{n}A_i\Kraw_j(i)X^{n-j}Y^j\\ &= \frac{1}{\card{C}} \sum_{i=0}^{n}A_i \sum_{j=0}^{n}\Kraw_j(i)X^{n-j}Y^j. \end{aligned}

In the generating function for Krawtchouk polynomials,

\sum_{j=0}^{n}\Kraw_j(i)z^j = \bigl(1+(q-1)z\bigr)^{n-i}(1-z)^i,

multiply both sides by $X^n$ and read $z^j$ as $X^{-j}Y^j$ . This gives

\sum_{j=0}^{n}\Kraw_j(i)X^{n-j}Y^j = \bigl(X+(q-1)Y\bigr)^{n-i}(X-Y)^i.

This is a calculation of polynomial identities; we are not dividing by $X$ as a number. Therefore

\begin{aligned} W_{C^{\perp}}(X,Y) &= \frac{1}{\card{C}} \sum_{i=0}^{n}A_i \bigl(X+(q-1)Y\bigr)^{n-i}(X-Y)^i\\ &= \frac{1}{\card{C}} W_C\bigl(X+(q-1)Y,X-Y\bigr). \end{aligned}

This proves the MacWilliams identity.

In this proof, the change of variables

X\mapsto X+(q-1)Y, \qquad Y\mapsto X-Y

came from the eigenvalue generating function of the Hamming scheme. Thus the change of variables is not merely an algebraic accident: it packages the eigenvalues of the matrices representing the distance relations.

A Small Example: $H(2,2)$ and the Binary Repetition Code

Finally, we check the association-scheme viewpoint in a small example. Let $\Omega=\F_2^2$ , and consider the Hamming scheme $H(2,2)$ . The vertices are

00,01,10,11.

The relations are divided by distance as

\begin{aligned} R_0&=\{(x,x):x\in \Omega\},\\ R_1&=\{(x,y):\dist(x,y)=1\},\\ R_2&=\{(x,y):\dist(x,y)=2\}. \end{aligned}

If the vertices are ordered as $00,01,10,11$ , the corresponding adjacency matrices are

\mathsf{A}_0=I, \qquad \mathsf{A}_1= \begin{pmatrix} 0&1&1&0\\ 1&0&0&1\\ 1&0&0&1\\ 0&1&1&0 \end{pmatrix}, \qquad \mathsf{A}_2= \begin{pmatrix} 0&0&0&1\\ 0&0&1&0\\ 0&1&0&0\\ 1&0&0&0 \end{pmatrix}.

For $q=2$ and $n=2$ , the Krawtchouk table is

\begin{array}{c|rrr} & w=0 & w=1 & w=2 \\ \hline j=0 & 1 & 1 & 1 \\ j=1 & 2 & 0 & -2 \\ j=2 & 1 & -1 & 1 \end{array}.

This is the table of eigenvalues of $\mathsf{A}_j$ on the eigenspaces $V_w$ . The row index $j$ is on the distance side, and the column index $w$ is on the eigenspace side.

Consider the binary repetition code

C=\{00,11\}\leq\F_2^2.

This code is self-dual. Its weight distribution is

(A_0,A_1,A_2)=(1,0,1).

The coefficient-level MacWilliams identity says

B_j = \frac{1}{\card{C}} \sum_{i=0}^{2}A_i\Kraw_j(i).

Here $\card{C}=2$ , $A_0=A_2=1$ , and $A_1=0$ , so

B_j = \frac{1}{2}\bigl(\Kraw_j(0)+\Kraw_j(2)\bigr).

Using the values in the table above,

B_{0} = \frac{1}{2}(1 + 1) = 1, \qquad B_{1} = \frac{1}{2}(2 - 2) = 0, \qquad B_{2} = \frac{1}{2}(1 + 1) = 1.

Therefore

(B_{0}, B_{1}, B_{2}) = (1, 0, 1),

which indeed agrees with the weight distribution of $C^{\perp} = C$ . In association-scheme terms, this says that

a(C)=(1,0,1), \qquad a^\ast(C)=(1,0,1).

The latter is the dual distribution obtained from the sizes of the components of $\one_C$ after projecting it to $V_0,V_1,V_2$ . Indeed, with vertex order $00,01,10,11$ ,

\one_{C} = (1,0,0,1),

and

\one_{C} = \frac{1}{2}(1,1,1,1) + \frac{1}{2}(1,-1,-1,1).

The first component is a constant vector, so it belongs to $V_0$ . The second component can be written as

(1,-1,-1,1) = (1, -1) \otimes (1, -1),

so it belongs to $V_{2}$ , and the $V_{1}$ component is $0$ . The squared norms of these components correspond to $1,0,1$ , respectively, so the fact that the dual distribution is $(1,0,1)$ can be seen directly from this projection decomposition, not only from the Krawtchouk transform.

From the association-scheme viewpoint, this calculation looks as follows. First, the distance distribution of pairs inside $C$ is measured by the adjacency matrices $\mathsf{A}_0,\mathsf{A}_1,\mathsf{A}_2$ . Next, the characteristic vector $\one_C$ is projected onto the eigenspaces $V_{0}$ , $V_{1}$ , $V_{2}$ , and we look at the sizes of those projected components. The transform coefficients connecting these two pieces of information are precisely the Krawtchouk values appearing in the table.

What Association Schemes Did in This Proof

Let us organise the role that association schemes played in the proof.

First, the association scheme turned the distance structure of Hamming space into a matrix algebra. From the relation of distance $i$ , we formed the adjacency matrix $\mathsf{A}_i$ , and considered the Bose–Mesner algebra spanned by these matrices. This algebra contains the distance structure of Hamming space in a compressed form.

Second, two bases of the Bose–Mesner algebra appeared. One is the adjacency-matrix basis $\mathsf{A}_{0}, \dots, \mathsf{A}_{n}$ , which represents distance relations. The other is the primitive-idempotent basis $\mathsf{E}_{0}, \dots, \mathsf{E}_{n}$ , which represents projections onto eigenspaces. The MacWilliams identity appeared as the change of basis between these two bases.

Third, the Krawtchouk polynomials appeared as eigenvalues. The adjacency matrix $\mathsf{A}_{j}$ acted on the eigenspace $V_{w}$ as multiplication by $\Kraw_j(w)$ . Thus the Krawtchouk polynomials are the table recording the eigenvalues of the Hamming scheme.

Fourth, the weight distribution of a code appeared as an inner distribution. For a linear code $C$ , the inner distribution

a_{i}(C) = \frac{1}{\card{C}}\langle \mathsf{A}_{i} \one_{C}, \one_{C} \rangle

agreed with the usual weight distribution $A_{i}(C)$ .

Fifth, the weight distribution of the dual code appeared as a dual distribution. Using primitive idempotents, define

a_{j}^{\ast}(C) = \frac{q^{n}}{\card{C}^{2}} \langle \mathsf{E}_{j} \one_{C}, \one_{C} \rangle.

For a linear code, $a_{j}^{\ast}(C) = A_{j}(C^{\perp})$ .

Thus the point of this proof can be summarised in one sentence:

The MacWilliams identity is the change of basis, in the Bose–Mesner algebra of the Hamming scheme, between the adjacency-matrix basis and the primitive-idempotent basis.

Concepts Seen in This Instalment

In this instalment, while aiming at a proof of the MacWilliams identity, we introduced the basic tools of association schemes. They can be summarised as follows.

Relation partition: This is a partition of $\Omega\times \Omega$ , for a finite set $\Omega$ , into relations $R_{0}, R_{1}, \dots, R_{d}$ . In the Hamming scheme, the partition is according to whether the distance between two words is $0, 1, \dots, n$ .
Adjacency matrix: This is the $0$ - $1$ matrix representing a relation $R_{i}$ . Turning relations into matrices allows us to use tools from linear algebra.
Association scheme: This is a situation where a relation partition is sufficiently regular and the intersection numbers $p_{ij}^{k}$ are defined. In matrix terms, it is the situation where the adjacency matrices are closed under multiplication.
Bose–Mesner algebra: This is the matrix algebra spanned by the adjacency matrices $\mathsf{A}_{0}, \dots, \mathsf{A}_{d}$ . In a symmetric association scheme, it is generated by real symmetric, mutually commuting adjacency matrices, so these adjacency matrices can be simultaneously diagonalised. In the language of abstract algebra, it is a commutative semisimple algebra.
Primitive idempotents: These are the projections onto the common eigenspaces of the Bose–Mesner algebra. In the Hamming scheme, they appear as the projections $\mathsf{E}_{0}, \dots, \mathsf{E}_{n}$ onto $V_{0}, \dots, V_{n}$ .
Hamming scheme: This is the association scheme on $\Omega = \F_{q}^{E}$ in which relations are divided according to the Hamming distance between two words. It is the example most directly connected with coding theory.
Krawtchouk polynomials: These are the eigenvalues of the adjacency matrix $\mathsf{A}_{j}$ of the Hamming scheme on the eigenspace $V_{w}$ . The generating function is

$\sum_{j=0}^{n} \Kraw_{j}(w) z^{j} = \bigl( 1 + (q - 1)z \bigr)^{n - w}(1 - z)^{w}.$
Inner distribution: This is the distribution counting how often two points in a subset $D\subseteq \Omega$ are in each relation $R_{i}$ . For a linear code, it agrees with the usual weight distribution.
Dual distribution: This is the distribution obtained by projecting the characteristic vector by the primitive idempotents and measuring the size of each eigenspace component. For a linear code, it agrees with the usual weight distribution of the dual code.

From the association-scheme viewpoint, a code is treated not merely as a linear subspace, but as a subset of the finite set Hamming space, which has a distance structure. The MacWilliams identity appears at the point where the distance distribution of that subset is connected to the eigenspace decomposition of the Bose–Mesner algebra.

Looking Back at This Proof Family

As stated at the beginning, the proof in this note belongs to the

orthogonal-polynomial and association-scheme family.

On the surface, it is a proof using adjacency matrices and the Bose–Mesner algebra built from the Hamming distance. At a deeper level, the distance structure of Hamming space forms a commutative matrix algebra, and its eigenvalue theory controls the transform of weight distributions.

When Krawtchouk polynomials are brought to the foreground, the MacWilliams identity is

a Krawtchouk transform of the weight distribution.

From the association-scheme viewpoint, one can understand this one step more deeply as

the Krawtchouk transform is the change of basis in the Bose–Mesner algebra of the Hamming scheme.

The advantage of this viewpoint is that it places the MacWilliams identity in a broader framework. Not only in the Hamming scheme, but also in many association schemes such as the Johnson schemes, the Grassmann schemes, and the dual polar schemes, notions such as inner distributions, dual distributions, eigenvalues, and linear-programming bounds appear in the same form. Delsarte's linear programming method in coding theory is also naturally derived from this association-scheme perspective. For this broader framework, see Delsarte [Del73] and Delsarte–Levenshtein [DL98].

The point of the proof in this note is the following sentence.

When the Bose–Mesner algebra of the complete graph coloured by Hamming distance is diagonalised, the Krawtchouk polynomials appear as its eigenvalues, and the MacWilliams identity is obtained as the formula connecting the relation-side distribution and the eigenspace-side distribution.

Next Time

Next time, we look at the MacWilliams identity from the viewpoint of moment identities.

In this proof, we transformed the weight distribution itself using the adjacency matrices and primitive idempotents of the Hamming scheme. Next time, instead of transforming the weight distribution directly, we first focus on moments such as

\sum_{i=0}^{n} A_{i}(C) i^{r} \quad\text{or}\quad \sum_{i=0}^{n} A_{i}(C) \binom{i}{r}.

Moments of the weight distribution can be computed by counting pairs consisting of a codeword and a coordinate subset in two ways. From this, the Pless power moment identities appear. Collecting sufficiently many moment identities lets us recover the whole MacWilliams transform of the weight distribution.

Thus the protagonists next time will be

weight distributions → moments → double counting → the MacWilliams identity

Even for the same MacWilliams identity, we will see a counting-theoretic form quite different from the eigenvalue and matrix-algebra viewpoint of this note.

References

[Del73] P. Delsarte. An algebraic approach to the association schemes of coding theory. Philips Res. Rep. Suppl., no. 10, pp. vi+97, 1973 Citation contextThe classical starting point for coding theory from the viewpoint of association schemes is Delsarte [Del73]. For a survey of the relation between association schemes and coding theory, including distance distributions, MacWilliams transforms, and linear programming, see Delsarte–Levenshtein [DL98]. For a systematic reference on association schemes, Bannai–Ito [BI84] is standard. For a detailed account including the relation with distance-regular graphs, see Brouwer–Cohen–Neumaier [BCN89]. For the MacWilliams identity and Krawtchouk polynomials in coding theory, MacWilliams–Sloane [MS77, Chapter 5] is also a classical standard reference. For basic material on association schemes used in coding theory, Camion [Cam98] is also useful.↩1 ↩2 Citation contextThe advantage of this viewpoint is that it places the MacWilliams identity in a broader framework. Not only in the Hamming scheme, but also in many association schemes such as the Johnson schemes, the Grassmann schemes, and the dual polar schemes, notions such as inner distributions, dual distributions, eigenvalues, and linear-programming bounds appear in the same form. Delsarte's linear programming method in coding theory is also naturally derived from this association-scheme perspective. For this broader framework, see Delsarte [Del73] and Delsarte–Levenshtein [DL98].↩3
[DL98] Philippe Delsarte and Vladimir I. Levenshtein. Association schemes and coding theory. IEEE Trans. Inform. Theory, vol. 44, no. 6, pp. 2477–2504, 1998. doi:10.1109/18.720545 Citation contextThe classical starting point for coding theory from the viewpoint of association schemes is Delsarte [Del73]. For a survey of the relation between association schemes and coding theory, including distance distributions, MacWilliams transforms, and linear programming, see Delsarte–Levenshtein [DL98]. For a systematic reference on association schemes, Bannai–Ito [BI84] is standard. For a detailed account including the relation with distance-regular graphs, see Brouwer–Cohen–Neumaier [BCN89]. For the MacWilliams identity and Krawtchouk polynomials in coding theory, MacWilliams–Sloane [MS77, Chapter 5] is also a classical standard reference. For basic material on association schemes used in coding theory, Camion [Cam98] is also useful.↩1 Citation contextThe advantage of this viewpoint is that it places the MacWilliams identity in a broader framework. Not only in the Hamming scheme, but also in many association schemes such as the Johnson schemes, the Grassmann schemes, and the dual polar schemes, notions such as inner distributions, dual distributions, eigenvalues, and linear-programming bounds appear in the same form. Delsarte's linear programming method in coding theory is also naturally derived from this association-scheme perspective. For this broader framework, see Delsarte [Del73] and Delsarte–Levenshtein [DL98].↩2
[BI84] Eiichi Bannai and Tatsuro Ito. Algebraic combinatorics. I. The Benjamin/Cummings Publishing Co., Inc., Menlo Park, CA, pp. xxiv+425, 1984 Citation contextThe classical starting point for coding theory from the viewpoint of association schemes is Delsarte [Del73]. For a survey of the relation between association schemes and coding theory, including distance distributions, MacWilliams transforms, and linear programming, see Delsarte–Levenshtein [DL98]. For a systematic reference on association schemes, Bannai–Ito [BI84] is standard. For a detailed account including the relation with distance-regular graphs, see Brouwer–Cohen–Neumaier [BCN89]. For the MacWilliams identity and Krawtchouk polynomials in coding theory, MacWilliams–Sloane [MS77, Chapter 5] is also a classical standard reference. For basic material on association schemes used in coding theory, Camion [Cam98] is also useful.↩
[BCN89] A. E. Brouwer, A. M. Cohen, and A. Neumaier. Distance-regular graphs. Springer-Verlag, Berlin, vol. 18, pp. xviii+495, 1989. doi:10.1007/978-3-642-74341-2 Citation contextThe classical starting point for coding theory from the viewpoint of association schemes is Delsarte [Del73]. For a survey of the relation between association schemes and coding theory, including distance distributions, MacWilliams transforms, and linear programming, see Delsarte–Levenshtein [DL98]. For a systematic reference on association schemes, Bannai–Ito [BI84] is standard. For a detailed account including the relation with distance-regular graphs, see Brouwer–Cohen–Neumaier [BCN89]. For the MacWilliams identity and Krawtchouk polynomials in coding theory, MacWilliams–Sloane [MS77, Chapter 5] is also a classical standard reference. For basic material on association schemes used in coding theory, Camion [Cam98] is also useful.↩
[MS77] F. J. MacWilliams and N. J. A. Sloane. The theory of error-correcting codes. I. North-Holland Publishing Co., Amsterdam-New York-Oxford, vol. Vol. 16, pp. i–xv and 1–369, 1977 Citation contextThe classical starting point for coding theory from the viewpoint of association schemes is Delsarte [Del73]. For a survey of the relation between association schemes and coding theory, including distance distributions, MacWilliams transforms, and linear programming, see Delsarte–Levenshtein [DL98]. For a systematic reference on association schemes, Bannai–Ito [BI84] is standard. For a detailed account including the relation with distance-regular graphs, see Brouwer–Cohen–Neumaier [BCN89]. For the MacWilliams identity and Krawtchouk polynomials in coding theory, MacWilliams–Sloane [MS77, Chapter 5] is also a classical standard reference. For basic material on association schemes used in coding theory, Camion [Cam98] is also useful.↩
[Cam98] Paul Camion. Codes and association schemes: basic properties of association schemes relevant to coding. Handbook of coding theory, Vol. I, II, pp. 1441–1566, 1998 Citation contextThe classical starting point for coding theory from the viewpoint of association schemes is Delsarte [Del73]. For a survey of the relation between association schemes and coding theory, including distance distributions, MacWilliams transforms, and linear programming, see Delsarte–Levenshtein [DL98]. For a systematic reference on association schemes, Bannai–Ito [BI84] is standard. For a detailed account including the relation with distance-regular graphs, see Brouwer–Cohen–Neumaier [BCN89]. For the MacWilliams identity and Krawtchouk polynomials in coding theory, MacWilliams–Sloane [MS77, Chapter 5] is also a classical standard reference. For basic material on association schemes used in coding theory, Camion [Cam98] is also useful.↩1 ↩2
[God93] C. D. Godsil. Algebraic combinatorics. Chapman & Hall, New York, pp. xvi+362, 1993 Citation contextIn the association-scheme proof of the MacWilliams identity, this passage between the “relation side” and the “eigenspace side” is essential. The weight distribution of a code is defined on the relation side, while the dual distribution is defined by projection onto the eigenspace side. For a readable reference on the linear-algebraic treatment of Bose–Mesner algebras and primitive idempotents discussed in this section, see also Godsil [God93].↩

This series

A Series Learning through the MacWilliams Identity · Part 5 of 12

PreviousAn Introduction to Krawtchouk Polynomials through the MacWilliams Identity NextAn Introduction to Pless Moments through the MacWilliams Identity

Back to series list

Disclaimer

Articles on this site are based on the operator's personal understanding, investigation, and research notes. I try to keep the content accurate, but it may contain errors or incomplete explanations. I do not guarantee its accuracy, completeness, usefulness, or currentness.

Please use the information on this site at your own judgment and responsibility. To the extent permitted by law, the operator is not liable for damages, losses, or disadvantages arising from using, or being unable to use, information on this site.

If you notice an error, unclear explanation, broken link, or insufficient citation, please contact the operator. I will review the content and, when appropriate, correct, update, or remove it.

§1Introduction

§2Viewing Relations on a Finite Set as Matrices

§3Association Schemes

§4Bose–Mesner Algebras

§5The Hamming Scheme

§6Eigenspaces of the Hamming Scheme

§7Writing the Primitive Idempotents Explicitly

§8Inner Distributions: Viewing Codes from the Relation Side

§9Dual Distributions: Viewing Codes from the Eigenspace Side

§10The Coefficient-Level MacWilliams Identity

§11The Polynomial Form of the MacWilliams Identity

§12A Small Example: H(2,2)H(2,2)H(2,2) and the Binary Repetition Code

§13What Association Schemes Did in This Proof

§14Concepts Seen in This Instalment

§15Looking Back at This Proof Family

§16Next Time

References

This series

Disclaimer

Introduction

Viewing Relations on a Finite Set as Matrices

Association Schemes

Bose–Mesner Algebras

The Hamming Scheme

Eigenspaces of the Hamming Scheme

Writing the Primitive Idempotents Explicitly

Inner Distributions: Viewing Codes from the Relation Side

Dual Distributions: Viewing Codes from the Eigenspace Side

The Coefficient-Level MacWilliams Identity

The Polynomial Form of the MacWilliams Identity

A Small Example: $H(2,2)$ and the Binary Repetition Code

What Association Schemes Did in This Proof

Concepts Seen in This Instalment

Looking Back at This Proof Family

Next Time