Check the match of the maximum of each subset Given a number of vectors with $n$ elements, i.e., $S=(a_1, \cdots, a_n)$, $T_j=(b_1^j, \cdots, b_n^j)$ for $j=1,\cdots, m$ where each $a_i$ or $b^i_j$ is a natural number.  

Question: determine whether, for all subset $I\subseteq \{1, \cdots, n\}$, there is some $T_j$ ($1\leq j\leq m$) such that $\max\{a_i\mid i\in I\}=\max\{b_i^j\mid i\in I\}$. 

Obviously there is an exponential time algorithm to do this (one can just enumerate all $I$), but can we do better to have a polynomial-time algorithm? or is it NP-hard?

Example: $S=(1,2,0)$, $T_1=(2,1,0)$, $T_2=(2,0,1)$, $T_3=(1,0,2)$, $T_4=(0,2,1)$ gives an affirmtive answer. 

Motivation: this question is from database research, the background of which is a bit hard to describe precisely here.
You can do the following. For every $i\in\{1,\dotsc,n\}$, start with the set $I=\{k\,:\,a_k\leqslant a_i\}$. Let $K=\{k\,:\,\exists j\ b_k^j=\max\{b^j_\ell\,:\,\ell\in I\}=a_i\}$. If $K=\emptyset$, then $I$ is a counterexample. If $i\in K$ then there is no counterexample with $i\in I$ and $a_i=\max\{a_k\,:\,k\in I\}$. If $K\neq\emptyset$ and $i\not\in K$ then any counterexample $J$ with $i\in J$ and $a_i=\max\{a_k\,:\,k\in J\}$ will be a subset of $I\setminus K$. So we can replace $I$ by $I\setminus K$, and iterate.

It is necessary and sufficient that for every $i$ we end up with $i\in K$.