How to find vectors that are multiple of other vectors inside a matrix

For example, given following matrix:

F = [0 1 2; 1 2 3; 0 2 4; 5 6 8; 2 4 6];

     0     1     2
     1     2     3
     0     2     4
     5     6     8
     2     4     6

Wrong:Identify the rows that are (integer) multiples of some previous rows in the matrix.

In this case 3rd row and 5th row are multiple respectively of 1st and 2nd rows.

• I want to copy the identified rows and create a new matrix out of it.
• Delete the identified rows from the original matrix.

Edit:

Correct: The matrix is composed by integers, each element correspond to a part in weight of a substance so what matters is the proportion, the objective is to delete from the original matrix all the rows that have same proportion of elements. Doesn't matter rows order.

Inside the matrix we could find N rows that are multiple of others, I have to eliminate all of them except one the one that is multiple of 1.

So if I have two rows like this (I made them consecutive to simplify):

2  4  6
1  2  3

I should eliminate one of them, better in this case to delete first row so I can keep the row which is multiplied by one.

Answer 1

[John D'Errico]

This is way easier than it has been made to be.

F = [0 1 2; 1 2 3; 0 2 4; 5 6 8; 2 4 6];

Assuming you have a recent release of MATLAB, do this:

Fscale = F./max(abs(F),[],2)
Fscale =
                       0                       0.5                         1
       0.333333333333333         0.666666666666667                         1
                       0                       0.5                         1
                   0.625                      0.75                         1
       0.333333333333333         0.666666666666667                         1

That scales the elements of F such that the MAXIMUM absolute element in any row is 1.

An older MATLAB release would have you write it as:

Fscale = bsxfun(@rdivide,F,max(abs(F),[],2));

Now, just look for replicate rows. uniquetol will suffice to solve the problem now.

[UniqF,I,J] = uniquetol(Fscale,10*eps,'byrows',true)
UniqF =
                         0                       0.5                         1
         0.333333333333333         0.666666666666667                         1
                     0.625                      0.75                         1
I =
     1
     2
     4
J =
     1
     2
     1
     3
     2

So these rows of F were scaled versions of some other row:

Frep = F;
Frep(I,:) = []
Frep =
   0     2     4
   2     4     6

We can look at the vector J to see that rows 1 and 3, and rows 2 and 5 appear twice. Those rows were multiples of each other. I suppose you could go further, and verify if the multiplier was an INTEGER factor easily enough. I don't know your real goal in this. Is it homework? If so, then they might slip in a row that is a factor of 2.5 times another, just to test your code.

If you want to discard all rows with a multiplier greater than 1? We can find ways to do that too.

[Stephen23]

+1 neat solution. Would need a special case for rows of zeros.

[Marco Salvo Cottone]

Yes it's homework, your solution is great, and incredibly simple, it also looks extremely efficient expecially on the memory side compared to the other solutions posted before.

Yes discarding the rows with multiplier greater rather than the others would be better. I'm going to test this with a very big matrix to see if it can handle speed and memory.

[Jan]

+1, the initial scaling is a smart idea.

[Marco Salvo Cottone]

Ok tested this on a big matrix, to do this I used permutations with repetition.

Used permn script by Jos:

F = permn(0:10,6);
F(1,:) =[]; % Delete this cause it contains only zeros

F is 1771560x6
Frep is 51415x6

Uniquetol takes a while to calculate around 8 minutes, but it is undestandable considering the size of the matrix. The other methods fail completely cause they have exponential memory requirements.

% Deleted Repetitions.

G = F;
G(ismember(G,Frep,'rows'),:)=[];

[John D'Errico]

I'm surprised that uniquetol is so slow. Were this not homework, you could probably use my consolidator to do some of the work. It has similar capabilities to uniquetol.

X= randi(10,[1e6,6]);
Xscale = X./max(abs(X),[],2);
XscaleU = consolidator(Xscale);
tic,[XscaleU,~,ind] = consolidator(Xscale);toc

Elapsed time is 1.298153 seconds.

whos XscaleU
Name              Size               Bytes  Class     Attributes
XscaleU      625689x6             30033072  double

So it reduced 1e6 rows down into 625689 in roughly a second.

I just tried the same with uniquetol, and it is still running. A bit surprising at that.

[Marco Salvo Cottone]

Yes I thought it was faster too, but works.

Well your consolidator seems to be the killer choice for this kind of operation.

[Andrei Bobrov]

Nice! +1

Answer 2

[Pawel Jastrzebski]

I think this will get you going. This code will help you identify which 'NextRow' is a multiplier of 'previousRow':

% DATA
F = [0 1 2; 1 2 3; 0 2 4; 5 6 8; 2 4 6]

% creating a matrix of conditions to be checked
% condition: is next row a multiplier of previous

nR = 2:size(F,1); 
pR = 1:size(F,1)-1;

c1 = repelem(nR,pR)';
c2 = [];

for i=1:numel(pR)
    ctemp = 1:i;
    c2 = [c2 ctemp];
end

% 'c' holds all the cases that needs to be checked
c = [c1 c2'];

% clean the mess
clear c1 c2 ctemp i nR pR;

% 'R' results - true if next row is multiplier of a previous
R = sum(mod(F(c(:,1),:),F(c(:,2),:)),2) == 0;

% store conditions and the result in the table for convenience
t = table(c(:,1),c(:,2), R);
t.Properties.VariableNames= {'nextRow', 'previousRow','IsNextMultiOfPrevious'}

% clean the mess
clear c R;

The outcome:

t =

    10×3 table

      nextRow    previousRow    IsNextMultiOfPrevious
      _______    ___________    _____________________

         2            1                 false        
         3            1                 true         
         3            2                 false        
         4            1                 false        
         4            2                 false        
         4            3                 false        
         5            1                 false        
         5            2                 true         
         5            3                 false        
         5            4                 false

[Stephen23]

It seems that this code does not check to make sure that the row elements are multiplied by the same integer. Unfortunately the example values in the question do not cover this, but my understanding is that the row should be multiplied by one scalar integer. Try it with

1  2  3
3  2  6

Of course this is for the OP to decide, if this is acceptable or not.

[Pawel Jastrzebski]

Thanks for pointing out - I missed this bit.

[Andrei Bobrov]

Nice! But if F:

F = [0  1  2
2  4  6
1  2  3
0  2  4
5  6  8];

[Pawel Jastrzebski]

True. But the multiplier was supposed to be an integer and in your case Row 3 is an instance of Row 2 but the multiplier is 0.5 - at least if you stay true to the requirement that you only look at comparing any given row with the previous ones.

[Marco Salvo Cottone]

Andrei Bobrov made a good point, the details I wrote were incorrect, and not true to the original question: "How to find vectors that are multiple of other vectors inside a matrix".

I'm correcting the question and adding details.

[Jan]

The clearing does not have benefits in Matlab, except for some huge arrays, which would exhaust the memory. Usually clearing variables reduces the processing speed only.

Answer 3

[Andrei Bobrov]

n = size(F,1);
[x,~] = ndgrid(1:n);
l = tril(x,-1);
u = tril(x',-1);
ii = [u(u~=0),l(l~=0)];
R = arrayfun(@(x)rank([F(ii(x,1),:);F(ii(x,2),:)]),1:size(ii,1))' == 1;
out = table(ii,R,'v',{'rows','rank'});

corrected

s = size(F);
F1 = sortrows(F,-(1:s(2)));

[x,~] = ndgrid(1:s(1));
l = tril(x,-1);
u = tril(x',-1);
ii = [u(u~=0),l(l~=0)];
R = arrayfun(@(x)rank([F1(ii(x,1),:);F1(ii(x,2),:)]),1:size(ii,1))' == 1;

F_out = F1(~ismember((1:n)',ii(R,2)),:)

[Marco Salvo Cottone]

Both code works. I've corrected and updated the question.