In this post, we study a few probability one results conerning the rank of random matrices: with probability one,

- a random asymmetric matrix has full rank;
- a random symmetric matrix has full rank;
- many random rank one positive semidefinite matrices (belonging to ) are linearly independent.

At least for the first two, they look quite natural and should be correct at first glance. However, to rigorously prove them does require some effort. The post is trying to show that one can use the concept of independence to prove the above assertions. Indeed, all the proof follows an inductive argument where independence makes life much easier:

- Draw the first sample, it satisfies the property we want to show,
- Suppose first samples satisfy the property we want to show, draw the next sample. Since it is independent of the previous samples, the first samples can be considered as
**fixed**. Then we make some effort to say the first sample does satisfy the property.

Before we going into each example, we further note for any probability measure that is absolutely continuous respect to the measure introduced below and vice versa (so independence is not needed), the probability results listed above still hold.

**1. Random Matrices are full rank **

Suppose with and each entry of is drawn independently from standard Gaussian . We prove that has rank with probability .

To start, we should assume without loss of generality that . Otherwise, we just repeat the following argument for .

The trick is to use the independence structure and consider columns of are drawn from left to right. Let’s write the -th column of by

For the first column, we know is linearly independent because it is with probability . For the second column, because it is drawn independently from the first column, we can consider the first column is fixed, and the probability of fall in to the span of a fixed column is because has a continuous density in . Thus the first two columns are linearly independent.

For general , because , we know the first columns forms a subspace in and so falls into that subspace with probability (linear subspace has Lebesgue measure in and Gaussian measure is absolutely continuous with respect to Lebesgue measure and vice versa). Thus we see first columns are linearly independent. Proceeding the argument until completes the proof.

**2. Symmetric Matrices are full rank **

Suppose with and each entry of the upper half of , , is drawn independently from standard Gaussian . We prove that has rank .

Let’s write the -th row of by . For the first entries of the -th row, we write . Similarly, denotes the first entries of the -th column. For the top left submatrix of , we denote it by . Similar notation applies to other submatrices.

The idea is drawing each column of from left to right sequentially and using the independence structure. Starting from the first column, with probability one, we have that is linearly independent (meaning ).

Now since is drawn and the second column except the first entry is independent of , we know it is in the span of if the second column is ( is with probability 0) multiple of . This still happens with probability since each entry of has continuous probability density and is drawn independently from .

Now assume we have drawn the first columns of , the first columns are linearly independent with probability , and the left top submatrix of is invertible (the base case is what we just proved). We want to show after we draw the column, the first columns are still linearly independent with probability . Since the first columns is drawn, the first entries of the column is fixed, we wish to show the rest entries which are drawn independently from all previous columns will ensure linearly independence of first columns.

Suppose instead is linearly dependent with first columns of . Since the left top submatrix of is invertible, we know there is only one way to write as a linear combination of previous columns. More precisely, we have

This means has to be a fixed vector which happens with probability because the last entries of is drawn independently from , Note this implies that the first columns of are linearly independent as well as the left top submatrix of is invertible because we can repeat the argument simply by thinking is (instead of ). Thus the induction is complete and we prove indeed has rank with probability .

**3. Rank positive semidefinite matrices are linearly independent **

This time, we consider , are drawn independently from standard normal distribution in . Denote the set of symmetric matrices in as . We show that with probability the matrices

are linearly independent in .

Denote the standard -th basis vector in as . First, let us consider the following basis (which can be verified easily) in ,

We order the basis according to the lexicographical order on . Suppose follows standard normal distribution in , we prove that for any fixed linear subspace with dimension less than , we have

We start by applying an fixed invertible linear map to so that the basis of is the first many basis vector of ({in lexicographical order.}), and the basis of the orthogonal complement (defined via the trace inner product) of , , is mapped to the rest of the basis vector of under . We then only need to prove

We prove by contradiction. Suppose . It implies that there exists infinitely many such that . Moreover, each component of takes infinitely many values. We show such situation cannot occur. Denote the -th largest element in as . Since has dimension less than , contains nonzero element and so

Now fix an , we know means that there is some (depending only on ) such that

where is the -th complement of . Now if we fix and only vary , then we have

which holds for infinitely many only if

Thus we can repeat the argument as before and conclude that holds for infinitely many with each component taking infinitely many values only if . This contradicts the fact that is invertible and hence we must have

Now proving spans with probability is easy. Because for each , the with being drawn can be considered fixed because is drawn independently of . But the probability of stays in the span of is by previous result and hence is linearly independent of all . This argument continues to hold for because the space spanned by is at most and so previous result applies. This completes the proof.