Thread Subject:

Finding Linearly dependent rows/columns

Hi!

Inverse of a m x n matrix A when matrix is rank deficient
and I can be find it using rank(A). However, I don't know
how to find which rows/columns of the matrix are linearly
dependent. I m sure there must be a way to find this. Can
any body help me with this?

Thanks,

Ali

On 11 Okt, 15:37, "Ali " <muhammad....@tut.fi> wrote:
> Hi!
>
> Inverse of a m x n matrix A when matrix is rank deficient
> and I can be find it using rank(A). However, I don't know
> how to find which rows/columns of the matrix are linearly
> dependent.

Both the QR decomposition and Singular Value Decomposition
come to mind?

Rune

"Ali " <muhammad.ali@tut.fi> wrote in message <fel8vk$qmj
$1@fred.mathworks.com>...
> Hi!
>
> Inverse of a m x n matrix A when matrix is rank deficient
> and I can be find it using rank(A). However, I don't know
> how to find which rows/columns of the matrix are linearly
> dependent. I m sure there must be a way to find this. Can
> any body help me with this?

A = randn(9,10);
B = A'*A;

rank(B) == 9

Which columns of B are dependent?

Answer: all of them. Any column can be written as a
linear combination of the rest.

John

"John D'Errico" <woodchips@rochester.rr.com> wrote in
message <fele9k$ltf$1@fred.mathworks.com>...
> "Ali " <muhammad.ali@tut.fi> wrote in message <fel8vk$qmj
> $1@fred.mathworks.com>...
> > Hi!
> >
> > Inverse of a m x n matrix A when matrix is rank
deficient
> > and I can be find it using rank(A). However, I don't
know
> > how to find which rows/columns of the matrix are
linearly
> > dependent. I m sure there must be a way to find this.
Can
> > any body help me with this?
>
> A = randn(9,10);
> B = A'*A;
>
> rank(B) == 9
>
> Which columns of B are dependent?
>
> Answer: all of them. Any column can be written as a
> linear combination of the rest.
>
> John
>

John --

I am not sure I understand the entire meaning of your
post. What about an example like this?

A = eye(9);
B = [A(:,1) A];

rank(B) == 9

However it is not true that any column in B is a linear
combination of the rest, e.g. B(:,10) is linearly
independent of the first 9.

-Justin

"Justin Abbott" <jjabbott.NOSPAM@gmail.com> wrote in message <feln7p
$rap$1@fred.mathworks.com>...
> "John D'Errico" <woodchips@rochester.rr.com> wrote in
> message <fele9k$ltf$1@fred.mathworks.com>...
> > "Ali " <muhammad.ali@tut.fi> wrote in message <fel8vk$qmj
> > $1@fred.mathworks.com>...
> > > Hi!
> > >
> > > Inverse of a m x n matrix A when matrix is rank
> deficient
> > > and I can be find it using rank(A). However, I don't
> know
> > > how to find which rows/columns of the matrix are
> linearly
> > > dependent. I m sure there must be a way to find this.
> Can
> > > any body help me with this?
> >
> > A = randn(9,10);
> > B = A'*A;
> >
> > rank(B) == 9
> >
> > Which columns of B are dependent?
> >
> > Answer: all of them. Any column can be written as a
> > linear combination of the rest.
> >
> > John
> >
>
> John --
>
> I am not sure I understand the entire meaning of your
> post. What about an example like this?
>
> A = eye(9);
> B = [A(:,1) A];
>
> rank(B) == 9
>
> However it is not true that any column in B is a linear
> combination of the rest, e.g. B(:,10) is linearly
> independent of the first 9.
>
> -Justin

Yes, but of the columns of B, which ONE is dependent?
Is it column 1 or column 2? I had the impression that
you were looking for a single column which is dependent
on the rest, at least from your original question.

All that you can do in general is list a group of columns
which when taken together form a dependent set.

