Maximum number of ones in a full rank matrix with a restriction

Question

Consider $n \times n$ binary matrices. I am interested in the largest number of ones possible in an $n \times n$ binary matrix with full rank over the field of integers mod 2 with the following restriction.

• No two rows have two or more bits set to 1 in common positions.

The following is an example of such a matrix.

[[1 0 0 1 1 0 1]
 [0 1 0 0 1 0 0]
 [0 0 1 0 1 0 0]
 [0 0 0 0 1 1 0]
 [1 1 1 0 0 0 0]
 [0 0 0 0 0 0 1]
 [0 0 1 1 0 1 0]]

The optimal values for $n = 2, 3, 4, 5$ are $3, 5, 9, 11$. The optimal value for $n=6$ is at least $15$.

Previously asked at math.stackexchange.com.

Answer 1

Fedor Petrov is right.

The additional restriction tells that the number of pairs of ones in one row is at most $n\choose 2$. This yields, in a usual manner, that the number of ones cannot exceed $n\sqrt n(1+o(1))$.

This estimate is asymptotically sharp. Take $n=q^2+q$ (where $q$ is an odd prime power) and consider a matrix of order $n+1$ which is the adjacency matrix of the (points and lines in the) projective plane over $\mathbb F_q$. It has $q+1$ ones in each row, so around $q^3$ ones in total.

This matrix is degenerate, as the sum in each row is zero. If we sum up all rows with $0$ at a fixed position, the sum will get ones at all other positions. From those vectors, you can get all vectors with zero sum, so the rank is $n$. So this matrix has a non-degenerate submatrix of order $n$ having $\Theta(n^{3/2})$ ones. Moreover, we can proceed on with eliminations; on each elimination, we lose only $O(\sqrt n)$ ones, so we may do $o(n)$ such.