Consider an $m\times n$ array $A$; that is, $A=\{(s,t)\mid 1\leq s\leq m,\,1\leq t\leq n\}$. Let $f$ be a permutation of $A$. Is it necessarily true that there exist a set $$ B=\{ (1,x_1),(2,x_2),...,(m,x_m)\}\subset A $$ where $1\leq x_i\leq n$ for $1\leq i\leq m$, such that $$ f(B)=\{(1,y_1),(2,y_2),...,(m,y_m)\} $$ where $1\leq y_i\leq n$ for $1\leq i\leq m$?
In other words, if we have a permutation of some rectangular array, does it contain a permutation of the rows and a permutation of the columns?
The result trivially holds when $m=n=0$. It's trivially false if $\min\{m,n\}=0$ and $\max\{m,n\}>0$. It's trivially true if $\min\{m,n\}=1$. So we skip these cases.
Let $X,Y$ be two disjoint $m$-element sets and write $X=\{x_1,\ldots, x_m\}$ and $Y=\{y_1,\ldots, y_m\}$. Define a simple, bipartite graph on the vertex set $X\cup Y$ by letting $x_i,y_j$ be adjacent iff there exist $s,t\in \{1,\ldots, n\}$ such that $f((i,s))=(j,t)$. For a subset $T$ of $X$, let $N_G(T)$ denote the set of $y\in Y$ which are adjacent to at least one $x\in T$. We claim that $|T|\leqslant |N_G(T)|$ for all $T\subset X$. If it were true that there existed some $T=\{i_1,\ldots, i_p\}\subset X$ such that $N_G(T)=\{j_1,\ldots, j_q\}$ with $q<p$, this would mean that the $pn$ members of $$\{(i_k,j):1\leqslant k\leqslant p, 1\leqslant j\leqslant n\}$$ would be sent by $f$ into $$\{(j_k,j):1\leqslant k\leqslant q,1\leqslant j\leqslant n\},$$ which has cardinality $qn<pn$. This is a contradiction, since $f$ is a bijection.
By Hall's marriage theorem, there exists a perfect matching. That means there exist distinct edges $e_1,\ldots, e_m$ in our graph such that $e_i$ is between $x_i$ and some member of $Y$, and such that no member of $Y$ is incident on two of the edges in the list $e_1,\ldots, e_m$. Therefore the $Y$-endpoints of the edges $e_1,\ldots, e_m$ must be all of $Y$, since $|Y|=m$. So there exist $j_1,\ldots, j_m$ such that $e_k$ is between $x_k$ and $y_{j_k}$, and such that $j_1,\ldots, j_m=\{1,\ldots, j_m\}$.
The edge $e_k$ between $x_k$ and $y_{j_k}$, by definition, means there exist $s_k,t_k\in\{1,\ldots, n\}$ such that $f(k,s_k)=(j_k,t_k)$. We let $$B=\{(1,s_1),\ldots, (m,s_m)\},$$ so that $$f(B)=\{(j_1,t_1), \ldots, (j_m,t_m)\}.$$ Since $j_1,\ldots, j_m$, $$f(B)=\{(1,u_1),\ldots, (m,u_m)\},$$ where $u_{j_k}=t_k$.