Linear Algebra Methods in Combinatorics

Fix a field $F$, a natural number $n$, and the standard basis $e_0,\dots ,e_{n-1}$ of $F^n$ (The standard list $e:n\to F^n$ with $e_i(i)=1_F$ and $e_i(j)=0_F$ for $j\mathrm{\ne }i$ is an ordered basis of $F^n$; hence ${\dim }_F{F}^n=n$, and $F^0$ is the zero space with basis $\mathrm{\varnothing }$ and dimension $0$).

For a subset $A\subseteq [n]=\{0,\dots ,n-1\}$, its incidence vector over $F$ is

$v_A\in F^n,(v_A{)}_i=\{\begin{array}{ll}{1}_F,& i\in A,\\ 0_F,& i\mathrm{\notin }A\mathrm{.}\end{array}$

Thus

$v_A={\sum }_{i\in A}{e}_i\mathrm{.}$

The field is part of the datum and is written whenever two fields are being used at once. The same subset may therefore produce different vectors on this page: the coordinates are the same zero-one pattern, but the arithmetic happens in the chosen field.

The assignment $A\mapsto v_A$ is injective: if $A\mathrm{\ne }B$, then some coordinate $i$ lies in exactly one of them, so $(v_A{)}_i\mathrm{\ne }(v_B{)}_i$. In particular $v_{\mathrm{\varnothing }}=0$ and $v_A\mathrm{\ne }0$ whenever $A\mathrm{\ne }\mathrm{\varnothing }$.

• Everything below turns set-system questions into vector-space questions through this definition. Distinctness of sets becomes distinctness of vectors, parity questions become equalities in ${\mathbb{F}}_2$, and intersection sizes become bilinear-form values.

Fix a field $F$ and a natural number $n$. The standard bilinear form on $F^n$ is

$⟨x,y⟩:={\sum }_{i<n}{x}_i{y}_i\mathrm{.}$

The symbol denotes the finite sum in the additive commutative group of the field $F$: it is $0_F$ at $n=0$ and is obtained by successively adding the terms $x_i{y}_i$ for $i<n$.

This is a symmetric bilinear form in the sense of Bilinear forms, and symmetric, skew-symmetric, and alternating bilinear forms, and its matrix in the standard basis of $F^n$ is the identity matrix. Hence it is nondegenerate in the sense of The matrix, left and right radicals, rank, and nondegeneracy of a bilinear form on a finite-dimensional space.

When $F={\mathbb{F}}_2$, the squaring law $t^2=t$ gives

$⟨x,x⟩={\sum }_{i<n}{x}_i\mathrm{.}$

So over ${\mathbb{F}}_2$ the form detects parity and not positivity. It is not an inner product there, and the page never treats it as one.

• The formula is the same over every field, but the consequences are not. The Oddtown and Eventown arguments use only bilinearity over ${\mathbb{F}}_2$; the Fisher argument later uses the order and positivity of $\mathbb{R}$ as well.

Let $F$ be a field, let $A,B\subseteq [n]$, and let $v_A,v_B\in F^n$ be their incidence vectors. Then

$⟨v_A,v_B⟩=\mid A\cap B\mid \cdot 1_F\mathrm{.}$

In particular:

1. over $\mathbb{R}$ one has $⟨v_A,v_B⟩=\mid A\cap B\mid$;
2. over ${\mathbb{F}}_2$ one has $⟨v_A,v_B⟩=1$ exactly when $\mid A\cap B\mid$ is odd, and it is $0$ exactly when $\mid A\cap B\mid$ is even;
3. taking $B=A$ gives $⟨v_A,v_A⟩=\mid A\mid \cdot 1_F$.

• This is the page's basic dictionary item. Every parity or intersection-size hypothesis below is rewritten through this lemma before any linear algebra is applied.

Fix a field $F$ and a natural number $n$.

A set family on $[n]$ is a finite list

$\mathcal{F}=(A_i{)}_{i<m}$

of pairwise distinct subsets of $[n]$. Its incidence matrix over $F$ is the matrix

$N(\mathcal{F})\in F^{m\times n}$

whose row indexed by $i<m$ is the incidence vector $v_{A_i}$ of $A_i$.

If $N=N(\mathcal{F})$, define its Gram matrix to be the $m\times m$ matrix $\mathrm{\Gamma }(\mathcal{F})$ whose $(i,j)$ entry is

${\sum }_{k<n}{N}_{ik}{N}_{jk}=⟨v_{A_i},v_{A_j}⟩,$

so the Gram matrix records all pairings of the incidence vectors at once.

• Distinctness of the sets is part of the definition because all the bounds on this page count sets, not repeated rows of a matrix.

Let $F$ be a field and let $\mathcal{F}=(A_1,\dots ,A_m)$ be a family of subsets of $[n]$. If the incidence vectors $v_{A_1},\dots ,v_{A_m}$ are linearly independent in $F^n$, then $m\le n$.

• This is the master lemma for the direct incidence-vector bounds, including Oddtown and Fisher's inequality. Other bounds on the page use subspace counts, shifting, or polynomial-function spaces instead.

Let $F$ be a field, let $V$ be an $F$-vector space, and let $⟨\cdot ,\cdot ⟩:V\times V\to F$ be a bilinear form. Suppose vectors $v_1,\dots ,v_m,w_1,\dots ,w_m\in V$ satisfy

$⟨v_i,w_i⟩\mathrm{\ne }0\text{and}⟨v_i,w_j⟩=0\text{ for }i\mathrm{\ne }j\mathrm{.}$

Then $v_1,\dots ,v_m$ are linearly independent.

• The argument uses only bilinearity and the diagonal pattern. No positivity and no nondegeneracy is involved, which is why the criterion works over ${\mathbb{F}}_2$ as well as over $\mathbb{R}$.

Let $F$ be a field, let $V$ be an $F$-vector space, and let $⟨\cdot ,\cdot ⟩:V\times V\to F$ be a bilinear form. Suppose vectors $v_1,\dots ,v_m,w_1,\dots ,w_m\in V$ satisfy

$⟨v_i,w_i⟩\mathrm{\ne }0\text{and}⟨v_i,w_j⟩=0\text{ whenever }j<i\mathrm{.}$

Then $v_1,\dots ,v_m$ are linearly independent.

• The direction of the triangular hypothesis matters. The proof chooses the least nonzero coefficient, so it kills the terms below the diagonal by minimality and the terms above it by hypothesis.

Let $F$ be a field, let $V$ be an $F$-vector space, and let $⟨\cdot ,\cdot ⟩:V\times V\to F$ be a bilinear form. If the matrix

$M=(⟨v_i,w_j⟩{)}_{1\le i,j\le m}$

is invertible, then both lists $v_1,\dots ,v_m$ and $w_1,\dots ,w_m$ are linearly independent.

• This is the matrix version of the diagonal and triangular criteria: there the matrix is visibly diagonal or triangular, while here only invertibility is assumed.

Let $A_1,\dots ,A_m$ be distinct subsets of $[n]$. If every $\mid A_i\mid$ is odd and every intersection $\mid A_i\cap A_j\mid$ with $i\mathrm{\ne }j$ is even, then $m\le n$.

• The argument uses the standard bilinear form on ${\mathbb{F}}_2^n$, not an inner product. Bilinearity and the diagonal pattern are enough.

For every natural number $n$, the singleton family

$(\{0\},\{1\},\dots ,\{n-1\})$

is an Oddtown family on $[n]$. Hence the bound $m\le n$ of Oddtown: distinct $A_1,\dots ,A_m\subseteq [n]$ with every $\mid A_i\mid$ odd and every $\mid A_i\cap A_j\mid$ ($i\mathrm{\ne }j$) even satisfy $m\le n$ is sharp.

• This is the standard extremal example, and the companion page uses it to refute the false improvement $m\le n-1$.

Let $F$ be a finite field with $q$ elements, and let $V$ be a $d$-dimensional $F$-vector space. Then

$\mid V\mid =q^d\mathrm{.}$

• The boundary case $d=0$ is included: the zero-dimensional vector space has one element and $q^0=1$.

Let $F$ be a field, let $U\le F^n$ be a subspace, and define

$U^{\perp }:=\{x\in F^n:⟨x,u⟩=0\text{ for every }u\in U\}\mathrm{.}$

Then

${\dim }_F{U}^{\perp }=n-{\dim }_{F}U\mathrm{.}$

• The cases $U=0$ and $U=F^n$ are included automatically: then $U^{\perp }=F^n$ and $U^{\perp }=0$ respectively.

Let $A_1,\dots ,A_m$ be distinct subsets of $[n]$. If every $\mid A_i\mid$ is even and every intersection $\mid A_i\cap A_j\mid$ with $i\mathrm{\ne }j$ is even, then

$m\le 2^{\lfloor n\mathrm{/}2\rfloor }\mathrm{.}$

• The floor enters only because $d$ is an integer and $2d\le n$. The proof is otherwise the same in both parities of $n$.

Let $\mathcal{F}$ be an Eventown family on $[n]$ that is maximal under inclusion among Eventown families on $[n]$. Then

$\mid \mathcal{F}\mid =2^{\lfloor n\mathrm{/}2\rfloor }\mathrm{.}$

• Maximality is used only once, in step 3.1, to turn the orthogonality conditions back into actual set membership.

Let $v_1,\dots ,v_m\in {\mathbb{R}}^n$ and let $t\ge 0$. Suppose

$⟨v_i,v_j⟩=t(i\mathrm{\ne }j),⟨v_i,v_i⟩>t(1\le i\le m)\mathrm{.}$

Then $v_1,\dots ,v_m$ are linearly independent.

• This is the one place in the page where the order and positivity of $\mathbb{R}$ are load-bearing. That is exactly what fails over ${\mathbb{F}}_2$.

Let $A_1,\dots ,A_m$ be distinct nonempty subsets of $[n]$. If there is a natural number $t$ such that

$\mid A_i\cap A_j\mid =t\text{for every }i\mathrm{\ne }j,$

then $m\le n$.