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 ($n \times n$ real) invertible matrix, are linearly independent to each other, and thus spans the full $\mathbb{R}^n$ 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 fixed¹ size, say, $n \times n$, 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 $n \times n$ matrix of real numbers².

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 $n \times n$ matrix (with $n^2$ entries) is also a polynomial function, as shown below ($\sigma$ represents a permutation function and $\operatorname{sgn}(\sigma)$ is either 1 or -1):

$$M := \begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} \end{pmatrix} \implies \det(M)=\sum _{\sigma \in S_{n}}\operatorname {sgn}(\sigma )a_{1,\sigma (1)}\cdots a_{n,\sigma (n)}$$

Therefore, since $\det(M) = 0$ if $M$ is singular, the collection of singular matrices is equivalent to the zero set of the determinant as a polynomial function from $\mathbb{R}^{n^2}$ to $\mathbb{R}$.

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 $n \times n$ matrices.

Why is that so? A less rigorous reasoning of this goes as follows: note that for an $n \times n$ matrix to be singular, it must have at least one column that is a linear combination of all the other $n-1$ columns.

Now, for a single nonzero vector $\vec{v}$ in $\mathbb{R}^n$, the collection of $\mathbb{R}^n$ vectors that are linearly dependent to that particular vector are its scalar multiples, i.e. $\{k\vec{v} : k \in \mathbb{R}\}$, and this is a one-dimensional subspace of $\mathbb{R}^n$. For two vectors $\vec{v_1}$ and $\vec{v_2}$, the collection of vectors that are linearly dependent to them is $\{ a\vec{v_1}+b\vec{v_2} : a,b \in \mathbb{R} \}$, which forms a 2-dimensional subspace. Following this pattern, if we have $n-1$ vectors in $\mathbb{R}^n$, the collection of vectors that are linearly dependent to them is exactly their linear span, which is an $n-1$-dimensional subspace.

This implies that the column space of a singular matrix is an at most $n-1$-dimensional subspace of $\mathbb{R}^n$, so the space of singular matrices form an $n - 1$-dimensional hypercube, compared to an $n$-dimensional hypercube formed by the space of all square matrices. Thus, the probability of finding a singular matrix is:

$$\dfrac{n \text{-dimensional volume of a cube in } \mathbb{R}^{n-1}}{n \text{-dimensional volume of a cube in } \mathbb{R}^{n}} = 0.$$

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 $n \times n$ matrices form an $n^2-1$-dimensional vector space, which similarly has measure zero, with respect to the $n^2$-dimensional space of all $n \times n$ 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 $n \times n$ binary matrix $M_n$ is invertible is given by

$$P(M_n \text{ is invertible})=1-\left(\frac{1}{2}+o_n(1)\right)^n$$

where $o_n(1)$ denotes a quantity that tends to 0 as $n$ tends to infinity.

We can see that as $n$ gets larger, the probability gets closer to 1.

As for binary matrices over the finite field $\mathbb{F}_2$, it corresponds to the case when $q = 2$ 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 $n$ 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 $\mathbb{F}_q$³.

In the lingo of abstract algebra, the number of invertible $n \times n$ matrices over the finite field $\mathbb{F}_q$ is the order of the general linear group of degree $n$ over $\mathbb{F}_q$, $\mathrm{GL}_n(\mathbb{F}_q)$. 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 $\mathbb{F}_q$, which is described in several sources.

For a square matrices of size $n$ whose entries are taken from a finite field $\mathbb{F}_q$ of order $q$ (i.e. contains $q$ elements), which we denote here by $A$, there are $q$ possibilities in each entry. Since there are $n^2$ available slots, we have a total of $q^{n^2}$ such matrices. If we only consider one of its columns, then as there are $n$ entries in a column, there are $q^n$ possibilities.

Note that $A$ is invertible if and only if for $j = 1,\ldots,n$, the $j$-th column cannot be expressed as a linear combination of the preceding $j-1$ columns. For the first column $v_1$, there are $q^n-1$ possibilities, as only the zero vector is excluded. For the second column $v_2$, since we need to exclude the $q$ multiples of the first column, there are $q^n-q$ possibilities. For the third column $v_3$, we need to exclude the linear combinations of the first and second column, i.e. vectors in the form of $av_1+bv_2$ where $a,b=1,\ldots,q$, which contains $q \cdot q = q^2$ vectors, so in the end we have $q^n-q^2$ choices. Continuing this pattern, the last column will have $q^n-q^{n-1}$ choices. Thus, the number of invertible matrices over $\mathbb{F}_q$, or the order of $\mathrm{GL}_n(\mathbb{F}_q)$ is given by

$$\prod _{k=0}^{n-1}(q^{n}-q^{k})=(q^{n}-1)(q^{n}-q)(q^{n}-q^{2})\ \cdots \ (q^{n}-q^{n-1}).$$

It follows that the invertibility probability is

$$\frac{\prod _{k=0}^{n-1}(q^{n}-q^{k})}{q^{n^2}}=\prod_{k=0}^{n-1}(1-q^{k-n}) < 1-\frac{1}{q}.$$

We then see that as the order $q$ increases, the probability tends to 1, whereas as the matrix size $n$ increases, the probability decreases and tends to a limiting number strictly between 0 and 1; for the case of binary matrices over $\mathbb{Z}_2$, the limit is approximately 0.288788.

