Any of the elements in $Q$ can be written as a linear combination of the elements in $S_0$. Let's say the elements in $S_0$ are $x_1,x_2,...x_r$. Thus, we have:
$$y_i=\alpha_{i,1}x_1+\alpha_{i,2}x_2+...+\alpha_{i,r}x_r \text{ for some scalars } \alpha_{i,j}$$
Now, let's say for some $y_i$, $\alpha_{i,j}$ is non-zero. Then, in $S_0$, we can replace $x_j$ with $y_i$ and we will still have the same span because $x_j$ can be found by subtracting $y_i$ by the other vectors in $S_0$ and then dividing by $\alpha_{i,j}$:
$$x_j=\frac{y_i-\alpha_{i,1}x_1-\alpha_{i,2}x_2-...-\alpha_{i,j-1}x_{j-1}-\alpha_{i,j+1}x_{j+1}-...-\alpha_{i,r}x_r}{\alpha{i,j}}$$
Thus, we replace $x_j$ with $y_i$ to get $S_1$.
Now, since $S_1$ spans $X$, we re-write all of the $Q$ as the following:
$$y_l=\beta_{l,1}x_1+\beta_{l,2}x_2+...+\beta_{l,j}y_j+...+\beta_{l,r}x_r \text{ for some scalar } \beta_{l,k}$$
Thus, we have new coefficients because of the new set $S_1$. However, there still exists a $y_l$ such that some $\beta_{l,k}$ is non-zero for $k \neq j$ because otherwise, all of the $y_l$ would be a linear combination of $y_i$, which would make $Q$ linearly dependent. Therefore, we can replace another element in $S_1$ as we did in $S_0$ by replacing $x_k$ with $y_l$.
Then, we get $S_2$ and we re-write the coefficients again. However, there is still some non-zero coefficient of an $x_n$ in one of the $y_m$s because otherwise, all of the elements in $Q$ would be a linear combination of $y_i$ and $y_l$, which would make $Q$ linearly dependent, so we replace $x_n$ with $y_m$ to get $S_3$.
Thus, we keep going with this until we get to $S_r$, at which point there are no $x_i$ vectors left and the last $r+1^{\text{th}}$ has to be a linear combination of the other $r$ vectors, contradicting the linear independence of $Q$.
