How many submatrices in a matrix for each element?
Answers
Answered by
0
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 2 x 2: |1 2| |1 2| |4 5| |1 3| |4 5|, |7 8|, |7 8|, |4 6|, 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 poss
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.
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 2 x 2: |1 2| |1 2| |4 5| |1 3| |4 5|, |7 8|, |7 8|, |4 6|, 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 poss
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.
Similar questions