Question

In a m*n order Matrix, How many submatrices are possible?

Answer 1

To form a Sub-matrix , we have a choice for each row & column - to take or not to take. 

So, total we have 2^m * 2ⁿ choices , 

But we have to exclude matrix having 0 rows & 0 columns -  which can be formed when we delete all rows OR All Columns , which correspond to  2^m + 2ⁿ - 1 ways.

Let's see with an example - 

Comments

Sir, what about matrix like

[1 1 2], how many submatrices exist for it?

Answer 2

no of submatirx  = m(m+1)n(n+1)/4

Answer 3

CONSIDER THIS AS SUBSTRING PROBLEM

given (ab)=a,b,ab(these are possible substrings) =3 number of substrings=x(x+1)/2

but null not be considered as that would produce null matrix

SIMILARLY u can think column also as substring ...so when

M         X         N  matrix is given ...we have

{M(M+1)}/2     * {N(N+1)}/2= M(M+1)N(N+1)/4 in total

Comments

if I take 1*3 order matrix [1 2 3] then according the formula provided by you total submatrices will be 6 but total submatrices should be 7.

---

u are making (123)= 1        2          3         

                              12         23           

                              123..........................dont make 13 as its not submatrix...and we dont include null matrix too soo ...its 6 in general and by formula too

and can see in string form too..substring of 123=1,2,3,12,23,123