Finding the number of sub-grids of a matrix 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-matrices.
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)
 A: 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.$
A: 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.
