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}$.

  • $\begingroup$ There is no uniform distribution on $\mathbb{R}$. Were you thinking of some bounded subset, or perhaps a different distribution? $\endgroup$ – Nick Peterson May 28 '14 at 12:53
  • 1
    $\begingroup$ Thanks, I will change it to $\mathbf{Z}$ $\endgroup$ – zvisofer May 28 '14 at 12:57
  • 4
    $\begingroup$ There isn't a uniform distribution on $\mathbf{Z}$ either. $\endgroup$ – Nick Peterson May 28 '14 at 12:58
  • $\begingroup$ 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. $\endgroup$ – zvisofer May 28 '14 at 13:13
  • $\begingroup$ Instead of thinking in terms of matrices, consider polynomials where zero is (or is not) a root and all coefficients are integers. $\endgroup$ – Random Excess May 28 '14 at 13:14

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.