Find all sub matrices of type N*M in it which are palindromic
Checking if a matrix is a palindrom can be simplified using the fact that you store your matrices as a list of rows.

If the matrix is a palindrom, then:


each line is a palindrom by itself;
each line is equal to its symetic (first with last, second with the one before last, etc).


Which can be written like:

def check_palindrome(mat):
    for i, row in enumerate(mat, 1):
        if row != row[::-1]:
            # The current row is not a palindrome
            return False
        if row != mat[-i]:
            # One of the columns is not a palindrome
            return False
    return True


Here I use the second argument of enumerate to get the correct index when accessing the matrix backwards.

This writing can be simplified using the all builtin:

def check_palindrome(mat):
    return all(
            row == mat[-i] and row == row[::-1]
            for i, row in enumerate(mat, 1)
    )


You can also shave half the tests by using enumerate(mat[:(len(mat)+1)//2], 1) but it won't change the overall complexity.