If you wish to find those subsets of columns which are
dependent, then form

  C = B'*B

if you can now symmetricaly permute the rows and
columns of C, such that it is block diagonal, with
zeros in the off diagonal blocks, then each block
represents one such dependent set of vectors.

A = eye(4);
B = [A(:,1)+2*A(:,4) A];

C = B'*B

C =
     5 1 0 0 2
     1 1 0 0 0
     0 0 1 0 0
     0 0 0 1 0
     2 0 0 0 1

p = symamd(C)
p =
     2 1 5 3 4

C(p,p)
ans =
     1 1 0 0 0
     1 5 2 0 0
     0 2 1 0 0
     0 0 0 1 0
     0 0 0 0 1

John

"Justin Abbott" <jjabbott.NOSPAM@gmail.com> wrote in message <feln7p
$rap$1@fred.mathworks.com>...
> "John D'Errico" <woodchips@rochester.rr.com> wrote in
> message <fele9k$ltf$1@fred.mathworks.com>...
> > "Ali " <muhammad.ali@tut.fi> wrote in message <fel8vk$qmj
> > $1@fred.mathworks.com>...
> > > Hi!
> > >
> > > Inverse of a m x n matrix A when matrix is rank
> deficient
> > > and I can be find it using rank(A). However, I don't
> know
> > > how to find which rows/columns of the matrix are
> linearly
> > > dependent. I m sure there must be a way to find this.
> Can
> > > any body help me with this?
> >
> > A = randn(9,10);
> > B = A'*A;
> >
> > rank(B) == 9
> >
> > Which columns of B are dependent?
> >
> > Answer: all of them. Any column can be written as a
> > linear combination of the rest.
> >
> > John
> >
>
> John --
>
> I am not sure I understand the entire meaning of your
> post. What about an example like this?
>
> A = eye(9);
> B = [A(:,1) A];
>
> rank(B) == 9
>
> However it is not true that any column in B is a linear
> combination of the rest, e.g. B(:,10) is linearly
> independent of the first 9.
>
> -Justin

Yes, but of the columns of B, which ONE is dependent?
Is it column 1 or column 2? I had the impression that
you were looking for a single column which is dependent
on the rest, at least from your original question.

All that you can do in general is list a group of columns
which when taken together form a dependent set.

If you wish to find those subsets of columns which are
dependent, then form

  C = B'*B

if you can now symmetricaly permute the rows and
columns of C, such that it is block diagonal, with
zeros in the off diagonal blocks, then each block
represents one such dependent set of vectors.

A = eye(4);
B = [A(:,1)+2*A(:,4) A];

C = B'*B

C =
     5 1 0 0 2
     1 1 0 0 0
     0 0 1 0 0
     0 0 0 1 0
     2 0 0 0 1

p = symamd(C)
p =
     2 1 5 3 4

C(p,p)
ans =
     1 1 0 0 0
     1 5 2 0 0
     0 2 1 0 0
     0 0 0 1 0
     0 0 0 0 1

John

"Justin Abbott" <jjabbott.NOSPAM@gmail.com> wrote in message <feln7p
$rap$1@fred.mathworks.com>...
> "John D'Errico" <woodchips@rochester.rr.com> wrote in
> message <fele9k$ltf$1@fred.mathworks.com>...
> > "Ali " <muhammad.ali@tut.fi> wrote in message <fel8vk$qmj
> > $1@fred.mathworks.com>...
> > > Hi!
> > >
> > > Inverse of a m x n matrix A when matrix is rank
> deficient
> > > and I can be find it using rank(A). However, I don't
> know
> > > how to find which rows/columns of the matrix are
> linearly
> > > dependent. I m sure there must be a way to find this.
> Can
> > > any body help me with this?
> >
> > A = randn(9,10);
> > B = A'*A;
> >
> > rank(B) == 9
> >
> > Which columns of B are dependent?
> >
> > Answer: all of them. Any column can be written as a
> > linear combination of the rest.
> >
> > John
> >
>
> John --
>
> I am not sure I understand the entire meaning of your
> post. What about an example like this?
>
> A = eye(9);
> B = [A(:,1) A];
>
> rank(B) == 9
>
> However it is not true that any column in B is a linear
> combination of the rest, e.g. B(:,10) is linearly
> independent of the first 9.
>
> -Justin

