75 views (last 30 days)

Dear All,

I have a very sparse matrix A. I need to find out a number of rows (smallest #) of A which satisfies the following conditions:

1). Let us suppose the number of rows form a sub-matrix B. In another word, for a given sparse tall matrix A, we need to find out sub-matrix B;

2). Matrix B must contain the first row of A;

3). The rank of B must be equal to the number of non-zero columns (a non-zero column is defined as a column containing at least one non-zero element in the column) of B.

4). The rank of B must be smaller than the rank of matrix A.

For example,

A = [

1 -1 0 0 0

0 2 0 0 0

0 0 2 -1 -1

1 0 1 0 0

];

The anwser is obvious. The matrix B is formed by the first 2 rows of A:

B = [

1 -1 0 0 0

0 2 0 0 0

];

The condition is satisfied: rank(B) = # of non-zero columns (the first 2 columns are non-zero columns) in B.

How about the following example?

A = [

1 -1 0 0 0 0 0 0 0

1 0 0 0 0 0 0 0 -1

0 0 0 0 0 0 0 0 0

0 0 -1 -1 0 0 0 -1 0

0 0 1 0 0 0 0 0 0

0 0 0 1 0 0 0 0 0

-1 0 0 0 4 -1 -1 -1 0

0 0 0 0 -1 1 0 0 0

0 0 0 0 -1 0 1 0 0

0 0 0 0 -1 0 0 2 0

0 0 0 0 0 0 0 0 0

3 -1 0 0 -1 0 0 0 -1

-1 1 0 0 0 0 0 0 0

-1 0 0 0 0 0 0 0 1

];

Please help to find out a sub-matrix B for a given sparse matrix A.

Thanks a lot.

Benson

Bruno Luong
on 20 Jan 2021

Edited: Bruno Luong
on 20 Jan 2021

Done, B=A (so all rows of A) meets your requirement

>> A = [

1 -1 0 0 0 0 0 0 0

1 0 0 0 0 0 0 0 -1

0 0 0 0 0 0 0 0 0

0 0 -1 -1 0 0 0 -1 0

0 0 1 0 0 0 0 0 0

0 0 0 1 0 0 0 0 0

-1 0 0 0 4 -1 -1 -1 0

0 0 0 0 -1 1 0 0 0

0 0 0 0 -1 0 1 0 0

0 0 0 0 -1 0 0 2 0

0 0 0 0 0 0 0 0 0

3 -1 0 0 -1 0 0 0 -1

-1 1 0 0 0 0 0 0 0

-1 0 0 0 0 0 0 0 1

];

>> B=A;

>> sum(any(B,1))

ans =

9

>> rank(B)

ans =

9

Bruno Luong
on 21 Jan 2021

Here is the brute force method:

A = [

1 -1 0 0 0 0 0 0 0

1 0 0 0 0 0 0 0 -1

0 0 0 0 0 0 0 0 0

0 0 -1 -1 0 0 0 -1 0

0 0 1 0 0 0 0 0 0

0 0 0 1 0 0 0 0 0

-1 0 0 0 4 -1 -1 -1 0

0 0 0 0 -1 1 0 0 0

0 0 0 0 -1 0 1 0 0

0 0 0 0 -1 0 0 2 0

0 0 0 0 0 0 0 0 0

3 -1 0 0 -1 0 0 0 -1

-1 1 0 0 0 0 0 0 0

-1 0 0 0 0 0 0 0 1

];

m = size(A,1);

b = dec2bin(0:2^(m-1)-2)-'0';

b = [true(size(b,1),1),logical(b)];

nc = size(b,1);

[~, is] = sort(sum(b,2));

b = b(is,:);

for i=1:nc

rows = b(i,:);

B = A(rows,:);

r = rank(B);

ncnz = sum(any(B,1));

if r==ncnz

fprintf('Found B, rows=%s\n', mat2str(find(rows)));

B

return

end

end

fprintf('B not found\n');

That find this rows

Found B, rows=[1 7 8 9 10 12 14]

B =

1 -1 0 0 0 0 0 0 0

-1 0 0 0 4 -1 -1 -1 0

0 0 0 0 -1 1 0 0 0

0 0 0 0 -1 0 1 0 0

0 0 0 0 -1 0 0 2 0

3 -1 0 0 -1 0 0 0 -1

-1 0 0 0 0 0 0 0 1

Bruno Luong
on 22 Jan 2021

Nothing in your question indicates that there is such sequencial suites of rows that the number of non-zeros columns increase by at most 1 between two adjacent selected rows.

You can make a modification in A by making an arbitrary combination the rows=[1 7 8 9 10 12 14] in A, and it will return the same row selection, and without such suites (they all have 7 non-zeros columns).

In this case it you apply your method of "speeding" up, it will fail to detect B.

Walter Roberson
on 21 Jan 2021

In general there is no solution.

Every dense matrix is also a spare matrix.

An NxN full-rank dense matrix might happen to have no zeros.

B is a submatrix of A, so if A has no zeros at all, it is impossible for the number of non-zero columns of B to be smaller than the number of columns of A.

B has N columns because A has N columns.

You require rank of B to be the number of non-zero columns of B, but the number of non-zero columns of B is, in this case, the number of columns of B.

A is square and (by selection) has full rank, N. And as discussed above, B would have to be rank N.

But rank(B) = N and rank(A) = N, so therefore rank(B) < rank(A) must be false.

Therefore there are matrices for which the conditions cannot hold.

Walter Roberson
on 22 Jan 2021

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

Start Hunting!
## 2 Comments

## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/722314-how-to-find-out-a-smallest-sub-matrix-b-from-a-sparse-matrix-a-which-has-the-equal-rank-and-of-non#comment_1275123

⋮## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/722314-how-to-find-out-a-smallest-sub-matrix-b-from-a-sparse-matrix-a-which-has-the-equal-rank-and-of-non#comment_1275123

## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/722314-how-to-find-out-a-smallest-sub-matrix-b-from-a-sparse-matrix-a-which-has-the-equal-rank-and-of-non#comment_1275528

⋮## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/722314-how-to-find-out-a-smallest-sub-matrix-b-from-a-sparse-matrix-a-which-has-the-equal-rank-and-of-non#comment_1275528

Sign in to comment.