Binary linear code ($C\le {\mathbb{F}}_2^n$)

A linear code over the two-element finite field. Its dimension $r$ gives $2^r$ codewords. Its weight enumerator in the convention $W_C(s,t)={\sum }_{c\in C}{s}^{w(c)}{t}^{n-w(c)}$ is symmetric in $s,t$ exactly when the all-ones word belongs to $C$: adding that word complements every bit and replaces weight $w$ by $n-w$. Conversely symmetry makes the coefficient of $s^n$ equal the coefficient of $t^n$, which is one.

A length-$n$, dimension-$k$ binary linear code has full support when no coordinate vanishes on every codeword, equivalently when the union of the supports of a vector of all codewords covers every coordinate. Every coordinate is then a nonzero linear functional on the message vector space ${\mathbb{F}}_2^k$. Translation by a vector on which it is one pairs the zero and one fibers, so exactly $2^{k-1}$ codewords contribute one in that coordinate. Summing these contributions proves the formula. If there are $r$ nonzero columns in a full-rank generator matrix, the same argument gives $r{2}^{k-1}$ instead.

For a binary linear code $C$, the linear functional $\sigma (x)={\sum }_j{x}_j$ records Hamming weight modulo two. Its kernel of a linear map is the even-weight subcode. If $\sigma {|}_C$ vanishes, this is all of $C$; otherwise rank-nullity theorem gives dimension $\dim C-1$. This also proves closure under addition without treating ordinary integer weight as a linear function.

A binary linear code is doubly even when the Hamming weight of every codeword is divisible by four.

// Target: algebra.bigb

Suppose the generators of a binary linear code have Hamming weights divisible by four and have pairwise zero binary inner products. Their linear span is doubly even: for any two vectors,The binary inner product says the intersection size is even. Induction on the number of generators in a sum proves divisibility by four.

// Target: algebra.bigb

A linear subspace $W\subseteq {\mathbb{F}}_2^n$ is self-orthogonal if $u\cdot v=0$ for every $u,v\in W$. The standard bilinear form is nondegenerate, whence $\dim W+\dim W^{\perp }=n$ and $\dim W\le \lfloor n/2\rfloor$. The condition with $u=v$ means every vector has even Hamming weight. Such a binary linear code gives the linear algebra behind the Eventown theorem.

If a self-orthogonal binary subspace has odd length $n$ and dimension $(n-1)/2$, its dual code is obtained by adjoining the all-ones word. Self-orthogonality makes every codeword even-weight, so $1\in C^{\perp }$ but $1\notin C$. Comparing dimensions proves the formula. The dimension hypothesis alone is insufficient: $C=⟨100⟩$ at length three is a counterexample.

The code consisting of all even-weight binary words. For $n\ge 1$ its dimension is $n-1$, and its weight enumerator is $[(t+s{)}^n+(t-s{)}^n]/2$, by selecting the even terms of the binomial theorem. The length-one code contains only zero.