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

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

[Bob Thompson]

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]

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

Answer 1

[Bruno Luong]

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

[Benson Gou]

Bruno,

I am sorry for my unclear description. The rank of B must be smaller than the row number of A. The smallest B, the better.

Thanks.

Benson

[Bruno Luong]

My B totally meets your requirement since rank(B)=9 < size(A,1)=14.

[Benson Gou]

I am talking about the # of columns. Matrix A and your B both have 9 columns.

Thanks.

Benson

[Bruno Luong]

Higllight of the question: "4). The rank of B must be smaller than the row number of matrix A."

[Bruno Luong]

You might take a look function dmperm.

It looks like no solution exist for your 14 x 9 example.

[Benson Gou]

Bruno,

The rank of B must be smaller than the rank of A. I changed this statement in my description.

Thanks for your questions.

Benson

[Bruno Luong]

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]

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]

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.

Answer 2

[Walter Roberson]

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.

[Benson Gou]

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]

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]

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