Article and note

A Series Learning through the MacWilliams IdentityPart 3 of 12

An Introduction to Tensor Products through the MacWilliams Identity

Among the five proof systems for the MacWilliams identity, this note focuses on a tensor-product proof in linear algebra belonging to the Fourier, character-theoretic, and Poisson approach, and introduces tensor products, tensor product linear maps, Kronecker products, code vectors, and complete weight enumerators.

Published:: May 28, 2026
Updated:: May 28, 2026
Reading time:: 23 min (about 4,875 words)

Tagscoding theoryMacWilliams identitytensor productKronecker productcomplete weight enumeratorfinite fieldsFourier matrixexpository note

Download PDF

Introduction

In coding theory, one of the basic theorems is the MacWilliams identity. For a linear code $C \leq \mathbb{F}_{q}^{E}$ over a finite field $\mathbb{F}_{q}$ with coordinate set $E$ , the weight enumerator of its dual code

C^{\perp} = \{ u \in \mathbb{F}_{q}^{E} : u \cdot c = 0 \text{ for all } c \in C \}

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 at least the following basic material:

We assume that the reader already knows, at least at a basic level, the following notions:

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.)

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 theory, and shortening/puncturing methods.
Orthogonal polynomials and association schemes.
Matroids and Tutte polynomials.
Moments and double-counting methods.

The proof in this note belongs to the first family: the Fourier, character-theoretic, and Poisson approach. However, character theory itself is not the main subject of this note. The aim of this note is to use a proof of the MacWilliams identity as a guide to an introduction to tensor products.

In a standard proof of the MacWilliams identity, one extends a transformation appearing in each coordinate to the whole space of words of length $n$ . The most natural language for this operation, “extending a one-coordinate transformation to all coordinates at once”, is the language of tensor products. Using tensor products, a word of length $n$ ,

(c_{1}, \dots, c_{n}) \in \mathbb{F}_{q}^{n},

can be treated as the product of one-coordinate basis vectors

e_{c_{1}} \tensor \cdots \tensor e_{c_{n}}.

Then a one-coordinate linear map $H$ acts on the space of length $n$ as

H^{\tensor n} = \underbrace{H \tensor \cdots \tensor H}_{n\text{ copies}}.

From this viewpoint, the MacWilliams identity can be read as follows.

Vectorise the code $C$ as the sum of the basis vectors corresponding to its words. When a one-coordinate Hadamard-type transformation is made to act on all coordinates by tensor product, that vector is sent to $\card{C}$ times the code vector of the dual code $C^{\perp}$ . Afterwards, reading each basis vector as a monomial produces the variable transformation in the weight enumerator.

The route in this note is as follows.

tensor product → tensor product linear map → tensor representation of words → code vector → complete weight enumerator → MacWilliams identity

Tensor products are a basic tool in multilinear algebra. For a standard reference on multilinear algebra, see Greub [Gre78]; for a more advanced textbook on linear algebra, see for instance Roman [Rom08]. Rather than developing the whole general theory, this note treats, concretely, tensor products of finite-dimensional vector spaces with chosen bases, restricting attention to the part needed for the proof of the MacWilliams identity.

From one-coordinate information to multi-coordinate information

Let us first see why tensor products arise naturally.

Consider a finite alphabet $\mathcal{A}$ . Later we shall take $\mathcal{A} = \mathbb{F}_{q}$ , but for now think of it simply as a finite set. The value in one coordinate is an element of $\mathcal{A}$ . A word of length $n$ is an element of

\mathcal{A}^{n} = \{ (a_{1},\dots,a_{n}) : a_{i} \in \mathcal{A} \}.

To handle one-coordinate information, prepare a basis vector $e_{a}$ for each alphabet symbol $a \in \mathcal{A}$ . In other words, consider the complex vector space $U \coloneqq \mathbb{C}^{\mathcal{A}}$ as a vector space with basis $\{ e_{a} \in U : a \in \mathcal{A} \}$ . Here $\mathbb{C}^{\mathcal{A}}$ may be viewed as the space of complex-valued functions on the alphabet $\mathcal{A}$ , but in this note we view it as “the vector space with a basis indexed by the elements of $\mathcal{A}$ ”.

For a word of length $n$ , $a = (a_{1}, \dots, a_{n}) \in \mathcal{A}^{n}$ , we would like to write the corresponding basis vector as $e_{a} = e_{a_{1}} \tensor \dots \tensor e_{a_{n}}$ . The space needed for this is

U^{\tensor n} = \underbrace{U \tensor \cdots \tensor U}_{n\text{ copies}}.

Then we obtain the following correspondence.

word of length $n$ , $(a_{1}, \dots, a_{n}) \in \mathcal{A}^{n}$ ↔ tensor product of $n$ basis vectors $e_{a_{1}}\tensor \dots \tensor e_{a_{n}} \in U^{\tensor n}$ .

Moreover, if a one-coordinate linear transformation $H \colon U \to U$ is given, then the transformation which applies it to all coordinates at once is

H^{\tensor n} \colon U^{\tensor n}\to U^{\tensor n}.

On pure tensors it acts by

H^{\tensor n} (u_{1}\tensor \cdots \tensor u_{n}) = H(u_{1})\tensor \cdots \tensor H(u_{n}).

Tensor products provide the language for this operation of extending one-coordinate objects to $n$ coordinates. In the tensor-product proof of the MacWilliams identity, we take the $n$ -fold tensor product of a one-coordinate Hadamard-type transformation and apply it to a vector representing the whole code.

Definition of the tensor product: construction from bases

Tensor products are often defined abstractly, but in this note we start from a concrete definition using chosen bases of finite-dimensional vector spaces.

Definition 3.1.

Let $U$ and $V$ be finite-dimensional vector spaces over $\mathbb{C}$ . Let $e_{1},\dots,e_{r}$ be a basis of $U$ , and let $f_{1}, \dots, f_{s}$ be a basis of $V$ . The tensor product $U\tensor V$ of $U$ and $V$ is the complex vector space whose basis consists of the symbols

e_{i} \tensor f_{j} \qquad (1 \leq i \leq r,\, 1 \leq j \leq s).

It follows immediately from the definition that

