5
$\begingroup$

This is a question from Strang's "Linear Algebra and its Applications", right in the first chapter (I'm studying it by myself). I couldn't solve it, it isn't in the Solutions Manual, and my research suggests that there shouldn't be a simple solution for it. However, its presence in the very first chapter suggests me that I'm missing something. Here it goes:

1.6:

a) There are sixteen 2x2 matrices whose entries are 1's and 0's. How many are invertible?

b) (Much harder!) If you put 1's and 0's at random into the entries of a 10 by 10 matrix, is it more likely to be invertible or singular?

From what I can tell, this can't be solved by elementary linear algebra so... it shouldn't be there? I'm guessing there is a clever computational way to exhaust all cases?

$\endgroup$
5
  • $\begingroup$ For the a question you have 3 possibile configurations for the first row and for each you can choose only 2 configurations for the second row. For the b point I think you can generalize the process: you have $2^{100}$ matrices, for the first row $2^{10}-1$ configurations could lead to an invertible matrix... and so on. $\endgroup$
    – N74
    Commented May 29, 2016 at 19:36
  • $\begingroup$ the problem is, sometimes you can combine vectors to generate new binary vectors, reducing the odds it's invertible. Consider the identity matrix: at every step, you're doubling the amount of vectors that can't be picked. $\endgroup$
    – FrancoVS
    Commented May 29, 2016 at 20:00
  • $\begingroup$ At every step you can and must add a single vector independent by all the ones selected before. And what happens for the identity matrix just happens for every other matrix. $\endgroup$
    – N74
    Commented May 29, 2016 at 20:06
  • 1
    $\begingroup$ Your linked solution might not really address your question. When invertibility is concerned, the underlying field does not matter if the matrices are $2\times2$, but important othwise. E.g. the matrix $A$ below is nonsingular over $\mathbb R$ ($\det A=-2$) but singular over $GF(2)$:$$A=\pmatrix{1&1&1&1\\ 1&1&0&0\\ 1&0&1&0\\ 1&0&0&1}.$$ I haven't Strang at hand, but my impression is that it's more numerically oriented. If this is the case, I think the matrix is real, not boolean. $\endgroup$
    – user1551
    Commented May 29, 2016 at 22:48
  • $\begingroup$ Yes, the matrix is real. One of the comments in the link I provided has a link to a paper dealing with a related case (entries are -1 and 1), and it seems they only managed to prove a very weak upper bound (something like 0.999^n) for the probability of the matrix being singular. $\endgroup$
    – FrancoVS
    Commented May 30, 2016 at 0:46

1 Answer 1

Reset to default
3
$\begingroup$

@FrancoVS @N74 This is not a proof, rather an indication that the larger the matrix, the more the odds that it IS invertible. The broken line below displays the results of a (Matlab) simulation: for each $n = 1,2 \cdots 20$, we have generated $20,000$ $n \times n$ matrices (with entries following a Bernoulli Ber(1/2) distribution), and their determinant has been computed. This graphic displays the fact that, for $n>15$, the frequency of non-zero determinants rapidly tends to 1... (after a small decline for small values of $n$).

enter image description here

$\endgroup$
1
  • $\begingroup$ In fact, there is a recent result giving aymptoticaly P($n \times n$ binary matrix non inversible) $\approx 1/2^n$: arxiv.org/pdf/1812.09016.pdf $\endgroup$
    – Jean Marie
    Commented Jan 1, 2021 at 16:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .