# Matrix challenge: How many submatrices in a matrix

I have came across a challenging question I'd to solve. I am a self-taught man, so be indulgent.

Caution: the following is a translation from a non English language. Sorry if it contains syntax inaccuracies.

Let A be a matrix with n rows and m columns such as: $\forall i, j: 1 ≤ i ≤ n, 1 ≤ j ≤ m$

Let B be a submatrix of A with d rows and d columns defined as: $\exists p, q: B[i,j] = A[p + i - 1, q + j - 1]$ $\forall i,j 1 ≤ i ≤ d, 1 ≤ j ≤ d$

So B is a part (as a square) of the image of A

Question: demonstrate how many submatrices B with d rows and d columns A contain?

• Would you mind translating the "tels que" as well? In your definition of $B$, is there some $q+j-1$ missing?= Is $d$ fixed? I would not consider $B$ as part of the image (as in range) of $A$. – Roland Mar 1 '14 at 18:52
• Updated: q + j - 1 was missing. – roland Mar 1 '14 at 18:55
• Possible duplicate of math.stackexchange.com/q/229182/66212 – taninamdar Mar 1 '14 at 19:04
• @TanmayInamdar: No, since your linked question is concerned with the total number of squares, not the number of squares with a fixed number. – Roland Mar 1 '14 at 19:06
• But if you see the answers, you will see that the total number of squares is calculated by summing over squares of all possible sizes. Hence, your question is part of that question. – taninamdar Mar 1 '14 at 19:07

If I'm understanding correctly, you're choosing $d$ neighbouring columns and rows for this, so if you had the matrix written down you'd be taking out a proper $d\times d$ square.
As such, you can choose to put the top-left corner of your matrix at any $A[x,y]$, which I'll write $(x,y)$ like coordinates, with $x\leq n-d+1$ and $y\leq m-d+1$. To illustrate this, given a $3\times 3$ matrix and a $2\times 2$ submatrix, you can put the top left corner at $(1,1),(1,2),(2,1)$, or $(2,2)$. Hence you have $(n-d+1)(m-d+1)$ choices.
Each $d\times d$ submatrix $B$ of $A$ is determined by the postition of its upper left element $B[1,1]=A[p,q]$: Starting from this element, we go to the right and down until we have a matrix with $d$ rows and $d$ columns. In order to make sure that we get $d$ rows and columns from $A$, we need to make sure that right of the $B[1,1]$, there are $d-1$ entries, i.e. $p \leq n+1 - d$, and below there are $d-1$ entries as well, requiring $q\leq m +1 -d$.
So we can choose the upper left entries from the rectangular matrix which we get when we keep the first $n+1 -d$ columns and the first $m+1-d$ rows, which has in total $(n+1-d)(m+1-d)$ entries.
• @roland: Thank you for pointing this out. I think that I made this error when I had $m - (d - 1)$ in mind. – Roland Mar 2 '14 at 11:19