\dim_{\mathbb{C}}(U\tensor V) = \dim_{\mathbb{C}}U \cdot \dim_{\mathbb{C}}V.

Thus, taking the tensor product of an $r$ -dimensional space and an $s$ -dimensional space produces an $rs$ -dimensional space.

For arbitrary vectors

u=\sum_{i=1}^{r}\alpha_{i}e_{i}\in U, \qquad v=\sum_{j=1}^{s}\beta_{j}f_{j}\in V,

define $u\tensor v\in U\tensor V$ by

u \tensor v = \sum_{i=1}^{r} \sum_{j=1}^{s} \alpha_{i}\beta_{j} (e_{i}\tensor f_{j}).

An element of this form is called a pure tensor.

From the definition, we have the following bilinearity:

\begin{aligned} (u + u^{\prime}) \tensor v &= u \tensor v + u^{\prime} \tensor v,\\ u \tensor (v + v^{\prime}) &= u \tensor v + u \tensor v^{\prime},\\ (\lambda u) \tensor v &= u \tensor (\lambda v) = \lambda (u\tensor v). \end{aligned}

Here $\lambda\in\mathbb{C}$ . In other words, the tensor product is linear in each variable.

However, not every element of $U \tensor V$ can be written as a single pure tensor $u \tensor v$ . A general element can be written as a finite sum of pure tensors. For example,

e_{1} \tensor f_{1} + e_{2} \tensor f_{2}

usually cannot be decomposed as one pure tensor. This point is important when getting used to tensor products.

Example 3.2.

Let $e_{0}, e_{1}$ be a basis of $U = \mathbb{C}^{2}$ , and let $f_{0}, f_{1}, f_{2}$ be a basis of $V = \mathbb{C}^{3}$ . Then $U \tensor V$ has the following six basis vectors:

e_{0} \tensor f_{0},\, e_{0} \tensor f_{1},\, e_{0} \tensor f_{2}, \, e_{1} \tensor f_{0},\, e_{1} \tensor f_{1},\, e_{1}\tensor f_{2}.

Therefore $\dim(U \tensor V) = 6$ .

The definition above appears to depend on the chosen bases. Indeed, the concrete construction used bases. However, if the bases are changed, the resulting tensor product is the same up to a natural isomorphism. The following universal property is the basis-free characterisation.

Definition 3.3.

Let $U$ , $V$ , and $W$ be complex vector spaces. A map $B \colon U \times V \to W$ is called bilinear if, when $u$ is fixed, the map $v \mapsto B(u,v)$ is linear, and when $v$ is fixed, the map $u \mapsto B(u,v)$ is linear.

Theorem 3.4 (Universal property of the tensor product).

Let $U$ and $V$ be finite-dimensional vector spaces constructed as above after choosing bases. Then, for any complex vector space $W$ and any bilinear map $B \colon U \times V \to W$ , there exists a unique linear map $\widetilde{B} \colon U \tensor V \to W$ such that

\widetilde{B}(u\tensor v)=B(u,v) \qquad (u \in U,\, v \in V).

Proof

Let $e_{1}, \dots, e_{r}$ be a basis of $U$ , and let $f_{1}, \dots, f_{s}$ be a basis of $V$ . Since $U \tensor V$ has basis $e_{i} \tensor f_{j}$ , it is enough, in order to define a linear map $\widetilde{B}$ , to decide its values on the basis. Define

\widetilde{B}(e_{i} \tensor f_{j}) = B(e_{i}, f_{j})

and extend linearly.

If $u = \sum_{i} \alpha_{i} e_{i}$ and $v = \sum_{j} \beta_{j} f_{j}$ , then

\begin{aligned} \widetilde{B}(u \tensor v) &= \widetilde{B}\left( \sum_{i,j} \alpha_{i} \beta_{j}(e_{i} \tensor f_{j}) \right)\\ &= \sum_{i, j} \alpha_{i} \beta_{j} B(e_{i}, f_{j}) \\ &= B\left(\sum_{i} \alpha_{i} e_{i}, \sum_{j} \beta_{j} f_{j} \right)\\ &= B(u,v). \end{aligned}

In the last equality we used the bilinearity of $B$ .

Uniqueness follows from the fact that the elements $e_{i} \tensor f_{j}$ form a basis of $U \tensor V$ and are themselves pure tensors. In other words, $\widetilde{B}(e_{i} \tensor f_{j})$ must be $B(e_{i}, f_{j})$ .

This theorem is the basic principle behind viewing the tensor product as

a device which lets us treat bilinear operations as linear operations.

In the proof of the MacWilliams identity in this note, we treat the coordinatewise product

\prod_{i = 1}^{n} Z_{c_{i}}

as a linear map on a tensor product. This feeling that products can be linearised is an important role of tensor products.

Tensor products of many vector spaces

To handle words of length $n$ , we need not only the tensor product of two spaces, but the tensor product of $n$ spaces.

When the same vector space $U$ is prepared $n$ times, we write its tensor product as

U^{\tensor n} = \underbrace{U\tensor\cdots\tensor U}_{n\text{ copies}}.

Suppose that $U$ has basis $\{ e_{a} \in U : a \in \mathcal{A} \}$ . Then $U^{\tensor n}$ has basis

e_{a_{1}}\tensor \cdots \tensor e_{a_{n}} \qquad ((a_{1},\dots,a_{n})\in \mathcal{A}^{n}).

Therefore

\dim U^{\tensor n} = \card{\mathcal{A}}^{n}.

This basis is in one-to-one correspondence with words of length $n$ . For $a = (a_{1}, \dots, a_{n}) \in \mathcal{A}^{n}$ , we therefore abbreviate

e_{a} \coloneqq e_{a_{1}} \tensor \dots \tensor e_{a_{n}}.

Then $\{ e_{a} \in U^{\tensor n} : a \in \mathcal{A}^{n} \}$ is a basis of $U^{\tensor n}$ .

From now on, even when the coordinate set $E$ is an arbitrary finite set, we shall write, to keep the notation light,

U^{\tensor E} = \bigotimes_{i \in E} U.

