Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have some discussion with my friend about matrix rank.

But we find that even we know how to compute rank, we don't know how to show the matrix is full rank.

How to show this?

share|improve this question
2  
I don't understand the problem. If you know how to compute the rank, just compute it and see whether it is the maximal possible rank. –  Stefan Geschke Feb 7 '12 at 9:39
    
I am considering to use this in some proof, so knowing how to compute may not be enough. Anyway thanks for you help :) –  Rein Feb 24 '12 at 3:48
add comment

2 Answers 2

up vote 3 down vote accepted

Stefan's suggestions for calculating rank are good for small matrices, or matrices that can be manipulated by hand. Even then, I'd use Gaussian elimination and reduce the matrix to row-echelon form; the number of nonzero rows will be the rank of the matrix. This algorithm will be faster than computing determinants for any matrix larger than 3 by 3, and it is similar to his suggestion to solve the linear equation $Ax = 0$.

If you have a sufficiently large matrix where this would be infeasible, you could determine the rank of the matrix numerically using a singular value decomposition (SVD) or a rank-revealing QR decomposition. If the matrix $A$ is $n$ by $m$, and its rank is equal to $\min(n,m)$, then it is full rank. If you can calculate the rank, then you can determine if the matrix is full rank.

If you were to use the SVD, the numerical rank of your matrix would be equal to the number of singular values greater than a certain numerical cutoff (usually set to be something small, like $10^{-12}$; a little discretion needs to be used here). MATLAB's rank function uses this algorithm.

If you were to use the rank-revealing QR decomposition, the numerical rank of your matrix would be equal to the number of values on the diagonal of the $R$ matrix whose magnitude is greater than a numerical cutoff (again, chosen like the SVD). This method is considered slightly less reliable than the SVD algorithm, but it is faster.

You can also use a rank-revealing QR decomposition to determine the linearly independent columns of your matrix. If the rank of your matrix is $k$ (as calculated from the $R$ matrix), the first $k$ entries of the permutation vector returned by the rank-revealing QR decomposition correspond to the linearly independent columns.

The problem with calculating the matrix rank using determinants is that calculation of determinants is expensive numerically, and in the context of numerical linear algebra, gives you less useful information. Calculating the matrix rank is possible using Gaussian elimination (i.e., LU decomposition) by hand, but using LU decomposition for determination of the rank of a matrix in floating point arithmetic is unreliable.

share|improve this answer
    
This suggestion is certainly numerically more feasible than my answer. –  Stefan Geschke Feb 9 '12 at 16:42
1  
Thanks! Very detailed information about rank computation! Very helpful for me :) –  Rein Feb 24 '12 at 3:51
add comment

If you are talking about square matrices, just compute the determinant. If that is non-zero, the matrix is of full rank.

If the matrix $A$ is $n$ by $m$, assume wlog that $m\leq n$ and compute all determinants of $m$ by $m$ submatrices. If one of them is non-zero, the matrix has full rank.

Also, you can solve the linear equation $Ax=0$ and figure out what dimension the space of solutions has. If the dimension of that space is $n-m$, then the matrix is of full rank.

Note that a matrix has the same rank as its transpose.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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