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$
$\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$– hardmathSep 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 SSep 10 at 17:29
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.