# Squares in a dot matrix

We have a matrix made up of $m$ by $n$ dots. Can you give a function that counts the number of squares that can be found by joining any $4$ dots in it?

• I thought this Q must be an old one, but I couldn't find it. – ghosts_in_the_code Oct 28 '15 at 15:34

For every $m\ge n$ (otherwise just swap $m$ and $n$) the number of squares $N$ is:

$N=\sum_{i=1}^{n-1}(n-i)\times(m-i)\times i$

Where $(n-i)\times(m-i)$ counts all squares of sidelength $i$ and sides parallel to the rows and columns and multiplies it by the amount of squares we get when we slide their corners along those sides($\times i$).

Example: squares size 3 in a 5 by 5 matrix:

++++*  *++++
+**+*  *+**+
+**+*  *+**+
++++*  *++++
*****  *****

*****  *****
++++*  *++++
+**+*  *+**+
+**+*  *+**+
++++*  *++++


squares by sliding along the edges of one size 3 square:

++++
+**+
+**+
++++

*+**
*+++
+++*
**+*

**+*
+++*
*+++
*+**


(i know its ugly but i couldn't do better)

• This formula is easy. The trick is counting all possible tilted squares as well. – ghosts_in_the_code Oct 28 '15 at 17:15
• @ghosts_in_the_code: This formula does that. I think better diagrams might be needed to explain why though ... – Tyler Seacrest Oct 28 '15 at 17:21