Strictly speaking, to write a tensor product one chooses an order of the coordinates, but the calculations in this note do not depend on the ordering. The reader may safely read everything with $E = \{ 1, \dots, n \}$ in mind.

Tensor product linear maps and Kronecker products

What is important about tensor products is that not only vectors, but also linear maps, can be tensored.

Definition 5.1.

Let $A \colon U \to U^{\prime}$ and $B \colon V \to V^{\prime}$ be linear maps. Define the linear map

A \tensor B \colon U \tensor V\to U^{\prime}\tensor V^{\prime}

on pure tensors by

(A\tensor B)(u\tensor v) = A(u)\tensor B(v).

This is called the tensor product linear map of $A$ and $B$ .

This definition determines a unique linear map because the right-hand side is bilinear in $(u,v)$ , so Theorem 3.4 (Universal property of the tensor product)Let $U$ and $V$ be finite-dimensional vector spaces constructed as above after choosing bases. Then, for any complex vector space $W$ and any bilinear map $B \colon U \times V \to W$ , there exists a unique linear map $\widetilde{B} \colon U \tensor V \to W$ such that $\widetilde{B}(u\tensor v)=B(u,v) \qquad (u \in U,\, v \in V).$ Theorem 3.4 applies.

For the tensor product of $n$ copies of the same linear map $H \colon U \to U$ , we write

H^{\tensor n} = \underbrace{H \tensor \dots \tensor H}_{n\text{ copies}}.

On pure tensors,

H^{\tensor n}(u_{1} \tensor \dots \tensor u_{n}) = H(u_{1}) \tensor \dots \tensor H(u_{n}).

In matrix form, a tensor product linear map becomes a Kronecker product. For example, if

A= \begin{pmatrix} a_{11} & a_{12}\\ a_{21} & a_{22} \end{pmatrix}, \qquad B= \begin{pmatrix} b_{11} & b_{12}\\ b_{21} & b_{22} \end{pmatrix},

then

A \tensor B = \begin{pmatrix} a_{11}B & a_{12}B\\ a_{21}B & a_{22}B \end{pmatrix}.

That is,

A \tensor B = \begin{pmatrix} a_{11}b_{11} & a_{11}b_{12} & a_{12}b_{11} & a_{12}b_{12}\\ a_{11}b_{21} & a_{11}b_{22} & a_{12}b_{21} & a_{12}b_{22}\\ a_{21}b_{11} & a_{21}b_{12} & a_{22}b_{11} & a_{22}b_{12}\\ a_{21}b_{21} & a_{21}b_{22} & a_{22}b_{21} & a_{22}b_{22} \end{pmatrix}.

Depending on the reference, this matrix is called the Kronecker product of $A \otimes B$ .

For matrix computations with Kronecker products themselves, Horn–Johnson [HJ91, Chapter 4] is a standard reference. For a readable overview including applications, see also Van Loan [Van00]. What we need in this note is the single point that, when a tensor product linear map is written in bases, it becomes a Kronecker product.

Example 5.2 (The Hadamard matrix in the binary case).

As a one-coordinate transformation for $\mathbb{F}_{2} = \{ 0, 1 \}$ , consider

H_{2} = \begin{pmatrix} 1 & 1\\ 1 & -1 \end{pmatrix}.

If the rows and columns are indexed by $0$ and $1$ , this can be written as

(H_{2})_{a,b} = (-1)^{ab} \qquad (a, b \in \mathbb{F}_{2}).

The transformation on words of length two is $H_{2} \tensor H_{2}$ . Order the words, both for rows and for columns, as $00$ , $01$ , $10$ , $11$ , and regard the rows as indexed by $u$ and the columns by $c$ .

H_{2}\tensor H_{2} = \begin{pmatrix} 1 & 1 & 1 & 1\\ 1 & -1 & 1 & -1\\ 1 & 1 & -1 & -1\\ 1 & -1 & -1 & 1 \end{pmatrix}.

The $(u,c)$ entry of this matrix is

(-1)^{u \cdot c}.

Thus, taking the tensor square of a one-coordinate matrix produces the matrix corresponding to the inner product of length $2$ .

This example is the model for the proof in this note. For a general $\mathbb{F}_{q}$ , too, we build a one-coordinate Hadamard-type matrix and take its tensor product to obtain a transformation acting on the whole space of length $n$ .

The one-coordinate Hadamard-type transformation over a finite field

We now return to the finite field $\mathbb{F}_{q}$ . Write $q = p^{m}$ . The finite field $\mathbb{F}_{q}$ can be viewed as an $m$ -dimensional vector space over its prime field $\mathbb{F}_{p}$ .

Choose a basis $\beta_{1}, \dots, \beta_{m}$ of $\mathbb{F}_{q}$ over $\mathbb{F}_{p}$ . Then every $x \in \mathbb{F}_{q}$ can be written uniquely as

x = x_{1}\beta_{1} + \dots + x_{m} \beta_{m} \qquad (x_{i} \in \mathbb{F}_{p}).

Put $\zeta \coloneqq \exp(2\pi\sqrt{-1}/p)$ , and define

\theta(x) \coloneqq \zeta^{x_1}

using the first coordinate $x_{1}$ of $x$ . Here $x_{1} \in \mathbb{F}_{p}$ is regarded as the representative $0, 1, \dots, p-1$ when it is placed in the exponent.

The function $\theta \colon \mathbb{F}_{q} \to \mathbb{C}^{\times}$ has the following two properties:

\theta(x + y) = \theta(x)\theta(y), \qquad \theta(\beta_{1}) = \zeta \neq 1.

In other words, $\theta$ is a non-constant function which turns addition into multiplication^{Footnote¹Here we have constructed $\theta$ concretely from the first coordinate with respect to the chosen basis. In the language of character theory, a non-constant function satisfying $\theta(x + y) = \theta(x)\theta(y)$ is called a non-trivial additive character of $\mathbb{F}_{q}$ . In many textbooks, functions of the same kind are often constructed using the trace map. In this note, I want to see the role of the tensor product, so I do not go deeply into character theory itself. For a systematic treatment of additive characters and their orthogonality relations, see the second note.1}. These two properties are all that we need in this note.

The property of characters needed for the tensor-product proof of the MacWilliams identity is the following.

