Probability of a matrix having full rank

In summary: This means that every nonzero vector in ##\mathbb R^{n^2}## has a neighborhood in which it is the sum of at most ##n^{2}## different vectors. So if you want to pick a random element from a matrix, there's a good chance you'll get it.
  • #1
anu914
3
0
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.
 
Physics news on Phys.org
  • #2
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?
 
  • #3
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}##
 

1. What is the definition of "full rank" for a matrix?

The rank of a matrix is the number of linearly independent rows or columns it contains. A matrix is said to have full rank if its rank is equal to the number of rows or columns it has.

2. How is the probability of a matrix having full rank calculated?

The probability of a matrix having full rank depends on the size and elements of the matrix. It is calculated using the concept of linear independence and can be determined by using Gaussian elimination or other matrix operations.

3. What factors affect the probability of a matrix having full rank?

The size of the matrix, the distribution of its elements, and the presence of any patterns or symmetries can affect the probability of a matrix having full rank. In general, larger and more randomly distributed matrices have a higher probability of having full rank.

4. Can a matrix with all non-zero elements have less than full rank?

Yes, a matrix can have all non-zero elements and still have less than full rank. This can occur if there are linearly dependent rows or columns, meaning that one row or column can be expressed as a linear combination of other rows or columns within the matrix.

5. What is the significance of a matrix having full rank?

A matrix with full rank is important because it indicates that all of its rows and columns are linearly independent. This means that the matrix is invertible and can be used to solve a system of linear equations, making it useful in many scientific and mathematical applications.

Similar threads

  • Linear and Abstract Algebra
Replies
4
Views
766
  • Linear and Abstract Algebra
Replies
14
Views
1K
  • Linear and Abstract Algebra
Replies
9
Views
4K
  • Linear and Abstract Algebra
Replies
5
Views
1K
Replies
2
Views
1K
  • Linear and Abstract Algebra
Replies
8
Views
2K
  • Linear and Abstract Algebra
Replies
3
Views
1K
  • Linear and Abstract Algebra
Replies
15
Views
4K
Replies
4
Views
1K
  • Linear and Abstract Algebra
Replies
1
Views
1K
Back
Top