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

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

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

Start Hunting!
## 4 Comments

## Direct link to this comment

https://au.mathworks.com/matlabcentral/answers/511969-how-to-find-a-minimal-number-of-rows-in-a-sparse-matrix-to-form-a-square-sub-matrix-for-a-given-row#comment_812799

⋮## Direct link to this comment

https://au.mathworks.com/matlabcentral/answers/511969-how-to-find-a-minimal-number-of-rows-in-a-sparse-matrix-to-form-a-square-sub-matrix-for-a-given-row#comment_812799

## Direct link to this comment

https://au.mathworks.com/matlabcentral/answers/511969-how-to-find-a-minimal-number-of-rows-in-a-sparse-matrix-to-form-a-square-sub-matrix-for-a-given-row#comment_812808

⋮## Direct link to this comment

https://au.mathworks.com/matlabcentral/answers/511969-how-to-find-a-minimal-number-of-rows-in-a-sparse-matrix-to-form-a-square-sub-matrix-for-a-given-row#comment_812808

## Direct link to this comment

https://au.mathworks.com/matlabcentral/answers/511969-how-to-find-a-minimal-number-of-rows-in-a-sparse-matrix-to-form-a-square-sub-matrix-for-a-given-row#comment_812814

⋮## Direct link to this comment

https://au.mathworks.com/matlabcentral/answers/511969-how-to-find-a-minimal-number-of-rows-in-a-sparse-matrix-to-form-a-square-sub-matrix-for-a-given-row#comment_812814

## Direct link to this comment

https://au.mathworks.com/matlabcentral/answers/511969-how-to-find-a-minimal-number-of-rows-in-a-sparse-matrix-to-form-a-square-sub-matrix-for-a-given-row#comment_812816

⋮## Direct link to this comment

https://au.mathworks.com/matlabcentral/answers/511969-how-to-find-a-minimal-number-of-rows-in-a-sparse-matrix-to-form-a-square-sub-matrix-for-a-given-row#comment_812816

Sign in to comment.