Lemma 6.1.

For $b \in \mathbb{F}_{q}$ ,

\sum_{a \in \mathbb{F}_{q}} \theta(ab) = \begin{cases} q, & b=0,\\ 0, & b\neq 0 \end{cases}

holds.

Proof

If $b = 0$ , then $\theta(ab) = \theta(0) = 1$ for all $a$ , so the sum is $q$ .

Suppose that $b\neq 0$ . Then the map $a\mapsto ab$ is a bijection of $\mathbb{F}_{q}$ , and therefore

\sum_{a\in\mathbb{F}_{q}}\theta(ab) = \sum_{t\in\mathbb{F}_{q}}\theta(t).

Put the right-hand side equal to $S$ .

As $t$ runs through all of $\mathbb{F}_{q}$ , so does $t+\beta_1$ . Hence

S = \sum_{t\in\mathbb{F}_{q}}\theta(t+\beta_1) = \sum_{t\in\mathbb{F}_{q}}\theta(t)\theta(\beta_1) = \theta(\beta_1)S.

Since $\theta(\beta_{1}) = \zeta \neq 1$ , it follows that $S=0$ .

Let the one-coordinate complex vector space be $U = \mathbb{C}^{\mathbb{F}_{q}}$ , with basis $\{ e_{a} \in U :a\in\mathbb{F}_{q} \}$ . Define the one-coordinate Hadamard-type transformation $\mathcal{H} \colon U \to U$ on the basis by

\mathcal{H}(e_{b}) \coloneqq \sum_{a\in\mathbb{F}_{q}}\theta(ab)e_{a} \qquad (b\in\mathbb{F}_{q}).

In matrix form, this is the $q \times q$ matrix

\mathcal{H}_{a,b}=\theta(ab),

with rows and columns indexed by elements of $\mathbb{F}_{q}$ .

This matrix is the Fourier matrix over the finite field. In this note, however, our focus is not Fourier analysis itself, but the process of extending this one-coordinate matrix to all coordinates by taking tensor products.

Proposition 6.2.

The columns of $\mathcal{H}$ are mutually orthogonal, and

\mathcal{H}^{\ast} \mathcal{H} = qI

holds.

Proof

The inner product of column $b$ and column $b^{\prime}$ is

\sum_{a\in\mathbb{F}_{q}} \overline{\theta(ab)}\theta(ab^{\prime}) = \sum_{a\in\mathbb{F}_{q}}\theta(a(b^{\prime}-b)).

Here we used $\overline{\theta(x)}=\theta(-x)$ . By Lemma 6.1, this is

\begin{cases} q, & b=b^{\prime},\\ 0, & b\neq b^{\prime}. \end{cases}

Hence $\mathcal{H}^{\ast} \mathcal{H} = qI$ .

This proposition shows that $\mathcal{H}$ is the finite-field analogue of a Hadamard matrix. After normalisation, $q^{-1/2}\mathcal{H}$ is a unitary matrix. For the MacWilliams identity itself, however, what is important is not this unitarity, but the property, seen below, that the map sends code vectors to dual-code vectors.

Words and codes inside tensor products

From now on, let $E$ be a finite coordinate set, and put $n = \card{E}$ . For simplicity, when necessary, think of $E = \{ 1, \dots, n \}$ .

Starting from the one-coordinate space $U = \mathbb{C}^{\mathbb{F}_{q}}$ , form the multi-coordinate space

U^{\tensor E} = \bigotimes_{i \in E} U.

For a word $v = (v_{i})_{i\in E} \in \mathbb{F}_{q}^{E}$ , write

e_{v} \coloneqq \bigotimes_{i \in E} e_{v_{i}}.

Then

\{ e_{v} \in U^{\tensor E} : v \in \mathbb{F}_{q}^{E}\}

is a basis of $U^{\tensor E}$ .

Definition 7.1.

For a code $C \leq \mathbb{F}_{q}^{E}$ , define

\gamma_{C} \coloneqq \sum_{c\in C}e_c \in U^{\tensor E}.

We call this the code vector of $C$ .

The code vector $\gamma_{C}$ is obtained by summing the basis vectors corresponding to all codewords. It may be regarded as the indicator function of the code $C$ , written as a sum of basis vectors. For example, if $C = \{ 00, 11 \} \leq \mathbb{F}_{2}^{2}$ , then

\gamma_{C} = e_{00} + e_{11} = e_{0} \tensor e_{0} + e_{1} \tensor e_{1}.

Write the extension of the one-coordinate transformation $\mathcal{H}$ to all coordinates as

\mathcal{H}^{\tensor E} = \bigotimes_{i \in E} \mathcal{H} \colon U^{\tensor E} \to U^{\tensor E}.

Computing its action on a basis vector $e_{c}$ gives

\begin{aligned} \mathcal{H}^{\tensor E}(e_{c}) &= \bigotimes_{i \in E}\mathcal{H}(e_{c_{i}})\\ &= \bigotimes_{i \in E} \left( \sum_{u_{i} \in \mathbb{F}_{q}}\theta(u_{i} c_{i}) e_{u_{i}} \right)\\ &= \sum_{u \in \mathbb{F}_{q}^{E}} \left( \prod_{i \in E} \theta(u_{i} c_{i}) \right) e_{u}\\ &= \sum_{u\in\mathbb{F}_{q}^{E}} \theta\left(\sum_{i\in E}u_i c_i\right)e_u\\ &= \sum_{u\in\mathbb{F}_{q}^{E}} \theta(u \cdot c) e_{u}. \end{aligned}

Here $u \cdot c = \sum_{i \in E} u_{i} c_{i}$ .

This formula is the centre of the tensor-product proof. In one coordinate, a coefficient $\theta(ab)$ appeared. After taking the tensor product, the coordinatewise coefficients are multiplied, and by the additive-character property we obtain

\prod_{i\in E}\theta(u_i c_i) = \theta\left(\sum_{i\in E}u_i c_i\right).

Thus the tensor product multiplies the coordinatewise coefficients, and the property of $\theta$ then gathers that product into the coefficient $\theta(u\cdot c)$ involving the length- $n$ inner product $u \cdot c$ .

The tensor product transformation sends a code to its dual code

