34
$\begingroup$

Just a random question which came to my mind while watching a linear algebra lecture online. The lecturer said that MATLAB always generates non-singular matrices. I wish to know that in the space of random matrices, what percentage are singular? Is there any work related to this?

$\endgroup$
12
  • 3
    $\begingroup$ How are the entries of the matrix distributed? Are they normally distributed? $\endgroup$ Jul 27, 2016 at 1:41
  • 7
    $\begingroup$ If you use real numbers then, I would think, the probability would be low (possibly zero). It would be much easier to answer for say a $2\times 2$ matrix with integer values within a given range. $\endgroup$
    – Jared
    Jul 27, 2016 at 1:45
  • 2
    $\begingroup$ Unfortunately, your question is underspecified. Nevertheless: see this, this, this, this, this, or this. $\endgroup$ Jul 27, 2016 at 3:46
  • 7
    $\begingroup$ Heh heh. "Just a random question..." $\endgroup$
    – eyuelt
    Jul 27, 2016 at 23:42
  • 3
    $\begingroup$ If you generate a random number what is the probability that it's zero? $\endgroup$
    – user541686
    Jul 28, 2016 at 9:53

7 Answers 7

55
$\begingroup$

A square matrix is singular if and only if the determinant is zero. The determinant is a polynomial in the entries of the matrix. So your question can be thought of as asking the probability that a matrix $A$, viewed as a point in $\mathbb{R}^{n^2}$, will land in the zero set of a polynomial.

The zero set of a polynomial has Lebesgue measure 0. For a proof, see for instance http://www1.uwindsor.ca/math/sites/uwindsor.ca.math/files/05-03.pdf.

Therefore its common to say that this probability is zero.

Note this isn't strictly correct because the Lebesgue measure on $\mathbb{R}^{n^2}$ is not a probability measure. If the entries of the matrix are, say, (multivariate) normally distributed, you are working with an actual probability measure, but the probability is still zero because this measure is absolutely continuous with respect to Lebesgue measure.

$\endgroup$
5
  • $\begingroup$ You might also be interested in the following question: mathoverflow.net/questions/12657/… $\endgroup$ Jul 27, 2016 at 2:09
  • 2
    $\begingroup$ How does this make sense? I'm only educated in maths to an A level standard, but I can't see how this is true. What if the random matrix was $$\begin{pmatrix}3&6\\2&4\\\end{pmatrix}$$? Obviously I can see that the probability of generating this specific matrix is extremely small, but if it is possible for this particular matrix to be generated then surely the probability can't be 0? $\endgroup$
    – imulsion
    Jul 27, 2016 at 13:57
  • 12
    $\begingroup$ @imulsion: "Probability 0" has a slightly unintuitive meaning when dealing with infinite-sets. It's possible for the set of exceptions to be non-empty (or even infinite) and still have probability 0. See en.wikipedia.org/wiki/Almost_surely $\endgroup$ Jul 27, 2016 at 14:13
  • 7
    $\begingroup$ @imulsion ok, what about this one $$\begin{pmatrix}3.000000001&6\\2&4\\\end{pmatrix}$$? Or that one $$\begin{pmatrix}3.000000002&6\\2&4\\\end{pmatrix}$$ By varying one element of the singular matrix, it's possible to create infinitely many non-singular matrices. There are 4 elements in your example, so the probability is something like $$1\over 4\cdot \infty$$. This is not extremely small, not even approaching extremely small, but 0. This is probably not a correct prove or rigorous reasoning, but an intuitive explanation that hopefully helps. $\endgroup$
    – null
    Jul 27, 2016 at 14:31
  • 4
    $\begingroup$ @null It's certainly not a correct proof (since it involves the symbol "$\infty$" in an arithmetic expression) or rigorous reasoning (since it involves the phrase "is something like"). But I agree that it's a helpful intuition. :-) $\endgroup$ Jul 28, 2016 at 9:12
18
$\begingroup$

The math part of the question has been answered already, and the probability is mathematically 0 indeed. About MATLAB though, computers do not work in infinite precision, and do not perform all numerical calculations with 100% accuracy.

