Row-valid and column-valid $nxn$ tables of 1..$n^2$. For what $n$ can any row-valid table be permuted into $a$ column-valid one?

Step 1 (Bipartite Graph Formulation): We represent the $n\times n$ table as a bipartite graph $G=(V_1\cup V_2,E)$. The vertices in $V_1$ represent the $n$ rows of the table, and the vertices in $V_2$ represent the $n$ column positions/values. An edge exists between row $i$ and value $v$ if value $v$ appears in row $i$.

Step 2 (Regularity and Hall's Condition): Since the table is row-valid, each row contains the numbers $1,2,\dots ,n$ exactly once. Thus, the degree of every vertex in $V_1$ is exactly $n$. By symmetric properties, each value appears exactly $n$ times in the table, meaning the degree of every vertex in $V_2$ is also exactly $n$. Therefore, $G$ is an $n$-regular bipartite graph.

Step 3 (Decomposition into Matchings): Every $n$-regular bipartite graph can be decomposed into exactly $n$ disjoint perfect matchings (by the Birkhoff-von Neumann theorem or Hall's Marriage Theorem). Each perfect matching corresponds to selecting exactly one element from each row such that all selected elements are distinct. By assigning each perfect matching to a different column position, we can permute the elements within each row to make the columns valid. Thus, it is possible for all $n$. $■$