How often do invertible matrices appear?
Introduction
Invertible matrices are fundamental in linear algebra. They represent reversible linear transformations which are pleasant to work with, because:-
- Invertible matrices give us a unique solution to a system of linear equations.
- Invertible matrices represent linear transformations that are of full rank, i.e. those that do not 'squish' the space in a way that reduces its dimension, and injective (one-to-one).
- The columns of an ( real) invertible matrix, are linearly independent to each other, and thus spans the full space.
- Invertible matrices have nonzero determinants.
– some of the logically equivalent statements in the Invertible Matrix Theorem (IMT)
As nice mathematical structures usually do not happen frequently, this makes one wonder: in the universe of square matrices of an arbitrarily fixed1 size, say, , what is the probability of finding an invertible matrix?
Surprisingly (at least to me), it turns out to be a very technical problem that has very different answers depending on various factors with respect to the entries of the matrix, including their probability distribution, allowable types of numbers (discrete or continuous, etc.) and even the underlying measure. In other words, there isn't a blanket answer and certain conditions need to be specified in order to reach an answer.
It is way more often than you may expect
Let's first consider the scenario that is considered 'default' or 'standard' by most people: the probability of finding an invertible matrix among the space of an matrix of real numbers2.
In this scenario, the answer turns out to be a surprising one (again, at least to me): it is almost surely to find an invertible matrix, i.e. the probability is 1 but this does not mean all real matrices are invertible (there are indeed singular, or non-invertible, matrices). This is a phenomenon that can happen when we are considering infinite sample spaces; even though there are an infinite number of singular matrices, invertible matrices still outnumber them so much that they are probabilistically negligible (literally zero probability). To quote the Wikipedia article about invertible matrices,
Singular matrices are rare in the sense that if a square matrix's entries are randomly selected from any bounded region on the number line or complex plane, the probability that the matrix is singular is 0, that is, it will "almost never" be singular.
There are two main approaches to prove this result, both of which make use of linear algebra and measure theory: one involves determinants, whereas the other involves subspaces and its dimension.
Determinant Argument
The argument involving determinants, as found in this post and this post from Mathematics Stack Exchange, applies the fact that invertible matrices have nonzero determinant, or in other words, singular matrices have zero determinant. The determinant of a real matrix (with entries) is also a polynomial function, as shown below ( represents a permutation function and is either 1 or -1):
Therefore, since if is singular, the collection of singular matrices is equivalent to the zero set of the determinant as a polynomial function from to .
There is a mathematical result which states that the zero set of a polynomial function has measure zero (a proof of this can be found here or here). It's fine if you don't understand what 'measure zero' means: what matters here is that an event represented by a (sub)set of measure zero has zero probability.
Thus, there is zero probability that a random real square matrix is singular, so the probability to obtain an invertible matrix is 1 (in the almost surely sense).
Subspace Dimension Argument
Another argument, as found in this Reddit comment, this blog post and this Mathematics Stack Exchange post, involves the fact that the collection of singular matrices form a subspace that is one dimension less than the space of all matrices.
Why is that so? A less rigorous reasoning of this goes as follows: note that for an matrix to be singular, it must have at least one column that is a linear combination of all the other columns.
Now, for a single nonzero vector in , the collection of vectors that are linearly dependent to that particular vector are its scalar multiples, i.e. , and this is a one-dimensional subspace of . For two vectors and , the collection of vectors that are linearly dependent to them is , which forms a 2-dimensional subspace. Following this pattern, if we have vectors in , the collection of vectors that are linearly dependent to them is exactly their linear span, which is an -dimensional subspace.
This implies that the column space of a singular matrix is an at most -dimensional subspace of , so the space of singular matrices form an -dimensional hypercube, compared to an -dimensional hypercube formed by the space of all square matrices. Thus, the probability of finding a singular matrix is:
An alternative but very similar argument, as described here, states that due to the fact that singular matrices have zero determinant which gives us one constraint equation, the set of singular matrices form an -dimensional vector space, which similarly has measure zero, with respect to the -dimensional space of all matrices over the real numbers.
Either way, it follows that the probability of finding an invertible real matrix is, surprisingly, 1. In other words, for whatever real matrices that you come up with randomly, it is extremely likely to have an inverse!
Matrices with discrete entries
Things start to get interesting when we restrict the entries of a square matrix to be discrete values, in particular binary (i.e. 0 or 1), finite field and integer values.
Binary matrices
For binary matrices, the probability trend depends on the underlying ring (or in laymen's terms: number system) of the entries of the matrix. For binary matrices over the real numbers, it is a long-time research problem stemming from the 1960s that involves contributions by multiple mathematicians, and is settled by Tikhomirov in his 2018 paper: the probability that an binary matrix is invertible is given by
where denotes a quantity that tends to 0 as tends to infinity.
We can see that as gets larger, the probability gets closer to 1.
As for binary matrices over the finite field , it corresponds to the case when in the next section of this article, where matrices over finite fields are discussed in more detail. One thing to note is that the change in probability as gets larger is different: it decreases and tends to a limiting number strictly between 0 and 1.
Matrices over finite fields
There is a pretty neat argument, which can be found in several sources including Wikipedia, that gives us the probability of finding an invertible matrix in the space of square matrices over a finite field 3.
In the lingo of abstract algebra, the number of invertible matrices over the finite field is the order of the general linear group of degree over , . There is a pretty neat argument that gives us the probability of finding an invertible matrix in the space of square matrices over a finite field , which is described in several sources.
For a square matrices of size whose entries are taken from a finite field of order (i.e. contains elements), which we denote here by , there are possibilities in each entry. Since there are available slots, we have a total of such matrices. If we only consider one of its columns, then as there are entries in a column, there are possibilities.
Note that is invertible if and only if for , the -th column cannot be expressed as a linear combination of the preceding columns. For the first column , there are possibilities, as only the zero vector is excluded. For the second column , since we need to exclude the multiples of the first column, there are possibilities. For the third column , we need to exclude the linear combinations of the first and second column, i.e. vectors in the form of where , which contains vectors, so in the end we have choices. Continuing this pattern, the last column will have choices. Thus, the number of invertible matrices over , or the order of is given by