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

3 visualizzazioni (ultimi 30 giorni)
Benson Gou il 20 Gen 2021
Commentato: Benson Gou il 22 Gen 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.
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
];
Thanks a lot.
Benson
##### 2 CommentiMostra NessunoNascondi Nessuno
Bob Thompson il 20 Gen 2021
Modificato: Bob Thompson il 20 Gen 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 il 20 Gen 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

Accedi per commentare.

### Risposta accettata

Bruno Luong il 20 Gen 2021
Modificato: Bruno Luong il 20 Gen 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 CommentiMostra 7 commenti meno recentiNascondi 7 commenti meno recenti
Benson Gou il 21 Gen 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 il 22 Gen 2021
Modificato: Bruno Luong il 22 Gen 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.

Accedi per commentare.

### Più risposte (1)

Walter Roberson il 21 Gen 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 CommentiMostra 1 commento meno recenteNascondi 1 commento meno recente
Walter Roberson il 22 Gen 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 il 22 Gen 2021
Hi, Walter,
Thanks a lot again.
Benson

Accedi per commentare.

### Categorie

Scopri di più su Just for fun in Help Center e File Exchange

### Community Treasure Hunt

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

Start Hunting!

Translated by