Find all subsets of basis vectors of a given spanned linear subspace The exercise is, given multiple vectors $v_1, v_2, \ldots, v_n$, which span a linear subspace $U=span\{v_1, v_2, \ldots, v_n\}$, to determine all subsets of them, which are a basis of that subspace. This implies, of course, that not all given vectors are linearly independent.
In class we discussed the method of writing all vectors vertically into a matrix $A = (v_1, v_2, \ldots, v_n)$ and then performing Gaussian elimination steps to obtain an upper triangular matrix.
For example I obtained for some (irrelevant) vectors $U = span\{v_1, v_2, v_3, v_4\}$ the matrix
$$A=\begin{pmatrix}
1 & 2 & 3 & 4 \\
0 & 7 & 8 & 9 \\
0 & 0 & 0 & 1
\end{pmatrix}$$
This implies that ${v_1, v_2, v_4}$ build a basis for $U$.
How can I determine other subsets of the given vectors, which form a basis as well?
A friend said that vectors on the same step are alternative, i.e. I could have chosen vector 3 instead of vector 2 in the aforementioned basis because vector 3 is on the same step as vector 2 in the matrix.

Once you got that matrix, you already know that the subspace has dimension $3$, so only subsets with three vectors matter. There are only four ways in which you can choose three out of four. 
From you matrix you can see that $v_4$ can never be written as a linear combination of the other three. So now the only possible subsets are 
$$
\{v_1,v_2,v_4\},\ \{v_1,v_3,v_4\}, \{v_2,v_3,v_4\}.
$$
And the three sets are good, because each of $\{v_1,v_2\}$, $\{v_1,v_3\}$, and $\{v_2,v_3\}$ are linearly independent. 
