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

1 view (last 30 days)
Benson Gou on 20 Mar 2020
Commented: Benson Gou on 22 Mar 2020
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
Benson Gou on 20 Mar 2020
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

Matt J on 22 Mar 2020
Edited: Matt J on 22 Mar 2020
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 on 22 Mar 2020
Dear Matt,
Thanks a lot for your great help. I will test it on my real cases.
You have a good weekend!
Benson

### Categories

Find more on Matrix Computations in Help Center and File Exchange

### Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by