# Probability that a random integer matrix is invertible

Assume that $A_{n\times m}$ is a random matrix, i.e. each of $A$'s entries is selected independently from a uniform distribution over $\mathbf{Z}$.

I want to show that $Pr(A\mbox{ is invertible})=1$.

I only know how to show this for $n=2$ because:

1. With probability 1 all entries are not zero (probability to select uniformly a single element from infinite set is zero).
2. Given 1, if we selected $A_{1,1}$, $A_{1,2}$ and $A_{2,1}$ and $\lambda \in\mathbf{Z}$ is the (only, if it exist) constant satisfying $A_{2,1} = \lambda A_{1,1}$ then if we select $A_{2,2} \neq\lambda A_{1,2}$ (which happens with probability 1 from the same considerations) then line 2 is linearly independent in line 1.

However the same argument will not work for line 3 since there are infinitely many combinations of $\lambda_1, \lambda_2$ that satisfy $A_{3,1} = \lambda_1A_{1,1}+ \lambda_2 A_{2,1}$.

• There is no uniform distribution on $\mathbb{R}$. Were you thinking of some bounded subset, or perhaps a different distribution? – Nick Peterson May 28 '14 at 12:53
• Thanks, I will change it to $\mathbf{Z}$ – zvisofer May 28 '14 at 12:57
• There isn't a uniform distribution on $\mathbf{Z}$ either. – Nick Peterson May 28 '14 at 12:58
• Nicholas, it can't be true for a bounded subset because there exist non-invertible matrices and the chance to get uniformly a specific matrix (when the set is bounded) is more than zero. I am sure that the distribution was meant to be uniform. Are you sure there is no alternative definition for uniform distribution over infinite set? I come from computer science and we don't have the highest mathematical formality. – zvisofer May 28 '14 at 13:13
• Instead of thinking in terms of matrices, consider polynomials where zero is (or is not) a root and all coefficients are integers. – Random Excess May 28 '14 at 13:14

## 2 Answers

On any line $A+tB$ in matrix space, the set of singular matrices is given by the solutions of the polynomial equation $$\det(A+tB)=0$$ Since there are only finitely many, this strongly hints that for most probability distributions the chance of hitting a singular matrix is zero.

Or told another way, the set of singular matrices forms a hypersurface, which thus has Lebesque measure zero. Any probability measure that has a Radon-Nikodym density relative to the Lebesque measure will also have the singular matrices as nullset.

A single random $2 \times 2$ matrix is invertible iff the determinant $ad-bc \neq 0$: $$\left[\begin{array}{cc} a & b \\ c & d \end{array}\right]$$

Regardless of what distribution we put on $\mathbb{Z}$, we can find the probability of the even $\mathbb{P}[ad-bc = 0]$ or its complement.

If we have a $3 \times 2$ matrix - I am not entirely sure what "invertible" means in this case - but we have more events to consider and they are not independent:

$$\left[\begin{array}{ccc} a & b & c\\ d & e & f\end{array}\right]$$

We need that $ae-bd, af-cd,bf-ce\neq 0$. In this case, one might try to study the rank of this matrix.

• the rank is $0$ if all entries are $0$
• the rank is $1$ if $d = ka, e = kb, f = kc$ for some $k$.
• the rank is $2$ if the rows are not proportional

$\mathbb{P}[rank = 0]$ is very small in some sense, but rank 1 is possible if all 3 "coincidences" above do occur.

We have said all of this without specifying a measure on the set of integers $(\mathbb{Z}, \mu)$. On possibility is to set $\mu$ to be the uniform measure on $[1,N]$ and let $N \to \infty$ but it's certainly not the only choice.