How to find out a smallest sub-matrix B from a sparse matrix A which has the equal rank and # of non-zero columns?

8 views (last 30 days)
Benson Gou
Benson Gou on 20 Jan 2021
Commented: Benson Gou on 22 Jan 2021
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
  2 Comments
Benson Gou
Benson Gou on 20 Jan 2021
Hi, Bob,
Thanks for your reply. I modified the description and place feel free to point it out if you still do not understand my question.
Thanks a lot.
Benson

Sign in to comment.

Accepted Answer

Bruno Luong
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
  9 Comments
Bruno Luong
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.

Sign in to comment.

More Answers (1)

Walter Roberson
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.
  3 Comments
Benson Gou
Benson Gou on 22 Jan 2021
Hi, Walter,
Thanks for your reply. I added the condition of matrix A according to your concerns. Now I think it should be OK.
Thanks a lot again.
Benson

Sign in to comment.

Community Treasure Hunt

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

Start Hunting!