combinatorics - How many sub-square matrices does a square matrix have and is there a simple formula for it?

Consider an $n \times n$ matrix $M$. I want to find the determinant for ALL sub-square matrices of $M$. There may be a better way but my method is to find all sub-square matrices and check them individually.

1. How many sub-square matrices does a square matrix have and is there a simple formula for it?

The other problem is, after checking several videos I am not sure what counts as a sub-square matrix. I thought I could use the formula for the sum of squares, i.e.
$$S(n) = \frac{n(n+1)(2n+1)}{6}$$

But this gives sixteen $(1 \times 1)$ matrices, nine $(2 \times 2)$ matrices, four $(3 \times 3)$ matrices and one $(4 \times 4)$ matrices, i.e. a total of $30$ sub-square matrices.

$$\begin{pmatrix} 2 & 3 & 1 & 1 \\ 1 & 2 & 3 & 1 \\ 1 & 1 & 2 & 3 \\ 3 & 1 & 1 & 2 \end{pmatrix}$$

But, for example, I can find thirty-six $(2 \times 2)$ matrices by observation, i.e. six for any pair of rows. For example, the first two rows give:
$$\begin{equation} \begin{pmatrix} 2 & 3 \\ 1 & 2 \end{pmatrix} \begin{pmatrix} 2 & 1 \\ 1 & 3 \end{pmatrix} \begin{pmatrix} 2 & 1 \\ 1 & 1 \end{pmatrix} \begin{pmatrix} 3 & 1 \\ 2 & 3 \end{pmatrix} \begin{pmatrix} 3 & 1 \\ 2 & 1 \end{pmatrix} \begin{pmatrix} 1 & 1 \\ 3 & 1 \end{pmatrix} \end{equation}$$
If I do the same for rows $1$ and $3$, $1$ and $4$, $2$ and $3$, $2$ and $4$, and $3$ and $4$, I get thirty-six sub-square matrices by considering only $(2 \times 2)$ matrices. So now I am wondering if my way of counting sub-square matrices is wrong.

Any ideas?

Answer

If you admit the zero-by-zero matrix as a square submatrix, then the number
of square submatrices is

$$\sum_{k=0}^n\binom nk^2.$$
This can be written as
$$\sum_{k=0}^n\binom nk\binom n{n-k}$$
which can be recognised as the coefficient of $t^n$ in $(1+t)^n(1+t)^n$
etc.