Can you find an invertible submatrix? Given an $m\times n$ matrix $\mathbf{A}$ $(m\gneqq n)$, I'm trying to efficiently find all $n\times n$ invertible submatrices using a computer. Equivalently, I'm trying to find which rows of $\mathbf{A}$ can form a linearly-independent set.
As an approach, I know I can iterate over all $m \choose n$ submatrices and compute their determinant, but I am hoping for a more efficient route. I thought about iteratively building up a solution, say starting by considering all solutions that include the first row. However, I don't know how to compute whether a set of fewer than $n$ vectors in $\mathbb{R}^n$ is linearly independent. (If it's exactly $n$ vectors, you test whether the determinant is zero or not; if it's more than $n$ vectors, it's obviously dependent; but if it's fewer, what do you do? Is there an algorithm?)
I am not sure I understand enough about linear algebra and properties of the null space to know how to compute these subsets efficiently. Any help would be appreciated.

Context #1 : The matrix $\mathbf{A}$ is not just any matrix. In my application, it's the null space of a particular matrix $\mathbf{B}$. So I am actually looking for the invertible submatrices $\mathrm{ null}(\mathbf{B})$.
Context #2: If it helps, I am working with a specific type of matrix useful for solving "number-tower puzzles".  The objective of the number-tower puzzle is to fill in numbers in a given triangular structure so that every number is equal to the sum of the two numbers below it. Some numbers are specified in advance, providing constraint. Example:

I wondered how many blocks (and which blocks) you had to specify in advance in order for the problem to be uniquely solvable. Because we're dealing with a sum constraint, we can express this as a matrix property. And because the $n$ nodes in the bottom row uniquely determine the solution, we know that it will always take exactly $n$ independent entries to uniquely determine the solution. But which of these blocks are independent?
A tower with $n$ blocks in the base has $n(n+1)/2$ total blocks. We can form an "ancestral path" matrix $\mathbf{A}$ with $n(n+1)/2$ rows and $n$ columns.  Entry $i,j$ is the number of upward paths to node $i$ from the base node $j$.  (Equivalently, the $j$th column of $\mathbf{A}$ lists the values of all the blocks in the pyramid when the $j$th base block has value 1, and all the other base blocks have value 0— a kind of basis set.) If you form a submatrix $\mathbf{D}$ by extracting $n$ rows of $\mathbf{A}$ (corresponding to $n$ blocks in the pyramid), those $n$ blocks may be filled out independently if and only if $\mathbf{D}$ is invertible. The question is then— how do you find all possible such submatrices?
Perhaps the triangular form of the tower offers some simplification, but I'm not sure.
 A: Updated Answer:
I would appreciate it if others double check this to make sure everything is correct, I would warn the reader there may be errors:
Important: I just realized that there are in fact invertible square matrices which are not triangular. Since any square matrix over the field of complex numbers can be conjugated to triangular matrices, so this approach could still be of use. I am not sure if this a good starting point for the question now that we are restricted to a field over the complex numbers, I'm going to leave this up in case it is of use to the OP or anyone else who wants to answer the question
--
I'm denoting the orignal m x n matrix B
Triangularize your n x n matrix A which is arbitrary if I understand the question correctly...
Then, we can put A in a matrix with abritrary m-n columns from B inserted into this matrix on the right side of A, such that (*) are nonzero, and * are either zero or nonzero. We'll call this new matrix C.
\begin{bmatrix}(*)&*&*&*&*&*&*&.&.&.&*\\0&(*)&*&*&*&*&*&.&.&.&*\\0&0&(*)&*&*&*&*&.&.&.&*\\0&0&0&(*)&*&*&*&.&.&.&*\\0&0&0&0&(*)&*&*&.&.&.&*\\0&0&0&0&0&(*)&*&.&.&.&*\end{bmatrix}
Note that this immediately implies that A, your n x n invertible matrix, will exist if and only if there exists a nonzero entry in each row of C!
A is thus an n x n triangular matrix with nonzero entries along the diagonal.
We can also determine at most how many A's are possible given B if C - A is a square triangular matrix with nonzeroes on the diagonal additionally with each column of C - A ≠ any column in A.. I haven't done the general case yet but I would be interested in seeing what it is if anyone else wants to try, as a general formula for the number of A's that exist may complete the answer.
Due to the conditions of C, A will still be invertible if we interchange any number of columns of A with the corresponding columns in C - A.
If we restrict the interchanging operation to just one column, we have (m - n) + 1 possible A's. We add the 1 as A, unchanged, is invertible.
If we restrict the interchanging operation to two columns, we have $(m - n) / 2 + 1$ possible A's
Continuing $m - n$ times,
There exist at most $$ y = \biggl(\sum_{i=1}^{m-n} \frac{m-n}{i}\biggr) + 1 $$
possible A's, given the conditions we set for C - A
