Proof: Rank of a Random (arbitrary size) Matrix is full rank with probability $1$?

Question

I am wondering how to prove that a complex-valued random matrix say $\mathbf{A} \in \mathbb{C}^{M \times N}$ with size $M \times N$ has full-rank, i.e., $\textrm{rank} = \min\left\{M,N\right\}$ with probability $1$, where each entry in $a_{m,n} = [\mathbf{A}]_{m,n}$ is distributed as independent complex Gaussian random variables, i.e., $a_{m,n} \sim \mathcal{CN}\left(\mu, \sigma^2\right)$.

Thank you very much in advance

Answer 1

Assume that $M \leq N$, $M$ rows each row picked from $\mathbb{C}^N$.

Fact 1: Let $M$ and $N$ be two positive integers with $M \leq N$. Next, for some $j \leq M$, let $v_1,\ldots, v_{j-1}$ be arbitrary vectors in $\mathbb{C}^N$. Now let $v_{j}$ be a vector picked from $\mathbb{C}^N$ independently from $v_1,\ldots, v_{j-1}$ according to some continuous distribution (i.e., the distribution is such that the probability that $v_{j}$ falls into any set in $\mathbb{C}^N$ of measure 0 (which includes subspaces of $\mathbb{C}^N$ of dimension $M-1$ or less) is 0). Then the probability $P_{j}$ that $v_{j}$ is linearly dependent on $v_1,\ldots, v_{j-1}$ is 0.

Check to make sure you understand and see Fact 1 for yourself.

So build ${\bf{A}}$ by picking the first row $v_1$, then the 2nd row $v_2$, and then for each $j=3, \ldots, M$, the $j$-th row $v_j$ of $\mathbb{A}$. IF each coordinate of each such $v_j$ is picked according to the Gaussian independently of one another and independently of $v_1,\ldots, v_{j-1}$, then $v_j$ is indeed picked according to a continuous distribution from $\mathbb{C}^N$. So by Fact 1 and the Union Bound, the probability that ${\bf{A}}$ has full row-rank (for the case where $M \leq N$) is at least $1 - \sum_{j=1}^M P_j$ where $P_j$ is as in Fact 1. But each $P_j$ is 0. So (for the case where $M \leq N$) the probability that ${\bf{A}}$ has full row rank is 1, which implies that (for the case where $M \leq N$)the probability that ${\bf{A}}$ does not have full row rank is 0.

Showing that ${\bf{A}}$ has full column rank for the case where $N \geq M$ can be handled analogously.

Answer 2

Let $\mathcal M$ be the set of all submatrices of $A$ of size $r=\min(M,N)$. Matrix $A$ is full-rank if and only if $det(B) \ne 0$ for eat least one submatrix $B\in \mathcal M$.

Consider $P = \sum_{B\in \mathcal M} (det(B))^2$. This is a polynomial function of the entries of $A$. This polynomial is not always equal to 0, for instance in the case when one submatrix of $A$ is equal to identity.

Since the zero-set of a nonzero polynomial has Lebesgue measure 0, $A$ is full-rank except on a set of Lebesgue measure 0 (with respect to the entries of $A$). Thus if the distribution of $A$ is absolutely continuous with respect to the Lebesgue measure, $\mathbb P(A \text{ is not full rank}) = \mathbb P(P=0) = 0$.