MATLAB Answers

# 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
##### 10 CommentsShowHide 9 older comments
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

Sign in to comment.

### Accepted Answer

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.
##### 7 CommentsShowHide 6 older comments
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.

Sign in to comment.

### Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!