# invertible $\{0, 1\}$ matrix

For an $n\times n$ matrix $A$ with entries from $\{0,1\}$. What is the maximum number of 1's such that $A$ is invertible?

If $n=2$, the answer is $3$.

If $n=3$, the answer is $7$. Is there a formula for general $n$?

-
For $n=1$, the answer is 1. –  Graphth Mar 30 '12 at 13:41
What field are you talking about? –  Graphth Mar 30 '12 at 13:42
oeis.org/A002061 says the answer is $n^2-n+1$ and references "Halmos". (Does he have a standard text or something?) –  Jason DeVito Mar 30 '12 at 13:54
@JasonDeVito: I guess "Halmos" stands for the Halmos's book "Finite-Dimensional Vector Spaces". BTW, it's a very good book on linear algebra. –  Damian Sobota Mar 30 '12 at 14:23

Obviously the answer cannot exceed $n^2 - n + 1$ as else there will be at least two rows that contain just 1's and therefore the determinant will become 0.

This bound can be obtained, in the following manner: Let $a_{ij}$ be zero iff i=j > 1 for elements $a_{ij}$ of A.

Clearly this has only $n-1$ zeroes.

Number of permutations in this whose product is non-zero = number of derangements in $n-1$ elements, which is odd. (consider the formula for number of derangements, $n!/k!$ is even being divisible by $(n-k)!$for all terms except when $k=n$). So determinant cannot be zero as it is sum of an odd number terms whose value is $+/-1$.

Therefore this has non-zero determinant and is therefore invertible.

EDIT: Number of permutations is not directly equal to number of derangements for n-1, but by using the same logic as in deriving the formula for number of derangements, we can obtain the following formula:

$\sum_{k=1}^{n-1} (-1)^k (n-1)!(n-k)/k!$. For k till n-3, $(n-1)!/k!$ is even. For $k=n-2$, $n-k$ is even. This leaves only the last term with k=n-1, which is 1 and thus odd.

-
There is a very easy proof that $A$ is invertible: simply subtract the first row (all 1s) from all other rows, which yields an upper triangular matrix with $\pm 1$ entries on the diagonal, therefore $\det A=\pm 1$. –  Generic Human Apr 24 '12 at 23:23