2

I am following https://taninamdar.files.wordpress.com/2013/11/submatrices3.pdf to find total number of sub matrix of a matrix.But am stuck how to find how many sub matrix of a given size is present in a matrix. Also 0<=A<=M and 0<=B<=N.
where AxB(submatrix size) and MxN(matrix size).

js_248
  • 2,032
  • 4
  • 27
  • 38
  • The answer is `C(M, A) * C(N, B)`, where `C(X, Y)` is the binomial coefficient, i.e. `C(X, Y) = X! / (Y! (X - Y)!)`. – WhatsUp Jun 04 '16 at 19:44
  • If we consider first matrix as 3X3 then number of submatrix of size 2X2 will be only 4.But by your answer I am getting 9. – js_248 Jun 04 '16 at 19:51
  • Apparently they must be contiguous submatrixes, the pdf neglects to mention that. – harold Jun 04 '16 at 20:16

1 Answers1

4

I didn't go through the pdf (math and I aren't friends), however simple logic is enough here. Simply, try to reduce the dimension: How many vectors of length m can you put in a vector of length n ?

Answer: n-m+1. To convince you, just go through the cases. Say n = 5 and m = 5. You've got one possibility. With n = 5 and m = 4, you've got two (second vector starts at index 0 or index 1). With n = 5 and m = 3, you've got three (vector can start at index 0, 1 or 2). And for n = 5 and m = 1, you've got 5, seems logic.

So, in order to apply that to a matrix, you have to add a dimension. How do you do that ? Multiplication. How many vectors of length a can you put inside a vector of length n ? n-a+1. How many vectors of length b can you put inside a vector of length m ? m-b+1.

So, how many matrices of size A*B can you put in a matrix of length N*M ? (N-A+1)*(M-B+1).

So, I didn't handle the case where one of the dimension is 0. It depends on how you consider this case.

T. Claverie
  • 11,380
  • 1
  • 17
  • 28