Largest matrix satisfying a rank constraint 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$.
 A: 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

*

*the rank of $B$ is $n+1$

*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$
