A motivated proof of the MacWilliams Identity

Wildon's Weblog 2018-03-12

Fix $n \in \mathbb{N}$ and let $V = \mathbb{F}_2^n$ . Let $\mathrm{wt}(u)$ denote the weight of $u \in V$ , defined by $\mathrm{wt}(u) = |\{i : u_i = 1\}|$ . Given a subset $S$ of $V$ , we define its weight enumerator $W_S(x,y)$ by

$W_S(x,y) = \sum_{u \in S} x^{\mathrm{wt}(u)} y^{n-\mathrm{wt}(u)}.$

The MacWilliams Identity states that if $C$ is a linear subspace of $V$ , and $C^\perp$ is its orthogonal complement with respect to the dot product $u \cdot v = \sum_{i=1}^n u_i v_i$ then

$\displaystyle W_{C^\perp}(x,y) = \frac{1}{|C|} W_C(-x+y,x+y).$

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 $(x+y)^n = \sum_{k=0}^n \binom{n}{k} x^k y^{n-k}$ . It has a one-line combinatorial proof: expand $(x+y)(x+y) \cdots (x+y)$ , by choosing $x$ from $k$ of the $n$ brackets and $y$ from the other $n-k$ brackets; there are $\binom{n}{k}$ ways to do this, so $\binom{n}{k}$ is the coefficient of $x^k y^{n-k}$ .

Now consider the sum $s = \binom{n}{0} + \binom{n}{2} + \binom{n}{4} + \cdots$ 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:

$\displaystyle s = \frac{1}{2} \sum_{k=0}^n \binom{n}{k} + \frac{1}{2} \sum_{k=0}^n (-1)^k \binom{n}{k}.$

For $n \in \mathbb{N}$ the sums are $(1+1)^n = 2^n$ and $(-1+1)^n = 0$ , respectively. Therefore $s = 2^{n-1}$ . More generally, this trick shows that

$\displaystyle \sum_{j \in \mathbb{N}_0} \binom{n}{2j} x^{2j} y^{n-2j} = \frac{1}{2} (x+y)^n + \frac{1}{2}(-x+y)^n$

which already has some of the appearance of the MacWilliams Identity. How about $s' = \binom{n}{0} + \binom{n}{4} + \binom{n}{8} + \cdots$ ? Since powers of $-1$ worked for the two-step identity, it is reasonable to try powers of $\mathrm{i}$ . This gives

$\begin{aligned} s' = \frac{1}{4} \sum_{k=0}^n \binom{n}{k} + \frac{1}{4} &\sum_{k=0}^n \binom{n}{k} \mathrm{i}^k \\& + \frac{1}{4} \sum_{k=0}^n \binom{n}{k} (-1)^k + \frac{1}{4} \sum_{k=0}^n \binom{n}{k} (\mathrm{-i})^k.\end{aligned}$

By the Binomial Theorem, the sums are $2^n$ , $(1+i)^n$ , $0$ and $(1-i)^n$ . For example, if $n = 4m$ where $m \in \mathbb{N}$ then $(1+i)^{4m} = (1-i)^{4m} = 2^{2m} (-1)^m$ , so we have $s' = 2^{4m-2} + 2^{2m-1} (-1)^m$ . Similar formulae can be obtained for the other cases for $n$ modulo $4$ .

Character theory

Consider the cyclic group $\mathbb{Z} / 4\mathbb{Z}$ . It has four irreducible complex characters, taking values $(1,1,1,1)$ , $(1,\mathrm{i},-1,\mathrm{-i})$ , $(1,-1,1,-1)$ and $(1, \mathrm{-i},-1,\mathrm{i})$ . The previous displayed equation for comes from expressing the indicator function $(1,0,0,0)$ as a linear combination of irreducible characters

$\begin{aligned} (1,0,0,0) = \frac{1}{4} (1,1,1,1) + \frac{1}{4} &(1,i,-1,-i) \\ &+ \frac{1}{4} (1,-1,1,-1) + \frac{1}{4}(1,-i,-1,i).\end{aligned}$

As an exercise, the reader might use the characters of $\mathbb{Z} / 3\mathbb{Z}$ to decompose the indicator function $(1,0,0)$ of $0 \in \mathbb{Z}/3\mathbb{Z}$ and so prove the related identity $\binom{n}{0} + \binom{n}{3} + \binom{n}{6} + \cdots = \frac{2^{n}}{3} + \frac{2}{3} \cos \frac{n\pi}{3}$ for $n \in \mathbb{N}$ .

MacWilliams’ Identity for the repetition code

Let $C = \langle 1\ldots 1 \rangle$ . In this case the left-hand side of the MacWilliams’ Identity is sum of all $x^{\mathrm{wt}(u)} y^{n - \mathrm{wt}(u)}$ over $u \in V$ of even weight. By analogy with the binomial sum, we write

