11
$\begingroup$

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$?

  • 0
    @JasonDeVito: I guess "Halmos" stands for the Halmos's book "Finite-Dimensional Vector Spaces". BTW, it's a very good book on linear algebra.2012-03-30

1 Answers 1

10

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.

  • 0
    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.2018-04-24