Apply the calculation from the previous section to the code vector $\gamma_{C}$ . Then

\begin{aligned} \mathcal{H}^{\tensor E}\gamma_{C} &= \sum_{c\in C}\mathcal{H}^{\tensor E} e_{c} \\ &= \sum_{c\in C} \sum_{u \in \mathbb{F}_{q}^{E}}\theta(u \cdot c) e_{u} \\ &= \sum_{u \in \mathbb{F}_{q}^{E}} \left( \sum_{c \in C}\theta(u \cdot c) \right)e_u. \end{aligned}

Thus the coefficient which appears is

\sum_{c \in C} \theta(u \cdot c).

This sum detects whether $u$ belongs to $C^{\perp}$ .

Lemma 8.1.

For every $u \in \mathbb{F}_{q}^{E}$ ,

\sum_{c \in C} \theta(u \cdot c) = \begin{cases} \card{C}, & u \in C^{\perp},\\ 0, & u \notin C^{\perp} \end{cases}

holds.

Proof

If $u \in C^{\perp}$ , then $u \cdot c=0$ for every $c\in C$ . Hence every term is $\theta(0) = 1$ , and the sum is $\card{C}$ .

Now suppose that $u\notin C^{\perp}$ . Then there exists some $c_{0} \in C$ such that $d = u \cdot c_{0} \neq 0$ . Since $d \neq 0$ , the map $a \mapsto ad$ is a bijection of $\mathbb{F}_{q}$ . Hence there exists $a \in \mathbb{F}_{q}$ such that $ad = \beta_{1}$ . Therefore

\theta(ad) = \theta(\beta_{1}) = \zeta \neq 1.

Put $\displaystyle S \coloneqq \sum_{c\in C}\theta(u\cdot c)$ . Since $C$ is a linear code, $ac_{0} \in C$ , and as $c$ runs through all of $C$ , the element $c+ac_0$ also runs through all of $C$ exactly once. Hence

S = \sum_{c\in C}\theta(u\cdot(c+ac_0)) = \sum_{c\in C}\theta(u\cdot c)\theta(a(u\cdot c_0)) = \theta(ad)S.

Since $\theta(ad) \neq 1$ , we have $S = 0$ .

Theorem 8.2.

For the code vector,

\mathcal{H}^{\tensor E}\gamma_{C} = \card{C}\,\gamma_{C^{\perp}}

holds.

Proof

As computed above,

\mathcal{H}^{\tensor E}\gamma_C = \sum_{u\in\mathbb{F}_{q}^{E}} \left( \sum_{c\in C}\theta(u\cdot c) \right)e_u.

By Lemma 8.1, the inner sum is $\card{C}$ when $u\in C^{\perp}$ , and is $0$ otherwise. Therefore

\mathcal{H}^{\tensor E}\gamma_C = \card{C} \sum_{u\in C^{\perp}}e_u = \card{C}\,\gamma_{C^{\perp}}.

This theorem is the linear-algebraic core of the proof in this note. Before viewing the MacWilliams identity as a polynomial identity, we have the following simple equality inside the tensor product space:

\mathcal{H}^{\tensor E}\gamma_C = \card{C}\,\gamma_{C^{\perp}}.

In other words, when the one-coordinate Hadamard-type transformation acts on all coordinates by tensor product, the vector representing the code $C$ is sent to the vector representing the dual code $C^{\perp}$ .

Complete weight enumerators: reading tensors as monomials

So far, we have treated a code as a vector in a tensor product space. Next, we read this vector as a polynomial. The complete weight enumerator is what naturally appears here.

In the ordinary Hamming weight enumerator, for each coordinate one only distinguishes

0 \mapsto X, \qquad \text{non-zero element} \mapsto Y.

In the complete weight enumerator, by contrast, we prepare a separate variable for each element of the finite field.

Definition 9.1.

For each $a\in\mathbb{F}_{q}$ , prepare a variable $Z_a$ . The complete weight enumerator of a code $C\leq\mathbb{F}_{q}^{E}$ is

\cwe_C((Z_a)_{a\in\mathbb{F}_{q}}) = \sum_{c\in C}\prod_{i\in E}Z_{c_i}.

For complete weight enumerators and the MacWilliams identity, MacWilliams–Sloane [MS77, Chapters 5 and 19] is the classical standard reference.

The ordinary Hamming weight enumerator is a specialisation of the complete weight enumerator. Indeed, if we put

Z_0=X, \qquad Z_a=Y\quad(a\neq 0),

then

\prod_{i\in E}Z_{c_i} = X^{n-\wt(c)}Y^{\wt(c)}.

Therefore

W_C(X,Y) = \cwe_C((Z_a))\bigg|_{Z_0=X,\ Z_a=Y\ (a\neq 0)}.

In the language of tensor products, the complete weight enumerator is very natural. Define the linear map from the one-coordinate space $U$ to the polynomial ring

R=\mathbb{C}[Z_a:a\in\mathbb{F}_{q}]

m_1\colon U\to R

and

m_1(e_a)=Z_a.

Then, by the universal property of the tensor product, we can define the $E$ -coordinate version $m_{E} \colon U^{\tensor E}\to R$ by

m_{E} \left( \bigotimes_{i \in E} e_{c_{i}} \right) = \prod_{i \in E} Z_{c_i}.

That is,

m_{E}(e_{c}) = \prod_{i \in E}Z_{c_i}.

^{Footnote²If you are not yet used to the universal property of the tensor product, it may be clearer to define this directly on the basis. The basis of $U^{\tensor E}$ is $\displaystyle e_{c} = \bigotimes_{i \in E}e_{c_i}$ ( $c \in \mathbb{F}_{q}^{E}$ ), so define $m_{E}(e_{c}) \coloneqq \prod_{i \in E}Z_{c_{i}}$ on the basis and extend linearly.2} This linear map is the map which reads tensors as monomials.

With this notation,

\cwe_C((Z_a)) = m_E(\gamma_C).

Thus, when the code vector $\gamma_C$ is read by the map $m_E$ which sends basis vectors to monomials, the complete weight enumerator appears.

The MacWilliams identity for complete weight enumerators

