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

19 views (last 30 days)
Benson Gou on 1 Dec 2018
Commented: Bruno Luong on 1 Aug 2020 at 14:04
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

Matt J on 4 Dec 2018
@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 on 4 Dec 2018
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 on 4 Dec 2018
@Matt, yes, I think you are right. But how can we find marix P in your description?
Thanks.
Benson

Matt J on 4 Dec 2018
Edited: Matt J on 4 Dec 2018
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.

Benson Gou on 5 Dec 2018
@Bruno,thanks a lot for your information. Do you know if I can find their Matlab code for the block-diagonal form?
Bruno Luong on 5 Dec 2018
No I don't
Bruno Luong on 1 Aug 2020 at 14:04
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.