An Introduction to Heat Kernels and Trace Formulas through the MacWilliams Identity

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

where

For a codeword $c \in \F_{q}^{E}$, write its support and Hamming weight as

respectively. Define the weight enumerator of the linear code $C$ by

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:

This is the MacWilliams identity.

In this series, we use proofs of the MacWilliams identity as a guide to introductions to neighbouring areas and concepts. For that reason, the series is aimed at readers with the following background:

We assume basic familiarity with elementary coding theory, namely 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.

(It is not necessary to know a proof of the MacWilliams identity.)

This note does not presuppose Parts 1–9. In the series as a whole, we compare several proofs of the MacWilliams identity, but the content of the previous parts is not needed in order to read this note. The necessary linear operators, kernels, traces, heat operators and heat kernels on finite graphs, Hamming graphs, translation actions, and character eigenfunctions are introduced in the text to the extent needed.

In this series, we view the proof methods for the MacWilliams identity as falling roughly into the following five families. However, this classification is a map of the whole series, and is not required for reading the proof in this note:

1. Fourier, character, and Poisson-type proofs.

2. Möbius inversion, lattice-theoretic, shortening-puncturing proofs.

3. Orthogonal-polynomial and association-scheme proofs.

4. Matroid and Tutte-polynomial proofs.

5. Moment and double-counting proofs.

The proof treated in this note is written, on the surface, in the language of

Compressed into the five families above, it belongs to the Fourier, character, and Poisson family. This is because, when the heat operator on the Hamming graph is diagonalised, characters of the finite abelian group $\F_{q}^{E}$ eventually appear as eigenfunctions. That said, character theory itself is not the main actor in this note. The aim here is to use a proof of the MacWilliams identity as a guide to an introduction to heat operators and heat kernels and to trace formulas.

Roughly speaking, a heat operator is an operator that describes how heat spreads on a graph or a space. Its matrix entries are called the heat kernel. On a finite set, a heat operator is a finite matrix, and the heat kernel is its matrix entry. A trace formula is an identity obtained by computing the trace of a single operator in two ways. In one computation, the operator is decomposed into eigenspaces and the eigenvalues are summed. In the other computation, the diagonal entries of the kernel are summed directly. The equality of these two computations gives a non-trivial identity. The trace formulas considered in this note are not deep trace formulas involving infinite-dimensional analysis or convergence issues, but finite trace formulas obtained by computing the trace of a finite-dimensional matrix in two ways.

The MacWilliams identity considered in this note appears as the following trace formula. Write $\Kop_{z}$ for the heat operator on the Hamming graph on $V = \F_{q}^{E}$, and write its kernel as $\Kop_{z}(x,y)$. We take the trace of $\Kop_{z}$ on the quotient space $V/C$ by the translation action of the code $C$. More precisely, we are not defining a new quotient graph or a heat operator on that quotient graph separately. Rather, we identify the function space $\C^{V/C}$ on the quotient set $V/C$ with the space $\Hspace^{C}$ of $C$-invariant functions on $V$, and compute the trace of the restriction $\res{\Kop_{z}}{\Hspace^{C}}$ of the original heat operator $\Kop_{z}$. Computing this trace from the spectral side produces the weight distribution of $C^{\perp}$. On the other hand, averaging along the translation action and then summing the diagonal entries produces the weight distribution of $C$. Comparing the two gives the MacWilliams identity.

The flow of the note is as follows.

Stating only the key point of the proof in advance, it is as follows. In one coordinate, the zero translation produces $1+(q-1)z$, and a non-zero translation produces $1-z$. In several coordinates, this zero/non-zero distinction occurs coordinate by coordinate, and so records the Hamming weight. Averaging further over the elements of $C$ produces the weight enumerator of $C$. On the other hand, from the viewpoint of eigenfunctions, the characters that remain on the quotient space are precisely the $C$-invariant characters, and these correspond exactly to $C^{\perp}$.

