# Square submatrix

We have $2n\times 2n$ binary matrix with $k$ of its elements are $1$. We are searching for an $n\times n$ submatrix full of $1$s.

What is the least $k$ such that we can always find one?

What is the least $k$ for $n=10$?

Definition of submatrix: http://en.wikipedia.org/wiki/Submatrix

-

We can represent this matrix as a bipartite graph, with rows as left vertices and columns as right vertices. This problem is then a special case of extremal problems with forbidden graphs, in particular, special case of Zarankiewicz problem. The answer to this special case was shown here as $4n^2 -3n$.

-
Suppose $n=2$, your answer says that it is necessary to set $16-6 = 10$ elements to $1$ to find a $2\times 2$ submatrix. But my trials on $4\times 4$ matrix claims $k=9$ is necessary to find a submatrix. My conjecture for the least $k$ is $4n^2 - 4n + 1$. I haven't proved it yet. – user27805 Mar 11 '13 at 18:41
$$\pmatrix{1&1&1&0\cr1&0&0&1\cr0&1&0&1\cr0&0&1&1\cr}$$ has $n=2$, $k=9$, and no $2\times2$ submatrix of ones. – Gerry Myerson Mar 11 '13 at 22:58
Here is a cheap lower bound. Let the first column, first row, and diagonal of a 2n by 2n matrix have zeros. Any nxn submatrix must intersect one of these lines, quickly giving $4n^2 - 6n + 2 \lt k$. This likely can be tweaked to close to $(2n-1)^2 \leq k$.
In fact, the diagonal, plus n elements in a row and n corresponding elements in a corresponding column also seems to work. Maybe further tweaking will easily take the number of zeros needed from $4n$ down to $3n$? Gerhard "Ask Me About System Design" Paseman, 2013.03.11 – Gerhard Paseman Mar 11 '13 at 19:13
$a_{1(n-1)} = a_{1n} = 0$ $a_{2n} = a_{21} = 0$ $\dots$ $a_{n(n-2)} = a_{n(n-1)} = 0$ So there are $4n^2 - 4n$ $1$s; $4n$ $0$s. Let $x_1,\dots, x_n$ be the row #s of square submatrix. Let $y_1,\dots, y_n$ be the column #s of square submatrix. If we have $x_1, y_1$, then we should remove $2$ of columns that doesn't contain $x_1$. For $x_2, y_1$, then we should remove at least $1$ more columns, \dots After $x_10, y_1$, we should remove at least $11$ columns at total. So for that distribution of $1$s, one can never find a $10\times10$ submatrix. So I think $k>4n^2-4n$. – user27805 Mar 11 '13 at 20:37