Yes, but of the columns of B, which ONE is dependent?
Is it column 1 or column 2? I had the impression that
you were looking for a single column which is dependent
on the rest, at least from your original question.

All that you can do in general is list a group of columns
which when taken together form a dependent set.

If you wish to find those subsets of columns which are
dependent, then form

  C = B'*B

if you can now symmetricaly permute the rows and
columns of C, such that it is block diagonal, with
zeros in the off diagonal blocks, then each block
represents one such dependent set of vectors.

A = eye(4);
B = [A(:,1)+2*A(:,4) A];

C = B'*B

C =
     5 1 0 0 2
     1 1 0 0 0
     0 0 1 0 0
     0 0 0 1 0
     2 0 0 0 1

p = symamd(C)
p =
     2 1 5 3 4

C(p,p)
ans =
     1 1 0 0 0
     1 5 2 0 0
     0 2 1 0 0
     0 0 0 1 0
     0 0 0 0 1

John

"John D'Errico" <woodchips@rochester.rr.com> wrote in
message <fels15$o47$1@fred.mathworks.com>...
> "Justin Abbott" <jjabbott.NOSPAM@gmail.com> wrote in
message <feln7p
> $rap$1@fred.mathworks.com>...
> > "John D'Errico" <woodchips@rochester.rr.com> wrote in
> > message <fele9k$ltf$1@fred.mathworks.com>...
> > > "Ali " <muhammad.ali@tut.fi> wrote in message
<fel8vk$qmj
> > > $1@fred.mathworks.com>...
> > > > Hi!
> > > >
> > > > Inverse of a m x n matrix A when matrix is rank
> > deficient
> > > > and I can be find it using rank(A). However, I
don't
> > know
> > > > how to find which rows/columns of the matrix are
> > linearly
> > > > dependent. I m sure there must be a way to find
this.
> > Can
> > > > any body help me with this?
> > >
> > > A = randn(9,10);
> > > B = A'*A;
> > >
> > > rank(B) == 9
> > >
> > > Which columns of B are dependent?
> > >
> > > Answer: all of them. Any column can be written as a
> > > linear combination of the rest.
> > >
> > > John
> > >
> >
> > John --
> >
> > I am not sure I understand the entire meaning of your
> > post. What about an example like this?
> >
> > A = eye(9);
> > B = [A(:,1) A];
> >
> > rank(B) == 9
> >
> > However it is not true that any column in B is a linear
> > combination of the rest, e.g. B(:,10) is linearly
> > independent of the first 9.
> >
> > -Justin
>
> Yes, but of the columns of B, which ONE is dependent?
> Is it column 1 or column 2? I had the impression that
> you were looking for a single column which is dependent
> on the rest, at least from your original question.
>
> All that you can do in general is list a group of columns
> which when taken together form a dependent set.
>
> If you wish to find those subsets of columns which are
> dependent, then form
>
> C = B'*B
>
> if you can now symmetricaly permute the rows and
> columns of C, such that it is block diagonal, with
> zeros in the off diagonal blocks, then each block
> represents one such dependent set of vectors.
>
> A = eye(4);
> B = [A(:,1)+2*A(:,4) A];
>
> C = B'*B
>
> C =
> 5 1 0 0 2
> 1 1 0 0 0
> 0 0 1 0 0
> 0 0 0 1 0
> 2 0 0 0 1
>
> p = symamd(C)
> p =
> 2 1 5 3 4
>
> C(p,p)
> ans =
> 1 1 0 0 0
> 1 5 2 0 0
> 0 2 1 0 0
> 0 0 0 1 0
> 0 0 0 0 1
>
> John