For the spectral theory of finite graphs, Chung [Chu97] and Godsil–Royle [GR01] are standard references. For heat kernels on graphs, see for instance Chung–Yau [CY99]. For Fourier analysis on finite groups and its applications to graph and coding theory, see also Terras [Ter99]. For the classical treatment of the MacWilliams identity in coding theory, see MacWilliams–Sloane [MS77]. In this note, we do not develop all this general theory, but instead extract only the part needed for the ordinary Hamming-weight MacWilliams identity for linear codes over finite fields.

Before treating heat operators and heat kernels, we prepare the language for viewing linear operators on finite sets as matrices. All spaces considered here are finite-dimensional, so no analytic convergence issues arise.

For a finite set $\Omega$, let $\C^{\Omega}$ be the set of all complex-valued functions on $\Omega$. In this note, an italic $C$ denotes a code, whereas the blackboard bold $\C$ denotes the field of complex numbers. For each $x \in \Omega$, define $\delta_{x} \in \C^{\Omega}$ by

Then $\{ \delta_x : x \in \Omega \}$ is a basis of $\C^{\Omega}$.

A linear operator $T \colon \C^{\Omega} \to \C^{\Omega}$ can be written as a matrix whose rows and columns are indexed by $\Omega$. In this note, we write its matrix entry as $K_{T}(x, y)$ and call it the kernel of $T$. Thus

On a finite set, a kernel is simply another name for a matrix entry. However, when we later call it a heat kernel, we think of this matrix entry as the amount of heat transmitted from the point $y$ to the point $x$. Here the basic convention in this note is that operators act on functions. As a matrix entry, $K_{T}(x,y)$ can be read as the contribution from the column index $y$ to the row index $x$. On the other hand, when the same matrix is read intuitively as an expectation operator for a Markov process, it is read as the probability of moving from the current point $x$ to the next point $y$. In general, the transpose matrix appears in the convention where one acts on probability distributions. The heat kernels actually used in this note are symmetric, so both readings use the same numerical matrix, and only the interpretation of the direction differs. The word kernel appears in two senses in this note. One is the matrix-entry sense just defined, written as $K_{T}(x,y)$ or $\Kop_{z}(x,y)$. The other is the linear-algebraic subspace sent to zero, written as $\Ker(T)$. To avoid confusion, kernels as matrix entries are denoted by symbols of the form $K_T(x,y)$, whereas linear-algebraic kernels are written as $\Ker(T)$. Also note the following notation. $K_{T}$ denotes the kernel of a general operator $T$. The symbol $K_{q}$ appearing later denotes the complete graph on $q$ vertices, and $\Kop_{z}$ denotes the heat operator on the Hamming graph. Its heat kernel is written $\Kop_{z}(x,y)$. We use the same letter for the operator and its kernel, but when $(x,y)$ is attached it denotes a matrix entry.

This is the usual trace of a matrix. That is, it is the sum of the diagonal entries. If $T$ is diagonalisable and its eigenvalues, counted with multiplicity, are $\lambda_{1}, \lambda_{2}, \dots, \lambda_{m}$, then

Thus the trace has at least two viewpoints.

Using these two viewpoints for the same operator is the basic idea of a trace formula.

In this note, we also use traces on subspaces. For that purpose we prepare a simple lemma using projections.

We will later apply this lemma to the space of functions invariant under translations by $C$. This is because we identify functions on the quotient space $\F_{q}^{E}/C$ with $C$-invariant functions on $\F_{q}^{E}$, and compute traces using the projection onto that space.

We next introduce the idea of heat operators and heat kernels on finite graphs. Rather than developing general graph theory, we keep in mind the finite regular graphs needed in this note, especially Hamming graphs.

Let $\Omega$ be the vertex set of a finite graph. The function space on the graph is $\C^{\Omega}$. The graph Laplacian is an operator that measures the difference between a function and its surrounding values. The standard combinatorial Laplacian is defined by $L \coloneqq D - A$. Here $A$ is the adjacency matrix, and $D$ is the diagonal matrix whose diagonal entries are the degrees. For a regular graph, $D$ is a constant multiple of the identity matrix.

