Finding Linearly dependent rows/columns
Ali
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
Rune Allnor
> 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
John D'Errico
$1...@fred.mathworks.com>...
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
Justin Abbott
message <fele9k$ltf$1...@fred.mathworks.com>...
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
John D'Errico
$rap$1...@fred.mathworks.com>...
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
Yes, but of the columns of B, which ONE is dependent?
John D'Errico
Yes, but of the columns of B, which ONE is dependent?
Randy Poe
wrote:
> "Justin Abbott" <jjabbott.NOS...@gmail.com> wrote in message <feln7p
>
> $ra...@fred.mathworks.com>...
>
>
>
> > "John D'Errico" <woodch...@rochester.rr.com> wrote in
> > message <fele9k$lt...@fred.mathworks.com>...
> > > "Ali " <muhammad....@tut.fi> wrote in message <fel8vk$qmj
> > > $...@fred.mathworks.com>...
An alternate question I was thinking of which
made more sense was "How do I identify a maximal
independent set of rows/columns?"
> 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)
Could you explain the concept behind what this
function is doing and why your statement about
block diagonals is true?
- Randy
John D'Errico
<1192130094.1...@o3g2000hsb.googlegroups.com>...
> > p = symamd(C)
>
> Could you explain the concept behind what this
> function is doing and why your statement about
> block diagonals is true?
Sorry, but its been too many years since I did much
with orderings like rcm, etc., so I can't say how it
works. Tim would be able to do so much more
accurately than would I. I'm not even certain that
amd would result in the desired block diagonal
form.
The statement about block diagonals is merely a
reflection that if the vector v1,...,vn are orthogonal
to another set of vectors, u1,...,um, then the dot
products between any of them will be zero.
If any of those dot products is not zero, so that
for some (i,j) the dot product dot(vi,uj) ~= 0,
then vi and uj will not be independent of each
other.
John
Ali
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
Steven Lord
*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
sl...@mathworks.com
Greg Heath
> "Ali " <muhammad....@tut.fi> 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
Tim Davis
...
> 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).
Greg Heath
I don't know.
If someone else doesn't reply with an answer,
try a simple test case.
Hope this helps.
Greg
Paula Olave
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
Dan Wunderli
Michel Kempkes
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
Matt
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.
Bjorn Gustavsson
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?
Matt
> 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.
Ryan Luong
Thanks
Ryan
Ali
> 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
Ryan Luong
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).
Deepesh
Abid Raza
[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
Matt J
> 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);
Abhinav
> 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
Steven Lord
"Abhinav " <thiyagaraja...@gmail.com> wrote in message
news:l6cqon$72g$1...@newscl01ah.mathworks.com...
inverse of a singular matrix DOES NOT EXIST.
If you're trying to compute the inverse to solve a system of equations,
DON'T. Use the backslash operator instead.
--
Steve Lord
sl...@mathworks.com
To contact Technical Support use the Contact Us link on
http://www.mathworks.com
Dave Stanley
For numerical matrices: https://www.mathworks.com/matlabcentral/fileexchange/64221-getlinearindependent-a-ignore-constant-shift-
For cell arrays: https://www.mathworks.com/matlabcentral/fileexchange/64222-getlinearindependentcell-a-ignore-constant-shift-
*Example usage:*
A = [1,1,1;1,2,3;4,4,4]'
[Abasis, Abasisi, Asub]= getLinearIndependent(A)
*Results:*
Input:
A =
1 1 4
1 2 4
1 3 4
Output:
Abasis =
1 1
1 2
1 3
Abasisi =
1 2
Asub =
1×2 cell array
[1,3] [2]