An Introduction to Matroids and Tutte Polynomials through the MacWilliams Identity

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}$, and consider its dual code

where

is the standard inner product. In this note, for a word $c \in \F_{q}^{E}$, write the support of $c$ and its 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, 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–6. However, to keep the perspective of the series clear, let us again begin by checking which proof family we are looking at. In this series, I look at proof methods for the MacWilliams identity under the following five broad families:

1. Fourier, character, and Poisson methods.

2. Möbius inversion, lattice-theoretic, and shortening/puncturing methods.

3. Orthogonal-polynomial and association-scheme methods.

4. Matroid and Tutte-polynomial methods.

5. Moment and double-counting methods.

In this note, I focus on the fourth of these: the matroid and Tutte-polynomial approach. Thus the aim of Part 7 is to use a proof of the MacWilliams identity as a guide to an introduction to the matroid associated with a code, the Tutte polynomial, and Greene's theorem connecting them.

One point to keep in mind is that this note does not develop matroid theory systematically. Matroids have many basic notions, such as independent sets, bases, circuits, closure, flats, minors, and representability. However, to reach the MacWilliams identity, what we need is the rank function obtained from a code $C \leq \F_{q}^{E}$, and the Tutte polynomial defined from that rank function. I am considering writing a separate article introducing matroid theory from the viewpoint of coding theory, so I leave a systematic treatment of matroid theory for that occasion. Thus, in this note, we pass through the entrance to matroids by the shortest route and put the emphasis on the relation between weight enumerators and Tutte polynomials.

From the viewpoint of coding theory, the reason matroids appear naturally is as follows. If we look only at a subset $A \subseteq E$ of the coordinate set $E$, then the code $C$ gives the restricted code $\res{C}{A} = \{ \res{c}{A} \in \F_{q}^{A} \mid c \in C \} \leq \F_{q}^{A}$. Its dimension

measures how much of the information in the code $C$ can be distinguished by the coordinates left in $A$. This function $r_{C}$ becomes the rank function of a matroid. On the other hand, the weight enumerator counts codewords according to the size of their supports. Thus, roughly speaking, Greene's theorem says:

From the Tutte polynomial collecting the dimensions of the restrictions to coordinate subsets, one can recover the distribution of supports of codewords.

This sentence is at the centre of the proof in this note.

The flow of the note is as follows. First, we define matroids by rank functions and construct a matroid $M(C)$ from a code $C \leq \F_{q}^{E}$ by $r_{C}(A) = \dim_{\F_{q}}(\res{C}{A})$. Next, we check that dual codes, puncturing, and shortening correspond to duality, deletion, and contraction for matroids. After that, we introduce the Tutte polynomial

and look at special values, duality, and the deletion-contraction formula. Finally, we prove Greene's theorem

and derive the MacWilliams identity from the duality of the Tutte polynomial.

Matroids were introduced by Whitney [Whi35]. A basic reference for the matroid version of the Tutte polynomial is Crapo [Cra69], and the relation between weight enumerators of codes and Tutte polynomials is due to Greene [Gre76]. For a survey of how properties of linear codes can be read from the Tutte polynomial starting from this theorem, see Britz–Cameron [BC22]. For a standard textbook on matroid theory, see Oxley [Oxl11].

In this note, we define matroids by rank functions. As the phrase "by rank functions" suggests, matroids have many equivalent definitions, connected by what is called cryptomorphism. Roughly speaking, this is similar to the way a topology can be described by open sets, closed sets, interior operators, or closure operators, with axioms for each description, and once one of them is fixed the others are determined. For matroids, there are many axiom systems, including those using independent sets, dependent sets, bases, circuits, flats, and hyperplanes. In this note, we adopt the axioms for a rank function. This is the most natural formulation for a note starting from coding theory. From a code $C \leq \F_{q}^{E}$, we directly obtain, for each coordinate subset $A \subseteq E$, the dimension of the restricted code $\res{C}{A}$. The rank function here is an abstraction of this "dimension for each subset".

In this sense, one may interpret a matroid as an abstraction of the notion of dimension appearing in linear algebra. The word "matroid", introduced by Whitney [Whi35], comes from "matrix" plus the suffix "-oid", meaning something like a matrix. Indeed, if we consider a generator matrix of a linear code, then the dimension of $\res{C}{A}$ corresponds to the rank of the submatrix consisting of the columns labelled by $A$. In fact, if $G$ is a generator matrix of $C$, then $\res{C}{A}$ is the row space of the submatrix $\res{G}{A}$ obtained by retaining only the columns of $G$ belonging to $A$. That is,

Thus $M(C)$ may also be viewed as recording the linear dependence relations among the column vectors of a generator matrix. In this sense, a matroid really can be regarded as something "matrix-like".

The third condition (R3)$r(A \cup B) + r(A \cap B) \leq r(A) + r(B)$.(R3) is called submodularity. It is obtained by replacing the equality in the dimension formula $\dim (V + W) + \dim (V \cap W) = \dim V + \dim W$ (for vector spaces $V$ and $W$ over a common field) by an inequality. Intuitively, it says that the sum of the amounts of information seen from two subsets separately is at least the sum of the amounts of information seen from their union and intersection. Since the Tutte polynomial can be defined using only the rank function, this definition is sufficient for this note.

Let us extract the terminology we need from the rank function. A subset $I \subseteq E$ is called independent if $r_{M}(I) = \card{I}$. Also, a subset $B \subseteq E$ is called a basis of $M$ (plural: bases) if $r_{M}(B) = \card{B} = r_{M}(E)$. In this note, we use this terminology especially when interpreting the special value $\Tutte_{M}(2, 1)$ of the Tutte polynomial.

An element $e \in E$ is called a loop if $r_{M}(\{ e \}) = 0$. Also, an element $e \in E$ is called a coloop or an isthmus (plural: isthmi) if $r_{M}(E) - r_{M}(E \setminus \{ e \}) = 1$.

Although we will not explain this in detail here because it is not the main topic, as already appears in Whitney's original paper [Whi35], matroids also abstract the rank of graphs. The terms "loop" and "isthmus" above come from loops and isthmi (bridges) in graphs.

Uniform matroids are the basic examples supporting most of the concrete examples used in this note. In particular, the single loop, the single coloop, and the small matroids arising from the repetition code and the even-weight code can all be written as uniform matroids.

As a special case of a uniform matroid, $U_{n, n}$ is called the free matroid. In this case, $r(A) = \card{A}$ for every $A \subseteq E$. Also, in $U_{0, n}$ we have $r(A) = 0$ for every $A \subseteq E$. In particular, $U_{0, 0}$ in the case $E = \emptyset$ is called the empty matroid.

We now translate the objects on the coding-theory side into the language of matroids. There is only one thing to do in this section. We restrict the code $C$ to each coordinate subset and record the dimension. This "record of the dimensions of all restricted codes" becomes a matroid.

Let $C \leq \F_{q}^{E}$ be a linear code and let $S \subseteq E$. If we change our viewpoint on a word $c \in \F_{q}^{E}$ from an $E$-indexed vector $c = (c_{i})_{i \in E}$ to a map from $E$ to $\F_{q}$, namely $c \colon E \to \F_{q}, \, i \mapsto c_{i}$, then the restriction map $\res{c}{S} \colon S \to \mathbb{F}_{q}$ corresponds to the vector $\res{c}{S} = (c_{i})_{i \in S}$ obtained by taking the part indexed by $S$. Thus define the restricted code to $S$ by

In other words, $\res{C}{S}$ is the punctured code $C^{E \setminus S}$ obtained from the codewords of $C$ by deleting the coordinates in $E \setminus S$.

Proof

Boundedness (R1)$0\leq r(A) \leq \card{A}$.(R1)

For every $A \subseteq E$, we have $\res{C}{A} \leq \F_{q}^{A}$, and hence

$$0 \leq r_{C}(A) \leq \dim_{\F_{q}} \F_{q}^{A} = \card{A}$$

Thus boundedness (R1)$0\leq r(A) \leq \card{A}$.(R1) holds.

Monotonicity (R2)If $A \subseteq B$, then $r(A) \leq r(B)$.(R2)

