MATLAB Answers

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

77 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

Bob Thompson
Bob Thompson on 20 Jan 2021
I don't understand what exactly you're trying to capture for B. This is what my understanding is, please correct where I'm wrong.
1) You have a matrix, A, which contains some numbers sprinkled among a bunch of zeros.
2) You want to look at the first row of A, and count the number of non-zero values in it, and the rank. What is rank?
3) You want to examine all rows of A to find which ones contain the same number of non-zero values, and same rank, as the first row.
4) Rows which pass step 3 should be placed in a separate matrix, B.
This kind of work certainly seems possible in MATLAB, I just want to make sure I understand what you're actually trying to do before I go fishing for answers.
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

Show 6 older comments
Bruno Luong
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
Benson Gou
Benson Gou on 21 Jan 2021
Hi, Bruno,
Thanks a lot for your great help. Your code wroks well. But it took more than 2400 iterations to reach the solution.
I have an idea to speed up the calculation. The idea is:
In order to find B, any row, which has zero elements in columns 1 & 2 (because the first row has non-zero elements in columns 1 & 2), will contribute more non-zero coulmns than (at most equal) the rank increase of B. For example, rows 2, 3, 4, 5, 6, 11 and 13 in this case. I compare those rows with the first row below:
Row 1: 1 -1 0 0 0 0 0 0 0 (Must included)
Row 3: 0 0 0 0 0 0 0 0 0
Row 4: 0 0 -1 -1 0 0 0 -1 0
Row 5: 0 0 1 0 0 0 0 0 0
Row 6: 0 0 0 1 0 0 0 0 0
Row 11: 0 0 0 0 0 0 0 0 0
Row 13: -1 1 0 0 0 0 0 0 0
We can define above rows (Rows 2, 3, 4, 5, 6, 11 and 13) as Irrelative Rows.
So my idea is: 1) in each iteration, we can avoid the Irrelative Rows; 2) in each iteration, we can only conider increasing the number of non-zero columns of B by 1; 3) As the size of B increses, the number of irrelative rows will reduce.
I am not a good Matlab coder and my code normally is more complex than necessary.
Thanks a lot again for your great help.
Benson
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 21 Jan 2021
Hi, Walter,
Thnkas for your sharing.
The condition of your results is A is dense matrix and A is a square matrix. But here A is a very sparse matrix and its size is MxN (M>N). Please check the example I provided: M=14 and N=9.
There must exist a sub-matrix B when A is full column rank, the worst case is that B is formed by N linear independent rows selected from A.
Thanks a lot again.
Benson
Walter Roberson
Walter Roberson on 22 Jan 2021
The example is not normative. The rules you gave for solution do not require that M > N or that it has any minimum sparsity. The question asks "Given a matrix A, find B that follows these rules", and I demonstrated that you cannot always do that. You could revise the rules, of course.
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!