The inclusion matrix $W_{t,k}(n)$ of $t$-sets against $k$-sets

Let $0\le t\le k\le n$. The inclusion matrix

$W_{t,k}(n)$

is the matrix over $\mathbb{Q}$ whose rows are indexed by the $t$-element subsets of $[n]$, whose columns are indexed by the $k$-element subsets of $[n]$, and whose $(S,K)$ entry is

$W_{t,k}(n{)}_{S,K}=\{\begin{array}{ll}1,& S\subseteq K,\\ 0,& S\subseteq ̸K\mathrm{.}\end{array}$

The rank of this matrix does not depend on the ordering of the index sets, since changing the order only permutes rows or columns.

Two boundary cases are immediate:

$W_{t,t}(n)=I,W_{0,k}(n)=\text{the all-ones row}\mathrm{.}$

The matrices compose by counting intermediate subsets:

$W_{s,t}(n)W_{t,k}(n)=\left(\genfrac{}{}{0px}{}{k-s}{t-s}\right)W_{s,k}(n)(s\le t\le k\le n)\mathrm{.}$

Indeed, the $(S,K)$ entry of the product counts the $t$-subsets $T$ with $S\subseteq T\subseteq K$, and there are exactly $\left(\genfrac{}{}{0px}{}{k-s}{t-s}\right)$ of them when $S\subseteq K$, and none otherwise.

• The point case $t=1$ is the only rank statement this page proves. The next remark records what is left open here for general $t$.