MATLAB: How to find a minimal number of rows in a sparse matrix to form a square sub-matrix for a given row

minimal square sub-matrix

Dear All,
I have a big sparse matrix A. For a given row, is it possible for me to find the minimal number of rows in A to form a square sub-matrix (zero columns are deleted if zero-columns exist)? (the square sub-matrix also has the minimal size)
For example,
A = [0 0 1 0 3;
     0 2 6 0 0;
     1 0 5 3 1;
     0 2 1 4 0;
    -4 0 0 5 1;
     3 0 0 0 0;
     5 0 0 2 0;
     0 1 0 3 4]
1). For the given row #7, row #6 can form a sub-matrix with row #7. 
rows_6_7 = [3     0     0     0     0;
            5     0     0     2     0]
Delete the zero columns, we have
submatrix = [3 0;
             5 2]
2). Given row #2, we can find 4 rows to form a square submatrix.
selected_rows = [0 2 6 0 0;
                 0 2 1 4 0;
                 0 1 0 3 4;
                 0 0 1 0 3]
Submatrix =  [2 6 0 0;
              2 1 4 0;
              1 0 3 4;
              0 1 0 3]
Thanks a lot.
Benson

Best Answer

If you have the Optimization Toolbox, you can try this linear programming solution:
A = [ -1     1     0     0     0     0
     0    -1     2     1     3     0
     0     3    -2     1     0     0
     0     0     1     0     4     0
     1     0     0     2    -1     0
     0    -1     0     0     0     3
     2     0     0     0     0     1];
 
 j=1;
 
[m,n]=size(A);
n0=nnz(A(j,:));
if n0==1
    
   rows=A(j,:),
   
else
    
   C=double(   logical(   A(:, ~A(j,:) )  ));
   [~,nc]=size(C);
   
   x=optimvar('x',[m,1], 'Low',0,'Up',1,'Type','integer');   x.LowerBound(j)=1;
   y=optimvar('y',[1,nc], 'Low',0,'Up',1,'Type','integer');
   
   prob=optimproblem('Objective',sum(x));
   prob.Constraints.xineq=sum(x)>=n0;
   prob.Constraints.yupper=x.'*C>=y; %forces y(i) to zero if sum(C)=0
   prob.Constraints.ylower=x.'*C<=m*y;%forces y(i) to one if sum(C)>0
   prob.Constraints.nz=sum(x)-sum(y)==n-nc;
   
    [sol,numrows]=solve(prob);
    
    rows=A(round(sol.x)>0,:)
    
end
results in,
rows =
    -1     1     0     0     0     0
     0    -1     0     0     0     3
     2     0     0     0     0     1
Related Question