I have a very sparse matrix A. I need to find out a smallest number of rows 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 formed by a smallest number of rows of A;
2). Matrix B must contain the first row (should be non-zero 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 of at worst equal to the rank of matrix A.
For example, A = [
1 0 -1 0 0
0 -1 0 2 0
0 0 2 -1 -1
2 0 1 0 0
];
The answer is obvious. The matrix B is formed by the first row and the last row of A:
B = [
1 0 -1 0 0
2 0 1 0 0
];
The condition is satisfied: rank(B) = 2, number of non-zero columns of B = 2.
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 tall matrix A.
Thanks a lot.
Benson