The finite-graph version of the heat equation can be written using the matrix exponential as $H_{t} = \exp(-tL)$. This $H_{t}$ is called the heat operator, and its kernel $H_{t}(x, y)$ is called the heat kernel. On a finite set, this is just an ordinary matrix exponential. Here the matrix exponential is the matrix defined by

In the situations actually used in this note, the eigenspace decomposition gives concrete formulas, so there is no need to compute this series directly.

In this note, however, we use a scalar multiple of the Laplacian in order to simplify the calculations. Multiplying the Laplacian by a positive constant amounts to viewing the heat operator after rescaling time. Indeed, replacing $L$ by $\alpha L$ gives $\exp(-t\alpha L)=\exp(-(\alpha t)L)$. Thus the structure of eigenfunctions and trace formulas is unchanged. What changes is only the reparametrisation of the time parameter appearing in the eigenvalues. In this note, we use the parameter $z = e^{-t}$ instead of time $t$. Strictly speaking, for finite $t$ we have $0 < z \leq 1$. The value $z=0$ corresponds to the limit $t \to \infty$. The time $t = 0$ corresponds to $z = 1$, and then the heat operator is the identity operator. As $t$ becomes larger, $z$ approaches $0$, and the heat operator moves towards averaging. In the one-coordinate case, at the limiting value $z = 0$ the operator $M_{z}$ becomes the averaging projection $\Pi_{0}$. Thus $z$ can be viewed as a parameter measuring how much of the original value is retained. The heat kernels and traces actually computed below are all expressed as polynomials in $z$. Therefore substituting $z=0$ also makes sense as a polynomial. At the stage where the MacWilliams identity is obtained, $z$ is read not as an analytic time parameter but as a formal variable. Thus we first understand the operators as heat operators for $0 \leq z \leq 1$, and in the end read the same formulas as polynomial identities. The later substitution $z = Y/X$ and homogenisation use precisely this polynomial viewpoint.

Heat operators and heat kernels on finite graphs have the following two basic viewpoints.

Spectral side

Decompose $H_{t}$ into eigenspaces and sum the eigenvalues $e^{-t\lambda}$.

Geometric side

Sum the diagonal entries $H_{t}(x, x)$ of the heat kernel over the vertices $x$.

Both compute the same trace $\Tr(H_{t})$. In this note, we also consider the trace of an operator obtained by composing a heat operator with a translation action. This operation of composing with a translation and then taking the trace is what extracts the weight distribution of the code $C$.

A Hamming graph is the Cartesian product, coordinate by coordinate, of complete graphs. Here the graph product is meant in the Cartesian sense. Two multi-coordinate vertices are adjacent precisely when they differ in exactly one coordinate, and in that coordinate they are adjacent in the one-coordinate complete graph. We therefore begin with the one-coordinate complete graph.

Let the one-coordinate vertex set be $\F_{q}$, and let the function space be $U \coloneqq \C^{\F_{q}}$. Define the averaging projection onto the one-dimensional subspace of $U$ consisting of constant functions by

Here $\one$ is the function that is identically $1$. The kernel of this projection in the linear-algebraic sense, namely the subspace on which $\Pi_{0}f=0$, is

Thus $U = \C \one \oplus U_{1}$. Here the subscript $1$ indicates that this is the space corresponding to the eigenvalue $1$ for the one-coordinate Laplacian $\Delta_{1}$ defined immediately below; it does not mean that $U_{1}$ is one-dimensional. In fact, $\dim_{\C} U_{1}=q-1$.

In this note, we define the one-coordinate Laplacian by

This is a scalar multiple of the combinatorial Laplacian of the complete graph $K_{q}$. Here $J$ is the $q \times q$ matrix all of whose entries are $1$. Indeed, the adjacency matrix of $K_{q}$ is $J - I$, and the combinatorial Laplacian is

