If I generate a random matrix what is the probability of it to be singular?

Question

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?

Answer 1

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.

Answer 2

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".

Answer 3

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.

Answer 4

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

Answer 5

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.

Answer 6

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.

Answer 7

If the field is a finite field $\mathbb{F}_q$ where things become more interesting then the answer is $$1-\prod_{i=1}^n(1-\dfrac{1}{q^i})$$ for a $n \times n$ matrix. For the case of $n=1$, the answer is obviously $\dfrac{1}{q}$ which is what you'd expect i.e. only when you hit the zero of the field is when the determinant vanishes. For case $n=2$, it is slightly more tedious but still, calculatable, giving you $\dfrac{q^2+q-1}{q^3}$. In the case of $q=2$, you can think of six out of the 16 possible combinations that give you a nonzero determinant i.e the four cases with 3 1's and 1 0's and the two cases with 1's on either diagonal. This gives you $\dfrac{10}{16} = \dfrac{5}{8}$ which is what you'd get from the expression for $q=2$

Answer 8

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.