For any given precision, however high that might be set, a computer will only ever generate a finite number of distinct matrices. So, instead of a continuum of matrices in $\mathbb{R} ^ {n ^ 2}$, that's more like a discrete, finite subset thereof.

Also, the calculated determinants for each of those matrices will be close, but not guaranteed equal, to the mathematical value, again because of the limited precision and accumulated errors. Some of those determinants will evaluate to 0 (sometimes when they shouldn't, which has been a long known curse in numerical programming).

In this context, the probability of getting a singular matrix is still small, but not 0. In that sense, the statement that MATLAB always generates non-singular matrices should probably be taken as "MATLAB will always generate a random matrix whose determinant, as evaluated by MATLAB itself, is guaranteed to be non-0".

$\endgroup$
5
  • 5
    $\begingroup$ The more interesting question is what's the probability of generating a "nearly" singular matrix. My computational science class I took is failing me now, but there is a measure where a matrix is not singular but very close (and no, it's not when the determinant is close to $0$--since you can scale any non-singular matrix to have a determinant as close to zero as you like). $\endgroup$
    – Jared
    Jul 27, 2016 at 3:12
  • 2
    $\begingroup$ @Jared Condition number and ill-conditioned matrices? $\endgroup$
    – dxiv
    Jul 27, 2016 at 3:14
  • $\begingroup$ FWIW, with single-precision IEEE floats, it's more than sure to stumble upon a singular matrix assuming all its elements are genuinely random and assuming you generate enough of them - what Jared said is also true; with even a single element only an ulp or two from 0, the matrix is numerically unstable; a [1 1][0 0+2*ulp] matrix should be treated like a singular one, because in reality it is. I was taught to always use sensible cutoff thresholds for matrices' elements in real-life (physics etc.) contexts. $\endgroup$
    – user81774
    Jul 27, 2016 at 9:29
  • 3
    $\begingroup$ I doubt there is any specific mechanism in MATLAB that guarantees random matrices will not be singular. Rather, the probability for a matrix randomly generated by MATLAB to be singular (truly or ostensibly) is so small that it probably never happened and probably never will, and that is what the professor meant. $\endgroup$ Jul 27, 2016 at 11:48
  • 2
    $\begingroup$ Note: in practice, no one uses determinants to check for singularity, in numerical computation. And for good reasons. $\endgroup$ Jul 28, 2016 at 6:39
15
$\begingroup$

The set of singular matrices is the zero set of the determinant function and so is a hypersurface in $M_n(\mathbb R) \cong \mathbb R^{n^2}$. As such, it has zero measure. Hence, the probability of a random matrix be singular is zero.

$\endgroup$
3
  • 12
    $\begingroup$ Technically OP didn't specify the distribution on $\mathbb{R}^{n^2}$, so your answer is correct, as long as we are dealing with distributions absolutely continuous with respect to Lebesgue measure on $\mathbb{R}^{n^2}$. Of course it is quite unlikely the OP was referring to anything else. $\endgroup$ Jul 27, 2016 at 1:57
  • $\begingroup$ @William, good point. $\endgroup$
    – lhf
    Jul 27, 2016 at 2:50
  • $\begingroup$ Plenty of distributions in real life have strictly positive probability for specific points (often 0). Say distance you throw a discus. A failure to throw is counted as length 0 which definitely has larger than 0 probability if you watch some sports. $\endgroup$ Jul 27, 2016 at 16:25
1
$\begingroup$

It will depend on the parameters of creating the random numbers. Are they integers, are they real, what is the upper and lower boundaries?
Once you know the answers to these questions, it is more possible to determine the probability.

If you permit, for example, only random numbers as shown on a regular 6-sided die, (whole, real, of the set: 1,2,3,4,5,6), then your odds are actually fairly reasonable.
However, if you permit vales 1-6 including non-integers by defining a 32-bit float (or 64-bit or something large), then your odds are essentially zero, as you end up with x/h as h approaches infinity, thus giving the answer of either epsilon or zero depending on your preference and argument.

Epsilon is a tiny, tiny, tiny number. Reference: https://en.wikipedia.org/wiki/(%CE%B5,_%CE%B4)-definition_of_limit

