In this post the matroid theory connections are everywhere, but I won’t use any matroid language. Can you spot them all?
I’m going to discuss my favorite lecture from the course MAT377 – Introduction to Combinatorics, which I have taught at Princeton in the past three years (lecture notes can be found here). This particular lecture was not part of the first run of the course, but inspired by it. After introducing the MacWilliams relations in coding theory (see below), I was asked by my students what they can be used for. The coding theory books that I consulted were not much help, although they claimed them to be deep, important, etc. But an email to Peter Cameron, and then an answer from Chris Godsil on Mathoverflow, led me to the paper [AM78], in which Assmus and Maher prove the following (and slightly more, but I try to keep this post as short as possible).
Theorem 1. There is no projective plane of order $q$, where $q \equiv 6 \pmod 8$.
Preliminaries
We need some design theory, coding theory, and linear algebra in our proof. Recall that a $t-(v,k,\lambda)$ design is a collection of subsets of a set of $v$ points (subsets can be repeated more than once), where each subset (or block) has size $k$, and every subset of $t$ points is contained in exactly $\lambda$ blocks. So in this terminology, a projective plane of order $q$, where the blocks are taken to be the lines, would be a $2-(q^2+q+1,q+1,1)$ design. Other parameters of the design include the number of blocks $b$, and the replication number $r$, the number of blocks containing a single point. One can show that $b$ and $r$ are determined by the parameters of the design, and that $r$ does not depend on the point chosen. The block-point incidence matrix of a design is the matrix $A$ with rows indexed by blocks, columns by points, and
$$
A_{ij} = \begin{cases} 1 & \text{ if point } j \text{ is in block } i\\
0 & \text{ otherwise.}\end{cases}
$$
Exercise 1. Let $A$ be the block-point incidence matrix of a design. Show that for a $2-(v,k,\lambda)$ design with $v=b$, we have the following:
- $k=r$
- $k(k-1) = \lambda(v-1)$
- $AA^T = A^TA$
- $|\det(A)| = k(k-\lambda)^{(v-1)/2}$
- Every two blocks meet in exactly $\lambda$ points
Misleadingly, such designs are called symmetric. Note that $A$ need not be a symmetric matrix at all!
A $q$-ary linear $[n,k,d]$ code $C$ is a linear subspace of $\mathrm{GF}(q)^n$ of dimension $k$. Think of it as the row space of a matrix. The elements of $C$ are called codewords, and the weight of a codeword $c \in C$ is $\mathrm{wt}(c) = |\{i : c_i\neq 0\}|$. The parameter $d$ of the code is the minimum weight of the nonzero codewords in $C$. Since weights are related to the Hamming distance between codewords (and thus to the error-correcting capabilities of the code), it makes sense to study the weight enumerator:
$$
W_C(x,y) := \sum_{c\in C} x^{\mathrm{wt}(c)}y^{n – \mathrm{wt}(c)}.
$$
The dual code is $C^\perp$, the orthogonal complement of the vector space $C$. We can derive the following relation between the weight enumerators of $C$ and $C^\perp$:
Theorem 2 (MacWilliams Relations).
$$
W_{C^\perp}(x,y) = q^{-k} W_C(y-x, y+ (q-1)x).
$$
From linear algebra we require the Smith Normal Form, of which we will only use the following restricted version:
Theorem 3. Let $A$ be an $n\times n$ nonsingular matrix over $\mathbb{Z}$. There exist integer matrices $M, N$ with $\det(M) = \det(N) = 1$, and $MAN = D$, where $D$ is a diagonal matrix with diagonal entries $d_1, \ldots, d_n$ such that $d_{i} | d_{i+1}$ for $i = 1, \ldots, n-1$.
The proof.
We start with two lemmas.
Lemma 1. Let $A$ be the incidence matrix of a symmetric $2-(v,k,\lambda)$ design. Let $A_+$ be obtained from $A$ by adding an all-ones column, and let $C$ be the binary linear code generated by the rows of $A_+$. If $k$ is odd, $k-\lambda$ is even, but $k-\lambda$ is not a multiple of $4$, then $C$ is a $[v+1, (v+1)/2, d]$ code for some $d$, and $C^\perp = C$.
Proof. Interpret $A$ as an integer matrix. Let $M, N$ be as in Theorem 3. Then $d_1d_2 \cdots d_n = \det(MAN) = \det(A) = \pm k(k-\lambda)^{(v-1)/2}$. Since $k$ is odd, and each factor $(k-\lambda)$ contributes one factor $2$, no more than $(v-1)/2$ of the $d_i$ are are divisible by $2$. Hence, writing $r_\mathbb{F}$ for matrix rank over the field $\mathbb{F}$, we have
$$
r_{\mathrm{GF}(2)}(A_+) \geq r_{\mathrm{GF}(2)}(A) = r_{\mathrm{GF}(2)}(MAN) \geq (v+1)/2.
$$
Conversely, let $a$ and $b$ be rows of $A_+$. The inner product of $a$ with itself is $\langle a, a\rangle = k + 1 \equiv 0 \pmod 2$. Also, $\langle a,b\rangle = \lambda + 1 \equiv 0 \pmod 2$. It follows by linearity that each codeword in $C$ is orthogonal to every codeword in $C$, i.e. $C \subseteq C^\perp$. Since $\dim(C) + \dim(C^\perp) = v+1$, it follows that $r_{\mathrm{GF}(2)}(A_+) \leq (v+1)/2$, so equality must hold. $\square$
A code is doubly even if all weights are multiples of four.
Lemma 2. If $C$ is a binary, linear $[v+1,(v+1)/2, d]$, self-dual, doubly even code, then $8|(v+1)$.
Proof. For a binary linear $[n,k,d]$ code, the MacWilliams relations specialize to
$$
W_{C^\perp}(x,y) = 2^{-k}W_C(y-x,y+x) = 2^{n/2 – k} W_C( (x,y)\sigma),
$$
where $\sigma$ is the linear transformation
$$
\sigma = \frac{1}{\sqrt{2}}\begin{bmatrix} -1 & 1\\ 1 & 1\end{bmatrix}.
$$
If $C$ is self-dual, then $W_C$ is invariant under $\sigma$. If $C$ is doubly even, then $W_C$ is also invariant under
$$
\pi = \begin{bmatrix} i & 0 \\ 0 & 1 \end{bmatrix},
$$
where $i \in \mathbb{C}, i^2 = -1$. Now $W_C$ is invariant under the group generated by $\sigma$ and $\pi$, and in particular under
$$(\pi\sigma)^3 = \frac{1+i}{\sqrt{2}}\begin{bmatrix} 1 & 0\\ 0 & 1 \end{bmatrix}.$$
Since this transformation multiplies each of $x$ and $y$ by a primitive eighth root of unity, the result follows.$\square$
Proof of Theorem 1. Suppose a binary projective plane of order $q \equiv 6 \pmod 8$ exists. Consider the corresponding $2-(q^2+q+1,q+1,1)$ design, its incidence matrix $A$, and the binary, linear code $C$ generated by $A_+$ as above. By Lemma 1, $C$ is self-dual. Each row of $A_+$ has $q+2$ nonzero entries, and therefore weight $0 \pmod 4$. Since $C$ is self-dual, any two codewords intersect in an even number of positions, and it follows that all codewords have weight $0 \pmod 4$. By Lemma 2, then, $v+1 = q^2 + q + 2$ is divisible by $8$, which contradicts the assumption that $q \equiv 6 \pmod 8$. $\square$
Note that the MacWilliams relations also played a big role in determining the nonexistence of a projective plane of order 10.
Problem. Are techniques like the ones used above applicable elsewhere in matroid theory?
[AM78] Assmus, E. F., Jr.; Maher, David P. Nonexistence proofs for projective designs. Amer. Math. Monthly 85 (1978), no. 2, 110–112
