How to obtain the minimum square full rank sub-matrix in a sparse matrix?
3 views (last 30 days)
Show older comments
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:
- Select the rows (we should know which rows to select);
- 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
Matt J
on 4 Dec 2018
Edited: 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.)
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 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.
More Answers (0)
See Also
Categories
Find more on Sparse Matrices in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!