How to find out a smallest sub-matrix B from a sparse matrix A which has the equal rank and # of non-zero columns?
4 visualizaciones (últimos 30 días)
Mostrar comentarios más antiguos
Benson Gou
el 20 de En. de 2021
Comentada: Benson Gou
el 22 de En. de 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 comentarios
Bob Thompson
el 20 de En. de 2021
Editada: Bob Thompson
el 20 de En. de 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.
Respuesta aceptada
Bruno Luong
el 20 de En. de 2021
Editada: Bruno Luong
el 20 de En. de 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 comentarios
Bruno Luong
el 22 de En. de 2021
Editada: Bruno Luong
el 22 de En. de 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.
Más respuestas (1)
Walter Roberson
el 21 de En. de 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 comentarios
Walter Roberson
el 22 de En. de 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.
Ver también
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!