Let $U$ be an $n \times n$ orthogonal matrix. Given an arbitrary partition ${\mathcal P}_c=\{y_1,y_2,\ldots,y_k\}$ of the columns of $U$, does there always exist a corresponding partition ${\mathcal P}_r=\{x_1,x_2,\ldots,x_k\}$ of the rows such that the cardinality of $x_i$ is the same as the cardinality of $y_i$ for all $i$, and each of the square submatrices obtained by taking the rows indexed by $x_i$ and columns indexed by $y_i$ has full rank?

For example, if $n=8$ and ${\mathcal P}_c=\{ \{1,2,3\}, \{4,5,6\}, \{7,8\} \}$, can I find a row permutation matrix $P$ such that the three submatrices $\bar{U}[1:3,1:3]$, $\bar{U}[4:6,4:6]$, and $\bar{U}[7:8,7:8]$ are all full rank, where $\bar{U}=PU$?

I am interested in (i) whether such a row partition always exists, and (ii) if so, if there is an efficient algorithm to construct it.

If the partition ${\mathcal P}_c$ has only two elements, say $\{1,2,\ldots,j\}$ and $\{j+1,\ldots,n\}$ w.l.o.g., then we can always find such a partition of the rows. By the Steinitz exchange lemma, we exchange $j$ columns of the identity matrix with the first $j$ columns of $U$ such that $\{u_1,u_2,\ldots,u_j,e_{i_{j+1}},e_{i_{j+2}},\ldots,e_{i_{n}}\}$ span $\mathbb{R}^n$, and the indices ${\mathcal I}=\{i_1,i_2,\ldots,i_j\}$ of the columns of the identity matrix that were removed form the element of ${\mathcal P}_r$ corresponding to $\{1,2,\ldots,j\}$ in ${\mathcal P}_c$. That is, the submatrix $U[{\mathcal I},1:j]$ has full rank $j$.

Then the complementary submatrix $U[{\mathcal I}^c,j+1:n]$ has full rank $n-j$. This fact follows from either the CS decomposition (see equation (32) of C.C. Paige and M. Wei, "History and generality of the CS decomposition," Linear Algebra and Its Applications, 1992), or the nullity theorem (see Theorem 2.1 of G. Strang and T. Nguyen, "The interplay of ranks and submatrices," SIAM Review, 2004).

Can this be extended to partitions ${\mathcal P}_c$ with $k>2$ elements?

It also probably isn't too difficulty to assign a probability measure to orthogonal matrices and show that the desired conclusion is true almost surely, but I am most interested in determining whether it is true for all orthogonal matrices (or perhaps even for all full rank square matrices).

Thanks in advance for any references or suggestions.