Friday, February 24, 2012

Invertability of Random Matrices

Wikipedia says:
Singular matrices are rare in the sense that if you pick a random square matrix over a continuous uniform distribution on its entries, it will almost surely not be singular.
This means that if you use generate a random matrix (using matlab's rand function for example) the resulting matrix is likely to be nonsingular.

How likely? That depends on the size of the matrix.

To look at it slightly more quantitatively consider the well-known problem:
Consider an n by n square matrix A, whose entries are, with equal probability, either 0 or 1. What is the probability that this matrix is invertible (or nonsingular)?
Let us consider a slightly generalized version of the problem.

Consider again, a random square n by n matrix A, whose entries are restricted to the set of integers {-p, -p+1, ..., 0, ... p-1, p}. Each of the 2p+1 values are equally probable.

Thus, if p = 1, then the matrix A has entries {-1, 0, 1}.
• What is the probability that this matrix is nonsingular?
• What is the probability that this matrix is nondefective?