Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
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
2  
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
add comment

1 Answer 1

up vote 9 down vote accepted

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.

share|improve this answer
1  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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