3

I am trying to find the number of $M\times M$ sub-grids given an $N\times N$ matrix, where $M \leq N$.

For any concrete example it is easy to find the correct answer: Eg:

$$\left( \begin{array}{ccc} 4 & 3 & 8\\ 9 & 5 & 1\\ 2 & 7 & 6\\ \end{array} \right)$$

This is a $3 \times 3$ matrix: The number of $1 \times 1$ sub-grids is 9; the number of $2 \times 2$ sub-grids is 4; and the number of $3 \times 3$ sub-grids is 1.

I am trying to find a general formula to find the number of sub-grids. So far I have been looking at the dimensions of each:

A $4 \times 4$ matrix will have:

$$16 \quad (1 \times 1)$$ $$9 \quad (2 \times 2)$$ $$4 \quad (3 \times 3)$$ $$1 \quad (4 \times 4)$$

sub-grids.

By trial I have concluded that the number of sub-grids can be calculated by:

$$({N-M+1})^2$$

Could someone please confirm that this is a correct conclusion and maybe give some intuition to why is so? (e.g. the number of shifts it is possible to make with the sub-grids in the matrix)

Ardent Coder
  • 173
Gabor Bakos
  • 423

2 Answers2

2

1) If you mean submatrix as continuous submatrix (rows and columns in your matrix are neighbors) then your expression is true.

Intuition: you need choose your first column and your first row in submatrix, you have $(N - M + 1)$ options for column and for row.

Others rows and columns are uniquely determined by the first.

2) If you mean submatrix as https://en.wikipedia.org/wiki/Matrix_(mathematics)#Submatrix then your expression is $\binom{N}{M}^2.$

Alfred XXX
  • 175
1

Your expression $(N-M+1)^2$ is correct, and the picture you describe (shifting the sub matrix around inside the matrix) is a natural/intuitive way to the expression.

So, what more needs to be said? It depends on who you're trying to convince :-).

If you're quite confident of the result, and in the mathematical ability of anyone you're trying to communicate, you might write something like "The number of $M\times M$ sub-matrices of an $N \times N$ matrix where $1 \le M \le N$ is $(N-M+1)^2$ since there are $N-M+1$ choices for the row and column of the top-left corner of the sub-matrix within the matrix."

If your reader might be in doubt about those $N-M+1$ choices, or if you're looking for a more formal/symbolic bridge from the intuition ("I know it's about sliding the smaller matrix around") to the correct expression for the amount of "wiggle room" ($N-M+1$ in each of two dimensions), you could reason: Suppose the first row of a sub-matrix is on row $r$ of the matrix. The sub-matrix is $M$ rows high, so its last row will be $r+M-1$ in the matrix. There are $N$ rows in the matrix, so $r+M-1 \le N$, or $r \le N-M+1$. There are $N-M+1$ choices for $r$ in the range $1 \le r \le N-M+1$. Similarly, there are $N-M+1$ choices for the first column of the sub-matrix, so $(N-M+1)^2$ choices for the position of the sub-matrix within the matrix.

Frentos
  • 3,041