Random Binary matrix

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?

• 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.
– N74
Commented May 29, 2016 at 19:36
• 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. Commented May 29, 2016 at 20:00
• 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.
– N74
Commented May 29, 2016 at 20:06
• 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. Commented May 29, 2016 at 22:48
• 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. Commented May 30, 2016 at 0:46

@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$).
• 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 Commented Jan 1, 2021 at 16:00