Proof that the span of a list is equal to the span of any reordering of the list

58 Views Asked by At

Claim: If $(w_1,w_2,...w_m)$ is an arbitrary reordering of $(v_1,v_2,...v_m)$, then $span(w_1,w_2,...w_m) = span(v_1,v_2,...v_m)$.

Proof

By definition, $span(w_1,w_2,...w_m)=\{a_1w_1+...a_mw_m|a_i \in \mathbb F\}$.

Also, $span(v_1,v_2,...v_m)=\{b_1v_1+...b_mv_m|b_i \in \mathbb F\}$

So, to prove that $span(w_1,w_2,...w_m) = span(v_1,v_2,...v_m)$, we take an arbitrary $u \in span(w_1,w_2,...w_m)$, and show that there exists $b_1,b_2....b_m \in \mathbb F$ such that $u = b_1v_1+....b_mv_m$, and vice-versa.

Let $u \in span(w_1,...w_m)$

$\implies \exists \space a_1,a_2....a_m \in \mathbb F$ such that $u =a_1w_1+....a_mw_m$. But since $(w_1,....w_m)$ is a reordering of $(v_1,...v_m)$, $\forall \space i\in \{1,2,...m\} \space \exists ! \space j\in \{1,2....m\}$ such that $w_i = v_j$.

Therefore, $u = a_{t_1}v_1+...a_{t_m}v_m$, where $t_k = i$, for some $i \in \{1,2,...m\}$.

Now, set $b_i = a_{t_i}.$ Then, $u = b_1v_1+....b_mv_m \implies u \in span(v_1,...v_m).$

Now, starting with an arbitrary element $v \in span(v_1,...v_m)$, we do the same and obtain that $v \in span(w_1,...w_m)$.

Hence, $span(w_1,...w_m) \subset span(v_1,...v_m)$ and $span(v_1,...v_m) \subset span(w_1,...w_m) \implies span(w_1,...w_m) = span(v_1,...v_m)$

Q.E.D

Is this proof correct? Also, is it rigorous enough?