On the other hand, since $\Pi_{0} = J/q$,

Thus we are simply using the usual Laplacian multiplied by $1/q$.

Writing $z = e^{-t}$, the one-coordinate heat operator is

It acts with eigenvalue $1$ in the constant direction and with eigenvalue $z$ in the direction where the sum is $0$.

This formula also has a probabilistic reading. The operator $M_{z}$ is the operation that keeps the current value with probability $z$, and replaces it by a uniformly chosen value of $\F_{q}$ with probability $1 - z$. In this note, we view $M_{z}$ not as acting on probability distributions, but as an operator acting on functions, that is, observables. In other words, it returns the average value of $f$ when the next state is chosen at random by this rule. In particular, when $0 \leq z \leq 1$, the operator $M_{z}$ sends non-negative functions to non-negative functions and preserves constant functions, so it can be read as a Markov operator on the function side. If the same symmetric matrix is made to act on distributions, it can also be read as an operator sending probability distributions to probability distributions. In the convention where one acts on distributions, the transpose matrix appears, but the heat kernel in the present case is symmetric, so we are looking at the same numerical matrix. However, in this note we use it not for the probabilistic interpretation but for trace computations.

The most important point in one coordinate is the trace after composing with a translation. For $a \in \F_{q}$, define the translation operator $\tau_{a} \colon U \to U$ by

With this definition, $\tau_{a}$ acts as pullback on functions. On basis vectors, $\tau_{a} \delta_{b} = \delta_{a + b}$. The points themselves are moved by $x \mapsto x+a$, but because the action on functions is by pullback, the formula contains $x-a$. Later we write $C$-invariance as $f(x+c)=f(x)$. Since $C$ is an additive subgroup, as $c$ runs through all of $C$, so does $-c$. Thus the condition $f(x+c)=f(x)$ is equivalent to the condition $\tau_{c}f=f$.

This lemma records the source of the change of variables in the MacWilliams identity. In the ordinary trace, one sums $M_{z}(x,x)$ over $x$. After composing with $\tau_{a}$, however, one reads $M_{z}(x-a,x)$ as the diagonal entry. In other words, translation shifts the diagonal entries of the heat kernel by $a$. The zero translation produces $1 + (q - 1)z$, and a non-zero translation produces $1 - z$. This is because, when $a=0$, only diagonal entries are read, whereas when $a\neq 0$, only off-diagonal entries are read. In several coordinates, this distinction occurs coordinate by coordinate, and the Hamming weight is recorded in the trace. After later substituting $z = Y/X$ and homogenising, this becomes

We now move to several coordinates. Put $V \coloneqq \F_{q}^{E}$. This is the vertex set of the Hamming graph. Define the Hamming distance between two vertices $x, y \in V$ by

In the Hamming graph, two vertices at distance $1$ are joined by an edge. This graph is the Cartesian product of $n$ copies of the one-coordinate complete graph.

Write the function space as $\Hspace \coloneqq \C^{V}$. Using the one-coordinate space $U = \C^{\F_{q}}$, this can be viewed as

For each coordinate $e \in E$, let $\Delta_{e}$ be the operator that applies the one-coordinate Laplacian $\Delta_{1}$ only in the $e$ coordinate and applies the identity operator in all other coordinates. Define the Laplacian on the Hamming graph by

This is the usual combinatorial Laplacian of the Hamming graph multiplied by $1/q$. Indeed, the usual combinatorial Laplacian in the $e$-coordinate direction is $q\Delta_{e}$. Thus, if $L_{\mathrm{Ham}}$ denotes the usual combinatorial Laplacian of the whole Hamming graph, then

Therefore the $\Delta$ used in the text is the usual combinatorial Laplacian multiplied by $1/q$, with the same normalisation as in the one-coordinate case. Since the operators $\Delta_{e}$ commute with one another, putting $z = e^{-t}$ gives

Thus the following operator is the natural heat operator on the Hamming graph. Under this identification, define the heat operator on the Hamming graph by

