Largest matrix satisfying a rank constraint

Question

Consider a matrix with entries in $\{0,1\}$. The matrix is of dimension $R\times N$, where $R$ should be viewed as much larger than $N$. Each row of this matrix has exactly $N/2$ ones and the rest are zeros. Each row of the matrix is distinct. The question is, what is the largest number of $R$ such that we can still guarantee that the matrix has row rank less than $K$? We always assume $N$ is an even number, and consider $1\leq K\leq N/2$.

Answer 1

Lemma: If $1\leq S\leq n+1$ then there is a 0-1 matrix $A_{S\times 2n}$ with rank $S$ such that each row of this matrix has exactly $n$ ones.

So if $R=K+1$, where $1\leq K\leq n$, then there is a 0-1 matrix $A_{K+1\times 2n}$ with rank $K+1$ such that each row of this matrix has exactly $n$ ones. So the maximum $R$ such that we can still guarantee that the matrix has row rank less or equal to is $K$.

Proof of the Lemma: If we construct a 0-1 matrix $B_{n+1\times 2n}$ such that

1. the rank of $B$ is $n+1$
2. each row of B has exactly $n$ ones

then we can choose any $S$ rows of $B$ to form $A_{S\times 2n}$ described in the lemma above.

Now we proceed with the construction of such $B_{n+1\times 2n}$ by induction on $n$.

If $n=1$, let $B_{2\times 2}$ be the identity matrix.

Assume we have constructed $B_{k+1\times 2k}$ satisfying 1 and 2. Define $$B'_{(k+2)\times (2k+2)}=\begin{pmatrix}B_{k+1\times 2k} & C_{2\times 2}\\ D_{1\times 2k} & E_{1\times 2} \end{pmatrix},$$ where $C_{2\times 2}=\begin{pmatrix}1 & 0\\1 & 0\end{pmatrix}$, $E_{1\times 2}=\begin{pmatrix}0 & 1\end{pmatrix}$ and $D_{1\times 2k}$ is any row vector with $k$ ones and the rest are zeros.

Now, the first $k+1$ rows of $B'$ are linearly independent since $B$ has rank $k+1$.

In addition, the last row of $B'$ does not belong to the span of the first $k+1$ rows, since the last entries of the first $k+1$ rows are zero and last entry of the last row is not zero.

So $B'$ has rank $k+2$.

By construction each row of $B'$ has $k+1$ ones and the rest are zeros. $\square$