Given a matrix $\mathbf{A} \in \mathbb{C}^{N\times M}$ with $N \gg M$. This matrix results from a linear equation system and has a certain structure (however, I do not think that details provide any advantages).

This matrix should be solved via LS using $L \gt M \ll N$ rows. Choosing a consecutive set of rows results in a terribly defined matrix (huge condition nr.) but selecting the rows at random seems to give good results. Is there a way to figure out the best possible rows for minimum condition nr without $\mathcal{O}(N^M)$?

I found the same question regarding columns and the reference to Tropp's paper here: Optimizing the condition number. Is there something similar for the case of rows? Does the same apply if I just transpose $\mathbf{A}$ or is this misleading?