Asked by Kees Roos
on 5 Oct 2012

Let A be an m by n matrix whose rows are linearly dependent. I want to remove rows from A such that the rank does not decrease. How can I find such rows of A?

Answer by Matt J
on 5 Oct 2012

Accepted Answer

function [Xsub,idx]=licols(X,tol)

%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

if ~nnz(X) %X has no non-zeros and hence no independent columns

Xsub=[]; idx=[];

return

end

if nargin<2, tol=1e-10; end

[Q, R, E] = qr(X,0);

if ~isvector(R)

diagr = abs(diag(R));

else

diagr = R(1);

end

%Rank estimation

r = find(diagr >= tol*diagr(1), 1, 'last'); %rank estimation

idx=sort(E(1:r));

Xsub=X(:,idx);

Matt J
on 28 Jun 2014

mohsen,

When I do plot(svd(docoeff)), I get the plot below, which to my eye says that the rank of your matrix is well below 200.

Nevertheless, if you do consider such tiny singular values significant, you can set the rank threshold lower

>> X=licols(docoeff,1e-15); whos X

Name Size Bytes Class Attributes

X 398x225 716400 double

mohsen
on 28 Jun 2014

I calculate rank with Matlab rank() function. it says the rank is 225

I must decrease raws from 398 to 261 without decreasing rnak,and you said the licols function removes raws ,but it removes columns.

Matt J
on 28 Jun 2014

Matlab's rank() function is not to be trusted blindly (as you can see from my previous plot). If nothing else, rank is subjectively dependent on the tolerance parameter that you use, just like I showed you that licols is. You chose to use the default tolerance, but a different choice would give you a different result, e.g.,

>> rank(docoeff,2)

ans =

203

I did not say that licols() removes rows. The help text clearly says that it removes columns. However, you can certainly use it to remove rows by transposing:

>> X=licols(docoeff.').'; whos X

Name Size Bytes Class Attributes

X 160x225 288000 double

Sign in to comment.

Answer by Jos (10584)
on 24 Jan 2014

Another, very straightforward, approach is to include them one by one and observe the changes in rank … (I agree that this is not so elegant!).

N = size(A,1) ; % number of rows

IncludeTF = false(N,1) ; % by default, exclude all rows, except ...

IncludeTF(1) = true ; % first row which can always be included

R0 = rank(A) ; % the original rank

for k = 2:N, % loop over all rows

B = A(IncludeTF,:) ; % select the currently included rows of A

IncludeTF(k) = rank(B) < R0 ; % include in B when the rank is less

end

isequal(rank(B), R0) % check!

Jeel Bhavsar
on 24 Nov 2018

I have the same question with gf matrix.Does this code work for gf(galois field) matrix?

Sign in to comment.

Answer by Arash Rabbani
on 24 Aug 2019

This is a shorter version of Jos solution if you needed:

R1=1;

for I=1:size(A,1)

R2=rank(A(1:I,:));

if R2~=R1; disp(I); end

R1=R2+1;

end

Arash Rabbani
on 24 Aug 2019

It displays the rows with linear dependany to other rows.

Sign in to comment.

Opportunities for recent engineering grads.

Apply Today
## 0 Comments

Sign in to comment.