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

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

[the cyclist]

Is this different from the question you asked here? If not, I suggest you delete the other one.

Also, I used the CODE button to format your code, to make it a bit easier to follow.

[the cyclist]

I have to admit that I do not understand the general rule that should be inferred from your two examples.

[Benson Gou]

Hello, Cyclist,

Thanks a lot for your great help.

Benson

[Benson Gou]

By the way, I do publish a similiar question yesterday. It is the original question I am seeking for help. This question, which was published because my original question does not get any reply, is a compremised equstion which is easier. I still hope that my origina question could get help.

Thanks a lot.

Benson

Answer 1

[Matt J]

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

[Benson Gou]

Dear Matt,

Thanks a lot for your great help. I will test it on my real cases.

You have a good weekend!

Benson