Question

After answering some questions, time for me to ask one; this is exercise 1.6(b) in the 3rd edition of Gilbert Strang's Linear Algebra and Its Applications. (I don't know if it's in the 4th edition or if it's in Strang's "Introduction to Linear Algebra".)

Assume you have a 10 by 10 matrix for which each entry is randomly chosen to be either 0 or 1. Is such a matrix more likely to be invertible (i.e., nonsingular) or singular?

Answer 1

To add a little more to the question: Since a 10 by 10 matrix has 100 entries, and each entry can be either 0 or 1, there are 2^100 possible matrices. Such a matrix will be singular if and only if one of its columns (or rows) is a linear combination of the other columns (or rows). My guess is that this is going to be unlikely, and thus that such a matrix chosen at random is more likely to be nonsingular. However this is just a hunch; I have no clear idea how to prove it.

Answer 2

To make this more concrete, here's an example of such a randomly-generated 10 by 10 matrix:

\[\begin{bmatrix} 1&0&1&1&0&1&1&0&1&0 \\ 0&0&1&0&0&1&1&0&1&0 \\ 1&1&1&0&1&0&0&1&1&0 \\ 0&0&1&0&0&1&0&0&0&0 \\ 0&0&0&0 &1&1&0&1&0&1 \\ 0&1&1&0&0&0&0 &0&0&1 \\ 0&0&1&0&1&1&1&1&0&0 \\ 1&1&1&0&1&1&1&1&0&1 \\ 1&1&0&1&1&0&1&0&1&1 \\ 0&1&0&1&1&0&0&1&0&1 \end{bmatrix}\]

Answer 3

I think I have a method to calculate the probability that such a randomly assigned matrix is invertible.

To get started, what do we know about the columns if the matrix is invertible? We know that each column must be linearly independent (after row reduction we will have n pivots).

So we have this matrix:
\[\left[\begin{matrix} .&.&\ldots&.\\.&.&\ldots&.\\col1&col2&\ldots&col10\\.&.&\ldots&.\\.&.&\ldots&. \end{matrix}\right]\]

If we assign randomly 0s and 1s to each column, starting from the left, what are the conditions on column one for the matrix to have a chance at being invertible?

Answer 4

Clearly the first column of the matrix has to have at least one entry with value 1; otherwise there wouldn't be a pivot in the first column. (The same is true for the other nine columns as well, of course.) Is this the "conditions on column one" you were referring to?

In any case, the probability of having at least one entry of value 1 in a given column is 1 minus the probability of having all zeros in a that column. The probability of having all zeros in a column is (1/2)^10 = 1/1024. The probability of having all zeros in any of the ten columns is 10 * 1/1024 or approx. 1% chance that the matrix is singular for this reason.

This isn't the only way a matrix could be singular though. Another way would be if two columns had the exact same set of entries, as in the following (where columns 1 and 2 are identical):

\[\begin{bmatrix} 1&1&1&0&0&0&0&1&1&0 \\ 0&0&1&0&0&1&0&1&1&1 \\ 1&1&1&1&0&1&1&1&0&0 \\ 0&0&0&0&0&0&0&0&1&1 \\ 0&0&1&0&1&0&1&1&1&1 \\ 1&1&0&1&1&0&1&1&0&0 \\ 1&1&0&0&0&0&1&1&1&0 \\ 0&0&1&0&1&0&1&1&0&1 \\ 1&1&1&0&0&0&0&0&1&0 \\ 0&0&0&0&1&1&0&1&1&1 \end{bmatrix}\]

One way to think of the probability of this happening is to consider each column as a 10-bit binary number, i.e., from 0 to 1023, where we sample 10 such numbers randomly (i.e., one for each column). The probability that at least two such numbers will be equal is essentially a variant of the birthday problem. I'm not going to bother going through the detailed math, but based on a birthday problem calculator I found online this probability appears to be on the order of 4% or so. So, again, the probability of a matrix being singular due to this cause is relatively small.

But, once more, this is not the only way for a matrix to be singular. It also might be the case that one column is equal to the sum of another two, like in the following matrix:

\[\begin{bmatrix} 1&0&1&0&0&0&0&1&1&0 \\ 0&1&1&0&0&1&0&1&1&1 \\ 1&0&1&1&0&1&1&1&0&0 \\ 0&0&0&0&0&0&0&0&1&1 \\ 0&1&1&0&1&0&1&1&1&1 \\ 0&1&1&1&1&0&1&1&0&0 \\ 0&0&0&0&0&0&1&1&1&0 \\ 1&0&1&0&1&0&1&1&0&1 \\ 0&1&1&0&0&0&0&0&1&0 \\ 0&0&0&0&1&1&0&1&1&1 \end{bmatrix}\]

