# Partitioning an orthogonal matrix into full rank square submatrices

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.

The permutation that you look for should exist for all nonsingular matrices $A$ --- the orthogonality is not necessary.

To see it, I will first present a proof based on determinants for the case of 2 submatrices. For simplicity, let us choose a fixed partition of the rows and permute columns rather than the opposite.

For each subset $\alpha$ of the rows of a matrix, you can divide the permutations in the Leibniz formula according to the image $\sigma(\alpha)$, hence getting the identity (generalized Laplace expansion) $$\tag{*} \det A = \sum_{\beta\subset\{1,2,\dots,n\}, |\beta|=|\alpha|} (-1)^{something} \det A(\alpha,\beta) \det A(\alpha^c,\beta^c).$$ The value of "something" depends on how one orders the elements in the various sets, and is not important here.

If $\det A$ is nonzero, then there is at least a nonzero summand; hence, for some $\beta$, $\det A(\alpha,\beta)$ and $\det A(\alpha^c,\beta^c)$ are nonzero. Choose a column permutation that brings $\beta$ to $\{1,2,\dots,|\beta|\}$, and bingo.

Expanding $A(\alpha,\beta)$ with the same formula inductively, one can obtain a generalization of ($*$) to more than two terms: for each row partition $(\alpha_1,\alpha_2,\dots,\alpha_k)$, $$\det A = \sum_{partitions(\beta_1,\dots,\beta_k) s.t. |\beta_i| = |\alpha_i|} (-1)^{something} \det A(\alpha_1,\beta_1) \det A(\alpha_2,\beta_2) \dots \det A(\alpha_k,\beta_k)$$ and then the same argument holds.

Thanks so much, Federico. That was very helpful. In case others are interested, this problem was also studied in the more general context of matroid theory in

C. Greene, "A multiple exchange property for bases," Proc. AMS, Jun. 1973

and

C. Greene and T. Magnanti, "Some abstract pivot algorithms," Linear Algebra Appl., Nov. 1975

which give proofs along the same lines suggested by Federico. Interestingly, the latter of the two articles also answers the second part of my original question by providing a constructive algorithm for carrying out multiple exchanges to find the desired partition.