Let $M \in \mathbb{R}^{n \times m}$ be a matrix of rank $r$. I believe that there always exist row and column permutation matrices $P$ and $Q$ such that
$$P M Q = \left(\begin{array}{@{}c|c@{}} \begin{matrix} A \end{matrix} & B \\ \hline C & \begin{matrix} D \end{matrix} \end{array}\right)$$
for an invertible $r \times r$ matrix $A$. Is it correct? If it is, is it also possible to select the permutations in such a way that the maximal entry of the matrix is not in the block $D$?
The answer to the first part of the quesion is "yes".Suppose the rank of $M$ is $r$ and $M$ has a non-singular sub-matrix in rows $a_1,...,a_r$ and columns $b_1,...,b_r$. Number the remaining rows and columns $a_{r+1},...,a_n$ and $b_{r+1},...b_m$ respectively.Let $P$ be the $n \times n$ matrix in which, for $1 \le i \le n$, the $i-$ th row has 1 in column $a_i$ and 0 elsewhere.Let $Q$ be the $m \times m$ matrix in which, for $1 \le j \le m$, the $j-$ th column has 1 in row $b_j$ and 0 elsewhere. Your second question is harder in the case that the maximum element of $M$ is not contained in any non-singular $r \times r$ sub-matrix of $M$.