Finding Submatrices of lesser rank from a full rank matrix

I am trying to find all the submatrices of a full rank matrix with a rank less than the original matrix rank. For example, if I have a 4x12 matrix with a rank of 4, I want to calculate all submatrices with rank 3 and rank 2. I tried to calculate the number of submatrices that can be formed from a 4x12 matrix, which itself is a considerable number. Out of all of them, the number of matrices that can have a rank equal to 3 will be less than or equal to the total number of submatrices formed. I thought there was a command for this called submatrix, but couldn't find anything related to it. Should I proceed by constructing all submatrices form the original 4x12 matrix and chefcking to see the rank? Won't that be super long? Is there a way to code this?

[David Goodmanson]

Hello Arjun,

Leaving out submatrices with only one row or one column (since they have rank<=1), for an m = 4, n = 12 matrix there are

(2^n-n-1)*(2^m-m-1) = 44913

possible submatrices. That's a lot to keep track of. If by 'submatrix' you mean only those that are pulled out of the matrix in blocks, i.e. those having contiguous rows and columns from the full matrix, then the cases reduce considerably, to m*(m-1)*n*(n-1)/4, or 396. That's a lot more doable.

Answer 1

[Shravan Kumar Vankaramoni]

Hi Arjun,

Currently there is no command in MATLAB that gives all submatrices with a given rank. You can try to reduce the number by eliminating the matrices with one row and column as mentioned in the above comment.

You can refer to below links to get all the submatrices in efficient way

https://www.mathworks.com/matlabcentral/answers/395258-most-efficent-way-of-finding-submatrices-of-a-matrix

https://www.mathworks.com/matlabcentral/answers/169278-all-submatrices-of-given-order-of-a-given-matrix