# Are most matrices invertible? [duplicate]

I asked myself this question, to which I think the answer is "yes". One reason would be that an invertible matrix has infinitely many options for its determinant (except $0$), whereas a non-invertible must have $0$ as the determinant.

Do you have another approach to this question, in terms of probability for example?

-

## marked as duplicate by Martin Brandenburg, Brandon Carter, Bruno Joyal, ncmathsadist, Brian RushtonDec 20 '13 at 5:34

–  copper.hat Dec 14 '13 at 8:16
–  copper.hat Dec 14 '13 at 8:29
I think most matrices are not even square. Do you mean, are most square matrices invertible? –  bof Dec 14 '13 at 12:42
Of course, we're dealing with square matrices –  LeGrandDODOM Dec 14 '13 at 12:54
It depends on the distribution you're obligated to define along with your use of the word "most". There's no such thing as a uniform distribution over an infinite range of real numbers. –  NovaDenizen Dec 14 '13 at 15:48

There are at least three ways of saying that a matrix over the real numbers is generically invertible:

The topological one: the set of invertible matrices is a dense open set in the set of all matrices.

The probabilistic one: with the Lebesgue measure on the set of matrices, the non-invertible matrices are of measure zero.

The algebraic one: The set of invertible matrices is open (and non-empty) for the Zariski topology; explicitly, this means that there is a polynomial defined on the coefficients of the matrices, such that the set of invertible matrices is exactly the set where this polynomial is not zero. Of course, here the polynomial is the determinant function.

Remark that your question makes sense for matrices with coefficients in an arbitrary infinite field (for finite fields, we are looking at finite sets...) and that we can still say that a matrix is generically invertible in the algebraic sense.

-
On the other hand, only 29% of square matrices over $GF(2)$ are invertible. –  bof Dec 14 '13 at 12:41
No, I don't consider finite fields in my answer. But what you say is true. It is well-known that $|GL_n(F_q)| = q^{n^2} \prod_{i=1}^n (1-q^{-i})$ –  Jeremy Daniel Dec 14 '13 at 14:24
Your answer is better than mine. So why doesn't it have more upvotes? :( –  Potato Dec 14 '13 at 21:24
@JeremyDaniel: but, what kind of global measure do you define in $\mathbb R^{n^2}$ in order to define probabilities? –  DBFdalwayse Dec 14 '13 at 21:58
Well, I take the Lebesgue measure, viewing the matrices as the space $\mathbb{R}^{n^2}$. Of course, this is not a probability measure since it is of infinite total mass. –  Jeremy Daniel Dec 15 '13 at 0:48

Yes. The non-invertible matrices form a set of measure zero in the space of all $n\times n$ matrices, when considered as a subset of $\mathbb R^{n^2}$.

-
What does it mean? I don't know measure theory. –  LeGrandDODOM Dec 14 '13 at 7:01
@GabrielR. Here's a simple description of measure zero: A set has measure zero if you can cover it by a countable collection of open balls with total volume less than $\epsilon$, for arbitrary small $\epsilon$. –  Potato Dec 14 '13 at 7:02
Since the concept is not being used technically, you may as well say that it's the same as the volume being zero for such a nice (i.e. algebraic) set. –  Ryan Reich Dec 14 '13 at 14:06

Here's how I like to think about it. A matrix $A$ is invertible $\iff$ $det(A) \neq 0$. Since the determinant depends continuously on the entiries, if we have $A$ such that $det(A)=0$, we should be able to perturb the entries slightly so that $det(A)$ is nonzero. Likewise, if $det(A) \neq 0$, then any small perturbation of the entries won't make $det(A)$ suddenly $0$. So in this sense, most matrices are invertible.

-
Continuity only gets you one direction of this. The zero function depends continuously on the entries, but you can't perturb the matrix to make it nonzero. –  Nate Eldredge Dec 14 '13 at 14:53
You may be able at times, but not always, since $Det^{-1}(0)$ is not open in $\mathbb R^{n^2}$. The opposite is the case, tho, since $Det^{-1}(\mathbb R-{0})$ is an open subset. –  DBFdalwayse Dec 14 '13 at 21:56

To expand on Potato's answer, the space of all $n \times n$ matrices is manifold isomorphic to $\mathbb{R}^{n^2}$. The determinant gives a smooth function from this space to $\mathbb{R}$, and by the regular value theorem the preimage of zero (so all noninvertible $n \times n$ matrices) is a manifold of dimension $\mathbb{R}^{n^2-1}$, which has measure zero in the ambient space of all $n \times n$ matrices.

-
Nice, and I think this also shows the interior is empty in $\mathbb R^{n^2}$, i.e., the matrices with $Det=0$ are nowhere-dense in $\mathbb R^{n^2}$. –  DBFdalwayse Dec 14 '13 at 21:50

