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

Question

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

Answer 1

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.