CODEWITHSUNDEEP
mathmatrix
Sohan Singh
Sohan Singh

Reputation: 13

Formula for the total no of square submatrixes in a matrix

In a matrix of size r * c, is there any formula to find the total no of square submatrixes in it? For example :

[ 4, 4, 4, 4

4, 4, 4, 4

4, 4, 4, 4 ]

There are 20 square submatrixes in it which is 12(all individual elements are square submatrixes themselves) + 6 (square submatrixes of size 2 * 2) + 2 (square submatrixes of size 3 * 3). Is there any formula to calculate it?

Upvotes: 0

Views: 92

Answers (1)

Yuri Ginsburg
Yuri Ginsburg

Reputation: 2601

For the rectangular matrix of dimension m x n (let's assume than n >= m) there are

K = m x (m+1) x (2m+1)/6 + (n-m) x m x (m+1)/2

square submatrices of the dimension 1 <= k <= m If you are not interested in 1 x 1 matrices substract m x n from K

Upvotes: 0

Related Questions