where the third column is equal to the sum of the first and second columns. So then you have to estimate the probability of that happening. Ditto for more complicated cases (e.g., fourth column is equal to the sum of the first three).

Answer 5

Okay, I have to admit my idea was a bit short-sited. I didn't think it would be so difficult to calculate the different combinations of columns because the only possible values a cell can have are 1 and 0... However, after going through 3 pieces of scratch paper, I realized solving the problem in that method ( a randomly generated column at a time) was beyond me.

So, I then considered using the determinant... All we'd have to do is calculate the likelihood that the determinant would be non-zero, and then we'd know the probability of a random matrix with 1's and 0's being invertible...

But, calculating the probability of a non-zero determinant is a bit complicated as well, so I had a third idea. This one is the simplest of all, and I'm a bit nervous that once again I'm being foolish. Nonetheless, here goes. :)

All invertible matrices can be row reduced to the identity matrix, so my idea was to start with I, and work backwards through row operations. Since only values of 1 and 0 are involved, multiplying a row by anything other than 1or 0 is not allowed (working backwards from I).

So, I started with a 2x2.\[\left[\begin{matrix} 1&0\\0&1 \end{matrix}\right]\] Through row operations I can only get one other matrix \[\left[\begin{matrix} 0&1\\1&0 \end{matrix}\right]\]. This is true for any n by n matrix. There will only be n permutations.

From there I went back to the matrix I again, and focused on the upper triangle (figuring that whatever I did to the upper triangle would be duplicated in it's transpose. There is only one spot in the upper triangle 2x2 matrix, so giving it a value of 1 and then permutating that, I found two more invertible matrices\[\left[\begin{matrix} 1&1\\0&1 \end{matrix}\right]\]&\[\left[\begin{matrix} 0&1\\1&1 \end{matrix}\right]
\]

Then supposing the transpose will then have two more similar permutations, there will be a total of 6 invertible for a probability of\[\frac{6}{2^4} = \frac{3}{8}\]

Answer 6

I don't know if it's this website, or the chrome browser, but if I enter an answer with more than a couple of lines of latex it crashes. I actually blame Chrome. I'm going to start typing longer answers in TeXStudio I think.

Answer 7

\[ u=\frac{n(n-1)}{2}\]
u represents the total number of positions in the upper triangle of above the diagonal in \[I_{nxn}\] .

\[\\Total\; invertibles \;=T_{I}=n!+\left(2^u-1\right)*n!*2\]

Starting from the left (in the 2nd equation), the first n! represents the total number of permutations of the identity matrix. They are all full rank invertible.

Subtracted 1 from $2^u$ because if all those positions are filled with 0's we still have I, which has already been accounted for.

Next there are n! possible permutations for each upper triangular matrix found.

Finally, multiply by 2 to account for the transposes of the upper triangular invertible matrices. The first n! is not multiplied by 2 because the identity is symetric \[I^T = I\]

Answer 8

Well, I am not confident in the above general formula for an n by n random 1's and 0's matrix. I would hope that it would be correct for n = 10, but I've probably missed something.

I was only able to check the formula for a 2by2 matrix. I think it would be possible to check with matlab or R, but I do not have either installed on my computer.

edit: Two posts ago, I should have said that there are n! possible permutations of I.

Answer 9

"Since only values of 1 and 0 are involved, multiplying a row by anything other than 1or 0 is not allowed (working backwards from I)." Are you saying that in doing Gauss-Jordan elimination on the original matrix (i.e., to find its inverse) you would never multiply a row by a factor other than 1 (or -1)?

