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

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.