Finding all possible row combinations of a matrix that add to zero
2 views (last 30 days)
Show older comments
Hello,
I'm looking for a general way to find all possible row combinations of a matrix that add to zero.
For instance, for the matrix
A = [-1 0 0 ; 1 0 0 ; 1 -1 0 ; 0 1 -1 ; 0 1 -1; 0 0 1];
the following 6 row combinations would all sum to zero
A(1,:)+A(2,:)
A(1,:)+A(3,:)+A(4,:)+A(6,:)
A(1,:)+A(3,:)+A(5,:)+A(6,:)
-A(2,:)+A(3,:)+A(4,:)+A(6,:)
-A(2,:)+A(3,:)+A(5,:)+A(6,:)
-A(4,:)+A(5,:)
Does MATLAB have any built-in functions that can help me do this? Generating all possible row combinations and testing to see which ones sum to zero seems like it would be extremely computationally intensive.
Thanks,
Kevin
0 Comments
Accepted Answer
Azzi Abdelmalek
on 21 Feb 2013
Edited: Azzi Abdelmalek
on 21 Feb 2013
Edit2
A = [-1 0 0 ; 1 0 0 ; 1 -1 0 ; 0 1 -1 ; 0 1 -1; 0 0 1];
n=size(A,1);
idx=logical(npermutek([0 1],n));
p=size(idx,1);
out=cell(p,1);
for k=1:p
out{k}=sum(A(idx(k,:),:),1);
end
You can get you sum in a matrix 647x3
M=cell2mat(out)
npermutek is a Matt Fig submission at http://www.mathworks.com/matlabcentral/fileexchange/11462-npermutek/content/npermutek.m
5 Comments
Azzi Abdelmalek
on 21 Feb 2013
Edited: Azzi Abdelmalek
on 21 Feb 2013
There is another error, it's
sum(A(idx(k,:),:),1)
instead of
sum(A(idx(k,:),:)
Look at the second Edit
More Answers (4)
Azzi Abdelmalek
on 21 Feb 2013
Edited: Azzi Abdelmalek
on 21 Feb 2013
Ok try this
Edit
A = [-1 0 0 ;1 0 0; 1 -1 0 ; 0 1 -1 ; 0 1 -1; 0 0 1];
n=size(A,1)
idx1=npermutek([0 -1 1],n);
p=size(idx1,1);
out=cell(p,1);
for k=1:p
out{k}=sum(bsxfun(@times,A,idx1(k,:)'),1);
end
M=cell2mat(out)
find(~any(M,2))
10 Comments
Azzi Abdelmalek
on 21 Feb 2013
Ok, You did not specify that in your question. You should give all information in your question to avoid wasting of time.
Azzi Abdelmalek
on 21 Feb 2013
Try this
A = [-1 0 0 ;1 0 0; 1 -1 0 ; 0 1 -1 ; 0 1 -1; 0 0 1];
n=size(A,1)
idx1=npermutek([0 -1 1],n);
p=size(idx1,1);
out=cell(p,1);
for k=1:p
out{k}=sum(bsxfun(@times,A,idx1(k,:)'),1);
end
M=cell2mat(out)
ii=find(~any(M,2))
idx2=idx1(ii,:)
for k=1:size(idx2,1)
jj{k}=find(idx2(k,:))
end
for k=1:numel(jj)
iddx{k}=find(cellfun(@(x) isequal(x,jj{k}),jj))
ee(k)=iddx{k}(1)
end
result=idx2(unique(ee),:)
Azzi Abdelmalek
on 22 Feb 2013
Edited: Azzi Abdelmalek
on 22 Feb 2013
Try this code
A = [-1 0 0 ;1 0 0; 1 -1 0 ; 0 1 -1 ; 0 1 -1; 0 0 1];
n=size(A,1)
idx1=npermutek([0 -1 1],n);
p=size(idx1,1);
out=cell(p,1);
for k=1:p
out{k}=sum(bsxfun(@times,A,idx1(k,:)'),1);
end
M=cell2mat(out);
ii=find(~any(M,2));
idx2=idx1(ii,:);
for k=1:size(idx2,1);
jj{k}=find(idx2(k,:));
end
for k=1:numel(jj);
iddx{k}=find(cellfun(@(x) isequal(x,jj{k}),jj));
ee(k)=iddx{k}(1);
end
result=idx2(unique(ee),:);
n=size(result,1);
test=0;
ii=1;
while test==0
ii=ii+1;
a=find(result(ii,:));
c=result(ii,a);
e=result(:,a);
f=find(ismember(e,c,'rows'));
f(1)=[];
if ~isempty(f);
result(f,:)=[];
n=n-1;
end
if ii==n-1
test=1;
end
end
result
See Also
Categories
Find more on Matrix Indexing in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!