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

1 Ansicht (letzte 30 Tage)
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 Kommentare
Benson Gou
Benson Gou am 20 Mär. 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

Melden Sie sich an, um zu kommentieren.

Akzeptierte Antwort

Matt J
Matt J am 22 Mär. 2020
Bearbeitet: Matt J am 22 Mär. 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

Weitere Antworten (0)

Kategorien

Mehr zu Mathematics finden Sie in Help Center und File Exchange

Community Treasure Hunt

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

Start Hunting!

Translated by