How to find a non-singular sub-matrix in a full-rank matrix.

Question

Suppose we are given $A\in\mathbb{R}^{n\times m}$, where $n<m$, and we know that $A$ is a full-rank matrix. What is a simple and efficient way to find any submatrix $B\in\mathbb{R}^{n\times n}$ constructed of columns of $A$, such that $B$ is not singular? I want to have a Matlab function of the form [ind]=find_B(A) that returns indices of the columns of $A$ that allow constructing $B$.

Answer 1

These $n$ columns will form a basis of the column space of $A$. If you perform a row reduction the columns containing a leading $1$ will form such a basis. If you use the Matlab command

[R,p] = rref(A)

the indices of those columns should be returned in p.

Answer 2

You start with an empty set of column vectors. Then you iterate over columns in matrix $A$. If the column can be expressed as a linear combination of the vectors in the set, you skip the vector. Otherwise you add the vector to the set and continue. After you get n linearly independednt vectors, it is the matrix you are looking for.