Hi!

I do not understand your solution and what I can get out of
there. I want to know is there a way to get the index
number of the rows which are linearly dependent or
conversely the index of rows which are linearly
independent. In that way I can seperate those rows and
proceed with the inverse of rest of the augumented matrix.

Thanks,

Ali

"Ali " <muhammad.ali@tut.fi> wrote in message
news:fenebk$ici$1@ginger.mathworks.com...

*snip*

> I do not understand your solution and what I can get out of
> there. I want to know is there a way to get the index
> number of the rows which are linearly dependent or
> conversely the index of rows which are linearly
> independent. In that way I can seperate those rows and
> proceed with the inverse of rest of the augumented matrix.

Don't split apart the matrix like this just to invert a submatrix that is of
full rank. Don't invert a matrix unless you ABSOLUTELY, POSITIVELY have to
do so. If you're trying to invert the matrix to solve a system of
equations, use backslash (\) instead.

--
Steve Lord
slord@mathworks.com

On Oct 15, 2:11 pm, "Tim Davis" <da...@cise.ufl.edu> wrote:
> Greg Heath <he...@alumni.brown.edu> wrote in message
> ...
>
>
>
>
>
> > Furthermore, when A is rank deficient, the BACKSLASH
> > solution will be a "BASIC" solution that contains zero
> > coefficients corresponding to variables that could be
> > considered to be "the most dependent". However, the
> > selection is completely based on partial pivoting
> > strategy using the QR algorithm and may not have a
> > corresponding causal or scientific explanation.
> > It may be helpful to search the CSSM archives in
> > Google groups with
>
> > greg-heath basic solution
>
> > The groups of dependent variables can be deduced from
> > the components of the null singular vector solutions
> > to A*x = 0.
>
> > Hope this helps.
>
> > Greg
>
> Does this apply just when backslash uses a dense QR
> factorization? Or does the sparse QR as used by backslash
> also give a basic solution when A is rank deficient? Sparse
> QR doesn't do any column pivoting, so A\b for sparse
> rectangular rank deficient A doesn't either (well, it does
> do column pivoting for sparsity, but not for numerical
> reasons, which is the issue here).

I don't know.

If someone else doesn't reply with an answer,
try a simple test case.

Hope this helps.

Greg

"Ali " <muhammad.ali@tut.fi> wrote in message
<fel8vk$qmj$1@fred.mathworks.com>...
> Hi!
>
> Inverse of a m x n matrix A when matrix is rank deficient
> and I can be find it using rank(A). However, I don't know
> how to find which rows/columns of the matrix are linearly
> dependent. I m sure there must be a way to find this. Can
> any body help me with this?
>
> Thanks,
>
> Ali

I found which are linearly dependent rows.

I modify the rref function

function [A,jb,b] = rrefs(A,tol)

% Copyright 1984-2004 The MathWorks, Inc.
% $Revision: 5.9.4.2 $ $Date: 2004/04/10 23:30:09 $

b is the new out
  
[m,n] = size(A);
b=1:m;
% Does it appear that elements of A are ratios of small
integers?
[num, den] = rat(A);
rats = isequal(A,num./den);

% Compute the default tolerance if none was provided.
if (nargin < 2), tol = max(m,n)*eps(class(A))*norm(A,'inf'); end

% Loop over the entire matrix.
i = 1;
j = 1;
jb = [];
xb=[];
while (i <= m) && (j <= n)
   % Find value and index of largest element in the
