Let's suppose I have a $4 \times 3$ matrix. Then, is there any way I can compute the number of square submatrices it can form, also the number of square submatrices of given order like say 3, which is 4 ( as I can count it easily for the given matrix), but what about for the number of square submatrices I can form of order 2 from the given matrix. Is it a permutation and combination problem, or we can figure it our intuitively.
Number of submatrices from a given matrix
combinatoricslinear algebramatricespermutations
Best Answer
If you have an $m \times n$ matrix, and you want to find the number of $p \times q$ submatrices found within it, then you need to choose $p$ rows from the $m$ available, and $q$ columns from the $n$ available. The total number of such is $\binom{m}{p}\binom{n}{q}$.
For example, if the matrix is $4 \times 3$ and you want to know the number of $3\times 3$ submatrices, the answer is $\binom{4}{3} \binom{3}{3} = 4$. Or the number of $2\times2$ submatrices will be $\binom{4}{2}\binom{3}{2} = 6 \times 3 = 18$.