What is the ratio of singular to non-singular matrices?

[Ad Infinitum NAU]

I'm not sure if this has been thought of, posted, or ran over before, but it's something I'm curious about..

Simply put, what is the ratio of singular to non-singular matrices? I've been thinking that it would probably be easier to start with a specific size, then work out from that.

So I just turned 21, so the last few days were spent sleeping with the nights being the vehicle of many parties. I figure I'll just post the most simple form of my idea then wait a few days for my capacity for abstract thought to return. Thanks for your minds.

 

[mathwonk]

sober up for a while and think about your question.

 

[shmoe]

Assuming your matrices have real entries, "just about all" of them non-singular. It's not so straightforward to find a ratio since there are infinitely many singular and infinitely many non-singular matrices. (except in the 1x1 case, what happens here?). You could replace "ratio" with what's the probability a randomly selected nxn matrix is non-singular, but then you have to come up with a way of randomly selecting your matrices.

To simplify things a little, let's modify the problem slightly. A non-singular matrix corresponds to an ordered basis. Let's randomly select unit vectors in R^n with the uniform distribution on the n-sphere. What is the probability that n randomly selected unit vectors will be a basis of R^n? Try n=2 first.

If you were thinking about matrices over finite fields, then there is a straightforward answer. It's not too difficult to count the non-singular matrices in this this case. Of course there's finitely many omatrices in this case so we get a genuine ratio.

 

[Ad Infinitum NAU]

ok.. how bout this..

Given a specific n (even or odd), what is the probability that a randomly generated n x n matrix will be non-singular? I understand there are infinite amounts of each, however I think there still should be some sort of ratio, such as in the question of "Given two sequential numbers (at random) what is the probability one of them is even?" of course it's 1:2.

Also, since thinking about this, I was wondering if the ratio changes depending on the n chosen. For example, is the probability greater for n=4 or n=5?

 

[shmoe]

How do you propose to randomly select your numbers? Can you describe a way that makes all positive integers equally likely to be chosen? This is the problem I was talking about, in order to have a probability, you need a probability measure on your set. This can be done on matrices, but it might not be easy to follow (are you happy with measure theory?). It also might not be what you had in mind for random.

This is why I suggested restricting to unit vectors, the probability measure here is much more transparent, can be uniform in the direction of our vectors, and will be very similar to the full case with one of the usual measures on the matrices. So let's return to this. Think about the n=2 case. Randomly pick your first vector X on the unit circle. Now randomly select your second vector Y. These are only dependent if Y=X or Y=-X. So there are 2 possibilities for dependence out of infinitely many that give independence. The probability of an independent set in this case is therefore 1. You should be able to do something similar for higher dimensions to see that the probability will still be 1. The dimension n your in doesn't matter.

 

[matt grime]

ok.. how bout this..

Given a specific n (even or odd), what is the probability that a randomly generated n x n matrix will be non-singular? I understand there are infinite amounts of each, however I think there still should be some sort of ratio, such as in the question of "Given two sequential numbers (at random) what is the probability one of them is even?" of course it's 1:2.

given two sequential numbers the probability one of them is even is 1, since they are sequential, ie of the form n, n+1.

Also, since thinking about this, I was wondering if the ratio changes depending on the n chosen. For example, is the probability greater for n=4 or n=5?

the problem is saying "at random" needs qualification. it needs measure theory, or some replacement for it. and that is up to you to provide. a lot of work went into developing probability for events like these, and you need to at least try and include some of it in your ideas.

you are asking a fairly impossible question to be honest, and different answers can be given for different meanings.

one way to do it is to take some compact, or measurable subset, and look at the proportion there, then take successively larger sets, and see if the proportion tends to some limit, then it is reasonable to take that as a probability. For instance, we may say that a randomly picked integer is even with probablilty 1/2 since in the sets [1,...,n] the probability is 1/2 if n is even or (n-1)/2n if n is odd, and that sequence of sets has limit N, and the sequence has limit 1/2.

that is something you can work on, since it isn't hard to work out some heuristic arguments (the singular matrices are parametrized by the set of zeroes of a polynomial, some basic measure theory you should learn will help you figure out the answer).


