Let
$$A = \left[ \begin{array}{ccc} & B_{(n(m+1)-m) \times (n(m+1))} & \\ \hline Z_{m \times (nm)} & | & S_{m \times n} \end{array} \right]$$
be a block matrix where $B_{(n(m+1)-m) \times (n(m+1))}$ is full rank, $Z_{m \times (nm)}$ is a "zero matrix", and $S_{m \times n}$ is some sort of "choice" matrix such that there is only one $1$ in each row and each column (the rest being zeros), e.g. $\bigl( \begin{smallmatrix} 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1\end{smallmatrix} \bigr)$. More importantly, $n \geq m$.
I want to minimize the condition number of $A$ w.r.t. $S$, i.e. $\min_{S} \kappa(A)$. It seems to me that one approach is to use some sort of branch-and-bound technique to cope with the combinatorial explosition, since there are $\frac{n!}{(n-m)!}$ possible ways $S$ can be.