19 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

Matt J
on 4 Dec 2018

Edited: Matt J
on 4 Dec 2018

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.

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

Start Hunting!