remainder of column j.
   [p,k] = max(abs(A(i:m,j)));
   k = k+i-1;
   if (p <= tol)
      % The column is negligible, zero it out.
      A(i:m,j) = zeros(m-i+1,1);
      j = j + 1;
   else
      % Remember column index
      jb = [jb j];
     
      % Swap i-th and k-th rows.
      
      >>>>>>b([i k])=b([k i]);<<<<<<< The modification
      A([i k],j:n) = A([k i],j:n);
      % Divide the pivot row by the pivot element.
      A(i,j:n) = A(i,j:n)/A(i,j);
      % Subtract multiples of the pivot row from all the
other rows.
     
      for k = [1:i-1 i+1:m]
         A(k,j:n) = A(k,j:n) - A(k,j)*A(i,j:n);
      end
      i = i + 1;
      j = j + 1;
   end
end

% Return "rational" numbers if appropriate.
if rats
    [num,den] = rat(A);
    A=num./den;
end


if c=rank(A)<m

the linearly dependent rows are b(c+1:m)

I hope that this help you

Thanks Paula, you're an Angel!

"Ali " <muhammad.ali@tut.fi> wrote in message <fel8vk$qmj$1@fred.mathworks.com>...
> Hi!
>
> Inverse of a m x n matrix A when matrix is rank deficient
> and I can be find it using rank(A). However, I don't know
> how to find which rows/columns of the matrix are linearly
> dependent. I m sure there must be a way to find this. Can
> any body help me with this?
>
> Thanks,
>
> Ali

I had the same problem. Here's how I find linearly dependent rows of matrix A:

[c,d]=lu(A);
c(find(c~=0))=1;
column_sum=sum(c);
check_columns=find(column_sum>1);
for m=1:length(check_columns)
    dependentrows=find(c(:,check_columns(m))>0);
end

every time the loop is evaluated, it will return the row-numbers that are linearly dependent on each other. Of course it can happen that one row is a linear combination of several other rows, but using something like setdiff or union, these should be easy to find. It might not be the most elegant way, but it works. I hope this helps,

Michel

"Ali " <muhammad.ali@tut.fi> wrote in message <fel8vk$qmj$1@fred.mathworks.com>...
> Hi!
>
> Inverse of a m x n matrix A when matrix is rank deficient
> and I can be find it using rank(A). However, I don't know
> how to find which rows/columns of the matrix are linearly
> dependent. I m sure there must be a way to find this. Can
> any body help me with this?

The following will do what you are asking for, but as Steve said what you're asking for is probably not what you really want.

[R,licols]=rref(A);

The resulting vector licols will index a full rank subset of the columns of A.

"Steven Lord" <slord@mathworks.com> wrote in message <fenst8$ju3$1@fred.mathworks.com>...
>
> "Ali " <muhammad.ali@tut.fi> wrote in message
> news:fenebk$ici$1@ginger.mathworks.com...
>
> *snip*
>
> > I do not understand your solution and what I can get out of
> > there. I want to know is there a way to get the index
> > number of the rows which are linearly dependent or
> > conversely the index of rows which are linearly
> > independent. In that way I can seperate those rows and
> > proceed with the inverse of rest of the augumented matrix.
>
> Don't split apart the matrix like this just to invert a submatrix that is of
> full rank. Don't invert a matrix unless you ABSOLUTELY, POSITIVELY have to
> do so. If you're trying to invert the matrix to solve a system of
> equations, use backslash (\) instead.
>
This is an advice I have failed to understand for a long time. When applied to under-determined systems of equation I would feel very nervous about applying \ (or pinv for that matter). I typically deal with under-determined systems with noise on the right-hand side and always go the route of SVD and then look at the eigenvalues, base-vectors, resolution matrix and null-space. Without doing this I wont know how or what noise would creep into the solutions and I cant choose proper truncation/damping.

This might be a completely contrarian view on equation solving in matlab, but I don't understand how I could justify other methods to solve under-determined problems. Am I missing something obvious?

"Bjorn Gustavsson" <bjonr@irf.se> wrote in message <gmk68h$9jp$1@fred.mathworks.com>...

