File Exchange

image thumbnail

Extract linearly independent subset of matrix columns

version 1.0.3 (1.3 KB) by Matt J
Loop-free code routine to find a maximal subset of linearly independent columns in a matrix

19 Downloads

Updated 05 Aug 2020

View Version History

View License

This submission is a very simple code routine that I have used for many years for finding a maximal subset of linearly independent columns of a matrix. It is based on an old conversation with Bruno Luong, which has recently resumed here,

https://www.mathworks.com/matlabcentral/answers/574543-algorithm-to-extract-linearly-dependent-columns-in-a-matrix#answer_474601

and where he gives some mathematical explanation behind the method. I post this here for ease of reference, as it seems to be a frequently sought tool by Matlab Community members.

USAGE:

Extract a linearly independent set of columns of a given matrix X

[Xsub,idx]=licols(X)

in:

X: The given input matrix
tol: A rank estimation tolerance. Default=1e-10

out:

Xsub: The extracted columns of X
idx: The indices (into X) of the extracted columns

EXAMPLE:

>> A=eye(3); A(:,3)=A(:,2)

A =

1 0 0
0 1 1
0 0 0

>> [X,idx]=licols(A)

X =

1 0
0 1
0 0

idx =

1 2

Cite As

Matt J (2020). Extract linearly independent subset of matrix columns (https://www.mathworks.com/matlabcentral/fileexchange/77437-extract-linearly-independent-subset-of-matrix-columns), MATLAB Central File Exchange. Retrieved .

Comments and Ratings (6)

Matt J

Basically, the QR decomposition is used to obtain a decomposition of the rank-r matrix A into the block form A*E=Q*[T,d; 0 0] where E is a column permutation matrix and T is an r-by-r upper triangular sub-matrix with non-zero decreasing diagonals. Because of the structure of the right hand side, we see that the sub-matrix Q*[T;0] has full rank r. Moreover, Q*[T;0] coincides with the first r columns of A*E and therefore these first r columns are also of full rank r. In other words, these columns are linearly independent and span the column space of A*E and therefore also of A. This is what we were looking for. Therefore, to obtain a linearly independent spanning subset of the original matrix A, we need only permute its columns to obtain A*E and extract the first r columns of A*E.

HN

HN

@Matt J,
I would love to ask how would you chose independent columns from raw matrix while we only have transformed matrices? Any explanation or reference I can read would be appreciated?

Matt J

@HN, It just means the code has always worked for me, but I don't know why, mathematically. It relies on the empirical observation that in the QR decomposition, the R matrix is diagonally dominant, but I haven't seen a source to say if or why that's always true. If I find out why, though, I will amend the description. Thanks for your feedback!

HN

By the way, does the statement "but to this day, I have not been able to find a rigorous mathematical explanation for why it works" implies there is no theoretical possibility to obtain linearly independent columns for the given matrix?
Thank you

HN

MATLAB Release Compatibility
Created with R2010a
Compatible with R2010a and later releases
Platform Compatibility
Windows macOS Linux

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!