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

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

1 Answer 1

10
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ 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$. $\endgroup$ Apr 24, 2012 at 23:23
  • $\begingroup$ 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. $\endgroup$ Apr 24, 2018 at 17:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.