# Prove Matrix Correspondence is NP-complete

Consider the following problem. Given a $m \times n$ integer matrix $A$ and a $p \times q$ integer matrix $B$, do there exist one-to-one functions $$r:\{1,2,...,m\} \rightarrow \{1,2,...,p\}$$ $$c:\{1,2,...,n\} \rightarrow \{1,2,...,q\}$$ where for all $1 \leq i \leq m$ and $1 \leq j \leq n$, $A[i,j] \leq B[r(i),c(j)]$?

What is the best way to show this problem is NP-complete? I am currently considering reducing the clique problem to this problem.

As you mentioned, we can reduce maximum clique problem to this. In fact we can reduce the more general subgraph isomorphism problem to this one easily. Given graphs $G$ and $H$, define $A$ and $B$ as their (undirected) incidence matrices. Then we can see that solving the matrix correspondence tells whether $G$ is isomorphic to some subgraph of $H$, which is an NP-complete problem.