We translate Theorem 8.2 into the language of complete weight enumerators.

First define the one-coordinate change of variables. For $b\in\mathbb{F}_{q}$ , put

Z_b^{\mathcal{H}} \coloneqq \sum_{a\in\mathbb{F}_{q}}\theta(ab)Z_a.

This is what we obtain by reading $\mathcal{H}(e_b)$ through $m_1$ . Indeed,

m_1(\mathcal{H}(e_b)) = m_1\left(\sum_{a\in\mathbb{F}_{q}}\theta(ab)e_a\right) = \sum_{a\in\mathbb{F}_{q}}\theta(ab)Z_a = Z_b^{\mathcal{H}}.

Since

\mathcal{H}^{\tensor E} e_{c} = \bigotimes_{i \in E} \left(\sum_{u_{i} \in \mathbb{F}_{q}} \theta(u_{i} c_{i}) e_{u_{i}} \right),

expanding this and reading it through $m_{E}$ gives

\begin{aligned} m_{E}(\mathcal H^{\tensor E}e_{c}) &= \sum_{u \in \mathbb{F}_{q}^{E}} \left(\prod_{i \in E}\theta(u_{i}c_{i})\right) \prod_{i \in E}Z_{u_{i}}\\ &= \prod_{i \in E} \left(\sum_{u_{i} \in \mathbb{F}_{q}} \theta(u_{i}c_{i})Z_{u_{i}}\right)\\ &= \prod_{i\in E}Z_{c_{i}}^{\mathcal{H}}. \end{aligned}

Theorem 10.1 (MacWilliams identity for complete weight enumerators).

Let $C\leq\mathbb{F}_{q}^{E}$ be a linear code. Then

\cwe_{C^{\perp}}((Z_a)_{a\in\mathbb{F}_{q}}) = \frac{1}{\card{C}} \cwe_C((Z_b^{\mathcal{H}})_{b\in\mathbb{F}_{q}})

holds, where

Z_b^{\mathcal{H}} = \sum_{a\in\mathbb{F}_{q}}\theta(ab)Z_a.

Proof

By Theorem 8.2,

\mathcal{H}^{\tensor E}\gamma_C = \card{C}\gamma_{C^{\perp}}.

Applying $m_E$ to both sides gives

m_E(\mathcal{H}^{\tensor E}\gamma_C) = \card{C}\,m_E(\gamma_{C^{\perp}}) = \card{C}\,\cwe_{C^{\perp}}((Z_a)).

On the other hand,

\begin{aligned} m_E(\mathcal{H}^{\tensor E}\gamma_C) &= \sum_{c\in C}m_E(\mathcal{H}^{\tensor E}e_c)\\ &= \sum_{c\in C}\prod_{i\in E}Z_{c_i}^{\mathcal{H}}\\ &= \cwe_C((Z_b^{\mathcal{H}})_{b\in\mathbb{F}_{q}}). \end{aligned}

Hence

\card{C}\,\cwe_{C^{\perp}}((Z_a)) = \cwe_C((Z_b^{\mathcal{H}})_{b\in\mathbb{F}_{q}}),

and it remains only to divide both sides by $\card{C}$ .

This is a slightly stronger form than the MacWilliams identity for the Hamming weight enumerator. The change of variables for the complete weight enumerator is obtained from the tensor product linear map $\mathcal{H}^{\tensor E}$ .

Specialisation to the Hamming weight enumerator

We specialise the complete-weight-enumerator identity to the Hamming weight enumerator. Put

Z_0=X, \qquad Z_a=Y\quad(a\neq 0).

First compute the case $b=0$ .

\begin{aligned} Z_0^{\mathcal{H}} &= \sum_{a\in\mathbb{F}_{q}}\theta(a\cdot 0)Z_a\\ &= \sum_{a\in\mathbb{F}_{q}}Z_a\\ &= X+(q-1)Y. \end{aligned}

Next suppose that $b\neq 0$ . Then

\begin{aligned} Z_b^{\mathcal{H}} &= \sum_{a\in\mathbb{F}_{q}}\theta(ab)Z_a\\ &= X + Y\sum_{a\in\mathbb{F}_{q}^{\times}}\theta(ab). \end{aligned}

By Lemma 6.1,

\sum_{a\in\mathbb{F}_{q}}\theta(ab)=0.

Therefore

\sum_{a\in\mathbb{F}_{q}^{\times}}\theta(ab) = -\theta(0) = -1.

Thus

Z_b^{\mathcal{H}}=X-Y \qquad (b\neq 0).

Therefore, when we apply this specialisation to the complete-weight-enumerator MacWilliams identity

\cwe_{C^{\perp}}((Z_a)) = \frac{1}{\card{C}}\cwe_C((Z_b^{\mathcal{H}})),

the left-hand side becomes

W_{C^{\perp}}(X,Y),

and the right-hand side becomes

\frac{1}{\card{C}} W_C\bigl(X+(q-1)Y,X-Y\bigr).

We have obtained the usual MacWilliams identity for the Hamming weight enumerator:

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

A small example: the binary repetition code of length $2$

Let us check what the tensor-product proof is doing using the binary repetition code of length $2$ . Let

C=\{00,11\}\leq\mathbb{F}_{2}^{2}.

The non-trivial additive character of $\mathbb{F}_{2}$ is

\theta(a)=(-1)^a.

The one-coordinate Hadamard-type matrix is

H_2= \begin{pmatrix} 1 & 1\\ 1 & -1 \end{pmatrix}.

The code vector is

\gamma_C=e_{00}+e_{11} = e_0\tensor e_0+e_1\tensor e_1.

This code is self-dual, so $C^{\perp}=C$ . Indeed, the condition that $u=(u_1,u_2)$ be orthogonal to $11$ is

u_1+u_2=0,

which means that $u=00$ or $u=11$ .

Apply $H_2\tensor H_2$ to $\gamma_C$ . First,

\begin{aligned} (H_2\tensor H_2)e_{00} &= (e_0+e_1)\tensor(e_0+e_1)\\ &= e_{00}+e_{01}+e_{10}+e_{11}, \end{aligned}

and