I think this needs work, but there is something to it: take a randomly-selected matrix $A$, and associate to it its characteristic polynomial $Det(A -\lambda I)$; this polynomial is also random. This polynomial will have $0$ as its root iff its constant term is 0. But most random polynomials will have non-zero constant term, so will not have zero as their root. Alternatively, consider a characteristic polynomial with a zero root. Any small change in an entry of the matrix will change the constant term from $0$ to non-zero. This last statement can be made more accurate/rigorous by using topology: the set of matrices with determinant non-zero is an open subset of $Gl(n,\mathbb R)$, since it is the complement in $\mathbb R^{n^2}$ of the closed set $Det^{-1}(0)$, so that each non-zero matrix, seen as a point in Euclidean space, has a radius around which its determinant is non-zero.

For low dimensions, you can see this geometrically: for a $2 \times 2$-matrix, its determinant is $0$ iff "the entries are on the same line through the origin" , meaning that the points $(a_{11}, a_{12})$ and $(a_{21},a_{22})$ are on the same line through the origin. There are $c$ possible slopes, and only one way of both points being on the same line through $0$. For a $3 \times 3$-matrix, there is a similar argument, seeing the matrix as the measure of the volume enclosed by $3$ vectors in $\mathbb R^3$. The determinant is $0$ here if the rows, seen as points, are "degenerate". The degenerate cases are finitely-many compared with the non-degenerate ones.

-

A probabilistic argument: choose $n^2$ real numbers randomly. Then the probability that the matrix formed by that numbers is not invertible is zero.

Edit: removed a wrong conjecture.

-
Can you give some ground on both arguments? –  LeGrandDODOM Dec 14 '13 at 9:06
@Michael, have a look at this easy counter-example: $A=\begin{pmatrix}-46&-54\\35&-17\end{pmatrix},B=\begin{pmatrix}48&51\\-60&20\end{‌​pmatrix}$. $\det(A)=2672,\det(B)=4020,\det(A+B)=-69$. Your result is valid when one considers SPD matrices. Who has given a point to your answer ? –  loup blanc Dec 15 '13 at 0:19
@loupblanc Your'e right, I have something mixed up. –  Michael Hoppe Dec 15 '13 at 11:27
Choose the real numbers randomly with what distribution? There's no uniform probability measure on the reals. –  Potato Dec 16 '13 at 20:26

No they're not. Think about it, the rank of a $n \times n$ matrix can be any integer $k \in \{0, \dots, n\}$. The only case where the matrix is invertible is when $k = n$.

Joke!

Seriously though, to make a precise answer, one has to define what is meant by "most". If we are talking about matrices with real or complex coefficients, the answer is "yes" for any reasonable definition of "most" (the other answers describe some examples). I think your intuitive answer with the determinant is fine.

-

Let us see. Any matrix can be represented as a finite list with ","s inserted. If we are talking about real numbers, then there would be $2^{\aleph_0}$ matrices. No let us see how can be inverted. Let us take a function $f_n(x)$, which is the determinant of a given $n \times n$ matrix, where the top right value is $x$, and all the other ones held constant. This is continuous, and not the constant function for $0$. Therefore, there are $2^{\aleph_0}$ invertible matrices of $n \times n$ and therefore the number of all invertible matrices. Therefore, there are as many invertible matrices as matrices themselves.

-
Are you saying that there exists a 1-1 function from the sets of the invertible matrices into the sets of those who aren't? –  LeGrandDODOM Dec 14 '13 at 14:43
@Gabriel: There must be such a function, mustn't there? Both sets have cardinality $2^{\aleph_0}$. But such a function won't be continuous. –  TonyK Dec 14 '13 at 14:53
Of course, there might be $2^{\aleph_0}$ uninvertible matrices too, in which case the same number of matrices would be invertible and noninvertible. Cardinal numbers break English. –  PyRulez Dec 14 '13 at 15:04

A square matrix is defined by its column vectors, which are the images of the vectors of the canonical basis through the linear map associated with the matrix. The column vectors are linearly dependent if and only if the matrix is not invertible. So we translated our problem to the problem: are most $n$-tuples of vectors in $\mathbb{R}^n$ linearly independent?

Let us pick an $n$-tuple of vectors in $\mathbb{R}^n$ as randomly as we can. For the first vector we have a whole $\mathbb{R}^n$ of possibilities, we should just avoid the null vector, but that is a very special one. Then we should pick the second vector: of all the possible vectors in $\mathbb{R}^n$ only with the ones on the line determined by the first vector will we end up with a pair of linearly dependent vectors, but those are very special vectors, so we will most likely choose another one. If you think of directions in $\mathbb{R}^n$ as determining a pair of antipodal points on the unit sphere, then apart from the two points determined by the direction of the first vector all other points will do. Then choose a third vector: there is now a plane of directions determined by the first two vectors so that if we choose a vector from this plane we end up with three linearly dependent vectors. On our sphere we have a circle of special directions: much less than the other 'generic' directions. Keep choosing vectors this way and you see that a random choice will give you a linearly independent $n$-tuple with probability $1$.

You could actually translate the original problem to the problem of choosing $n$ points at random on a sphere (or a projective space if you want to have a single point in every direction). Then you would be asking yourself how likely it is that all the points you have chosen lie on a proper subspace of $\mathbb{R}^n$.

-