If $A \subseteq B \subseteq E$, then $\res{C}{A}$ is the image $\res{\res{C}{B}}{A}$ obtained by restricting $\res{C}{B}$ further to $A$. Hence $r_{C}(A) \leq r_{C}(B)$.

Submodularity (R3)$r(A \cup B) + r(A \cap B) \leq r(A) + r(B)$.(R3)

Let $A, B \subseteq E$. Using the restriction maps $\res{C}{A} \to \res{C}{A \cap B}$ and $\res{C}{B} \to \res{C}{A \cap B}$, consider the vector space

$$P \coloneqq \{ (u, v) \in \res{C}{A} \oplus \res{C}{B}: \res{u}{A \cap B} = \res{v}{A \cap B} \}$$

This $P$ is the kernel of the map

$$\res{C}{A} \oplus \res{C}{B} \to \res{C}{A\cap B},\quad (u,v)\mapsto \res{u}{A\cap B}-\res{v}{A\cap B}$$

and this map is surjective. Indeed, for any $w \in \res{C}{A \cap B}$, choose $c \in C$ such that $w = \res{c}{A \cap B}$. Then $(\res{c}{A}, 0)$ is sent to $w$ by this map. Therefore, by the rank-nullity theorem,

$$\begin{aligned} \dim_{\F_{q}} P &= \dim_{\F_{q}} \res{C}{A} + \dim_{\F_{q}} \res{C}{B} - \dim_{\F_{q}} \res{C}{A \cap B} \\ &= r_{C}(A) + r_{C}(B) - r_{C}(A \cap B) \end{aligned}$$

On the other hand, restricting an element of $\res{C}{A \cup B}$ to $A$ and to $B$ gives an element of $P$, and this correspondence is injective. Thus $\dim \res{C}{A \cup B} \leq \dim_{\F_{q}} P$, and so

$$r_{C}(A \cup B) \leq r_{C}(A) + r_{C}(B) - r_{C}(A \cap B)$$

Submodularity follows.

End of proof□

The matroid $M(C)$ on $E$ determined by this rank function is called the matroid associated with $C$, or the matroid of $C$. Let us first look at small examples to see what this definition is observing.

Both examples gave uniform matroids. Of course, the matroid obtained from a code is not always a uniform matroid. (For instance, try considering the matroid associated with $C = \{ 000, 100, 011, 111 \} \leq \F_{2}^{\{ 1, 2, 3 \}}$.) However, the repetition code and the even-weight code are just the right size for following the later calculations of Tutte polynomials by hand.

To move towards the MacWilliams identity, we next need to handle duality and the removal of coordinates. On the coding-theory side, dual codes, punctured codes, and shortened codes appear. On the matroid side, the corresponding operations are duality, deletion, and contraction.

To connect the Tutte polynomial with the MacWilliams identity, we need to be able to handle duality, deletion, and contraction in terms of rank functions. First, just as codes have dual codes, matroids have duals.

The dual of a matroid is indeed a matroid, and is called the dual matroid.

Proof

It suffices to check that $r_{M^{\ast}} = r^{\ast}$ satisfies the axioms for the rank function of a matroid.

Boundedness (R1)$0\leq r(A) \leq \card{A}$.(R1)

Note that $r_{M}$ satisfies the rank-function axioms. For $S \subseteq E$ and $e \in E \setminus S$, applying submodularity of $r_{M}$ gives

$$r_{M}(S \cup \{ e \}) + r_{M}(S \cap \{ e \}) \leq r_{M}(S) + r_{M}(\{ e \}) \leq r_{M}(S) + 1$$

Since $e \notin S$, we have $r_{M}(S \cap \{ e \}) = r_{M}(\emptyset) = 0$, and hence $r_{M}(S \cup \{ e \}) \leq r_{M}(S) + 1$. Repeating this, for $S \subseteq E$ and $T \subseteq E \setminus S$ we get

$$r_{M}(S \cup T) \leq r_{M}(S) + \card{T} \tag{4.1}$$

Applying this with $S = E \setminus A$ and $T = A$ gives

$$r_{M}(E) \leq r_{M}(E \setminus A) + \card{A}$$

Therefore

$$\card{A} - r_{M}(E) + r_{M}(E \setminus A) \geq 0$$

Also, by monotonicity, $r_{M}(E\setminus A) \leq r_M(E)$, and hence

$$r_{M^{\ast}}(A) = \card{A} - r_{M}(E) + r_{M}(E \setminus A) \leq \card{A}$$

Monotonicity (R2)If $A \subseteq B$, then $r(A) \leq r(B)$.(R2)

If $A \subseteq B$, then $E \setminus B \subseteq E \setminus A$. Applying $$r_{M}(S \cup T) \leq r_{M}(S) + \card{T} \tag{4.1}$$(4.1) with $S = E \setminus B$ and $T = B \setminus A$, we get

$$\begin{aligned} r_{M}(E \setminus A) &= r_{M}\bigl( (E \setminus B) \cup (B \setminus A) \bigr) \\ &\leq r_{M}(E \setminus B) + \card{B \setminus A} \end{aligned}$$

Adding $\card{A} - r_{M}(E)$ to both sides gives

$$\begin{aligned} r_{M^{\ast}}(A) &= \card{A} - r_{M}(E) + r_{M}(E \setminus A) \\ &\leq \card{A} - r_{M}(E) + r_{M}(E \setminus B) + \card{B \setminus A} \\ &= \card{B} - r_{M}(E) + r_{M}(E \setminus B) = r_{M^{\ast}}(B) \end{aligned}$$

This proves monotonicity (R2)If $A \subseteq B$, then $r(A) \leq r(B)$.(R2).

Submodularity (R3)$r(A \cup B) + r(A \cap B) \leq r(A) + r(B)$.(R3)

Since $E \setminus (A \cup B) = (E \setminus A) \cap (E \setminus B)$ and $E \setminus (A \cap B) = (E \setminus A) \cup (E \setminus B)$, submodularity of $r_{M^{\ast}}$ is exactly submodularity of $r_{M}$. Indeed,

$$\begin{aligned} &r^{\ast}(A) + r^{\ast}(B) - r^{\ast}(A \cup B) - r^{\ast}(A \cap B)\\ &= r(E \setminus A) + r(E \setminus B)\\ &\quad - r(E \setminus (A \cap B)) - r(E \setminus(A \cup B)) \end{aligned}$$

and the right-hand side is non-negative by submodularity of $r$.

Thus Definition Definition 4.1 (Dual matroid)Let $M = (E, r_{M})$ be a matroid. Define a function $r^{\ast} \colon 2^{E} \to \mathbb{Z}$ by $$r^{\ast}(A) \coloneqq \card{A} - r_{M}(E) + r_{M}(E \setminus A)$$ for each $A \subseteq E$. The pair $(E, r^{\ast})$ is called the dual of $M$, and is denoted by $M^{\ast}$.Definition 4.1 indeed defines a matroid.

End of proof□

In particular, the rank of the dual matroid $M^{\ast}$ is

Also, the formula immediately gives $(M^{\ast})^{\ast}=M$. As we show below, $M^{\ast}$ corresponds to the dual code $C^{\perp}$. These facts abstract $\dim C^{\perp} = \card{E} - \dim C$ and $(C^{\perp})^{\perp} = C$.

Proof

Put $k \coloneqq \dim C$, and let $A \subseteq E$. The kernel of the projection $C^{\perp} \to \res{C^{\perp}}{A}$ consists of the codewords of $C^{\perp}$ that are $0$ on $A$. If this kernel is restricted to $E \setminus A$, it can be identified with the orthogonal complement of $\res{C}{E \setminus A} \leq \F_{q}^{E \setminus A}$. Indeed, an element $u \in C^{\perp}$ that is zero on $A$ can be identified with a vector $w$ on $E \setminus A$. Then, for every $c \in C$, we have $0 = u \cdot c = w \cdot \res{c}{E \setminus A}$, so $w$ belongs to the orthogonal complement of $\res{C}{E \setminus A}$. Conversely, given such a $w$, extend it by zero on $A$. Therefore the dimension of the kernel is

$$\card{E \setminus A} - r_{C}(E \setminus A)$$

