Find complementary column combination of a matrix

Hello! Need your help!

I have a 30x9 matrix A filled with 0, 4, 8.

Get the matrix MaxA where A has its maxima per row:

V = max(A,[ ],2);
MaxA = A==V;

And now i want the indices of the minimum combination of colmuns that gets me a complete column filled with 1, so after all the most complementary columns.

Example:

A = [8 4 0 8 8                   [1 0 0 1 1
     4 8 0 8 0            MaxA =  0 1 0 1 0         
     4 0 4 0 0]                   1 0 1 0 0]

-> column 1 and 2 of MaxA give me

Result = [1 2  (column 1 and 2)                                  
          1 4  (column 1 and 4)      -> give me a column with [1; 1; 1]
          3 4] (column 3 and 4) 

-> column 2, 3 and 5 does the same but i would net 3 instead of 2 columns

Many thanks in advance!!!

Answer 1

[Bruno Luong]

I start with MaxA, brute force method

% Dummy test
A = [8 4 0 8 8  
     4 8 0 8 0   
     4 0 4 0 0];
V = max(A,[ ],2);
MaxA = A==V;

% Algo starts here
n = size(MaxA,2);
% each row c(i,:) of c stores a subset of colums of A
% c(i,j) is 1 if the ci=olumns c is in the subset
% there are 2^n subset.
c = dec2bin(0:2^n-1)-'0';

% number of columns (cardinal of the subset of column);
sc = sum(c,2);
% Find which subsets have "complementary" by adding all the subset columns
% of maxA, using matrix multiplication trick and observe if the
% product have all elements > 0
j = find(all(MaxA*c',1));
% Find candidate subset
if ~isempty(j)
    % find the minimum of cardinals (umber of columns)
    nc = min(sc(j));
    % select all solution having the same cardinal (==nc)
    % find returns the list of nc x nr columns, nr is the number of subsets
    [col,~] = find(c(j(sc(j)==nc),:)');
    % reshape and transpose to put in the shape you want
    Result = reshape(col,nc,[])';
else
    Result = [];
end
Result

Result = 3×2

3 4 1 4 1 2

[L. Edwin M.]

Thanks for your answer!

Could you please explain it? Would be great!

[Bruno Luong]

I add the comments for you to read

[L. Edwin M.]

Ok cool, thank you!

Anyway hard to follow for me..

[L. Edwin M.]

Could you write me your contact (mail etc.)

Still don't get the solution and really want to understand it!

Would highly aprecciate it!

[Bruno Luong]

Just feel free to ask question here.

[Matt J]

% find the minimum of cardinals (umber of columns)

This part can be replaced with my answer. No need to search all possible numbers of columns by brute force.

[Bruno Luong]

Stricly speaking no, since intlinprog is not warranty to converge to the true minimum, eventhough the chance of failure is tiny.

But yes it could really help to reduce the memory requirement for large n (say > 20)

[Bruno Luong]

This is the implementation with preprocess of finding candidate by Matt's minL1intlin

% Dummy test
A = [8 4 0 8 8  
     4 8 0 8 0   
     4 0 4 0 0]
V = max(A,[ ],2);
MaxA = double(A==V);

[m,n] = size(MaxA);
% Find a candidate of complementary using Matt's FEX
% https://www.mathworks.com/matlabcentral/fileexchange/52795-constrained-minimum-l1-norm-solutions-of-linear-equations 
% This relies on the good convergence of minL1intlin
em = ones(m,1);
en = ones(n,1);
Candidate = minL1intlin(speye(n),0*en,1:n,-MaxA,-em,[],[], 0*en, 1*en);

if ~isempty(Candidate)
    % solution exists
    nc = sum(Candidate);
    % all combinations of nc-columns among n 
    j = nchoosek(1:n, nc);
    p = size(j,1); % nchoosek(n, nc)
    % each row c(i,:) of c stores a subset of colums of A
    % c(i,j) is 1 if the columns c is in the subset
    % there are p subsets with nc columns.
    i = repmat((1:p)', 1, nc);
    c = sparse(i, j, 1, p, n);
    % Only keep those who meet
    Result = j(all(MaxA*c',1),:);
else
    Result = [];
end
Result  

[Matt J]

You could instead have done,

[~,nc] = minL1intlin(speye(n),0*en,1:n,-MaxA,-em,[],[], 0*en, 1*en);

Answer 2

[Matt J]

Do you need all combinations or just one of the minimium-length combinations? If the latter, then download minL1intlin

https://www.mathworks.com/matlabcentral/fileexchange/52795-constrained-minimum-l1-norm-solutions-of-linear-equations

and,

 MaxA = [1 0 0 1 1
        0 1 0 1 0         
        1 0 1 0 0];

 [m,n]=size(MaxA);

  em=ones(m,1);
  en=ones(n,1);

Result = find( minL1intlin(speye(n),0*en,1:n,[],[],MaxA,em,0*en,1*en) )'

LP:                Optimal objective value is 2.000000.                                             


Optimal solution found.

Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value, options.AbsoluteGapTolerance = 0 (the default value). The intcon variables are integer within tolerance,
options.IntegerTolerance = 1e-05 (the default value).

Result = 1×2

3 4

[Bruno Luong]

Careful, OP state (1,4) is a valid solution. Your current formulation can never find such solution since

MaxA*[1; 0; 0; 1; 0] = [2; 1; 1] % and not em

You should specify A, b and not Aeq, beq.

[Matt J]

Careful, OP state (1,4) is a valid solution.

I wonder if that was a mistake..

[Bruno Luong]

What nc value returned when there is no admissible solution?

[Matt J]

Whatever intlinprog returns for fval.