If so, I don't believe this is correct. For example, take the case of the following 5 x 5 matrix:
\[\begin{bmatrix} 1&1&1&1&1 \\ 1&0&0&1&0 \\ 0&0&1&1&0 \\ 1&0&1&0&0 \\ 0&0&0&1&1 \end{bmatrix}\]
Elimination on this matrix would proceed as follows: First, subtract 1 times the first row from both the second row and the fourth row; this gives the following matrix:
\[\begin{bmatrix} 1&1&1&1&1 \\ 0&-1&-1&0&-1 \\ 0&0&1&1&0 \\ 0&-1&0&-1&-1 \\ 0&0&0&1&1 \end{bmatrix}\]
Then subtract 1 times the second row from the fourth, producing the following matrix:
\[\begin{bmatrix} 1&1&1&1&1 \\ 0&-1&-1&0&-1 \\ 0&0&1&1&0 \\ 0&0&1&-1&0 \\ 0&0&0&1&1 \end{bmatrix}\]
Then subtract 1 times the third row from the fourth, producing the following matrix:
\[\begin{bmatrix} 1&1&1&1&1 \\ 0&-1&-1&0&-1 \\ 0&0&1&1&0 \\ 0&0&0&-2&0 \\ 0&0&0&1&1 \end{bmatrix}\]
Thus far the only multiplier has been 1. However here it breaks down, as the next step would be to multiply the fourth row by \(-\frac{1}{2}\) and subtract it from the fifth row.

Answer 10

Just going through Strang's class online and I saw this problem and can't stop thinking about it :-) I approached it by considering the value of the determinant; if zero then it's not invertible. Wrote a MATLAB routine to check the first few dimensions and came up with the following:

n invert total percent
2 6 16 0.375000
3 174 512 0.339844
4 22,560 65,536 0.344238
5 12,514,320 33,554,432 0.372956

If this is correct, then it's even more interesting! (note the dip and rise in the percent column?! )

However, I'm new to MATLAB too, hope I didn't make a mistake:

I=0;
T=0;
n=5;
for seed = 0:2^(n*n)-1
% build the matrix A
A = zeros(n,n);
for row = 1:n
for col = 1:n
if mod(seed,2) == 1
A(row,col) = 1;
seed = seed - 1;
end
seed = seed / 2;
end
end
% check A
if det(A) ~= 0
I = I + 1;
end
T = T + 1;
end
disp('ANSWER...')
disp(sprintf( 'Invertable Count = %d', I));
disp(sprintf( 'Total Count = %d', T));
disp(sprintf( 'Probability = %f', I/T));

As far as coming up with the probability as a function of n, it's a bit of an explosion of terms when considering the determinant; and I've not seen the pattern yet. Will keep thinking about it though.

Answer 11

Thanks much for doing these calculations. It looks like my hunch was wrong then: The probability of an n x n matrix of random 1s and 0s being invertible looks to be approx. 0.37. For n = 6 and above the most feasible approach would be to sample from the (very large) space of possible matrices, and do an estimate. If you did multiple samples you could also compute a sample mean and standard deviation.

I wouldn't worry about the seeming dip between 2 and 6. For a 2 x 2 matrix the number of possibilities is so small that you'd get "chunkiness" in any case. For example, if the number of invertible matrices were 5 out of 16 rather than 6 out of 16 you'd get a value of 0.3125 instead of 0.375

Answer 12

Did a little more MATLAB... For n=3..20, I did 10 trials, 100K random matrices per trial and got the following, (including n=3..5 exact values because I was able to calculate those exactly)...

n percent exact error
3 0.34 0.339844 0.000156
4 0.34 0.344238 0.004238
5 0.37 0.372956 0.002956
6 0.42
7 0.48
8 0.56
9 0.64
10 0.73
11 0.82
12 0.89
13 0.94
14 0.97
15 0.987
16 0.994
17 0.997
18 0.9986
19 0.9993
20 0.9996
(attached a graph as well)

So the probability that the described random matrix is invertible approaches certainty as n increases, (looks a little like a sigmodal curve as well). Once n reaches 16+ it's almost certain. This is very counter-intuitive (hence very interesting :-).

Now to think about why... Perhaps a good direction would be to consider dependent columns: the chance to get a column dependent on other columns decreases as n increases, because each column becomes more 'unique' so to speak? I'm still trying to come up with some kind of recursive routine that will result in this data...

Answer 13

Thanks for doing this test. I was wrong to think this was converging to a 0.37 probability of being invertible; I should have trusted my original intuition.

I will confess that I broke down and googled this general topic, and discovered some interesting sources, including a paper written by some high school students working for extra credit. I won't post any spoilers here, except to say that Strang was right to characterize this as a "much harder" problem; some heavyweight mathematicians have worked in this general area.

Answer 14

I forgot to add: You actually did answer the question to my satisfaction: A 10x10 matrix of random 1s and 0s is in fact more likely to be invertible than not. So you get a medal :-)