> This might be a completely contrarian view on equation solving in matlab, but I don't understand how I could justify other methods to solve under-determined problems. Am I missing something obvious?

I'm pretty sure that Steve was talking about over-determined systems (i.e. more matrix rows than columns).

Often, people who are only accustomed to inverting square matrices to solve linear systems will think the only good path to a solution is to weed out the redundant rows.

could you clarify this for me: is the system Ax = 0, where A known to be rank deficient, equivalent to: rref(A)x = 0?
Thanks
Ryan

"Ryan Luong" <vu.luong@imperial.ac.uk> wrote in message <hogufu$sb7$1@fred.mathworks.com>...
> could you clarify this for me: is the system Ax = 0, where A known to be rank deficient, equivalent to: rref(A)x = 0?
> Thanks
> Ryan

Hi!

The way to solve such system depends what you are looking to solve and may be what is your background. In my case it is a Jacobian matrix describing the configuration of a robot. If I have linearly dependent columns I know that one or more joints of the robot do not contribute to my solution any more. However, I can continue the motion of the rest of the joints and robot by removing the linearly dependent columns and temporarily deactivating those joints. I appriciate all the help but so far I did not manage to find the solution.

Ali

I'm a learning how to solve a large-scale constraint optimization prob with both linear constrait and nonlinear costraint therefore I'm very interested in this topic. I treat linear constraints seperately, and discuss it here:
My initial constraint Jacobian is rank deficient (linearly dependent rows, ie. some constraints are redundant) therefore I need to do some preprocessing before parsing it to the solver. If I have a set of linear constraints of the form Ax=b (in my case, b=0) then the redundant constraints are basically the linearly dependent rows in A. Therefore redundant constraints can be removed by reducing linear dependent rows in A. And this can be done by **rref(A)** in MATLAB, to make ** [rref(A)]x = 0 ** equivalent to the system *Ax=0* ? << I understand this way but not very confident, please comment on this.

>If I have linearly dependent columns I know that one or more joints of the robot do not contribute to my solution any more. However, I can continue the motion of the rest of the joints and robot by removing the linearly dependent columns and temporarily deactivating those joints.
> Ali
In this case I guess first you need to do the preprocess for linear dependent rows as I said above. Secondly, you are interested in linear dependent columns. There is techniques to reduce the lin. dep. col. that is described in:
http://optlab.mcmaster.ca/index2.php?option=com_docman&task=doc_view&gid=30&Itemid=92
but I'm not sure if you really want it because it seems to reduce the variables x(j), x(k) corresponding to lin. dep. col a(:,j), a(:,k).

Thanks, Paula.

"Ali" wrote in message <fel8vk$qmj$1@fred.mathworks.com>...
> Hi!
>
> Inverse of a m x n matrix A when matrix is rank deficient
> and I can be find it using rank(A). However, I don't know
> how to find which rows/columns of the matrix are linearly
> dependent. I m sure there must be a way to find this. Can
> any body help me with this?
>
> Thanks,
>
> Ali


Here is very simple method to extract the Linearly Independent Columns of a Martix W


[r c] = size (W);
j=1;
for i=1:c
    if rank (W (:,1:i)) == j;
        P(:,j) = W(:,i);
        j = j+1;
    else
    end
end

"Abid Raza" wrote in message <ka279l$c8q$1@newscl01ah.mathworks.com>...
>
> Here is very simple method to extract the Linearly Independent Columns of a Martix W
>
>
> [r c] = size (W);
> j=1;
> for i=1:c
> if rank (W (:,1:i)) == j;
> P(:,j) = W(:,i);
> j = j+1;
> else
> end
> end
================

This can be a bit unreliable, in part due to some of the quirks of the RANK command. For example, for this W

  W=[1e-16, 1; 1e-16 2]

many people would consider the 2nd column to be the only independent one, but your code returns the first one.


Here is a routine that I recommend:


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);