[Question]
  [
*This is the 2-dimensional generalisation [of this challenge](https://codegolf.stackexchange.com/q/5529/8478).*
For our purposes, one matrix (or 2D array) *A* is considered a **submatrix** of another matrix *B*, if *A* can be obtained by completely removing a number of rows and columns from *B*. *(Note: some sources have different/more restrictive definitions.)*
Here's an example:
```
A = [1 4      B = [1 2 3 4 5 6
     2 1]          6 5 4 3 2 1
                   2 1 2 1 2 1
                   9 1 8 2 7 6]
```
We can delete columns 2, 3, 5, 6 and rows 2, 4 from *B* to obtain *A*:
```
B = [1 2 3 4 5 6         [1 _ _ 4 _ _         [1 4  = A
     6 5 4 3 2 1   -->    _ _ _ _ _ _   -->    2 1]
     2 1 2 1 2 1          2 _ _ 1 _ _
     9 1 8 2 7 6]         _ _ _ _ _ _]
```
Note that *A* is still a submatrix of *B* if all rows or all columns of *B* are retained (or in fact if *A = B*).
## The Challenge
You guessed it. Given two non-empty integer matrices *A* and *B*, determine if *A* is a submatrix of *B*.
You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument and outputting the result via STDOUT (or closest alternative), function return value or function (out) parameter.
Input may be in any convenient format. The matrices can be given as nested lists, strings using two different separators, flat lists along with the dimensions of the matrix, etc, as long as the input is not pre-processed. You may choose to take *B* first and *A* second, as long as your choice is consistent. You may assume that the elements of the matrices are positive and less then 256.
Output should be [truthy](http://meta.codegolf.stackexchange.com/a/2194/8478) if *A* is a submatrix of *B* and [falsy](http://meta.codegolf.stackexchange.com/a/2194/8478) otherwise. The specific output value does not have to be consistent.
Standard [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'") rules apply.
## Test Cases
Each test case is on a separate line, `A, B`.
Truthy cases:
```
[[1]], [[1]]
[[149, 221]], [[177, 149, 44, 221]]
[[1, 1, 2], [1, 2, 2]], [[1, 1, 1, 2, 2, 2], [3, 1, 3, 2, 3, 2], [1, 1, 2, 2, 2, 2]]
[[1, 2, 3], [4, 5, 6], [7, 8, 9]], [[1, 2, 3], [4, 7, 6], [7, 8, 9], [1, 2, 3], [4, 5, 6], [7, 8, 9]]
[[228, 66], [58, 228]], [[228, 66], [58, 228]]
[[1, 2], [2, 1]], [[1, 2, 2], [2, 1, 2], [2, 2, 1]]
[[136, 196], [252, 136]], [[136, 252, 210, 196, 79, 222], [222, 79, 196, 210, 252, 136], [252, 136, 252, 136, 252, 136], [180, 136, 56, 252, 158, 222]]
```
Falsy cases:
```
[[1]], [[2]]
[[224, 15]], [[144, 15, 12, 224]]
[[41], [150]], [[20, 41, 197, 150]]
[[1, 2, 3], [4, 5, 6], [7, 8, 9]], [[1, 2, 3], [7, 8, 9], [4, 5, 6]]
[[1, 2, 2], [2, 1, 2], [2, 2, 1]], [[1, 2], [2, 1]]
[[1, 2, 2], [2, 1, 2]], [[1, 2], [2, 1], [2, 2]]
[[1, 2], [3, 4]], [[5, 3, 4, 5], [2, 5, 5, 1], [4, 5, 5, 3], [5, 1, 2, 5]]
[[158, 112], [211, 211]], [[158, 211, 189, 112, 73, 8], [8, 73, 112, 189, 211, 158], [211, 158, 211, 158, 211, 158], [21, 158, 199, 211, 212, 8]]
```
  
[Answer]
# Pyth, 10 bytes
```
}CQsyMCMyE
```
[Test suite](https://pyth.herokuapp.com/?code=%7DCQsyMCMyE&input=%5B%5B1%5D%5D%0A%5B%5B1%5D%5D%0A%5B%5B1%2C+3%5D%5D%0A%5B%5B5%2C+1%2C+255%2C+3%5D%5D%0A%5B%5B1%2C+4%5D%2C+%5B2%2C+1%5D%5D%0A%5B%5B1%2C+4%5D%2C+%5B2%2C+1%5D%5D%0A%5B%5B1%2C+4%5D%2C+%5B2%2C+1%5D%5D%0A%5B%5B1%2C+2%2C+3%2C+4%2C+5%2C+6%5D%2C+%5B6%2C+5%2C+4%2C+3%2C+2%2C+1%5D%2C+%5B2%2C+1%2C+2%2C+1%2C+2%2C+1%5D%2C+%5B9%2C+1%2C+8%2C+2%2C+7%2C+6%5D%5D%0A%5B%5B1%5D%5D%0A%5B%5B2%5D%5D%0A%5B%5B3%2C+1%5D%5D%0A%5B%5B5%2C+1%2C+255%2C+3%5D%5D%0A%5B%5B1%5D%2C+%5B3%5D%5D%0A%5B%5B5%2C+1%2C+255%2C+3%5D%5D%0A%5B%5B1%2C+4%5D%2C+%5B2%2C+2%5D%5D%0A%5B%5B1%2C+2%2C+3%2C+4%2C+5%2C+6%5D%2C+%5B6%2C+5%2C+4%2C+3%2C+2%2C+1%5D%2C+%5B2%2C+1%2C+2%2C+1%2C+2%2C+1%5D%2C+%5B9%2C+1%2C+8%2C+2%2C+7%2C+6%5D%5D%0A&test_suite=1&test_suite_input=%5B%5B1%5D%5D%0A%5B%5B1%5D%5D%0A%5B%5B1%2C+3%5D%5D%0A%5B%5B5%2C+1%2C+255%2C+3%5D%5D%0A%5B%5B1%2C+4%5D%2C+%5B2%2C+1%5D%5D%0A%5B%5B1%2C+4%5D%2C+%5B2%2C+1%5D%5D%0A%5B%5B1%2C+4%5D%2C+%5B2%2C+1%5D%5D%0A%5B%5B1%2C+2%2C+3%2C+4%2C+5%2C+6%5D%2C+%5B6%2C+5%2C+4%2C+3%2C+2%2C+1%5D%2C+%5B2%2C+1%2C+2%2C+1%2C+2%2C+1%5D%2C+%5B9%2C+1%2C+8%2C+2%2C+7%2C+6%5D%5D%0A%5B%5B1%5D%5D%0A%5B%5B2%5D%5D%0A%5B%5B3%2C+1%5D%5D%0A%5B%5B5%2C+1%2C+255%2C+3%5D%5D%0A%5B%5B1%5D%2C+%5B3%5D%5D%0A%5B%5B5%2C+1%2C+255%2C+3%5D%5D%0A%5B%5B1%2C+4%5D%2C+%5B2%2C+2%5D%5D%0A%5B%5B1%2C+2%2C+3%2C+4%2C+5%2C+6%5D%2C+%5B6%2C+5%2C+4%2C+3%2C+2%2C+1%5D%2C+%5B2%2C+1%2C+2%2C+1%2C+2%2C+1%5D%2C+%5B9%2C+1%2C+8%2C+2%2C+7%2C+6%5D%5D&debug=0&input_size=2)
This is fairly straightforward. First, we consider B as a list of rows, and take all subsets using `yE`. Then, each of those matrices is transposed with `CM`, and all subsets are taken of their rows, with `yM`. Concatenating these sublists with `s` gives all possible transposed submatrices. So we transpose A with `CQ`, and check if it is present with `}`.
[Answer]
# Dyalog APL, ~~53~~ 43 bytes
```
(⊂A)∊⊃∘.{∧/∊2</¨⍺⍵:B[⍺;⍵]⋄⍬}/⍳¨(⍴A←⎕)/¨⍴B←⎕
```
`B←⎕`, `A←⎕`prompt for `B` and `A`  
`⍴B`, `⍴A` dimensions of `B` and `A`  
`/¨` replicate each, e.g. `2 3/¨4 5` → `(4 4) (5 5 5)`  
`⍳¨` all indices in each of the coordinate systems with those dimensions  
`∘.{`…`}/` table of possible submatrices, where each submatrix is defined as the result of the anonymous function `{`…`}` applied between a pair of coordinates `⍺` and `⍵`  
`∧/∊2</¨:` if both `⍺` and `⍵` are (`∧/∊`) both (`¨`) increasing (`2</`), then...  
`B[⍺;⍵]` return submatrix of `B` created from the intersections of rows `⍺` and columns `⍵`  
`⋄⍬` else, return an empty vector (something that A is not identical to)  
`(⊂A)∊⊃` check if the whole of `A` (`⊂A`) is a member of `∊` any of the submatrices (`⊃`)
---
### Old 53-byte solution:
```
{(⊂⍺)∊v∘.⌿h/¨⊂⍵⊣v h←(⍴⍺){↓⍉⍺{⍵/⍨⍺=+⌿⍵}(⍵/2)⊤⍳⍵*2}¨⍴⍵}
```
`{`…`}` an anonymous inline function, where `⍺` is left argument and `⍵` is right argument  
`⍴` shape, e.g. 2 3 for a 2-by-3 matrix  
`(⍴⍺){`…`}¨⍴⍵` for each pair of corresponding dimension-lengths, apply this anonymous function  
`⍳⍵*2` indices of the square of, i.e. 2 → 1 2 3 4  
`(⍵/2)⊤` convert to binary (number of bits is dimension-length squared)  
`{⍵/⍨⍺=+⌿⍵}` of the binary table, select the columns (`⍵/⍨`) where the number of 1s (`+⌿⍵`) is equal to the the length of that dimension in the potential submatrix (`⍺=`)  
`↓⍉` make table into list of columns  
`v h←` store as `v`(ertical masks) and `h`(horizontal masks)  
`⊣` then  
`h/¨⊂⍵` apply each horizontal mask to the right argument matrix  
`v∘.⌿` apply each vertical mask each one of the horizontally masked versions of the large matrix  
`(⊂⍺)∊` check if the left argument matrix is member thereof
[Answer]
## Jelly, ~~12~~ 10 bytes
*Thanks @Dennis for -2 bytes*
```
ZŒP
ÇÇ€;/i
```
Nearly the same algorithm as @isaacg, except we transpose the matrix before taking subsets.
```
ZŒP      Helper link. Input: z
Z          Transpose z
ZŒP        All subsets of columns of z.
ÇÇ€;/i   Main link. Input: B, A. B is a list of rows.
Ç          Call the helper link on B. This is the subsequences of columns of A.
 Ç€        Call the helper link on each column-subsequence.
           Now we have a list of lists of submatrices of B.
   ;/      Flatten that once. The list of submatrices of B.
     i     then get the 1-based index of A in that list.
           If A is not in the list, returns 0.
```
Try it [here](http://jelly.tryitonline.net/#code=WsWSUArDh8OH4oKsOy9p&input=&args=W1sxMzYsIDI1MiwgMjEwLCAxOTYsIDc5LCAyMjJdLCBbMjIyLCA3OSwgMTk2LCAyMTAsIDI1MiwgMTM2XSwgWzI1MiwgMTM2LCAyNTIsIDEzNiwgMjUyLCAxMzZdLCBbMTgwLCAxMzYsIDU2LCAyNTIsIDE1OCwgMjIyXV0+W1sxMzYsIDE5Nl0sIFsyNTIsIDEzNl1d).
[Answer]
# [Brachylog](https://github.com/JCumin/Brachylog), 4 bytes
```
⊇z⊇z
```
[Try it online!](https://tio.run/##nVLNTsMwDH6VqOeCGjdp0ws8SNXDQPwcJiEN0ARjF5BgcOItuCKkXTjyJuuLFNtx0hTBBWlV7M@f7c/2jhaz4/Ob@cUZDKtlpvYOVLY8XPWP7/39w267@froN2/Z1eL6ZD@7I/N0Nr9Ee737fF7vtq9D//J0S98wtKptW911ueKH3@BD9E2TK4BAq@tcMWSMwJ4GgL62wjLs4AdEMrEWIgiQQy@Zns@4QEIoGSgZKMekkcTZvq7RHLWFaC9QHnEbEktobE/FyEF9KK8iEzkuV01UklDqH5So@88a/2mUVA/suFQMVJxsHW3SyYC/4GlnXhbIsmO7AMoLaU6MJeImVSSHKdM0PI7xkOVL0QxCt/zT42RWRrbhkDZWKys6GM8ElvqUlYihCEOgC@bgYfg/6VUBeJ8DTIn5Sa0Rnca1KwS1MeJ3Ou6HfK19N026ddgTMwnSrmEOSsEVOIo6bzPIYU@0LtZJ0lPLxwXUTcgEKkSHVt03 "Brachylog – Try It Online")
Takes matrix B through the input variable and matrix A through the output variable, and outputs through success or failure. This is pretty much just the Pyth solution, except the input is more implicit and there's no explicit generation or membership checking for the powersets.
```
        B
⊇       has a sublist
 z      which transposed
  ⊇     has a sublist
   z    which transposed
        is A.
```
[Answer]
# Mathematica, 40 ~~65~~ bytes
```
!FreeQ[s[# ]&/@(s=Subsets)@#2,# ]&
```
Explanation: See one of the other answers -- it looks like they all did the same thing.
[Answer]
## Haskell, 66 bytes
```
import Data.List
t=transpose
s=subsequences
(.((s.t=<<).s)).elem.t
```
Usage example: `( (.((s.t=<<).s)).elem.t ) [[149, 221]] [[177, 149, 44, 221]]` -> `True`.
A non-pointfree version is
```
f a b = elem(transpose a) $ (subsequences.transpose=<<) $ subsequences b
                      subsequences b     -- make all subsequences of b, i.e. all 
                                         -- all combinations of rows removed
     (subsequences.transpose=<<)         -- transpose each such sub-matrix and
                                         -- remove rows again. Concatenate into a
                                         -- single list
elem(transpose a)                        -- check if the transposition of a is in
                                         -- the list
```
[Answer]
# Python + NumPy, ~~176~~ 173 bytes
```
from itertools import*
from numpy import*
def f(A,B):
 r,c=A.shape
 R,C=B.shape
 S=combinations
 print any([all(B[ix_(i,j)]==A)for i in S(range(R),r)for j in S(range(C),c)])
```
]