Hence

$$\begin{aligned} r_{C^{\perp}}(A) &= \dim C^{\perp} -\bigl(\card{E \setminus A} - r_{C}(E \setminus A) \bigr)\\ &= (n - k) - \card{E \setminus A} + r_{C}(E \setminus A) \\ &= \card{A} - r_{C}(E) + r_{C}(E \setminus A) \end{aligned}$$

This is exactly the dual rank function in Definition Definition 4.1 (Dual matroid)Let $M = (E, r_{M})$ be a matroid. Define a function $r^{\ast} \colon 2^{E} \to \mathbb{Z}$ by $$r^{\ast}(A) \coloneqq \card{A} - r_{M}(E) + r_{M}(E \setminus A)$$ for each $A \subseteq E$. The pair $(E, r^{\ast})$ is called the dual of $M$, and is denoted by $M^{\ast}$.Definition 4.1.

End of proof□

Proposition 4.3 (Dual codes and dual matroids)For every linear code $C \leq \F_{q}^{E}$, $$M(C^{\perp}) = M(C)^{\ast}$$ holds.Proposition 4.3 is one of the most important translations in this part. Taking the dual code agrees with taking the dual of the associated matroid. Therefore, when we later use the duality of the Tutte polynomial, it will be reflected directly as an identity about the weight enumerator of the dual code.

Next come deletion and contraction. On the matroid side, these are defined by rank functions. On the coding-theory side, deletion corresponds to puncturing, and the operation corresponding to contraction is shortening.

The rank functions of deletion and contraction also satisfy the three conditions in Definition 2.1 (Matroid)Let $E$ be a finite set and let $r \colon 2^{E} \to \mathbb{Z}$ be an integer-valued function. The pair $M = (E, r)$ is called a matroid if the following conditions hold for all $A, B \subseteq E$:

1. $0\leq r(A) \leq \card{A}$.
2. If $A \subseteq B$, then $r(A) \leq r(B)$.
3. $r(A \cup B) + r(A \cap B) \leq r(A) + r(B)$.

The set $E$ is called the ground set of $M$, and $r$ is called the rank function of $M$. When we want to emphasise $M$, we write $r_{M}$. Also, $r(A)$ is called the rank of $A$, and $r(M) \coloneqq r(E)$ is called the rank of $M$.Definition 2.1. For deletion, this is clear because we have simply restricted the domain of $r_{M}$. For contraction, non-negativity follows from $r_{M}(A \cup S) \geq r_{M}(S)$, and the upper bound $r_{M}(A \cup S) - r_{M}(S) \leq \card{A}$ follows from the inequality $$r_{M}(S \cup T) \leq r_{M}(S) + \card{T} \tag{4.1}$$(4.1), which appeared in the proof of Proposition 4.2For every matroid $M$, the dual $M^{\ast}$ is a matroid.Proposition 4.2 and says that adding elements can increase rank by at most the number of added elements. Monotonicity follows from monotonicity of $r_{M}$. Submodularity follows by applying submodularity to $A \cup S$ and $B \cup S$ for $A, B \subseteq E \setminus S$, which gives

To avoid confusion, let us summarise the notation in a table.

Notation	Operation	Coordinate set of the resulting code
$\res{C}{S}$	restrict to $S$	$S$
$C^{S}$	puncture, deleting $S$	$E \setminus S$
$C_{S}$	take codewords with $0$ on $S$, then delete $S$	$E\setminus S$
$C(S)$	subcode of codewords whose supports are contained in $S$	subcode on $E$

The following proposition shows that deletion and contraction of matroids correspond to puncturing and shortening of codes:

Proof

Let $A \subseteq E \setminus S$. For puncturing,

$$r_{C^{S}}(A) = \dim(\res{(\res{C}{E \setminus S})}{A}) = \dim(\res{C}{A}) = r_{C}(A)$$

so indeed $M(C^{S}) = M(C) \backslash S$.

For shortening, consider the restriction map $\res{C}{A \cup S} \to \res{C}{S}$. This map is surjective, and its kernel consists of the codewords of $C$ that are $0$ on $S$, restricted to $A \cup S$. If we then remove the coordinates in $S$, this kernel can be identified with $\res{C_{S}}{A}$. Therefore

$$r_{C_{S}}(A) = \dim(\res{C_{S}}{A}) = \dim(\res{C}{A \cup S}) - \dim(\res{C}{S}) = r_{C}(A \cup S) - r_{C}(S)$$

This is exactly the rank function of $M(C)/S$.

End of proof□

Deletion and contraction, and likewise puncturing and shortening, are dual operations. Indeed, direct calculation from the rank functions shows that for every $S\subseteq E$,

This corresponds, on the coding-theory side, to the fact that puncturing and shortening are interchanged by taking dual codes:

We now turn to the Tutte polynomial. All the matroid information prepared so far is contained in the rank function $r_{M}$. The Tutte polynomial is a two-variable polynomial that uses the rank function to count all subsets according to their rank defect and their degree of dependence. However, it is worth noting that in general one cannot recover the matroid from its Tutte polynomial.

If one looks only at the defining formula, it may seem a little sudden. However, for each $A \subseteq E$, the two exponents in the summand,

each have meaning. The first measures how far $A$ falls short of the rank of the whole matroid. For the second, recall that $A$ is independent when $\card{A} = r_{M}(A)$. Thus the second measures how much dependence is contained in $A$, or how much room there is with respect to being dependent. The Tutte polynomial collects these two quantities over all $A \subseteq E$. The former is sometimes called the rank defect of $A$, and the latter the nullity of $A$.

By the rank-function axioms in Definition 2.1 (Matroid)Let $E$ be a finite set and let $r \colon 2^{E} \to \mathbb{Z}$ be an integer-valued function. The pair $M = (E, r)$ is called a matroid if the following conditions hold for all $A, B \subseteq E$:

1. $0\leq r(A) \leq \card{A}$.
2. If $A \subseteq B$, then $r(A) \leq r(B)$.
3. $r(A \cup B) + r(A \cap B) \leq r(A) + r(B)$.

The set $E$ is called the ground set of $M$, and $r$ is called the rank function of $M$. When we want to emphasise $M$, we write $r_{M}$. Also, $r(A)$ is called the rank of $A$, and $r(M) \coloneqq r(E)$ is called the rank of $M$.Definition 2.1, the exponents $r_{M}(E) - r_{M}(A)$ and $\card{A} - r_{M}(A)$ are both non-negative integers. Therefore $\Tutte_{M}(x, y)$ is a two-variable polynomial with integer coefficients.

The empty matroid $U_{0, 0}$, the single loop $U_{0, 1}$, and the single coloop $U_{1, 1}$ play an important role in the Tutte polynomial, even though they are simple examples. Let us first compute these three Tutte polynomials.

The empty matroid, the single loop, and the single coloop are important because they also appear as initial values for the deletion-contraction formula. In particular, the fact that a single loop gives $y$ and a single coloop gives $x$ appears directly in the later formula.

The following special values are useful for grasping the meaning of the Tutte polynomial.

Proof

Note that $(x - 1)^{0}$ and $(y - 1)^{0}$ are, as usual, equal to $1$.

When $x = 1$ and $y = 1$, a term is not $0$ if and only if both exponents are $0$, that is,

$$r_{M}(E) - r_{M}(A) = 0 \quad\text{and}\quad \card{A} - r_{M}(A) = 0$$

This is equivalent to $A$ being a basis. Therefore $\Tutte_M(1, 1)$ is equal to the number of bases.

Next let $x = 2$ and $y = 1$. Then for every $A \subseteq E$,

$$(x - 1)^{r_{M}(E) - r_{M}(A)} = 1$$

so a term is not $0$ if and only if the exponent of $(y - 1)$ is $0$, that is,

$$\card{A} - r_{M}(A) = 0$$

This is equivalent to $A$ being independent.

End of proof□

We now check two basic properties of the Tutte polynomial. The first is duality.

Proof

By the definition of the dual matroid,

$$r_{M^{\ast}}(E \setminus A) = \card{E \setminus A} - r_{M}(E) + r_{M}(A)$$

Hence

