# Identify the minimum number of rows in a matrix meeting a condition

9 views (last 30 days)
Amirhossein Moosavi on 8 Jul 2020
Edited: Matt J on 8 Jul 2020
Hi everyone,
Please assume that I have a matrix as follows:
A = [0 1 0 0
1 1 0 0
0 0 1 0
0 0 0 1
1 0 1 1]
I would like to identify and selcet the minimum number of rows that have value of one in all columns (altoghether). For example, rows 2 and 5 are the best choice for matrix A. Do you have any suggestion?
Regards,
Amir

Matt J on 8 Jul 2020
A = [1 1 0 0
0 0 0 1
0 0 1 1]
You could argue that A([1,3],:) is the minimal selection because only those two rows contain a cluster of two [1,1] whereas all three rows contain the single-element cluster , possibly as sub-clusters of the [1,1] sequences.
On the other hand, if you make the rule that a cluster of length n cannot belong to a longer cluster of length m>n and can therefore be neighbored only by zeros, then A(2,:) is the minimal selection because now it is the only row qualifying as having a single-element cluster .
Amirhossein Moosavi on 8 Jul 2020
I am not sure if I have understood completely.

Matt J on 8 Jul 2020
Edited: Matt J on 8 Jul 2020
This solution uses the Optimization Toolbox, although I am still only half certain what row-selection rule you are looking for (see my question here).
[m,n]=size(A);
irp=1:m;
rp=randperm(m); %row permutation
irp(rp)=irp; %inverse permutation
Ap=A(rp,:);
x=optimvar('x',[1,m],'LowerBound',0,'UpperBound',1,'Type','integer');
prob=optimproblem('Objective',sum(x));
prob.Constraints=(x*Ap>=ones(1,n));
sol=solve(prob);
selection=find(round(sol.x(irp)));

Amirhossein Moosavi on 8 Jul 2020
Yes, it seems to be a solution. However, there are two problems:
1) It is not fast.
2) It is baised toward one combination when multiple combinations meet the condition. For example, see the below matrix:
A = [0 1 0 0
0 0 1 0
0 0 1 0
0 0 1 0
1 0 0 1]
Matt J on 8 Jul 2020
2) Just randomly pre-permute the rows of A (see my edited version above).
1) I find that my version is faster than yours for larger problems even when adding in the above permutation. For example, with A = randi([0,1],40,100), I find
Elapsed time is 0.193646 seconds.%Matt J
Elapsed time is 0.367822 seconds.%Amir

madhan ravi on 8 Jul 2020
Edited: madhan ravi on 8 Jul 2020
According to what I understood, see if this does what you want to do:
[a, b] = unique(A, 'rows', 'stable');
s = sum(a, 2);
rows = b(s > 1)

#### 1 Comment

Amirhossein Moosavi on 8 Jul 2020
Thanks! Unfortunately, this is not a solution for my quesiton. You would follow my above examples (1 and 2) for further clarification. If you still need more explanation, please let me know.

Amirhossein Moosavi on 8 Jul 2020
This is a code that addresses my question, but I am not sure whether it is the fastest way or not.
EG = cell(1, 100); % A place to store eligible combinations
cn1 = 1; cn2 = 1; FG = 0;
for i = 1:size(A, 2)
C = nchoosek(1:size(A, 1), cn1); % A function to create all combinations of rows (starting from the minimum number)
for j = 1:size(C, 1)
S = sum(A(C(j, :), :));
if all(S >= 1) && (sum(S) >= size(A, 2)) % The condition that I explained in my question
EG{cn2} = C(j, :);
cn2 = cn2 + 1;
FG = 1;
end
end
if FG == 1 % If at least one combination has been found, break the loop (no need to check combinations with more number of rows)
break;
end
cn1 = cn1 + 1;
end
EG(cn2:end) = [];
selection = EG{randi([1 numel(EG)])}; % Randomly select one of the eligible combinations
Do you have any suggestion to make it faster?

Matt J on 8 Jul 2020
My method is faster for larger problems. For this matrix,
A = randi([0,1],40,100);
I obtain these timings,
Elapsed time is 0.193646 seconds.%Matt J
Elapsed time is 0.367822 seconds.%Amir
Amirhossein Moosavi on 8 Jul 2020
Thank you so much for your kind help!