Let $A$ be an $m \times n$ matrix, $m\geq n$, and let $A=U\Sigma V^T$ be its singular value decomposition.

Let us partition $A$ as $A=(A_1|A_2)$, where $A_1$ is of size $m \times k$, and all columns of $A_2$ are linear combinations of the columns of $A_1$. The columns of $A_1$ are linearly independent, so rank$(A)=k$.

Let us consider permutation matrices $\Pi_{i,k}$ that switch columns $i$ and $k$, where $1 \leq i\leq k$. That is, permutations are restricted to the first $k$ columns. Let us partition $\Pi_{i,k}$ and $V$ as $\Pi_{i,k}=(\Pi_1|\Pi_2)$, $V=(V_1|V_2)$ where $\Pi_1,V_1$ are of size $n\times k-1$.

For each $\Pi_{i,k}$, we consider a submatrix of $V$ defined as $$ V_{i,k}'= \Pi_2^TV_2 $$

If we denote the smallest singular value of some matrix $M$ as $\sigma_{min}(M)$, we consider the permutation $\Pi_{i,k}$ such that $\sigma_{min}(V_{i,k}')$ is maximized.

**Can we provide a lower bound for $\sigma_{min}(V_{i,k}')$ ?**

The following reference might be helpful. In

*Hong, Yoo Pyo, and C-T. Pan. "Rank-revealing ๐๐
factorizations and the singular value decomposition." Mathematics of Computation 58.197 (1992): 213-232.*

a bound is given for general permutations $\Pi$.

The ultimate purpose is to bound the lower-right $n-k+1 \times n-k+1$ block of matrix $R$ in the $QR$ factorization of the permuted matrix $A$.