$$\card{E \setminus A} - r_{M^{\ast}}(E \setminus A) = r_{M}(E) - r_{M}(A)$$

Also, since $r_{M^{\ast}}(E) = \card{E} - r_{M}(E)$, we also get

$$r_{M^{\ast}}(E) - r_{M^{\ast}}(E \setminus A) = \card{A} - r_M(A)$$

Therefore

$$\begin{aligned} \Tutte_{M^{\ast}}(x, y) &= \sum_{A \subseteq E} (x - 1)^{r_{M^{\ast}}(E) - r_{M^{\ast}}(A)} (y - 1)^{\card{A} - r_{M^{\ast}}(A)}\\ &= \sum_{B \subseteq E} (x - 1)^{\card{B} - r_{M}(B)} (y - 1)^{r_{M}(E) - r_{M}(B)}\\ &=\Tutte_{M}(y, x) \end{aligned}$$

as required.

End of proof□

The second is the deletion-contraction formula. This is the basic formula for computing the Tutte polynomial recursively.

Proof

Put $E^{\prime} \coloneqq E \setminus\{ e \}$.

(i)If $e$ is a loop, then $$\Tutte_{M}(x, y) = y\Tutte_{M \backslash e}(x, y).$$(i)

Assume that $e$ is a loop. Then, for every $A \subseteq E^{\prime}$,

$$r_{M}(A \cup \{ e \}) = r_{M}(A), \qquad r_{M}(E) = r_{M}(E^{\prime})$$

Splitting the sum defining the Tutte polynomial into subsets containing $e$ and subsets not containing it, we get

$$\begin{aligned} \Tutte_{M}(x, y) &= \sum_{e \in D \subseteq E} (x - 1)^{r_{M}(E) - r_{M}(D)} (y - 1)^{\card{D} - r_{M}(D)}\\ &\qquad + \sum_{e \notin S \subseteq E} (x - 1)^{r_{M}(E) - r_{M}(S)} (y - 1)^{\card{S} - r_{M}(S)} \\ &= \sum_{D^{\prime} \subseteq E^{\prime}} (x - 1)^{r_{M}(E^{\prime}) - r_{M}(D^{\prime})} (y - 1)^{\bigl( \card{D^{\prime}} + 1 \bigr) - r_{M}(D^{\prime})} \\ &\qquad + \sum_{S \subseteq E^{\prime}} (x - 1)^{r_{M \backslash e}(E^{\prime}) - r_{M \backslash e}(S)} (y - 1)^{\card{S} - r_{M \backslash e}(S)} \\ &= (y - 1) \Tutte_{M \backslash e}(x, y) + \Tutte_{M \backslash e}(x, y) \\ &= y\Tutte_{M \backslash e}(x, y) \end{aligned}$$

This proves (i)If $e$ is a loop, then $$\Tutte_{M}(x, y) = y\Tutte_{M \backslash e}(x, y).$$(i).

(ii)If $e$ is a coloop, then $$\Tutte_{M}(x, y) = x\Tutte_{M/e}(x, y).$$(ii)

The case where $e$ is a coloop follows from duality. Indeed, $e$ is a coloop of $M$ if and only if $e$ is a loop of $M^{\ast}$. Also, $(M/e)^{\ast} = M^{\ast} \backslash e$. Therefore, by (i)If $e$ is a loop, then $$\Tutte_{M}(x, y) = y\Tutte_{M \backslash e}(x, y).$$(i) and Proposition 6.1 (Duality of the Tutte polynomial)For every matroid $M$, $$\Tutte_{M^{\ast}}(x, y) = \Tutte_{M}(y, x)$$ holds.Proposition 6.1,

$$\begin{aligned} \Tutte_M(x, y) &= \Tutte_{M^{\ast}}(y, x)\\ &= x\Tutte_{M^{\ast} \backslash e}(y, x)\\ &= x\Tutte_{(M/e)^{\ast}}(y, x)\\ &= x\Tutte_{M/e}(x, y) \end{aligned}$$

This proves (ii)If $e$ is a coloop, then $$\Tutte_{M}(x, y) = x\Tutte_{M/e}(x, y).$$(ii).

(iii)If $e$ is neither a loop nor a coloop, then $$\Tutte_{M}(x, y) = \Tutte_{M \backslash e}(x, y) + \Tutte_{M/e}(x, y).$$(iii)

Suppose that $e$ is neither a loop nor a coloop. Then $r_{M}(\{ e \}) = 1$ and $r_{M}(E) = r_{M}(E^{\prime})$. The contribution from subsets not containing $e$ is, by definition, exactly $\Tutte_{M \backslash e}(x, y)$. Write a subset containing $e$ as $A \cup \{e\}$, where $A \subseteq E^{\prime}$. By the rank formula for contraction,

$$r_{M/e}(A) = r_{M}(A \cup \{ e \}) - 1, \qquad r_{M/e}(E^{\prime}) = r_{M}(E) - 1$$

Therefore the contribution from subsets containing $e$ is $\Tutte_{M/e}(x, y)$. Hence

$$\Tutte_{M}(x, y) = \Tutte_{M \backslash e}(x, y) + \Tutte_{M/e}(x, y)$$

End of proof□

Invariants of this deletion-contraction type are often treated as Tutte–Grothendieck invariants, or simply T–G invariants. For a classical survey of the basic properties, universality, and applications of the Tutte polynomial, Brylawski–Oxley [BO92] is a standard reference.

If we generalise the above formula slightly, the relation with weight enumerators becomes easier to see. Consider a matroid invariant $\widetilde{\Tutte}_{M}(s, t, a, b)$ satisfying the following recursions:

1. $\widetilde{\Tutte}_{U_{0, 0}}(s, t, a, b) = 1$,

2. if $e$ is a loop, then $\widetilde{\Tutte}_{M}(s, t, a, b) = s\widetilde{\Tutte}_{M \backslash e}(s, t, a, b)$,

3. if $e$ is a coloop, then $\widetilde{\Tutte}_{M}(s, t, a, b) = t\widetilde{\Tutte}_{M/e}(s, t, a, b)$,

4. if $e$ is neither a loop nor a coloop, then

   $$\widetilde{\Tutte}_{M}(s, t, a, b) = a\widetilde{\Tutte}_{M \backslash e}(s, t, a, b) + b \widetilde{\Tutte}_{M/e}(s, t, a, b).$$

The uniqueness is clear by induction on the size of the ground set. The value is determined on the empty matroid, and in the non-empty case, once an element $e$ is chosen, the right-hand side is written in terms of matroids whose ground sets have one fewer element. By a simple renormalisation of the ordinary Tutte polynomial, the solution is obtained as follows. Here $a$ and $b$ are treated as invertible formal parameters. More strictly, one should work in a suitable coefficient ring, or read the formula after clearing denominators.

Proof

Put $\displaystyle \overline{\Tutte}_{M}(s, t, a, b) \coloneqq a^{\card{E} - r_{M}(E)} b^{r_{M}(E)} \Tutte_{M}\left( \frac{t}{b}, \frac{s}{a} \right)$. We show that $\widetilde{\Tutte}_{M}(s, t, a, b) = \overline{\Tutte}_{M}(s, t, a, b)$ by checking that $\overline{\Tutte}_{M}(s, t, a, b)$ actually satisfies the recurrence in (a)$\widetilde{\Tutte}_{U_{0, 0}}(s, t, a, b) = 1$,(a), (b)if $e$ is a loop, then $\widetilde{\Tutte}_{M}(s, t, a, b) = s\widetilde{\Tutte}_{M \backslash e}(s, t, a, b)$,(b), (c)if $e$ is a coloop, then $\widetilde{\Tutte}_{M}(s, t, a, b) = t\widetilde{\Tutte}_{M/e}(s, t, a, b)$,(c), and (d)if $e$ is neither a loop nor a coloop, then $$\widetilde{\Tutte}_{M}(s, t, a, b) = a\widetilde{\Tutte}_{M \backslash e}(s, t, a, b) + b \widetilde{\Tutte}_{M/e}(s, t, a, b).$$(d).

(a)$\widetilde{\Tutte}_{U_{0, 0}}(s, t, a, b) = 1$,(a)

