[Math] Number of square submatrices of a matrix and occurrence of each value in the new submatrices

combinatoricsdiscrete mathematicsmatricesrandom matrices

We are given a n x m matrix. I have to find the total number of square sub-matrices possible of the given matrix.

For e.g.,

3 x 3 matrix is given as follows:

1 2 3
4 5 6
7 8 9

All possible square submatrices are:

1 x 1: |1|, |2|, |3|, |4|, |5|, |6|, |7|, |8|, |9| = Total = 9
2 x 2: |1 2|  |1 2|  |4 5|  |1 3|  |1 3|  |4 6|  |2 3|  |2 3|  |5 6|
       |4 5|, |7 8|, |7 8|, |4 6|, |7 9|, |7 9|, |5 6|, |8 9|, |8 9| = Total = 9
3 x 3: |1 2 3|
       |4 5 6|
       |7 8 9| = Total = 1

I referred this question. But the formula there gives me total of only matrices which can be formed by consecutive rows and columns. And I have to calculate all the dimensions separately.

For 3 x 2 matrix:

1 2
3 4
5 6

1 x 1: 6 possible.
2 x 2: |1 2|  |1 2|  |3 4|
       |3 4|, |5 6|, |5 6| = 3 possible

We can't get a 3 x 3 matrix for above, so we take min(n, m) and only produce square matrix with min value. Similarly for (2 x 3) matrix, (2 x 4) matrix and so on.

And if we see the total number of occurrences of each value in the matrix of 3 x 3 is 6. Means in the above given example the total number of occurrences of 1 is 6 times and similarly all other numbers appear exactly 6 times. And for 3 x 2
matrix each number appears 3 times in the submatrices. For a 2 x 2 matrix each value occurs exactly 2 times.

Question:

(1) Total number of square submatrices which can be formed from a given n x m matrix.

(2) Total number of occurrences of each value of a matrix in the new square submatrices made.

Here, 1 <= n, m <= 1000000000. Value of n and m may be same and may not be same.

EDIT 1:
As suggested by the community members, I referred this question too, but the answer given there also ignores skipping of rows and columns while forming new submatrices.

From given 3 x 3 matrix, they are: |1 2|  |2 3|  |1 3|  |4 6|  |1 3|
                                   |7 8|, |8 9|, |4 6|, |7 9|, |7 9|

The formula given there gives answer as 14 but it is 19. It doesn't take into account this given matrices.

Best Answer

For an $n$-by-$m$ matrix, an $r$-by-$r$ submatrix is completely determined by which rows it contains and which columns it contains. As a result, the number of $r$-by-$r$ submatrices is $\dbinom n r \dbinom m r$, where $\dbinom x y$ is the binomial coefficient.

Therefore, the answer to your first question is $\displaystyle \sum_{r=1}^{\min(n,m)} \dbinom n r \dbinom m r$.

For a particular entry to be included, its row and its column must be chosen, leaving us with $\dbinom {n-1} {r-1}$ for the choice of rows and $\dbinom {m-1} {r-1}$ for the choice of columns.

Therefore, the answer to your second question is $\displaystyle \sum_{r=1}^{\min(n,m)} \dbinom {n-1} {r-1} \dbinom {m-1} {r-1}$.

Related Question