Probability of a matrix having full rank

[anu914]

Hi all,

I am trying to find the probability that a matrix has full rank.

Consider a K*N matrix where the first K columns are linearly independent columns and the next N-K columns are linear combinations of these K columns.

I want to find the probability that a sub matrix formed by randomly selecting columns of this matrix has full rank. (or all the columns of this sub matrix are linearly independent).

My logic is as follows,

Step 1 : Select u1 number of columns randomly from the first K columns. Then rank(Gu) = u1.
No. of ways to select = K choose u1

Step 2: Now I select one column from the N-K columns and check whether this belong to the span of u1 columns. If not then I increase rank by one.
span of u1 contain 2^u1 possibilities.
So ideally I have to select 1 from 2^K - 2^u1 columns in order to have rank(Gu) = u1 + 1

But my problem is that, N-K < 2^K so the total number of columns I have to make the selection is N-K and not 2^K.

I'm finding it really difficult to interpret this in mathematical formulas using combinations.

Really appreciate if someone can help.

Thanks in advance.

 

[fresh_42]

This depends on which scalar field you use. As you haven't specified it, I assume we are talking about real numbers. The distinction $k \times n$ is only for confusion. We can equally ask: How are the chances a randomly chosen $k \times k$ matrix is regular, since this is what you are looking for. This probability is $1$ as the chances to randomly choose a singular matrix are zero. Singular means the determinant is equal to zero. Now how are the chances to pick zero out of all reals?

 

[WWGD]

There is a result that GL(V) is dense in $\mathbb R^{n^2}$ , i.e., you're given a matrix$A=(a_ij) \rightarrow ( a_{11}, a_{12},..., a_{nn})$ as an $n^2-$ple , the set $Gl(n,\mathbb R)$ is dense in $\mathbb R^{n^2}$