note for shmoe: you've said dependent at one point when you mean independent.

 

[selfAdjoint]

given two sequential numbers the probability one of them is even is 1, since they are sequential, ie of the form n, n+1.



the problem is saying "at random" needs qualification. it needs measure theory, or some replacement for it. and that is up to you to provide. a lot of work went into developing probability for events like these, and you need to at least try and include some of it in your ideas.

you are asking a fairly impossible question to be honest, and different answers can be given for different meanings.

one way to do it is to take some compact, or measurable subset, and look at the proportion there, then take successively larger sets, and see if the proportion tends to some limit, then it is reasonable to take that as a probability. For instance, we may say that a randomly picked integer is even with probablilty 1/2 since in the sets [1,...,n] the probability is 1/2 if n is even or (n-1)/2n if n is odd, and that sequence of sets has limit N, and the sequence has limit 1/2.

that is something you can work on, since it isn't hard to work out some heuristic arguments (the singular matrices are parametrized by the set of zeroes of a polynomial, some basic measure theory you should learn will help you figure out the answer).


note for shmoe: you've said dependent at one point when you mean independent.

THere's a big field called stochastic matrices. You can look it up on the arxiv; it has physical implications.

 

[matt grime]

As in random matrix theory, which I presume is the same idea? however that might be different from picking a matrix at random, since "at random" in this question has not been given a meaning, and we've had to guess at the author's intent, and somehow I don't think, "let X be a matrix with entries iidrvs with distribution f..." is what was meant.

I could pop next door and ask Keating if he knows a random matrix theory answer to this question.

 

[mathwonk]

Now that you guys have clarified the question, it is indeed much clearer. But there seem to be two questions emerging from the discussion:

1) given a positive integer n, what is the probability a randomly CHOSEN (i.e. theoretically genuinely random) n by n matrix is non singular?

2) ...what is the probability a randomly GENERATED n by n matrix (i.e. mechanically chosen by some algorithm or machine) is non singular?

The first question seems clearly to have answer: one. The second seems to depend on the method of trying to approximate randomness in the actual choice.

For question 1, ( a version of) Shmoe's approach seems to do it: i.e. rule out the zero matrix. Scaling the rows uniformly has no effect on non singularity, so then you are simply choosing a point on the projective space of dimension (n^2) -1.

the singular matrices correspond to the points of the hypersurface det = 0, which has lower dimension, hence has (n^2)-1 dimensional volume zero. So if we define the probability of a random point's lying in the non singular matrices as the ratio of the volume of the non singular matrix points in P^([n^2] -1), to the volume of all of the projective space, that ratio is one.

(this is for real matrics, say.)

As to question 2), I have no idea how random generating algorithms work, but it seems very hard in real life to actually choose anything randomly.

For instance, the set of points of projective space whose coordinates are real number decimals of length less than one billion symbols, is also of measure zero.

So in real life, the numbers are not zero and one.

It is sort of like in the old days when we used to assume the ocean was an infinite heat sink, for calculations, until we noticed it was heating up.

 

[mathwonk]

so here is a "real life" question. (maybe this is what you guys were already thinking of.)

Notice also that being non singular is not a real life property. I.e. a matrix is non singular iff the determinant is non zero, but in real life it cannot be determiend perfectly if a real number is exactly zero or not. So we have to introduce error, by saying we will consider the matrix to be non singular if the determinant has absolute value say larger than 1/100, or some other number we can reliably believe is non zero.

Then given that an n by n matrix has real entries represented by decimals with at most 100 symbols on the left and 100 symbols on the right of the decimal point, what is the probability that the determinant of a matrix genuinely chosen at random has determinant of absolute value greater than 1/100?

 

[mathwonk]

so we are looking at a finite "cube" in the space of all matrices, those whose entries acn be stored in our calculator. Then in that cube we look at the cone of singular ones, but more than that, for security we consider a slight thickening of that cone, all matrices which are close enough to singular thatw e cannot be sure. Then we want the ratio of the volumes of these thigns. This is not zero or one, but the ration again must be an approaximation we can compute, so to our limits of accuarcy it might be effectively still zero or one. ??