\begin{aligned} (H_2\tensor H_2)e_{11} &= (e_0-e_1)\tensor(e_0-e_1)\\ &= e_{00}-e_{01}-e_{10}+e_{11}. \end{aligned}

Therefore

\begin{aligned} (H_2\tensor H_2)\gamma_C &= 2e_{00}+2e_{11}\\ &= 2\gamma_C\\ &= \card{C}\gamma_{C^{\perp}}. \end{aligned}

This is a concrete example of Theorem 8.2.

The complete weight enumerator is

\cwe_C(Z_0,Z_1)=Z_0^2+Z_1^2.

The one-coordinate change of variables is

Z_0^{\mathcal{H}}=Z_0+Z_1, \qquad Z_1^{\mathcal{H}}=Z_0-Z_1.

Hence

\begin{aligned} \frac{1}{\card{C}}\cwe_C(Z_0^{\mathcal H},Z_1^{\mathcal H}) &= \frac{1}{2}\left((Z_0+Z_1)^2+(Z_0-Z_1)^2\right)\\ &= Z_0^2+Z_1^2\\ &= \cwe_{C^{\perp}}(Z_0,Z_1). \end{aligned}

Finally, setting $Z_0=X$ and $Z_1=Y$ gives the MacWilliams identity for

W_C(X,Y)=X^2+Y^2.

What the tensor product was doing in this proof

Let us organise the roles played by the tensor product in the proof.

First, the tensor product represented words as basis vectors. If the one-coordinate basis is

\{e_a:a\in\mathbb{F}_{q}\},

then a word $c=(c_i)$ of length $n$ is represented as

e_c=\bigotimes_{i\in E}e_{c_i}.

This makes the code $C$ into a single vector

\gamma_C=\sum_{c\in C}e_c.

Second, the tensor product extended a one-coordinate transformation to all coordinates. The one-coordinate Hadamard-type transformation

\mathcal{H}(e_b)=\sum_{a\in\mathbb{F}_{q}}\theta(ab)e_a

was made to act on the length- $n$ space as

\mathcal{H}^{\tensor E}.

As a result, we obtained

\mathcal{H}^{\tensor E}e_c = \sum_{u\in\mathbb{F}_{q}^{E}}\theta(u\cdot c)e_u.

When the coordinatewise coefficients $\theta(u_i c_i)$ are multiplied, the global inner product $u\cdot c$ appears.

Third, the tensor product naturally produced the complete weight enumerator. If in one coordinate we read

e_a\mapsto Z_a,

then on the tensor product we read

e_{c_1}\tensor\cdots\tensor e_{c_n} \mapsto Z_{c_1}\cdots Z_{c_n}.

This allowed us to read the code vector $\gamma_C$ as the complete weight enumerator

\cwe_C((Z_a))=\sum_{c\in C}\prod_{i\in E}Z_{c_i}.

In short, in the proof in this note the tensor product played three roles:

vectorising words,
lifting a one-coordinate transformation to a multi-coordinate transformation,
treating the product of coordinatewise monomials as a linear map.

Concepts covered in this note

In this note, while aiming at a proof of the MacWilliams identity, we introduced some basic tools of tensor product linear algebra. They may be summarised as follows.

Tensor product

The vector space $U\tensor V$ constructed from vector spaces $U,V$ . Once bases $e_i$ and $f_j$ are chosen, the elements $e_i\tensor f_j$ form a basis.

Pure tensor

An element $u\tensor v\in U\tensor V$ formed from $u\in U$ and $v\in V$ . A general tensor can be written as a sum of pure tensors, but it need not be writable as a single pure tensor.

Universal property

The tensor product is a device for treating bilinear maps as linear maps. A bilinear map $B\colon U\times V\to W$ corresponds to a unique linear map $\widetilde B\colon U\tensor V\to W$ .

Tensor product linear map

From linear maps $A\colon U\to U'$ and $B\colon V\to V'$ , one obtains a linear map $A\tensor B\colon U\tensor V\to U'\tensor V'$ . On pure tensors it acts by

(A\tensor B)(u\tensor v)=A(u)\tensor B(v).

Kronecker product

A tensor product linear map written as a matrix after choosing bases. Taking the $n$ -fold Kronecker product of a one-coordinate matrix gives a matrix acting on all words of length $n$ .

Code vector

The vector in the tensor product space which represents a code $C$ :

\gamma_C=\sum_{c\in C}e_c.

Complete weight enumerator

A weight enumerator in which a variable $Z_a$ is assigned to each element $a\in\mathbb{F}_{q}$ of the finite field. On the tensor product, it is obtained from the linear map sending $e_c$ to $\prod_i Z_{c_i}$ .

Hadamard-type transformation

The one-coordinate linear transformation defined using a non-trivial additive character $\theta$ by

\mathcal{H}(e_b)=\sum_{a\in\mathbb{F}_{q}}\theta(ab)e_a.

Its tensor product $\mathcal{H}^{\tensor E}$ sends the code vector to $\card{C}$ times the dual-code vector.

Tensor products are often regarded as rather abstract tools, but in this proof they appeared quite concretely. We used the tensor product to extend the one-coordinate basis, the one-coordinate transformation, and the one-coordinate reading of variables to all coordinates at once.

Looking back at this proof family

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

Fourier, character-theoretic, and Poisson methods.

On the surface, it is a linear-algebraic proof using tensor products and Kronecker products. But at a deeper level, it uses the one-coordinate Hadamard-type transformation

\mathcal{H}_{a,b}=\theta(ab),

which is the matrix representation of the Fourier transform over the finite field. For a more advanced perspective on the relation between finite Fourier transforms and weight-enumerator identities for codes, see Tolimieri [Tol85]. This note does not enter that whole picture, but extracts, in elementary form, only the part where a one-coordinate Fourier matrix is made multi-coordinate by taking tensor products.

The key point of the proof in this note can be summarised in one sentence:

When a one-coordinate Fourier matrix is made to act on all coordinates by tensor product, the code vector $\gamma_C$ is sent to the dual-code vector $\card{C}\gamma_{C^\perp}$ .

From this viewpoint, the MacWilliams identity is obtained by reading the linear-algebraic equality

\mathcal{H}^{\tensor E}\gamma_C = \card{C}\gamma_{C^{\perp}}

