Determine all square sub matrices of a given NxN matrix in C++

Question

GIven an NxN square matrix, I would like to determine all possible square sub matrices by removing equal number of rows and columns.

In order to determine all possible 2x2 matrices I need to loop 4 times. Similarly for 3x3 matrices I need to loop 6 times and so on. Is there a way to generate code in C++ so that the code for the loops is generated dynamically? I have checked some answers related to code generation in C++, but most of them use python in it. I have no idea regarding python. So, is it possible to write code to generate code in C++?

Answer 1

If I get what you are saying, you mean you require M loops to choose M rows, and M loops for M columns for an M x M sub matrix, 1 <= M <= N

You don't need 2*M loops to do this. No need to dynamically generate code with an ever-increasing number of loops!

Essentially, you need to "combine" all possible combinations of i_{1}, i_{2}, ..., i_{M} and j_{1}, j_{2}, ..., j_{M} such that 1 <= i_{1} < i_{2} < ... < i_{M} <= N (and similarly for j)

If you have all possible combinations of all such i_{1}, ..., i_{M} you are essentially done.

Say for example you are working with a 10 x 10 matrix and you require 4 x 4 sub matrices.

Suppose you selected rows {1, 2, 3, 4} and columns {1, 2, 3, 4} initially. Next select column {1, 2, 3, 5}. Next {1, 2, 3, 6} and so on till {1, 2, 3, 10}. Next select {1, 2, 4, 5}, next {1, 2, 4, 6} and so on till you reach {7, 8, 9, 10}. This is one way you could generate all ("10 choose 4") combinations in a sequence.

Go ahead, write a function that generates this sequence and you are done. It can take as input M, N, current combination (as an array of M values) and return the next combination.

You need to call this sequence to select the next row and the next column.

I have put this a little loosely. If something is not clear I can edit to update my answer.

---

Edit:

I will be assuming loop index starts from 0 (the C++ way!). To elaborate the algorithm further, given one combination as input the next combination can be generated by treating the combination as a "counter" of sorts (except that no digit repeats).

Disclaimer : I have not run or tested the below snippet of code. But the idea is there for you to see. Also, I don't use C++ anymore. Bear with me for any mistakes.

// Requires M <= N as input, (N as in N x N matrix)
void nextCombination( int *currentCombination, int M, int N ) {
    int *arr = currentCombination;
    for( int i = M - 1; i >= 0; i-- ) {
        if( arr[i] < N - M + i ) {
            arr[i]++;
            for( i = i + 1, i < M; i++ ) {
                arr[i] = arr[i - 1] + 1;
            }
            break;
        }
    }

}

// Write code for Initialization: arr = [0, 1, 2, 3]
nextCombination( arr, 4, 10 );
// arr = [0, 1, 2, 4]

// You can check if the last combination has been reached by checking if arr[0] == N - M + 1. Please incorporate that into the function if you wish.

---

Edit:

Actually I want to check singularity of all possible sub matrices. My approach is to compute all submatrices and then find their determinants. How ever after computing the determinant of 2x2 matrices , I'll store them and use while computing determinants of 3x3 matrices. And so on. Can you suggest me a better approach. I have no space and time constraints. – vineel

A straight-forward approach using what you suggest is to index the determinants based on the the rows-columns combination that makes a sub matrix. At first store determinants for 1 x 1 sub matrices in a hash map (basically the entries themselves).

So the hash map would look like this for the 10 x 10 case
{ "0-0" : arr_{0, 0}, "0-1" : arr_{0, 1}, . . . "1-0" : arr_{1, 0}, "1-1" : arr_{1, 1}, . . . "9-9" : arr_{9, 9} }

When M = 2, you can calculate determinant using the usual formula (the determinants for 1 x 1 sub matrices having been initialized) and then add to the hash map. The hash string for a 2 x 2 sub matrix would look something like 1:3-2:8 where the row indices in the original 10 x 10 matrix are 1,3 and the column indices are 2, 8. In general, for m x m sub matrix, the determinant can be determined by looking up all necessary (already) computed (m - 1) x (m - 1) determinants - this is a simple hash map lookup. Again, add the determinant to hash map once calculated.

Of course, you may need to slightly modify the nextCombination() function - it currently assumes row and column indices run from 0 to N - 1.

On another note, since all sub matrices are to be processed starting from 1 x 1, you don't need something like a nextCombination() function. Given a 2 x 2 matrix, you just need to select one more row and column to form a 3 x 3 matrix. So you need to select one row-index (that's not part of the row indices that make the 2 x 2 sub matrix) and similarly one column-index. But doing this for every 2 x 2 matrix will generate duplicate 3 x 3 matrices - you need to think of some way to eliminate duplicates. One way to avoid duplicates is by choosing only such row/column whose index is greater than the highest row/column index in the sub matrix.

Again I have loosely defined the idea. You can build upon it.