The incidence vector $v_A\in F^n$ of a subset $A\subseteq [n]$ over a stated field

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.