5
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Ethan Bolker Feb 15 '18 at 18:11
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Red Book 1 Feb 15 '18 at 18:52
  • $\begingroup$ $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. $\endgroup$ – Lord Shark the Unknown Feb 15 '18 at 18:54
  • $\begingroup$ 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? $\endgroup$ – Red Book 1 Feb 15 '18 at 18:59
  • $\begingroup$ @RedBook1 you could always just compute them all... $\endgroup$ – Lord Shark the Unknown Feb 15 '18 at 19:01
  • $\begingroup$ Yes I could but I am not a programmer and some of the matrices I shall be looking at will be much larger. Rgds. $\endgroup$ – Red Book 1 Feb 15 '18 at 19:05
0
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.