Square submatrix of a binary matrix with all columns having the same sum

Question

Let $M$ be a $m \times n$ matrix with binary entries (i.e. a matrix all whose entries belong to the set $\{0,1\}$), with $m\geq n$. Suppose each row of $M$ contains exactly $k$ ones. Given $n$ distinct rows $R=(r_1,\ldots, r_n)$ of $M$, let $M[R]$ denote the $n\times n$ matrix consisting in the $n$ rows $r_1,\ldots, r_n$. Say $M[R]$ is suitable if there exists a constant $c$ such that, for each column of $M[R]$, the sum of the entries in the column is $c$.

Given $n$, how large does $m$ need to be so that, for any binary $m\times n$ matrix $M$ with pairwise distinct rows, there exist $n$ distinct rows $R=(r_1,\ldots, r_n)$ of $M$ such that $M[R]$ is suitable?

Answer 1

Having $m$ large enough does not guarantee this.

Fix $n,k\in\mathbb N$: for your hypothesis to be possible, we need $k\leq n$. Obviously, the matrix has all ones if $k=n$, so focus on the nontrivial case of $k<n$. Because you're talking about taking $n$ rows from $M$, I also take it you mean $m\geq n$.

But now, for any $m\geq n>k$, we can construct an $m\times n$ binary-valued matrix $M$ with each row summing to $k$ such that $M[R]$ is not suitable for any list $R$ of $n$ rows. For instance, suppose $M_{ij}=\mathbf1_{j\leq k}$, which. Every row is identical, so that $M[R]$ is the same matrix for any list of $n$ rows. But the first $k$ columns of $M[R]$ each sum to $n$, and the other columns sum to $0$. Thus $M[R]$ is not suitable.