The ground set of $U_{0,0}$ is empty and its rank is $0$, so by Example 5.2 (The empty matroid and one-point matroids)For the empty matroid $U_{0, 0}$, the only subset in the sum is $\emptyset$, so $$\Tutte_{U_{0, 0}}(x, y) = (x - 1)^{0 - 0}(y - 1)^{0 - 0} = 1$$ For $U_{0, 1}$ on the singleton $E = \{ e \}$, the element $e$ is a loop, and $$\Tutte_{U_{0,1}}(x, y) = (x - 1)^{0 - 0}(y - 1)^{0 - 0} + (x - 1)^{0 - 0}(y - 1)^{1 - 0} = 1 + (y - 1) = y$$ On the other hand, in $U_{1, 1}$ the element $e$ is a coloop, and $$\Tutte_{U_{1,1}}(x, y) = (x - 1)^{1 - 0}(y - 1)^{0 - 0} + (x - 1)^{1 - 1}(y - 1)^{1 - 1} = (x - 1) + 1 = x$$Example 5.2,

$$\overline{\Tutte}_{U_{0, 0}}(s, t, a, b) = a^{0-0}b^{0}\Tutte_{U_{0,0}}\left( \frac{t}{b}, \frac{s}{a} \right) = 1$$

as required.

(b)if $e$ is a loop, then $\widetilde{\Tutte}_{M}(s, t, a, b) = s\widetilde{\Tutte}_{M \backslash e}(s, t, a, b)$,(b)

If $e$ is a loop, then $r_{M \backslash e}(E \setminus \{ e \}) = r_{M}(E)$. Therefore, by Proposition 6.2 (Deletion-contraction formula)Let $M$ be a matroid on $E$, and let $e \in E$. Then the following hold:

1. If $e$ is a loop, then $$\Tutte_{M}(x, y) = y\Tutte_{M \backslash e}(x, y).$$
2. If $e$ is a coloop, then $$\Tutte_{M}(x, y) = x\Tutte_{M/e}(x, y).$$
3. If $e$ is neither a loop nor a coloop, then $$\Tutte_{M}(x, y) = \Tutte_{M \backslash e}(x, y) + \Tutte_{M/e}(x, y).$$

Proposition 6.2(i)If $e$ is a loop, then $$\Tutte_{M}(x, y) = y\Tutte_{M \backslash e}(x, y).$$(i),

$$\begin{aligned} \overline{\Tutte}_{M}(s, t, a, b) &= a \cdot a^{\card{E \setminus \{ e \}} - r_{M \backslash e}(E \setminus \{ e \})} b^{r_{M \backslash e}(E \setminus \{ e \})} \frac{s}{a} \Tutte_{M \backslash e}\left( \frac{t}{b}, \frac{s}{a} \right) \\ &= s\overline{\Tutte}_{M \backslash e}(s, t, a, b) \end{aligned}$$

as required.

(c)if $e$ is a coloop, then $\widetilde{\Tutte}_{M}(s, t, a, b) = t\widetilde{\Tutte}_{M/e}(s, t, a, b)$,(c)

If $e$ is a coloop, then $r_{M/e}(E \setminus \{ e \}) = r_{M}(E) - 1$. Therefore, by Proposition 6.2 (Deletion-contraction formula)Let $M$ be a matroid on $E$, and let $e \in E$. Then the following hold:

1. If $e$ is a loop, then $$\Tutte_{M}(x, y) = y\Tutte_{M \backslash e}(x, y).$$
2. If $e$ is a coloop, then $$\Tutte_{M}(x, y) = x\Tutte_{M/e}(x, y).$$
3. If $e$ is neither a loop nor a coloop, then $$\Tutte_{M}(x, y) = \Tutte_{M \backslash e}(x, y) + \Tutte_{M/e}(x, y).$$

Proposition 6.2(ii)If $e$ is a coloop, then $$\Tutte_{M}(x, y) = x\Tutte_{M/e}(x, y).$$(ii),

$$\begin{aligned} \overline{\Tutte}_{M}(s, t, a, b) &= a^{\card{E \setminus \{ e \}} - r_{M/e}(E \setminus \{ e \})} b^{r_{M/e}(E \setminus \{ e \})} \cdot b \cdot \frac{t}{b} \Tutte_{M/e}\left( \frac{t}{b}, \frac{s}{a} \right) \\ &= t\overline{\Tutte}_{M/e}(s, t, a, b) \end{aligned}$$

as required.

(d)if $e$ is neither a loop nor a coloop, then $$\widetilde{\Tutte}_{M}(s, t, a, b) = a\widetilde{\Tutte}_{M \backslash e}(s, t, a, b) + b \widetilde{\Tutte}_{M/e}(s, t, a, b).$$(d)

If $e$ is neither a loop nor a coloop, then by Proposition 6.2 (Deletion-contraction formula)Let $M$ be a matroid on $E$, and let $e \in E$. Then the following hold:

1. If $e$ is a loop, then $$\Tutte_{M}(x, y) = y\Tutte_{M \backslash e}(x, y).$$
2. If $e$ is a coloop, then $$\Tutte_{M}(x, y) = x\Tutte_{M/e}(x, y).$$
3. If $e$ is neither a loop nor a coloop, then $$\Tutte_{M}(x, y) = \Tutte_{M \backslash e}(x, y) + \Tutte_{M/e}(x, y).$$

Proposition 6.2(iii)If $e$ is neither a loop nor a coloop, then $$\Tutte_{M}(x, y) = \Tutte_{M \backslash e}(x, y) + \Tutte_{M/e}(x, y).$$(iii),

$$\begin{aligned} \overline{\Tutte}_{M}(s, t, a, b) &= a^{\card{E} - r_{M}(E)} b^{r_{M}(E)} \left(\Tutte_{M \backslash e} \left( \frac{t}{b}, \frac{s}{a} \right) + \Tutte_{M/e} \left( \frac{t}{b}, \frac{s}{a} \right) \right) \\ &= a \cdot a^{\card{E \setminus \{ e \}} - r_{M \backslash e}(E \setminus \{ e \})} b^{r_{M \backslash e}(E \setminus \{ e \})} \Tutte_{M \backslash e}\left( \frac{t}{b}, \frac{s}{a} \right) \\ &\quad + a^{\card{E \setminus \{ e \}} - r_{M/e}(E \setminus \{ e \})} b \cdot b^{r_{M/e}(E \setminus \{ e \})} \Tutte_{M/e}\left( \frac{t}{b}, \frac{s}{a} \right) \\ &= a\overline{\Tutte}_{M \backslash e}(s, t, a, b) + b\overline{\Tutte}_{M/e}(s, t, a, b) \end{aligned}$$

as required.

End of proof□

Indeed, one can check directly from Proposition 6.2 (Deletion-contraction formula)Let $M$ be a matroid on $E$, and let $e \in E$. Then the following hold:

1. If $e$ is a loop, then $$\Tutte_{M}(x, y) = y\Tutte_{M \backslash e}(x, y).$$
2. If $e$ is a coloop, then $$\Tutte_{M}(x, y) = x\Tutte_{M/e}(x, y).$$
3. If $e$ is neither a loop nor a coloop, then $$\Tutte_{M}(x, y) = \Tutte_{M \backslash e}(x, y) + \Tutte_{M/e}(x, y).$$

Proposition 6.2 that the right-hand side satisfies the four recursions above. Thus the proposition says the powerful fact that every polynomial satisfying these four recursions for deletion and contraction is obtained from the Tutte polynomial. In this sense, the Tutte polynomial can be viewed as one of the most universal matroid invariants involving deletion and contraction. This viewpoint is a shortcut to reading Greene's theorem as saying that the weight enumerator is a specialisation of the Tutte polynomial.

We now connect the weight enumerator of a code with the Tutte polynomial. Let us first organise what we want to prove. The Tutte polynomial satisfies very clean recursions with respect to deletion and contraction of matroids. On the other hand, the weight enumerator of a code can also be decomposed recursively by puncturing or shortening one coordinate. Greene's theorem writes the fact that these two recursions have the same form as an explicit change of variables.

