suppose we have a matrix of n*n .And we want to know that how many submatrix includes aij for any i
I found the formula for same here
that is S(x, y) = (X + 1) * (Y + 1) * (N – X) * (N – Y).
My target was to find the sum of all submatrix and latter i can do s(x,y)*a[x][y] for all elements of matrix.
There explanation is like this:
For each element of the matrix, let us try to find the number of sub-matrices, the element will lie in. This can be done in O(1) time. Let us suppose the index of an element be (X, Y) in 0 based indexing, then the number of submatrices (Sx, y) for this element will be in can be given by the formula S(x, y) = (X + 1) * (Y + 1) * (N – X) * (N – Y) . This formula works, because we just have to choose two different positions on the matrix that will create a submatrix that envelopes the element. Thus, for each element, ‘sum’ can be updated as sum += S(x,y) * Arr[x][y].
As given in the program in above link
// Number of ways to choose
// from top-left elements
int top_left = (i + 1) * (j + 1);
// Number of ways to choose
// from bottom-right elements
int bottom_right = (n - i) * (n - j);
I am not getting this formula S(x, y) = (X + 1) * (Y + 1) * (N – X) * (N – Y). that how they are forming the elements from above formula.
Please can someone explain me with an example that how the top_left and bottom_right forming all possible matrix .
Lets say $X = 2$, $Y = 3$, $N = 5$. Then $x$ coordinate of top-left corner is $0$, $1$ or $2$ - total $X + 1$ choices. $y$ coordinate of top-left corner is $0$, $1$, $2$ or $3$ - total $Y + 1$ choices. So there total $(X + 1) \cdot (Y + 1)$ choices for top-left.
Similarly, $x$ coordinate for bottom-right corner is $2$, $3$ or $4$ - total $3 = 5 - 2 = N - X$ choices, and $y$ coordinate is $3$ or $4$ - total $2 = 5 - 3 = N - Y$ choices. So there are total $(N - X) \cdot (N - Y)$ choices to bottom-right corner.
And total number of submatrices including $(X, Y)$ is equal to product of possible top-left corners and possible bottom-right corners (as any pair of this corners specify unique submatrix), so it is $(X + 1) \cdot (Y + 1) \cdot (N - X) \cdot (N - Y)$.