In this post the matroid theory connections are everywhere, but I won’t use any matroid language. Can you spot them all?<\/p>\n
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<\/a>). 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<\/a>, and then an answer from Chris Godsil on Mathoverflow<\/a>, 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).<\/p>\n Theorem 1.\u00a0<\/strong>There is no projective plane of order $q$, where $q \\equiv 6 \\pmod 8$.<\/em><\/p>\n We need some design theory, coding theory, and linear algebra in our proof. Recall that a $t-(v,k,\\lambda)$\u00a0design<\/em> is a collection of subsets of a set of $v$\u00a0points\u00a0<\/em>(subsets can be repeated more than once), where each subset (or\u00a0block<\/em>) 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\u00a0number of blocks\u00a0<\/em>$b$, and the\u00a0replication number\u00a0<\/em>$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\u00a0block-point incidence matrix<\/em> of a design is the matrix $A$ with rows indexed by blocks, columns by points, and Exercise 1.\u00a0<\/strong>Let $A$\u00a0be the block-point incidence matrix of a design. Show that for a $2-(v,k,\\lambda)$\u00a0design with $v=b$, we have the following:<\/p>\n Misleadingly, such designs are called\u00a0symmetric<\/em>. Note that $A$ need not be a symmetric matrix at all!<\/p>\n A $q$-ary linear $[n,k,d]$ code<\/em>\u00a0$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\u00a0codewords<\/em>, and the\u00a0weight<\/em> 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\u00a0weight enumerator: The\u00a0dual code<\/em> 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$:<\/p>\n Theorem 2 (MacWilliams Relations). From linear algebra we require the\u00a0Smith Normal Form<\/em>,\u00a0<\/em>of which we will only use the following restricted version:<\/p>\n Theorem 3.\u00a0<\/strong>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$.<\/em><\/p>\n We start with two lemmas.<\/p>\n Lemma 1.\u00a0<\/strong>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$.<\/em><\/p>\n Proof. <\/em>Interpret $A$ as an integer matrix.\u00a0<\/em>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 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$<\/p>\n A code is\u00a0doubly even<\/em> if all weights are multiples of four.<\/p>\n Lemma 2.\u00a0<\/strong>If $C$ is a binary, linear $[v+1,(v+1)\/2, d]$, self-dual, doubly even code, then $8|(v+1)$.<\/em><\/p>\n Proof.\u00a0<\/em>For a binary linear $[n,k,d]$ code, the MacWilliams relations specialize to Proof of Theorem 1.\u00a0<\/em>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$<\/p>\n Note that the MacWilliams relations also played a big role in determining the nonexistence of a projective plane of order 10.<\/p>\n Problem.\u00a0<\/strong>Are techniques like the ones used above applicable elsewhere in matroid theory?<\/p>\n [AM78] Assmus, E. F., Jr.; Maher, David P. Nonexistence proofs for projective designs<\/em>. Amer. Math. Monthly 85 (1978), no. 2, 110\u2013112<\/p>\n","protected":false},"excerpt":{"rendered":" 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 … Continue reading Preliminaries<\/h1>\n
\n$$
\nA_{ij} = \\begin{cases} 1 & \\text{ if point } j \\text{ is in block } i\\\\
\n0 & \\text{ otherwise.}\\end{cases}
\n$$<\/p>\n\n
\n<\/em>$$
\nW_C(x,y) := \\sum_{c\\in C} x^{\\mathrm{wt}(c)}y^{n – \\mathrm{wt}(c)}.
\n$$<\/p>\n
\n<\/strong>$$
\nW_{C^\\perp}(x,y) = q^{-k} W_C(y-x, y+ (q-1)x).
\n$$<\/p>\nThe proof.<\/h1>\n
\n$$
\nr_{\\mathrm{GF}(2)}(A_+) \\geq r_{\\mathrm{GF}(2)}(A) = r_{\\mathrm{GF}(2)}(MAN) \\geq (v+1)\/2.
\n$$<\/p>\n
\n$$
\nW_{C^\\perp}(x,y) = 2^{-k}W_C(y-x,y+x) = 2^{n\/2 – k} W_C( (x,y)\\sigma),
\n$$
\nwhere $\\sigma$ is the linear transformation
\n$$
\n\\sigma = \\frac{1}{\\sqrt{2}}\\begin{bmatrix} -1 & 1\\\\ 1 & 1\\end{bmatrix}.
\n$$
\nIf $C$ is self-dual, then $W_C$ is invariant under $\\sigma$. If $C$ is doubly even, then $W_C$ is also invariant under
\n$$
\n\\pi = \\begin{bmatrix} i & 0 \\\\ 0 & 1 \\end{bmatrix},
\n$$
\nwhere $i \\in \\mathbb{C}, i^2 = -1$. Now $W_C$ is invariant under the group generated by $\\sigma$ and $\\pi$, and in particular under
\n$$(\\pi\\sigma)^3 = \\frac{1+i}{\\sqrt{2}}\\begin{bmatrix} 1 & 0\\\\ 0 & 1 \\end{bmatrix}.$$
\nSince this transformation multiplies each of $x$ and $y$ by a primitive eighth root of unity, the result follows.$\\square$<\/p>\n