This applies the same one-coordinate heat operator $M_{z}$ independently in all coordinates. Although we use tensor-product notation here, the only concrete meaning needed in this note is the following. For $x=(x_{e})_{e \in E}$ and $y=(y_{e})_{e \in E}$, set

and define its action on a function $f \in \C^{V}$ by

Thus even without knowing the general theory of tensor products, all trace computations below can be read using only this product formula. In particular, when $0 \leq z \leq 1$, $\Kop_{z}$ can be viewed as a Markov operator that independently, in each coordinate, either keeps the value or replaces it by a uniformly chosen value. This is an explanation as an expectation operator acting on functions, that is, observables. The same symmetric matrix can also be made to act on distributions. The probabilistic interpretation here is for intuition; in the proof, we use trace computations and polynomial identities.

This formula shows that $\Kop_{z}(x, y)$ depends not on the particular values of $x$ and $y$, but only on the Hamming distance $\dist(x,y)$. Thus $\Kop_{z}$ is an operator compatible with the symmetries of the Hamming graph. In the language of association schemes, $\Kop_{z}$ belongs to the Bose–Mesner algebra of the Hamming scheme. However, in this note we do not use the general theory of association schemes; we proceed only by computations with heat operators, heat kernels, and traces.

Translations on $V$ are defined in the same way. For $a \in V$, define $\tau_{a} \colon \Hspace \to \Hspace$ by

This is the tensor product of the one-coordinate translations.

The meaning of this proposition is transparent. If we take the trace of the heat operator $\Kop_{z}$ after composing with the translation $a$, the zero and non-zero coordinates of $a$ produce different factors. Thus the Hamming weight of $a$ is recorded in the trace. This is why the weight enumerator of $C$ appears later.

Next, consider the action of the code $C \leq V = \F_{q}^{E}$ by translations. As an additive group, $C$ acts on $V$. Write the quotient set as $V/C$. Functions on the quotient set can be identified with $C$-invariant functions on $V$.

The space $\Hspace^{C}$ can be identified with the function space $\C^{V/C}$ on $V/C$. Indeed, a $C$-invariant function is constant on cosets, so it is the same thing as a function with one value for each coset. Concretely, given $g \in \C^{V/C}$, define a function $\widetilde{g}$ on $V$ by

Then $\widetilde{g}$ is $C$-invariant. Conversely, if $f \in \Hspace^{C}$, then $f$ is constant on each coset $x+C$, and hence a function $g$ on $V/C$ is defined by

Through these two correspondences, we identify $\C^{V/C}$ with $\Hspace^{C}$. What we are doing here is not constructing a new quotient graph or its Laplacian separately. Rather, we identify the subspace of $C$-invariant functions inside the original function space $\Hspace = \C^{V}$ with the function space on the quotient set $V/C$, and compute the trace of the restriction $\res{\Kop_{z}}{\Hspace^{C}}$ of the original heat operator $\Kop_{z}$. If one writes the kernel on the quotient set explicitly, then for cosets $x+C$ and $y+C$ it is

This expression is independent of the choice of representatives $x$ and $y$. This is because $\Kop_{z}$ is translation-invariant, and, as $c$ ranges over all of $C$, the points $y+c$ range over the same coset. Taking the diagonal sum of this kernel on the quotient set is the same content as taking the trace of $P_{C}\Kop_{z}$ on $V$. In the text, however, we do not define a quotient graph anew; instead, we compute the trace using the restriction to $\Hspace^{C}$ and the averaging projection. This trace does not count the points of $V$ individually. It is the trace in which each coset is counted as one degree of freedom. In other words, we are not simply summing diagonal entries over all $q^{n}$ points of $V$; rather, we are taking the trace corresponding to the degrees of freedom of the $C$-invariant function space $\Hspace^{C}$, namely to the number of cosets. This distinction is important when we later rewrite the trace by using the averaging projection $P_{C}$ as

