You would be selecting a permutation of columns and a permutation of the rows. The largest possible number is $(n!)^2$, if all entries are distinct: choose a permutation of the rows, $n!$; the resulting matrix satisfies the conditions. Then choose a permutation of the columns, $n!$ possibilities, and the matrix still satisfies the conditions.
If there are repeated entries, then it depends on exactly how you have repeats.
For example, if $n=2$, you get $4$ different matrices: $\left(\begin{array}{cc} a&b\\c&d\end{array}\right),\quad\left(\begin{array}{cc}b&a\\d&c\end{array}\right),\quad \left(\begin{array}{cc}c&d\\a&b\end{array}\right),\quad\left(\begin{array}{cc}d&c\\b&a\end{array}\right).$
If $n=3$, you have $36$ possibilities ( which I will not write in extenso); here is a way of verifying this by counting in a different way: if the original matrix is $\left(\begin{array}{ccc} a&b&c\\ d&e&f\\ g&h&k \end{array}\right)$ then you have $9$ possible positions for $a$; once $a$ is selected, you get two possibilities for placing $b$ in the same row, and two for placing $d$ in the same row. That determines uniquely the positions of $c$ and $g$; Once $c$ and $d$ are determined, that uniquely determines the position of $f$ (must be in the same row as $d$, same column as $c$), hence of $e$, and likewise the positions of $g$, $h$, and $k$ are now fixed. So in total you get $9\times2\times2=36 = 6\times 6 = 3!\times 3! = (3!)^2$ ways of doing it.