First, let us check the recursion on the side of weight enumerators. Here we fix an element $e \in E$ and split into cases according to whether $e$ is a loop, a coloop, or neither, in the matroid $M(C)$. In the matroid $M(C)$ associated with a code, $e$ being a loop is equivalent to every codeword having $0$ in coordinate $e$. Indeed, for $r_{C}(\{ e \}) = \dim \res{C}{\{ e \}} = 0$ to hold, it is necessary and sufficient that $\res{C}{\{ e \}} = \{ 0 \}$, and this is equivalent to every codeword having $0$ in coordinate $e$.

On the other hand, $e$ being a coloop is equivalent to the existence in $C$ of a codeword which is non-zero only in coordinate $e$. This may be easier to understand by looking at duality rather than directly at ranks. A coloop is a loop in the dual matroid, and the dual matroid corresponds exactly to the dual code. Thus $e$ being a coloop means that every codeword of the dual code $C^{\perp}$ has $0$ in coordinate $e$. A word that is non-zero only in coordinate $e$ and zero everywhere else is orthogonal to all such vectors, hence is a codeword of $C$. Conversely, if $C$ contains a codeword which is non-zero only in coordinate $e$ and zero everywhere else, then every codeword of $C^{\perp}$ has $0$ in coordinate $e$. More algebraically, $e$ being a coloop means that $r_{C}(E) - r_{C}(E \setminus \{ e \}) = 1$. This is equivalent to saying that the kernel of the projection $C \to \res{C}{E \setminus \{ e \}}$ is $1$-dimensional. This kernel consists of all codewords whose coordinates other than $e$ are all $0$.

Proof

Put $E^{\prime} \coloneqq E \setminus \{ e \}$.

(i)If $e$ is a loop of $M(C)$, then $$W_{C}(X, Y) = X W_{C^{\{ e \}}}(X, Y).$$(i)

Assume that $e$ is a loop. Then $r_{C}(\{ e \}) = 0$, so every codeword has $0$ in coordinate $e$. Therefore each codeword of $C$ is obtained by extending a codeword of $C^{\{ e \}}$ by adding one zero coordinate. The weight does not change, while the length increases by $1$, so the weight enumerator is multiplied by $X$. Hence $W_{C}(X, Y) = XW_{C^{\{ e \}}}(X, Y)$. Formally,

$$\begin{aligned} W_{C}(X, Y) &= \sum_{c \in C} X^{\card{E} - \wt(c)} Y^{\wt(c)} \\ &= \sum_{c \in C} X \cdot X^{(\card{E} - 1) - \wt(\res{c}{E \setminus \{ e \}})} Y^{\wt(\res{c}{E \setminus \{ e \}})} \\ &= X \sum_{c^{\prime} \in C^{\{ e \}}} X^{\card{E \setminus \{ e \}} - \wt(c^{\prime})} Y^{\wt(c^{\prime})} = XW_{C^{\{ e \}}}(X, Y) \end{aligned}$$

(ii)If $e$ is a coloop of $M(C)$, then $$W_{C}(X, Y) = \bigl( X + (q - 1)Y \bigr) W_{C_{\{ e \}}}(X, Y).$$(ii)

Assume that $e$ is a coloop. Then $r_{C}(E) - r_{C}(E^{\prime}) = 1$, so the kernel of the projection $C \to \res{C}{E^{\prime}} = C^{\{ e \}}$ is one-dimensional. This kernel is a one-dimensional subspace supported only on coordinate $e$. In particular, there exists a codeword which is non-zero only in coordinate $e$. By subtracting a suitable scalar multiple of such a codeword from any $c \in C$, we can make coordinate $e$ equal to $0$ without changing the values on $E^{\prime}$. Therefore $C^{\{ e \}} = C_{\{ e \}}$, and each codeword of $C_{\{ e \}}$ lifts to $C$ in $q$ ways. Among these lifts, one has coordinate $e$ equal to $0$, while the remaining $q - 1$ have coordinate $e$ non-zero. The former contributes a factor $X$ to the weight enumerator, and the latter contribute a factor $Y$. Thus, writing the argument formally,

$$\begin{aligned} W_{C}(X, Y) &= \sum_{c^{\prime} \in C_{\{ e \}}} \left( X \cdot X^{\card{E^{\prime}}-\wt(c^{\prime})}Y^{\wt(c^{\prime})} + (q - 1)Y \cdot X^{\card{E^{\prime}} - \wt(c^{\prime})} Y^{\wt(c^{\prime})} \right) \\ &= \bigl( X + (q - 1)Y \bigr) W_{C_{\{ e \}}}(X, Y) \end{aligned}$$

(iii)If $e$ is neither a loop nor a coloop of $M(C)$, then $$W_{C}(X, Y) = YW_{C^{\{ e \}}}(X, Y) + (X - Y)W_{C_{\{ e \}}}(X, Y).$$(iii)

Assume that $e$ is neither a loop nor a coloop. Since it is not a coloop, we have $r_{C}(E) = r_{C}(E^{\prime})$, so the projection $C \to C^{\{ e \}}$ is injective. Therefore each codeword of $C^{\{ e \}}$ corresponds to a unique codeword of $C$. Since it is not a loop, the projection $C \to \F_{q}$ to coordinate $e$ is non-zero. Its image is the one-dimensional space $\F_{q}$, so this map is surjective, and its kernel is a codimension-one subspace of $C$. Restricting this kernel to $E^{\prime}$ gives $C_{\{ e \}}$. Thus the codewords of $C^{\{ e \}}$ whose lift to $C$ has $0$ in coordinate $e$ are exactly the codewords of $C_{\{ e \}}$.

We therefore split the codewords of $C^{\{ e \}}$ into two parts. Those belonging to $C_{\{ e \}}$ acquire one zero coordinate in $C$, giving a factor $X$. Those not belonging to $C_{\{ e \}}$ acquire one non-zero coordinate, giving a factor $Y$.

$$W_{C}(X, Y) = \underbrace{\sum_{\substack{c \in C \\ e \notin \supp(c)}} X^{\card{E} - \wt(c)} Y^{\wt(c)}}_{\eqqcolon W_{C}^{-}(X, Y)} + \underbrace{\sum_{\substack{c \in C \\ e \in \supp(c)}} X^{\card{E} - \wt(c)} Y^{\wt(c)}}_{\eqqcolon W_{C}^{+}(X, Y)}$$

Then $W_{C_{\{ e \}}}(X, Y) = W_{C}^{-}/X$ and $W_{C^{\{ e \}}}(X, Y) = W_{C}^{-}(X, Y)/X + W_{C}^{+}/Y$. Therefore

$$\begin{aligned} W_{C}(X, Y) &= W_{C}^{-}(X, Y) + W_{C}^{+}(X, Y) \\ &= Y W_{C^{\{ e \}}}(X, Y) + (X - Y)W_{C_{\{ e \}}}(X, Y) \end{aligned}$$

as required.

End of proof□

Combining Proposition 7.1 (Puncturing-shortening recursion for weight enumerators)Let $C \leq \F_{q}^{E}$ be a linear code, and let $e \in E$.

1. If $e$ is a loop of $M(C)$, then $$W_{C}(X, Y) = X W_{C^{\{ e \}}}(X, Y).$$
2. If $e$ is a coloop of $M(C)$, then $$W_{C}(X, Y) = \bigl( X + (q - 1)Y \bigr) W_{C_{\{ e \}}}(X, Y).$$
3. If $e$ is neither a loop nor a coloop of $M(C)$, then $$W_{C}(X, Y) = YW_{C^{\{ e \}}}(X, Y) + (X - Y)W_{C_{\{ e \}}}(X, Y).$$

Proposition 7.1 with Proposition 4.6 (Puncturing, shortening, deletion, and contraction)For every linear code $C \leq \F_{q}^{E}$ and every $S \subseteq E$, $$M(C^{S}) = M(C) \backslash S, \qquad M(C_{S}) = M(C)/S$$ holds.Proposition 4.6, we see that the recursion for weight enumerators operates on the same ground set as the deletion-contraction recursion for matroids. However, the coefficients are different from those of the Tutte polynomial itself. For the Tutte polynomial, the coefficients in the loop, coloop, and general cases were respectively $y$, $x$, $1$, and $1$. For the weight enumerator, these are replaced by $X$, $X + (q - 1)Y$, $Y$, and $X - Y$. Greene's theorem is the precise reflection of this replacement.