in the tensor product space as a complete weight enumerator. The identity for the ordinary Hamming weight enumerator is the result of specialising the complete-weight-enumerator identity by

Z_0=X, \qquad Z_a=Y\quad(a\neq 0).

Thus, the proof in this note is very close in spirit to the character-theoretic proof. The difference is that instead of directly computing character sums, we package the one-coordinate character sum as a matrix $\mathcal{H}$ and then make it multi-coordinate using tensor products. Even though the underlying principle is the same Fourier principle, writing it in the language of tensor products makes the structure of “lifting a local transformation to the whole space” clearly visible.

Next time

Next time, we shall revisit the MacWilliams identity in the language of Krawtchouk polynomials.

In the tensor-product proof in this note, we used the complete weight enumerator. That is, we prepared a variable $Z_a$ for each element $a\in\mathbb{F}_{q}$ of the finite field, and used the one-coordinate Fourier matrix itself as a change of variables.

On the other hand, in the ordinary Hamming weight enumerator, all non-zero elements are gathered into the same variable $Y$ . As a result, the fine information in the complete weight enumerator is forgotten, and only the coefficients for the weights

0,1,\dots,n

remain. The Krawtchouk polynomials appear as the coefficient transformation obtained by looking only at these weights.

Next time, we shall view the MacWilliams identity as the coefficient-level transformation

A_j(C^\perp) = \frac{1}{\card{C}}\sum_{i=0}^{n}A_i(C)K_j(i)

and use it as an introduction to Krawtchouk polynomials.

Footnotes

Here we have constructed $\theta$ concretely from the first coordinate with respect to the chosen basis. In the language of character theory, a non-constant function satisfying $\theta(x + y) = \theta(x)\theta(y)$ is called a non-trivial additive character of $\mathbb{F}_{q}$ . In many textbooks, functions of the same kind are often constructed using the trace map. In this note, I want to see the role of the tensor product, so I do not go deeply into character theory itself. For a systematic treatment of additive characters and their orthogonality relations, see the second note. ↩
If you are not yet used to the universal property of the tensor product, it may be clearer to define this directly on the basis. The basis of $U^{\tensor E}$ is $\displaystyle e_{c} = \bigotimes_{i \in E}e_{c_i}$ ( $c \in \mathbb{F}_{q}^{E}$ ), so define $m_{E}(e_{c}) \coloneqq \prod_{i \in E}Z_{c_{i}}$ on the basis and extend linearly. ↩

References

[Gre78] Werner Greub. Multilinear algebra. Springer-Verlag, New York-Heidelberg, pp. vii+294, 1978 Citation contextTensor products are a basic tool in multilinear algebra. For a standard reference on multilinear algebra, see Greub [Gre78]; for a more advanced textbook on linear algebra, see for instance Roman [Rom08]. Rather than developing the whole general theory, this note treats, concretely, tensor products of finite-dimensional vector spaces with chosen bases, restricting attention to the part needed for the proof of the MacWilliams identity.↩
[Rom08] Steven Roman. Advanced linear algebra. Springer, New York, vol. 135, pp. xviii+522, 2008 Citation contextTensor products are a basic tool in multilinear algebra. For a standard reference on multilinear algebra, see Greub [Gre78]; for a more advanced textbook on linear algebra, see for instance Roman [Rom08]. Rather than developing the whole general theory, this note treats, concretely, tensor products of finite-dimensional vector spaces with chosen bases, restricting attention to the part needed for the proof of the MacWilliams identity.↩
[HJ91] Roger A. Horn and Charles R. Johnson. Topics in matrix analysis. Cambridge University Press, Cambridge, pp. viii+607, 1991. doi:10.1017/CBO9780511840371 ↩
[Van00] Charles F. Van Loan. The ubiquitous Kronecker product. J. Comput. Appl. Math., vol. 123, no. 1-2, pp. 85–100, 2000. doi:10.1016/S0377-0427(00)00393-9 ↩
[MS77] F. J. MacWilliams and N. J. A. Sloane. The theory of error-correcting codes. II. North-Holland Publishing Co., Amsterdam-New York-Oxford, vol. Vol. 16, pp. i–ix and 370–762, 1977 ↩
[Tol85] R. Tolimieri. The algebra of the finite Fourier transform and coding theory. Trans. Amer. Math. Soc., vol. 287, no. 1, pp. 253–273, 1985. doi:10.2307/2000409 Citation contextwhich is the matrix representation of the Fourier transform over the finite field. For a more advanced perspective on the relation between finite Fourier transforms and weight-enumerator identities for codes, see Tolimieri [Tol85]. This note does not enter that whole picture, but extracts, in elementary form, only the part where a one-coordinate Fourier matrix is made multi-coordinate by taking tensor products.↩

This series

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

PreviousAn Introduction to Character Theory through the MacWilliams Identity NextAn Introduction to Krawtchouk Polynomials 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

§2From one-coordinate information to multi-coordinate information

§3Definition of the tensor product: construction from bases

§4Tensor products of many vector spaces

§5Tensor product linear maps and Kronecker products

§6The one-coordinate Hadamard-type transformation over a finite field

§7Words and codes inside tensor products

§8The tensor product transformation sends a code to its dual code

§9Complete weight enumerators: reading tensors as monomials

§10The MacWilliams identity for complete weight enumerators

§11Specialisation to the Hamming weight enumerator

§12A small example: the binary repetition code of length 222

§13What the tensor product was doing in this proof

§14Concepts covered in this note

§15Looking back at this proof family

§16Next time

Footnotes

References

This series

Disclaimer

Introduction

From one-coordinate information to multi-coordinate information

Definition of the tensor product: construction from bases

Tensor products of many vector spaces

Tensor product linear maps and Kronecker products

The one-coordinate Hadamard-type transformation over a finite field

Words and codes inside tensor products

The tensor product transformation sends a code to its dual code

Complete weight enumerators: reading tensors as monomials

The MacWilliams identity for complete weight enumerators

Specialisation to the Hamming weight enumerator

A small example: the binary repetition code of length $2$

What the tensor product was doing in this proof

Concepts covered in this note

Looking back at this proof family

Next time