Here the condition $f(x + c)=f(x)$ appearing in the definition is the same as $\tau_{c}f=f$. Indeed, $\tau_{c}f=f$ means $f(x - c)=f(x)$. Since $C$ is an additive subgroup, as $c$ ranges over all of $C$, so does $-c$. Therefore $f(x + c)=f(x)$ and $\tau_{c}f=f$ are equivalent.

Define the averaging projection from $\Hspace$ to $\Hspace^{C}$ by

This operator averages over translations by $C$. Acting on functions, it is

This means that it averages the values on the coset $x + C$. As $c$ ranges over all of $C$, both $x-c$ and $x+c$ range over the same coset $x+C$, so the sign difference does not affect the average. The operator $P_{C}$ averages the values of a function on each coset $x+C$, and then extends that average value over the whole coset. Thus, once a function has been averaged, averaging it again does not change it. This is the intuition for $P_{C}^{2}=P_{C}$, namely for the fact that it is a projection. The coefficient $1/\card{C}$ appears because we normalise the average in the translation directions by $C$. A point of the quotient set $V/C$ appears inside $V$ as a coset consisting of $\card{C}$ points. By averaging the values along that coset direction, we extract from a function on $V$ only its $C$-invariant part.

By this commutativity, if $f$ is $C$-invariant, then $\Kop_{z}f$ is also $C$-invariant. Thus $\Kop_{z}$ preserves $\Hspace^{C}$, and we can consider the restricted operator $\res{\Kop_{z}}{\Hspace^{C}}$. Therefore, by Lemma 2.2.Let $S \subseteq \C^{\Omega}$ be a subspace, and let $P \colon \C^{\Omega} \to \C^{\Omega}$ be a projection onto $S$. That is, assume $P^{2} = P$ and $\Image(P) = S$. Suppose that the linear operator $T$ commutes with $P$. Then $\Tr(\res{T}{S})=\Tr(PT)$.Lemma 2.2,

Computing the right-hand side produces the weight enumerator of $C$. From here, we compute the same left-hand side $\Tr(\res{\Kop_{z}}{\Hspace^{C}})$ by averaging over translations and then summing the diagonal entries of the kernel.

We call this computation the geometric side. We composed the heat operator with translations $c \in C$, took their traces, and averaged over $c$. Since the weight of $c$ appeared inside the trace, the weight enumerator of $C$ appeared.

As a check on the coefficients, let us look at $z=1$ and $z=0$. When $z=1$, we have $\Kop_{1}=\Id$, so the left-hand side is

The right-hand side is

so the two agree. When $z=0$, the one-coordinate heat operator becomes the averaging projection $\Pi_{0}$, and in several coordinates it corresponds to averaging over all of $V$ and producing a constant function. As heat time, this is not a finite time but the limit $t \to \infty$. On the other hand, the formulas here are polynomials in $z$, so we may substitute $z=0$. Thus on the quotient space only the constant direction contributes, and the left-hand side is $1$. The right-hand side is also

This is not a proof, but a check that the coefficients in the formula fit naturally.

Next, we compute the same trace as a sum of eigenvalues. Here we use the eigenfunctions of the heat operator on the Hamming graph. These eigenfunctions are additive characters of the finite abelian group $V = \F_{q}^{E}$.

Fix a non-trivial additive character

of $\F_{q}$. That is, assume that $\psi(a + b) = \psi(a)\psi(b)$ holds and that $\psi$ is not identically $1$. If $q = p^{m}$, such a character can be constructed, for example, using the trace map in the form

In this expression, elements of $\F_{p}$ are read as the representatives $0,1,\dots,p-1$. The symbol $\operatorname{tr}_{\F_{q}/\F_{p}}$ appearing here is the trace map of finite fields, and is different from $\Tr$, which denotes the trace of an operator. In this text, the trace of an operator is written as $\Tr$, while the trace map of finite fields is written as $\operatorname{tr}_{\F_{q}/\F_{p}}$. The property needed in this note is the following one-coordinate orthogonality relation.