At first glance, $r_{C}(A) = \dim \res{C}{A}$ seems to record only "the dimension of the image visible from the coordinate set $A$", and does not seem to count individual codeword weights directly. However, the number of codewords whose support is contained in $A$ is determined by $\card{C(A)} = q^{k - r_{C}(E \setminus A)}$. This fact is the key reason why a weight enumerator emerges from a Tutte polynomial.

Combining Proposition 7.1 (Puncturing-shortening recursion for weight enumerators)Let $C \leq \F_{q}^{E}$ be a linear code, and let $e \in E$.

1. If $e$ is a loop of $M(C)$, then $$W_{C}(X, Y) = X W_{C^{\{ e \}}}(X, Y).$$
2. If $e$ is a coloop of $M(C)$, then $$W_{C}(X, Y) = \bigl( X + (q - 1)Y \bigr) W_{C_{\{ e \}}}(X, Y).$$
3. If $e$ is neither a loop nor a coloop of $M(C)$, then $$W_{C}(X, Y) = YW_{C^{\{ e \}}}(X, Y) + (X - Y)W_{C_{\{ e \}}}(X, Y).$$

Proposition 7.1 with Proposition 4.6 (Puncturing, shortening, deletion, and contraction)For every linear code $C \leq \F_{q}^{E}$ and every $S \subseteq E$, $$M(C^{S}) = M(C) \backslash S, \qquad M(C_{S}) = M(C)/S$$ holds.Proposition 4.6, we obtain

so the desired result follows immediately from the recursion. Below, however, keeping this recursive viewpoint in the background, we give a direct proof by counting supports subset by subset. The advantage is that it makes it easier to see where the factors in the change of variables come from. Also, although the right-hand side looks at first like a rational expression, the proof below shows that the denominators cancel term by term. Thus Greene's identity is an identity of polynomials.

Proof

First, since the kernel of the projection $C \to \res{C}{E \setminus A}$ is $C(A)$, we have

$$\dim C(A) = k - r_{C}(E \setminus A)$$

For a fixed codeword $c \in C$, put $S = \supp(c)$. Then

$$X^{n - \wt(c)} Y^{\wt(c)} = \sum_{S \subseteq A \subseteq E}(X - Y)^{n - \card{A}} Y^{\card{A}}$$

Indeed, the right-hand side is

$$Y^{\card{S}} \sum_{B \subseteq E \setminus S}(X - Y)^{\card{E \setminus S} - \card{B}} Y^{\card{B}} =Y^{\card{S}}X^{\card{E \setminus S}}$$

Therefore, changing the order of summation gives

$$\begin{aligned} W_{C}(X, Y) &= \sum_{c \in C} \sum_{\supp(c) \subseteq A \subseteq E}(X - Y)^{n - \card{A}} Y^{\card{A}} \\ &= \sum_{A \subseteq E} \card{C(A)}(X - Y)^{n - \card{A}}Y^{\card{A}} \\ &= \sum_{A \subseteq E} q^{k - r_{C}(E \setminus A)}(X - Y)^{n - \card{A}} Y^{\card{A}} \end{aligned}$$

Rewriting with $B = E \setminus A$, we obtain

$$W_{C}(X, Y) = \sum_{B \subseteq E} q^{k - r_{C}(B)}(X - Y)^{\card{B}} Y^{n - \card{B}}$$

On the other hand, put

$$u \coloneqq \frac{X + (q - 1)Y}{X - Y}, \qquad v \coloneqq \frac{X}{Y}$$

Then

$$u - 1 = \frac{qY}{X - Y}, \qquad v - 1 = \frac{X - Y}{Y}$$

Hence

$$\begin{aligned} &Y^{n - k}(X - Y)^{k}\Tutte_{M(C)}(u, v) \\ &\quad= \sum_{B \subseteq E} Y^{n - k}(X - Y)^{k} \left(\frac{qY}{X - Y}\right)^{k - r_{C}(B)} \left(\frac{X - Y}{Y}\right)^{\card{B} - r_{C}(B)}\\ &\quad= \sum_{B \subseteq E} q^{k-r_{C}(B)}(X - Y)^{\card{B}} Y^{n - \card{B}} \end{aligned}$$

This agrees with the expression for $W_{C}(X, Y)$ obtained above.

End of proof□

The substitution appearing in Greene's theorem has a geometrically transparent property.

Then

Thus the weight enumerator appears as an evaluation of the Tutte polynomial along the hyperbola $(u - 1)(v - 1) = q$ in the Tutte plane.

In Example 7.3 (Checking the binary repetition code)As seen in , for the binary repetition code $C = \{ 000, 111 \}$, $$\Tutte_{M(C)}(x, y) = x + y + y^{2}$$ Since $q = 2$, $n = 3$, and $k = 1$, Greene's theorem gives $$W_{C}(X,Y) = Y^{2}(X - Y) \left( \frac{X + Y}{X - Y} + \frac{X}{Y} + \frac{X^{2}}{Y^{2}} \right)$$ Simplifying the right-hand side gives $$W_{C}(X, Y) = X^{3} + Y^{3}$$ which agrees with the weight enumerator of the repetition code.Example 7.3, we checked that the denominators on the right-hand side really cancel and that the weight enumerator itself is obtained. The same cancellation occurs in the proof of the theorem in general. Thus Greene's theorem is not saying that we evaluate the Tutte polynomial as a rational function; it is a polynomial identity saying that a specialisation of the Tutte polynomial gives the weight enumerator.

Finally, we derive the MacWilliams identity from Greene's theorem.

Proof

Put $n = \card{E}$ and $k = \dim C$. By Proposition 4.3 (Dual codes and dual matroids)For every linear code $C \leq \F_{q}^{E}$, $$M(C^{\perp}) = M(C)^{\ast}$$ holds.Proposition 4.3, we have $M(C^{\perp}) = M(C)^{\ast}$. Also, $\dim C^{\perp} = n - k$. By Greene's theorem and the duality of the Tutte polynomial, we get

$$\begin{aligned} W_{C^{\perp}}(X, Y) &=Y^{k}(X - Y)^{n - k} \Tutte_{M(C)^{\ast}}\left( \frac{X + (q - 1)Y}{X - Y}, \frac{X}{Y} \right)\\ &=Y^{k}(X - Y)^{n - k} \Tutte_{M(C)}\left( \frac{X}{Y}, \frac{X + (q - 1)Y}{X - Y} \right) \end{aligned}$$

On the other hand, applying Greene's theorem to $C$ and substituting $X + (q - 1)Y$ for $X$ and $X - Y$ for $Y$, we obtain

$$\begin{aligned} &W_{C}(X + (q - 1)Y, X - Y)\\ &=(X - Y)^{n - k}(qY)^{k} \times \Tutte_{M(C)}\left( \frac{qX}{qY}, \frac{X + (q - 1)Y}{X - Y} \right)\\ &= q^{k} Y^{k}(X - Y)^{n - k} \Tutte_{M(C)}\left( \frac{X}{Y}, \frac{X + (q - 1)Y}{X - Y} \right) \end{aligned}$$

Since $\card{C} = q^{k}$, dividing both sides by $\card{C}$ gives exactly the expression for $W_{C^{\perp}}(X, Y)$ obtained above.

End of proof□

The structures used in the proof above can be summarised in three points. First, from a code $C$ we obtain a matroid $M(C)$ by the dimensions of coordinate restrictions, $r_{C}(A) = \dim(\res{C}{A})$. This rank function measures how well the coordinate subset $A$ can distinguish the information in the code $C$.

Second, the dual code corresponds to the dual matroid: $M(C^{\perp})=M(C)^{\ast}$. This means that duality on the coding-theory side and duality on the matroid side are seeing the same structure.

Third, the weight enumerator is a specialisation of the Tutte polynomial:

This formula shows that the weight enumerator is not merely a direct count of codewords, but can also be recovered from rank information over all coordinate subsets.

Combining these three points, the duality of the Tutte polynomial,

