Algorithms for extracting a basis

Question

Let us consider a rectangle matrix $A$ in $M_{mn}(\mathbb{C})$ with $m<n$. Suppose that $\operatorname{rank}A=m$. What are the well-know algorithms to extract $m$ linearly independent columns of $A$?

Answer 1

You can simply reduce the rows of $A$ to its reduced row echelon form: $E$. We know that this process corresponds to multiply an invertible matrix $B$ to left side of $A$, i.e., $BA=E$.

Now it is easy to find the linearly independent columns of $E$, since they are some vectors of the canonical basis of $\mathbb{C}^m$.

Suppose the linearly independent columns of $E$ are $e_{i_1},\ldots,e_{i_s}$, let $a_{i_1},\ldots,a_{i_s}$ be the corresponding columns of $A$. Since $B$ is invertible and $Ba_{i_1}=e_{i_1}, \ldots, Ba_{i_s}=e_{i_s}$ then $a_{i_1},\ldots,a_{i_s}$ are linearly independent too.

Answer 2

Gauss-Jordan elimination is a convenient way to write a matrix with entries in $\mathbb{C}$ in reduced row echelon form, thereby revealing any pivot columns, corresponding to the linearly independent columns of the matrix in question.