Random integer matrices

For the case of $n \times n$ matrices with entries over the integers, with an appropriate probability distribution and measure chosen², since there are infinitely many such random integer matrices, the result is analogous to the real matrices case as discussed above, i.e. the probability of finding an invertible matrix is 1, in the sense of being almost surely.

Sidenote: diagonalisable matrices

There is another matrix-related property that is nice to work with and highly sought after for its usefulness in improving computational efficiency: being diagonalisable. Sadly, not all matrices are diagonalisable, even over complex numbers, but what is the probability of finding one, or more accurately speaking: the "density" of diagonalisable matrices?

There is a paper about this topic that quotes or features some important results, but they are mainly about integer matrices instead of real matrices. They are only presented briefly as a list here, but one can consult the paper for more details.

• The probability of an $n \times n$ matrix, where $n$ is arbitrary fixed, with real entries being diagonalisable over the complex numbers (i.e. the eigenvalues are allowed to be non-real), is 1.
• If the entries are only allowed to be integers, the probability of such $n \times n$ matrix being diagonalisable over the complex numbers is also 1.
• It turns out that for $n \times n$ matrices over the real or rational numbers, the question becomes remarkably difficult; even for $2 \times 2$ matrices the result is not straightforward: techinques in multivariable calculus and mathematical analysis are employed in the said paper to prove the results. Nonetheless, here are some key results concerning $2 \times 2$ matrices provided by the paper:
  • The probability of finding a $2 \times 2$ matrix with only integer entries that is diagonalisable over the real numbers (i.e. the eigenvalues can only be real numbers) among all $2 \times 2$ matrices with only integer entries is $\dfrac{49}{72}$. Not a particularly elegant number, but this seems to show that diagonalisable matrices might be denser than we expect.
  • The probability of obtaining a $2 \times 2$ matrix with only integer entries that is diagonalisable over the rational numbers (i.e. the eigenvalues can only be rational) among all $2 \times 2$ matrices with only integer entries is $0$, implying that diagonalisable integer matrices with only rational eigenvalues are so sparse that it is virtually negligible.

References, further reading

• A Reddit post thread that discusses this topic

• Hetzel, A. J., Liew, J. S., & Morrison, K. E. (2007). The Probability that a Matrix of Integers Is Diagonalizable. The American Mathematical Monthly, 114(6), 491–499. https://doi.org/10.1080/00029890.2007.11920438

• Caron, R. & Traynor, T. (2005). The Zero Set of a Polynomial.

• Wicklin, R. (2011). What is the chance that a random matrix is singular?

• Sources that discuss binary matrices and matrices over a finite field:

  • Dai, A., Kim, C. & Kim, J. (2008). Invertibility Probability of Binary Matrices.
  • Morrison, K. E. (2006). Integer Sequences and Matrices Over Finite Fields. Journal of Integer Sequences.
  • Comment by Reddit user u/HotPocketRemix
  • Praveen Sriram (https://math.stackexchange.com/users/211932/praveen-sriram), Probability of building an Invertible Matrix, Mathematics Stack Exchange
  • Tikhomirov, K. (2020). Singularity of random Bernoulli matrices. Annals of Mathematics, 191(2), 593-634.

• Tao, T. & Vu, V. (2007). On the singularity probability of random Bernoulli matrices. Journal of the American Mathematical Society, 20(3), 603-628.

• Bourgain, V., Vu, V. H. & Wood, P. M. (2009). On the singularity probability of discrete random matrices. Journal of Functional Analysis, 258(2), 559-603.

• Some Mathematics Stack Exchange posts referenced:

  • kosmos (https://math.stackexchange.com/users/65781/kosmos), If I generate a random matrix what is the probability of it to be singular?
  • Gabriel Romon (https://math.stackexchange.com/users/66096/gabriel-romon), Are most matrices invertible?
  • Fred Daniel Kline (https://math.stackexchange.com/users/28555/fred-daniel-kline), Why is a singular matrix rare?

Footnotes

1. Funnily enough, this almost sounds like an oxymoron, yet it's just mutually understood in the mathematics literature (and beyond) to mean 'anything but not everything'. If you're confused, see here for explanation. ↩

2. Technically, we are considering the space of $n \times n$ matrix whose entries are allowed to be any real number, so that they act as absolutely continuous random variables. We also require the entries to be independent and identically distributed (i.i.d.) so that each entry does not influence each other and exhibits the same trend. To ensure that this question of looking for a probability is well-posed, we need to specify a probability measure. In this case, the Lebesgue measure (or Borel measure) will suffice. ↩ ↩²

3. For those who are puzzled by the term "finite field", one can think about counting the numbers on a clock face that only has 11 numbers instead of the usual 12. The number pointed by the hands cycles back from 11 to 1 as time passes. This gives us an example of a cyclic group of order 11: the integers modulo 11, i.e. $\mathbb{Z}_{11}$. Since 11 is prime, this gives us an example of a finite field as well: the field of integers modulo $p$ where $p$ is prime. Indeed, this is just a relatively simple example of finite fields. For those who want to know more about the subject, which is central in the study of Galois theory, I recommend this excellent expository paper by Keith Conrad. ↩