I am trying to understand how to use LU Decomposition to calculate the rank of a matrix. I tried googling, but I could not find any details except vague comments that lead me to believe that there is a connection. After some time I came up with the following:
One of the properties of the rank is (taken from Wikipedia):
If B is an n × k matrix of rank n, then rank(AB)=rank(A).
Therefore, if A, L, and U are nxn matrices, in the LU decomposition A = L*U, if U is a unit upper triangular matrix then we can compute the rank of A easily (rank of a triangular matrix is the number of non zero elements on the main diagonal).
However, it is not always possible to have an unit upper triangular matrix as part of the decomposition.
In particular, I would like to compute the rank of the following matrix:
$\begin{matrix}
0&0&t \\ 0&0&t \\ 0&0&0
\end{matrix}$
The rank is one, but I would like to use LU decomposition to prove it.
p.s. I am not concerned about numberical stability.
Best Answer
LU factorization with partial pivoting (i.e. standard LU) will not help you to determine rank of a matrix A.
However LU factorization with complete pivoting or rook pivoting reveals rank of A, estimated rank is simply number of nonzero elements in U factor (up to given tolerance)