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)
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
  4 Comments
Benson Gou
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

Sign in to comment.

Accepted Answer

Matt J
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

More Answers (0)

Categories

Find more on Mathematics 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!