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
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
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.
Bruno Luong on 1 Aug 2020
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.
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}