$W_{C^\perp}(x,y) = \frac{1}{2} \sum_{v \in V} x^{\mathrm{wt}(v)} y^{n-\mathrm{wt}(v)} + \frac{1}{2} \sum_{v \in V} (-x)^{\mathrm{wt}(v)} y^{n-\mathrm{wt}(v)}.$

The first summand is the generating function enumerating all $v \in V$ by their weight. Since there are $\binom{n}{k}$ elements of $V$ of weight $k$ , it is $\sum_{k =0}^n \binom{n}{k} x^k y^{n-k}$ , which is $(x+y)^n$ by the Binomial Theorem. Replacing $x$ with $-x$ we see that the second summand is $(-x+y)^n$ . Therefore

$W_{C^\perp}(x,y) = \frac{1}{2} (x+y)^n + \frac{1}{2} (-x+y)^n.$

Since $W_C(x,y) = x^n + y^n$ , this agrees with the MacWilliams’ Identity. Note that the second sum could be written as

$\displaystyle \sum_{v \in V} (-1)^{1\ldots 1 \cdot v} x^{\mathrm{wt}(v)} y^{n-\mathrm{wt}(v)}$ .

MacWilliams Identity for a larger code

Take $n=4$ and $C = \langle 1100, 0011 \rangle$ . Then

$W_C(x,y) = x^4 + 2x^2y^2 + y^4.$

We can describe $C^\perp$ as the intersection of the two codimension $1$ hyperplanes $U, U'$ , with ‘normals’ $1100$ and $0011$ . Thus

$\displaystyle W_{C^\perp}(x,y) = \sum_{v} [v \in U \cap U'] x^{\mathrm{wt}(v)}y^{n-\mathrm{wt}(v)}.$

For each $b \in V$ , we define $\chi_b(v) = (-1)^{b \cdot v}$ ; these are the irreducible complex characters of $V$ . Using them to decompose the indicator function $[v \in U \cap U'] : V \rightarrow \mathbb{C}$ we get

$[v \in U \cap U'] = \frac{1}{4} \chi_{0}(v) + \frac{1}{4} \chi_{1100}(v) + \frac{1}{4} \chi_{0011}(v) + \frac{1}{4} \chi_{1111}(v)$ .

It now suffices to find $\sum_{v \in V} \chi_{b}(v) x^{\mathrm{wt}(v)} y^{n-\mathrm{wt}(v)}$ . If $\mathrm{wt}(b) = t$ then, by symmetry, we may assume that $b = 1\ldots 10\ldots 0$ , where there are exactly $t$ ones. Now $(-1)^{b \cdot v}$ records the parity of the number of ones in the first $t$ positions of $v$ , so writing $v \in V$ as the concatenated vector $(u | w)$ where $u \in \mathbb{F}_2^t$ and $w \in \mathbb{F}_2^{n-t}$ , we have

$\begin{aligned} \sum_{v \in V} &\chi_{b}(v) x^{\mathrm{wt}(v)} y^{n-\mathrm{wt}(v)}\\ &= \sum_{u \in U} (-1)^{\mathrm{wt}(u)} x^{\mathrm{wt}(u)} y^{t-\mathrm{wt}(v)} \sum_{w \in W} x^{\mathrm{wt}(w)} y^{n-t-\mathrm{wt}(w)} \\ &= (-x+y)^t (x+y)^{n-t} \end{aligned}.$

Therefore

$\begin{aligned} W_{C^\perp}(x,y) &= \frac{1}{4} (x+y)^4 + \frac{2}{4} (-x+y)^2 (x+y)^2 + \frac{1}{4} (-x+y)^4 \\ &= W_C(-x+y,x+y) \end{aligned}$

as required. (In this case, since $C$ is self-dual, we even have $W_{C^\perp}(x,y) = W_C(x,y)$ .)

MacWilliams Identity in general

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

$\displaystyle [v \in C^\perp] = \frac{1}{|C|} \sum_{b \in C} \chi_b(v)$

and so

$\begin{aligned} \sum_{v \in C^\perp} x^{\mathrm{wt}(v)} y^{n-\mathrm{wt}(v)} &= \sum_{v \in V} \frac{1}{|C|} \sum_{b \in C} \chi_b(v) x^{\mathrm{wt}(v)} y^{n-\mathrm{wt}(v)} \\ &= \frac{1}{|C|} \sum_{b \in C} \sum_{v \in V} \chi_b(v) x^{\mathrm{wt}(v)} y^{n-\mathrm{wt}(v)} \\ &= \frac{1}{|C|} \sum_{t=0}^n \sum_{b \in C : \mathrm{wt}(b) = t} (-x+y)^t (x+y)^{n-t} \\ &= \frac{1}{|C|} W_C(-x+y,x+y) \end{aligned}$

as required.