$\endgroup$
1
$\begingroup$

If you want to build some intuition to matrices where the elements are randomized, you can first consider that any element (position in the matrix): $$\text{Matrix element } {\bf A}_{ij} \text{ will be at position } {\bf e_i}{\bf e_j}^T$$ Where $\bf e_k$ is the standard basis vector with $1$ in position $k$ and $0$ elsewhere. This makes the matrix a linear combination of such matrices where the weights in the linear combination are scalar random variables. Now you can take a look at the Sherman-Morrison formula for the inverse of a rank 1 perturbation of a matrix. It says:

$$({\bf A}+{\bf uv}^T)^{-1} = {\bf A}^{-1}-\frac{{\bf A}^{-1}{\bf uv}^T{\bf A}^{-1}}{1+{\bf v}^T{\bf A}^{-1}{\bf u}}$$

This formula breaks down for us iff the denominator equals zero: $1+{\bf v}^T{\bf A}^{-1}{\bf u} = 0$, which is the case when the inverse stops existing - which is when the (updated) matrix ${\bf A}+{\bf uv}^T$ becomes singular. So that is what needs to happen by chance to leave non-singularity.

$\endgroup$
1
$\begingroup$

Clearly, only @ Jared asks the right question: how to choose the positive integers $n$ and $p$ s.t. if we randomly choose $A\in M_n([[-p,p]])$ (the $(a_{i,j})$ are uniformly choosen in $[[-p,p]]$), then the probability that $d=\det(A)=0$ is $<\epsilon$. But how to choose $\epsilon$ ?

A cryptographic system is assumed to be reliable when the probability of breaking it, is less than $2^{-80}$; that is to say, if we randomly test a secret key with a probability of success $\leq 2^{-80}$, then the event "I obtain the true key" is assumed to be impossible. Even bankers agree with this idea !

Thus we put $\epsilon=2^{-80}$. Now we choose $n=10,p=220$. Experiments with a PC give the following approximations:

The mean of the random variable $|d|$ is $m(|d|)\approx 1.2\times 10^{24}$. $prob(|d|\leq 10^{20})\approx 12\times 10^{-5},prob(|d|\leq 10^{21})\approx 140\times 10^{-5},prob(|d|\leq 10^{22})\approx 1452\times 10^{-5}$.

Then in a first approximation, we may assume that the probability associated to $d\in [[-10^{-k},10^{k}]]$ ($k\leq 22$) is uniformly equally distributed.

Then $prob(d=0)\approx \dfrac{prob(|d|\leq 10^{k})}{2.10^k}$; here we find for $k=20,21,22$: $prob(d=0)\approx 6.10^{-25},7.10^{-25},7.26.10^{-25}$, that is $\approx 2^{-80}$. Of course, the previous estimate is valid (perhaps) up to a factor $10$; what is important is the order of magnitude.

Conclusion: if $n\geq 10$ and $p\geq 220$, then $\det(A)=0$ is an "impossible" event.

EDIT. In fact, it seems that $prob(d=0)$ is significantly higher than the average of the $(prob(d=u))_u$ where $|u|\leq 10^k$ (cf. above). Then likely, the conditions specified in the conclusion above do not suffice.

$\endgroup$
-4
$\begingroup$

The claim is false. MATLAB can be made to produce a matrix containing only zeroes. For instance,

zeros(5,5)

produces a $5 \times 5$ matrix of zeroes. This matrix is singular and MATLAB can determine this.

det(zeros(5,5))
(*  0  *)

Further, it is no challenge to direct MATLAB to create matrices which are just copies of a single nonzero vector, which will also be singular. See, for instance, ones(), which can produce a matrix of all ones.

$\endgroup$
2
  • 2
    $\begingroup$ I don't think that's what the OP meant. $\endgroup$
    – nbubis
    Jul 27, 2016 at 7:57
  • 7
    $\begingroup$ From the context of the OP, they are clearly talking about matrices generated by rand(n,n) or randn(n,n). $\endgroup$
    – user1551
    Jul 27, 2016 at 8:11

Not the answer you're looking for? Browse other questions tagged or ask your own question.