19 views (last 30 days)

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 at 14:04

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.

Opportunities for recent engineering grads.

Apply Today
## 10 Comments

## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/433227-how-to-obtain-the-minimum-square-full-rank-sub-matrix-in-a-sparse-matrix#comment_644951

⋮## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/433227-how-to-obtain-the-minimum-square-full-rank-sub-matrix-in-a-sparse-matrix#comment_644951

## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/433227-how-to-obtain-the-minimum-square-full-rank-sub-matrix-in-a-sparse-matrix#comment_644954

⋮## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/433227-how-to-obtain-the-minimum-square-full-rank-sub-matrix-in-a-sparse-matrix#comment_644954

## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/433227-how-to-obtain-the-minimum-square-full-rank-sub-matrix-in-a-sparse-matrix#comment_646240

⋮## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/433227-how-to-obtain-the-minimum-square-full-rank-sub-matrix-in-a-sparse-matrix#comment_646240

## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/433227-how-to-obtain-the-minimum-square-full-rank-sub-matrix-in-a-sparse-matrix#comment_646242

⋮## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/433227-how-to-obtain-the-minimum-square-full-rank-sub-matrix-in-a-sparse-matrix#comment_646242

## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/433227-how-to-obtain-the-minimum-square-full-rank-sub-matrix-in-a-sparse-matrix#comment_646268

⋮## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/433227-how-to-obtain-the-minimum-square-full-rank-sub-matrix-in-a-sparse-matrix#comment_646268

## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/433227-how-to-obtain-the-minimum-square-full-rank-sub-matrix-in-a-sparse-matrix#comment_646290

⋮## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/433227-how-to-obtain-the-minimum-square-full-rank-sub-matrix-in-a-sparse-matrix#comment_646290

## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/433227-how-to-obtain-the-minimum-square-full-rank-sub-matrix-in-a-sparse-matrix#comment_646307

⋮## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/433227-how-to-obtain-the-minimum-square-full-rank-sub-matrix-in-a-sparse-matrix#comment_646307

## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/433227-how-to-obtain-the-minimum-square-full-rank-sub-matrix-in-a-sparse-matrix#comment_646313

⋮## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/433227-how-to-obtain-the-minimum-square-full-rank-sub-matrix-in-a-sparse-matrix#comment_646313

## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/433227-how-to-obtain-the-minimum-square-full-rank-sub-matrix-in-a-sparse-matrix#comment_646317

⋮## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/433227-how-to-obtain-the-minimum-square-full-rank-sub-matrix-in-a-sparse-matrix#comment_646317

## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/433227-how-to-obtain-the-minimum-square-full-rank-sub-matrix-in-a-sparse-matrix#comment_646323

⋮## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/433227-how-to-obtain-the-minimum-square-full-rank-sub-matrix-in-a-sparse-matrix#comment_646323

Sign in to comment.