# How do I determine if a matrix is contained in another matrix?

Is there a clever way of determining if one matrix is contained within another larger matrix? Iterating over the larger matrix to check each item until potential matches show up is straightforward but gets slow for large matrices.

Example, a smaller matrix:

$\begin{pmatrix}4&3&2\\2&3&4\end{pmatrix}$

which is "within" (I'm probably not using the right terminology) this larger matrix:

$\begin{pmatrix}1&2&3&4&5\\5&\color{red}4&\color{red}3&\color{red}2&1\\1&\color{red}2&\color{red}3&\color{red}4&5\end{pmatrix}$

It feels like a problem that could have a smart mathematics trick for determining if this is the case - is there one?

• What does "contained" mean? Are you looking for any submatrix, or only those that form a single contiguous block? Feb 20 '12 at 1:03
• I updated the question with an example, please let me know what the proper terminology is.
– Nick
Feb 20 '12 at 1:18
• I think I've heard the term "contiguous submatrix" used in that context. Feb 20 '12 at 1:25
• That does make the problem easier; I think the arbitrary submatrix problem is a generalisation of the induced subgraph isomorphism problem, which is NP-complete. Luckily, you don't have to worry about that. Feb 20 '12 at 1:26
• This might be helpful for you: en.wikipedia.org/wiki/String_searching_algorithm Feb 20 '12 at 1:34