Can a nonsingular matrix be column-permuted so that the diagonal blocks are nonsingular?

Question

Suppose that $A\in M_{n+m}(\mathbf C)$ (i.e. a $(n+m)\times (n+m)$ complex matrix) is non-singular. Is it always possible to find a permutation matrix $P$ so that

$$AP = \begin{bmatrix} A_1 & A_2 \\ A_3 & A_4\end{bmatrix}$$

where $A_1\in M_n(\mathbf C)$ and $A_4 \in M_m(\mathbf C)$ are non-singular?

It appears true for small matrices, e.g., $n = m = 1$. But I had a hard time proving it in general or coming up with a counter-example, and would appreciate some help.

Answer 1

Yes, it's always possible. For any positive integer $k$, define $[k]=\{1,2,\ldots,k\}$. Let $I=[n]$. By Laplace expansion theorem, $$ \det(A)=(-1)^{\sum_{i\in I}i}\sum_{J\in\binom{[n+m]}{m}}(-1)^{\sum_{j\in J}j}\det(A[I,J])\det(A(I,J)),\tag{1} $$ where:

• $\binom{[n+m]}{m}$ is the set of all strictly increasing sequences of $m$ distinct indices chosen from $[n+m]=\{1,2,\ldots,n+m\}$,
• $A(I,J)$ denotes the submatrix of $A$ obtained by removing all rows indexed by $I$ and all columns indexed by $J$, and
• $A[I,J]$ denotes the submatrix of $A$ obtained from the rows indexed by $I$ and the columns indexed by $J$, i.e. it is the submatrix complementary to $A(I,J)$. Formally, $A[I,J]=A([n+m]-I,\,[n+m]-J)$.

It follows from $(1)$ that if $A$ is nonsingular, $\det(A[I,J])\det(A(I,J))$ must be nonzero for some $J$. Hence $A[I,J]$ and $A(I,J)$ are nonsingular. Let $P$ be any permutation matrix whose first $n$ columns are the standard basis vectors $e_j$s such that $j\in J$. Then the result follows.