Fix and let . Let denote the *weight* of , defined by . Given a subset of , we define its *weight enumerator* by

The MacWilliams Identity states that if is a linear subspace of , and is its orthogonal complement with respect to the dot product then

The MacWilliams Identity is important in coding theory. It was first proved by the coding theorist Jessie MacWilliams, yet another alumnus of Bell Labs. To my mind, the best motivation for its proof comes from certain related identities in binomial coefficients and the generating function techniques used to prove them, which, in turn, are best understood in terms of the characters of cyclic groups.

#### Binomial coefficients

The Binomial Theorem states that . It has a one-line combinatorial proof: expand , by choosing from of the brackets and from the other brackets; there are ways to do this, so is the coefficient of .

Now consider the sum of binomial coefficients with even `denominator’. This can be evaluated using the binomial theorem, using the two sums below to cancel out the unwanted binomial coefficients with odd denominator:

For the sums are and , respectively. Therefore . More generally, this trick shows that

which already has some of the appearance of the MacWilliams Identity.

How about ? Since powers of worked for the two-step identity, it is reasonable to try powers of . This gives

By the Binomial Theorem, the sums are , , and . For example, if where then , so we have . Similar formulae can be obtained for the other cases for modulo .

#### Character theory

Consider the cyclic group . It has four irreducible complex characters, taking values , , and . The previous displayed equation comes from expressing the indicator function as a linear combination of irreducible characters

As an exercise, the reader might use the characters of to decompose the indicator function of and so prove the related identity for .

#### MacWilliams’ Identity for the repetition code

Let . In this case the left-hand side of the MacWilliams’ Identity is sum of all over of even weight. By analogy with the binomial sum, we write

The first summand is the generating function enumerating all by their weight. Since there are elements of of weight , it is , which is by the Binomial Theorem. Replacing with we see that the second summand is . Therefore

Since , this agrees with the MacWilliams’ Identity. Note that the second sum could be written as

.

#### MacWilliams Identity for a larger code

Take and . Then

We can describe as the intersection of the two codimension hyperplanes , with ‘normals’ and . Thus

For each , we define ; these are the irreducible complex characters of . Using them to decompose the indicator function we get

.

It now suffices to find . If then, by symmetry, we may assume that , where there are exactly ones. Now records the parity of the number of ones in the first positions of , so writing as the concatenated vector where and , we have

Therefore

as required. (In this case, since is self-dual, we even have .)

#### MacWilliams Identity in general

The general proof needs no more ideas than those seen in the previous example. The indicator function decomposition is

and so

as required.