How to obtain the minimum square full rank sub-matrix in a sparse matrix?

Dear All,

For a given sparse matrix, I am looking for the minimum square full-rank sub-matrix which is formed by nonzero columns for the selected rows.

If we know the rows in the sparse matrix A to be selected, the minimum square sub-matrix which should be full rank can be obtained using the following steps:

1. Select the rows (we should know which rows to select);
2. Remove all the zero columns, then we get a sub-matrix B, which should be square and full rank.

For example, a given sparse matrix as below:

A =[1 0 -1 0 0 0 0

-1 -1 0 0 0 0 0

0 0 0 0 -1 0 -1

-1 3 0 0 0 -1 0

0 -1 0 0 0 1 0

4 -1 -1 -1 0 0 0

-1 0 0 2 -1 0 0

0 0 0 -1 2 0 0

0 0 -1 0 0 0 -1];

The minimum square matrix is 3 by 3 for the example given above, which is formed by rows 2, 4 and 5 (please note: all nonzero elements in these 3 rows must be considered). B = [-1 -1 0 0 0 0 0; -1 3 0 0 0 -1 0; 0 -1 0 0 0 1 0]. Discard the zero columns in B, we obtain the minimum full-rank square matrix is: [-1 -1 0; -1 3 -1; 0 -1 1].

I am wondering if there exist Matlab functions to find the minimum square full rank sub-matrix for a given sparse matrix. The sparse matrix size is 1000 by 1000.

Thanks a lot and happy holidays.

Benson

[John D'Errico]

For a 1000x1000 matrix? There can easily be billions of such full rank submatrices, and certainly billions of matrices to consider. That your matrix is sparse will reduce the number, but also make things slower to compute. I'd ask if you really, desperately need to do this, or if there is something simpler you can try to do.

Start by computing the rank of your matrix. It will give an upper limit on the size of the sub-matrices you need to consider.

[Benson Gou]

hello, John,

Thanks for your response. We can reduce the size of matric to 200 by 200.

Do you have any ideas to achieve the goal?

Thanks a lit again.

Benson

[Matt J]

The minimum square matrix is 3 by 3

The 1x1 matrix A(1) or the 2x2 matrix A(1:2,1:2) are full rank. Why don't they count?

[Benson Gou]

Dear Matt,

If we consider the first 2 rows, all non-zero elements in these two rows must be considered. So the reduced matrix becomse B = [1 0 -1; -1 -1 0]. It is not a square matrix.

In summary, if we select a row, all nonzero elements in this row must be considered.

Thanks for your question.

Benson

[Bruno Luong]

Your description is confusing to us.

Given a (n x m) matrix with rank k, there is maximal a square submatrix (k x k) full rank (=k). Maximal because any (k + 1) x (k x 1) will not be invertible (since the matrix is rank k). It is possible to find it.

I minimal invertible matrix is (1 x 1). It is also possible to find it, but it will be just a scalar different than 0, and it's trivial fo find it.

It does NOT exist a minimal submatrix invertible of 3 x 3, that does not make sense.

So we don't know what you look for: maximal, minimal, all possible full rank squares?

If you want the later, John has already warned that you might run into a huge number of combination.

So this thread will remain answered until those points are resolved.

[Benson Gou]

Hi, Bruno,

I am looking for a minimum square full-rank sub-matrix in A. Of course, this matrix must contain at least one row. But you may ask how about the first row? If we select the 1st row, we get B = [1 0 -1 0 0 0 0], remove all the zero columns, we get B1 = [1 -1]. It is Not a squre matrix.

For example, if we know the rows in A to form the required sub-matrix, the steps to form the final sub-matrix are given as:

1. Select the rows (we should know which rows to select);
2. Remove all the zero columns, then we get the final sub-matrix B, which should be square and full rank.

I donot know if it now is clear. Thanks a lot for your feedback.

Benson

[Bruno Luong]

No, it's not clear: why can't you select B = A(1,1). That's a submatrix of full-rank and square and minima! Done!!!!

[Matt J]

@Bruno, because the submatrix A(1,1) cannot be extracted in the two step process that Benson described in his last comment. If you select just the first row, as you propose, and remove all the zero columns, you get the matrix [1,-1] which is not square.

[Matt J]

It seems to me that the question is equivalent to the following: find a permutation of the rows and columns of A achieving the block triangular form

  [P 0
   Q R]

with the smallest possible non-singular matrix P. (If you can do this, then P will be the desired sub-matrix.)

[Benson Gou]

@Matt, yes, I think you are right. But how can we find marix P in your description?

Thanks.

Benson

Answer 1

[Matt J]

This article may help: Computing the Block Triangular Form of a Sparse Matrix by Alex Pothen and Chin-Ju Fan. They talk about something called the "Dulmage–Mendelsohn decomposition", which I notice Matlab also has a command for DMPERM.

[Matt J]

I don't know enough about the theory of the DM decomposition, but for square matrices, it seems to do what is desired,

A =

    -1    -1     0     0     0     0     0
     0     0     0     0    -1     0    -1
    -1     3     0     0     0    -1     0
     0    -1     0     0     0     1     0
     4    -1    -1    -1     0     0     0
    -1     0     0     2    -1     0     0
     0     0     0    -1     2     0     0


>> [p,q] = dmperm(A.'); A(q,p)

ans =

    -1    -1     0     0     0     0     0
    -1     3    -1     0     0     0     0
     0    -1     1     0     0     0     0
    -1     0     0    -1     2     0     0
     0     0     0     2    -1     0     0
     0     0     0    -1     0    -1     0
     4    -1     0     0    -1     0    -1

[Bruno Luong]

I think you might find at least the right direction

[Benson Gou]

@Matt, @Bruno, Thanks for your good suggestion. I tried to apply MD decompisition on the original sparse matrix A (9 X 7), I got the re-ordered matrix as below:

A(q,p) = [0 -1 0 1 0 0 0

0 0 2 0 0 -1 0

1 0 0 0 -1 0 0

-1 -1 0 0 0 0 0

0 0 -1 0 0 0 -1

-1 3 0 -1 0 0 0

4 -1 0 0 -1 -1 0

-1 0 -1 0 0 2 0

0 0 0 0 -1 0 -1].

It is good if we can get a lower triangular matrix at the bottom, but 5th row created a problem. If I remove 5th row, the lower triangular matrix will be affected.

In another word, if we can obtain an exact lower triangular matrix at the bottom, it will be easy for us to obtain the minimum full-rank sub-matrix.

Do you think if it is possible to obtain an exact lower triangular matrix for any size of sparse matrix?

Thanks a lot.

Benson

[Bruno Luong]

This paper might also be interested PERMUTING SPARSE RECTANGULAR MATRICES INTO BLOCK-DIAGONAL FORM

[Benson Gou]

@Bruno,thanks a lot for your information. Do you know if I can find their Matlab code for the block-diagonal form?

[Bruno Luong]

No I don't

[Bruno Luong]

I revisit this thread as Benson Gou just accepted one of the old question and I remember this question that I have not able to understand.

But just as I participate lately many post on graph, I would comment a property of graph: for adjacent matrix of the graph, there is a relation ship between connected component of the graph.

When we reorders the node by group of connected components, the matrix become block diagonal (and each block is likely full-rank).

Just a comment, I still don't understand the question asked by Benson.