0
$\begingroup$

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!)

$\endgroup$
2
  • $\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
    Commented Sep 10, 2023 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
    Commented Sep 10, 2023 at 17:29

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

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

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