MATLAB Answers

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

19 views (last 30 days)
Benson Gou
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 Comments
Benson Gou
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
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 Comments
Bruno Luong
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.

More Answers (0)

Community Treasure Hunt

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

Start Hunting!