# 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. Mar 30, 2012 at 13:41
• What field are you talking about? Mar 30, 2012 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?) Mar 30, 2012 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. Mar 30, 2012 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$. Apr 24, 2012 at 23:23
• If I understand this answer right and your matrix $A$ consists of $1's$ everywhere except for the superdiagonal then $A$ can be easily seen to be invertible by noting that if $v= (1, 1, \ldots, 1)$ and $e_i$ are the standard basis vectors then the rows of $A$ are $v, v-e_1, \ldots v-e_n$ and this set is linearly independent since $v, e_1, \ldots, e_n$ is linearly independent. Apr 24, 2018 at 17:14