# 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?

• You just figured out that you miscounted the number of $2 \times 2$ submatrices by showing how to count them all by choosing $2$ rows and $3$ columns. That kind of argument will count the square submatrices of any size. Then sum the counts. I don't know whether that sum has a nice closed form, but you could edit to make that your question. – Ethan Bolker Feb 15 '18 at 18:11

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.

• So by your formula I should find $1^2 + 4^2 + 6^2 + 4^2 + 1^2 = 70$ sub-square matrices from a $4 \times 4$ matrix? This is with $k = 0, 1,2,3,4$, respectively. Well, the $0$-by-$0$, $1$-by-$1$ and $4$-by-$4$ matrices are easy enough to spot. And I have already found the thirty-six $2$-by-$2$ matrices ... so just the sixteen $3$-by-$3$ matrices then? I shall keep trying, at least know how many I need to find. Many thanks. And is there some easy way to check if the determinants of all $70$ sub-matrices are singular? – Red Book 1 Feb 15 '18 at 18:52
• $1^2+\cdots+1^2=70$, not $81$. You get the three-by-three submatrices by deleting one row and one column of your original matrix. – Lord Shark the Unknown Feb 15 '18 at 18:54
• Yes indeed. I thought I had corrected it in time! This is my seeing $1^2$ as $12$. So is there a way to check if all sub-square matrices have non-zero determinants? – Red Book 1 Feb 15 '18 at 18:59
• @RedBook1 you could always just compute them all... – Lord Shark the Unknown Feb 15 '18 at 19:01
• Yes I could but I am not a programmer and some of the matrices I shall be looking at will be much larger. Rgds. – Red Book 1 Feb 15 '18 at 19:05

There’s 9 2x2 matrices if you only count ones that are touching. 3 for each row.

2 3 _ 3 1 _ 1 1 _ 1 2 _ 2 3 _ 3 1 _ 1 1 _ 1 2 _ 2 3
1 2 _ 2 3 _ 3 1 _ 1 1 _ 1 2 _ 2 3 _ 3 1 _ 1 1 _ 1 2

• How do you add matrices? – Joshiepillow Feb 15 '18 at 18:20