Is there a better way than brute forcing (choose $k=\mathrm{rank}(A)$ first columns - test the determinant, if determinant = 0 choose new column set - there are $\binom nk$ many possibilities which is inefficient if the full rank sub matrices are rare!)

  • $\begingroup$ I suppose that efficiency is relative to how one knows that $\operatorname{rank}(A) = k$. If that was determined by computing the row echelon form of $A$, naturally the way @DanielS proposes to pick the rows will be attractive. Far from being rare, "full rank sub matrices" are (in general position) of probability one. So perhaps the rank of the matrix is not known? It would be helpful in any case to more fully describe what is known a priori about $A$. $\endgroup$
    – hardmath
    Sep 10 at 17:20
  • 1
    $\begingroup$ @hardmath the probability of a full rank sub matrix depends on what field you are working over (and indeed the structure of the matrix) . $\endgroup$
    – Daniel S
    Sep 10 at 17:29

1 Answer 1


Compute the row echelon form of the matrix and select the pivot columns. Computing the row echelon form of a $m\times n$ matrix will take $O(m^2n)$ field operation, which is pretty straightforward. If full rank submatrices are not sparse, you can save further work by ignoring some of the columns.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.