Rank of matrix over $GF(2)$ whose rows have exactly $k$ elements $1$

Question

Consider the $\binom{n}{k}\times n$ matrix $A$ whose rows have $k$ $1$'s and $n-k$ $0$'s. There are no repeated rows. What is the rank of $A$ over $GF(2)$?

Answer 1

You’re asking for the dimension over $\mathbb{F}_2$ of the span of the functions $\{1,\ldots,n\}\rightarrow \mathbb{F}_2$ that have a support of size exactly $k$.

If $k=1$, it’s clearly $n$. If $k=0$, it’s clearly $0$; if $k=n$, it’s $1$. Now we assume $2 \leq k < n$.

In particular, if $1 \leq a < b \leq n$ are integers, there is a subset $S$ of $\{1,\ldots,n\}$ containing neither $a$ nor $b$ with size $k-1$. Consider the difference of the functions with support $S \cup \{a\}$ and $S \cup \{b\}$: it’s a function with support $\{a,b\}$ exactly.

So if $S_{n,k}$ is the space generated by these functions, then $S_{n,k} \supset S_{n,2}$. But it’s easy to see that $S_{n,2}$ is the space of functions whose values sum to $0$ (a hyperplane). So $S_{n,k}$ has rank $n$, unless all of its generators are in $S_{n,2}$ (which is equivalent to $k$ being even) and then $S_{n,k}=S_{n,2}$ has rank $n-1$.

Finally: if $k=n$, $A$ has rank $1$, if $k=0$, $A$ has rank $0$, if $1 \leq k < n$, $A$ has rank $n-1$ when $k$ is even and $n$ when $k$ is odd.