becomes the MacWilliams identity directly. Thus, in this proof, the change of variables in the MacWilliams identity does not appear out of nowhere. It appears as the result of combining the interchange of variables in the Tutte plane with the specialisation appearing in Greene's theorem.

Let us organise the concepts used in this part according to their roles.

Matroids as rank functions

We defined a matroid on a finite set $E$ as a map $r \colon 2^{E} \to \mathbb{Z}$ satisfying boundedness, monotonicity, and submodularity.

Matroid associated with a code

For a linear code $C \leq \F_{q}^{E}$, we defined $M(C)$ by $r_{C}(A) = \dim(\res{C}{A})$.

Dual matroid

We defined it by the rank function $r_{M^{\ast}}(A) = \card{A} - r_{M}(E) + r_{M}(E \setminus A)$. For codes, $M(C^{\perp}) = M(C)^{\ast}$ holds.

Deletion and contraction

For matroids, these were defined by $r_{M \backslash S}(A) = r_{M}(A)$ and $r_{M/S}(A) = r_{M}(A \cup S)- r_{M}(S)$. For codes, deletion corresponds to puncturing, and contraction corresponds to shortening.

Tutte polynomial

We defined it as a two-variable polynomial which records, for all $A \subseteq E$, the two quantities $r_{M}(E) - r_{M}(A)$ and $\card{A} - r_{M}(A)$ at the same time.

Greene's theorem

This theorem expresses the weight enumerator of a code as a specialisation of the Tutte polynomial of the associated matroid.

Among these, what was directly needed for the proof of the MacWilliams identity was the rank function, duality, deletion and contraction, the Tutte polynomial, and Greene's theorem. Matroid theory has many other important concepts, but this note proceeded without using them. This is not so much an omission as a choice fitted to the purpose of this part.

The proof family in this part was the "matroid and Tutte-polynomial approach". By collecting the dimensions of restricted codes over coordinate subsets, the structure of the matroid $M(C)$ enters, and its Tutte polynomial recovers the weight enumerator. From this viewpoint, the MacWilliams identity is organised as the statement:

The operation corresponding to the dual code is, for the Tutte polynomial, the operation of interchanging the variables $x$ and $y$.

This organisation explains why the MacWilliams identity emerges naturally from Greene's theorem.

The proof in this note uses the interface between coding theory and matroid theory quite directly. I hope to return on another occasion to a more systematic treatment of matroid theory from the viewpoint of coding theory, including circuits, closure, flats, simplification, minors, representability, and related notions.

For the broader reach of the Tutte polynomial itself, the handbook edited by Ellis-Monaghan–Moffatt [EM22] gives a broad view of applications to graphs, matroids, statistical physics, coding theory, knot theory, and more.

Next time, we shall look at the MacWilliams identity from the side of group actions and cycle indices.

In the proof in this note, we extracted a matroid structure from the dimensions of restricted codes over coordinate subsets, and derived the MacWilliams identity from the duality of the Tutte polynomial. Next time, we shall use group actions on codewords and coordinates, and revisit the same identity in the language of orbits, Burnside's lemma, Pólya counting, and cycle indices.

Thus the protagonist next time will be

Even though it is the same MacWilliams identity, instead of looking at the "dimensions of restricted codes over coordinate subsets" as in this note, next time we will look at "averages over group actions" and "counting orbits".

References

1. [Whi35] Hassler Whitney. On the Abstract Properties of Linear Dependence. Amer. J. Math., vol. 57, no. 3, pp. 509–533, 1935. doi:10.2307/2371182 Citation contextMatroids were introduced by Whitney [Whi35]. A basic reference for the matroid version of the Tutte polynomial is Crapo [Cra69], and the relation between weight enumerators of codes and Tutte polynomials is due to Greene [Gre76]. For a survey of how properties of linear codes can be read from the Tutte polynomial starting from this theorem, see Britz–Cameron [BC22]. For a standard textbook on matroid theory, see Oxley [Oxl11].↩1 Citation contextIn this sense, one may interpret a matroid as an abstraction of the notion of dimension appearing in linear algebra. The word "matroid", introduced by Whitney [Whi35], comes from "matrix" plus the suffix "-oid", meaning something like a matrix. Indeed, if we consider a generator matrix of a linear code, then the dimension of $\res{C}{A}$ corresponds to the rank of the submatrix consisting of the columns labelled by $A$. In fact, if $G$ is a generator matrix of $C$, then $\res{C}{A}$ is the row space of the submatrix $\res{G}{A}$ obtained by retaining only the columns of $G$ belonging to $A$. That is,↩2 Citation contextAlthough we will not explain this in detail here because it is not the main topic, as already appears in Whitney's original paper [Whi35], matroids also abstract the rank of graphs. The terms "loop" and "isthmus" above come from loops and isthmi (bridges) in graphs.↩3
2. [Cra69] Henry H. Crapo. The Tutte polynomial. Aequationes Math., vol. 3, pp. 211–229, 1969. doi:10.1007/BF01817442 Citation contextMatroids were introduced by Whitney [Whi35]. A basic reference for the matroid version of the Tutte polynomial is Crapo [Cra69], and the relation between weight enumerators of codes and Tutte polynomials is due to Greene [Gre76]. For a survey of how properties of linear codes can be read from the Tutte polynomial starting from this theorem, see Britz–Cameron [BC22]. For a standard textbook on matroid theory, see Oxley [Oxl11].↩
3. [Gre76] Curtis Greene. Weight enumeration and the geometry of linear codes. Studies in Appl. Math., vol. 55, no. 2, pp. 119–128, 1976. doi:10.1002/sapm1976552119 Citation contextMatroids were introduced by Whitney [Whi35]. A basic reference for the matroid version of the Tutte polynomial is Crapo [Cra69], and the relation between weight enumerators of codes and Tutte polynomials is due to Greene [Gre76]. For a survey of how properties of linear codes can be read from the Tutte polynomial starting from this theorem, see Britz–Cameron [BC22]. For a standard textbook on matroid theory, see Oxley [Oxl11].↩
4. [BC22] Thomas Britz and Peter J. Cameron. Codes. Handbook of the Tutte polynomial and related topics, pp. 328–344, 2022. doi:10.1201/9780429161612-16 Citation contextMatroids were introduced by Whitney [Whi35]. A basic reference for the matroid version of the Tutte polynomial is Crapo [Cra69], and the relation between weight enumerators of codes and Tutte polynomials is due to Greene [Gre76]. For a survey of how properties of linear codes can be read from the Tutte polynomial starting from this theorem, see Britz–Cameron [BC22]. For a standard textbook on matroid theory, see Oxley [Oxl11].↩
5. [Oxl11] James Oxley. Matroid theory. Oxford University Press, Oxford, vol. 21, pp. xiv+684, 2011. doi:10.1093/acprof:oso/9780198566946.001.0001 Citation contextMatroids were introduced by Whitney [Whi35]. A basic reference for the matroid version of the Tutte polynomial is Crapo [Cra69], and the relation between weight enumerators of codes and Tutte polynomials is due to Greene [Gre76]. For a survey of how properties of linear codes can be read from the Tutte polynomial starting from this theorem, see Britz–Cameron [BC22]. For a standard textbook on matroid theory, see Oxley [Oxl11].↩
6. [BO92] Thomas Brylawski and James Oxley. The Tutte polynomial and its applications. Matroid applications, vol. 40, pp. 123–225, 1992. doi:10.1017/CBO9780511662041.007 Citation contextInvariants of this deletion-contraction type are often treated as Tutte–Grothendieck invariants, or simply T–G invariants. For a classical survey of the basic properties, universality, and applications of the Tutte polynomial, Brylawski–Oxley [BO92] is a standard reference.↩
7. [EM22] Joanna A. Ellis-Monaghan and Iain Moffatt. Handbook of the Tutte polynomial and related topics. Chapman & Hall/CRC, Boca Raton, FL, pp. xix+784, 2022. doi:10.1201/9780429161612 Citation contextFor the broader reach of the Tutte polynomial itself, the handbook edited by Ellis-Monaghan–Moffatt [EM22] gives a broad view of applications to graphs, matroids, statistical physics, coding theory, knot theory, and more.↩