Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Digital systems, linear algebra, introduction to formal proof / 4 / a

For the equal-cardinality basis criterion, because $S$ spans $V$, repeatedly remove a vector whenever it is a linear combination of the others. Such a removal does not change the span. The finite process ends with a linearly independent spanning subset $T$, hence a basis of $V$.

If the original $S$ were linearly dependent, at least one removal would occur and $|T|<n$. But a basis of an $n$-dimensional vector space has $n$ vectors. Equivalently, apply the allowed claim to the basis $T$ and any fixed $n$-vector basis of $V$: the latter would wrongly be linearly dependent. Thus no removal was possible. The original spanning set is linearly independent and therefore a basis.

Suppose a vector $v$ lies outside the span of $S$. Then $S\cup \{v\}$ is linearly independent: in an equation $\alpha v+{\sum }_i{\beta }_i{s}_i=0$, a nonzero $\alpha$ would express $v$ in that span, and with $\alpha =0$ the independence of $S$ forces every ${\beta }_i=0$.

This would give $n+1$ linearly independent vectors in a space with an $n$-vector basis, contrary to the supplied claim. Therefore $S$ spans $V$. Independence plus spanning makes $S$ a basis.