Proving U_1 + U_2 + ... + U_k = span (U_1 \cup U_2 \cup \ ... \ \cup U_k)

[JD_PM]

TL;DR Summary

I want to prove that $U_1 + U_2 + ... + U_k = span (U_1 \cup U_2 \cup ... \cup U_k)$ by induction

1) Base case $k=2$

$U_1 + U_2 = span (U_1 \cup U_2)$, which I understand how to prove is OK.

2) Induction hypothesis

We assume that the following statement holds

$$U_1 + U_2 + ... + U_{k-1} = span (U_1 \cup U_2 \cup \ ... \ \cup U_{k-1})$$

3) Induction step

$$U_1 + U_2 + ... + U_k = \underbrace{U_1 + U_2 + ... + U_{k-1}}_{=span (U_1 \cup U_2 \cup \ ... \ \cup U_{k-1})} + U_k = \ ? $$

But my issue is that I do not see how to move from $span (U_1 \cup U_2 \cup \ ... \ \cup U_{k-1})+U_k$

Might you guide me on how to proceed further?

Thanks!

 

[PeroK]

To prove two sets, $A$ and $B$, are equal you often show that $x \in A$ implies $x \in B$ and vice versa.

 

[JD_PM]

Hi @PeroK !

To prove two sets, $A$ and $B$, are equal you often show that $x \in A$ implies $x \in B$ and vice versa.

Oh, I see! So let's forget about induction.

We take $x=u_1 + u_2 + \dots + u_k \in U_1 + U_2 + \dots + U_k$ where $u_i \in U_i$.

Given that each element $u_i$ is found exclusively in $U_i$, there is no difference between $U_1 + U_2 + \dots + U_k$ and $U_1 \cup U_2 \cup \dots \cup U_k$. (let me know if you disagree with this statement).

Taking a linear combination of the elements $u_1 + u_2 + \dots + u_k$ leads to $x = \sum\limits_{j = 1}^k \beta_j u_j \in span (U_1 \cup U_2 \cup \dots \cup U_k)$

Let's now go the other way and take $x = \sum\limits_{j = 1}^r \beta_j u_j \in span (U_1 \cup U_2 \cup \dots \cup U_k)$. Next we construct sets: let $K_1$ be the set of indices $j$ such that $u_j \in U_1$, $K_2$ be the set of indices $j$ not in $K_1$ such that $u_j \in U_2$ and so on up to $u_j \in U_k$

Given that $K_i$ sets are disjoint, $x = \sum\limits_{i = 1}^n \sum\limits_{j \in K_j} \beta_j u_j$ and $\sum\limits_{j \in K_i} \beta_j u_j \in U_i$, we get $x \in U_1 + U_2 + \dots + U_k$

How do you see it? :)

PS: For what kind of proofs is best to use induction though?

 

[PeroK]

Hi @PeroK !



Oh, I see! So let's forget about induction.

That approach could apply to the inductive step!

 

[JD_PM]

OK I misunderstood you then. Do you have any comments on #3 though? Or you want me to focus only on induction.

 

[PeroK]

OK I misunderstood you then. Do you have any comments on #3 though? Or you want me to focus only on induction.

Hi @PeroK !



Oh, I see! So let's forget about induction.

We take $x=u_1 + u_2 + \dots + u_k \in U_1 + U_2 + \dots + U_k$ where $u_i \in U_i$.

Given that each element $u_i$ is found exclusively in $U_i$, there is no difference between $U_1 + U_2 + \dots + U_k$ and $U_1 \cup U_2 \cup \dots \cup U_k$. (let me know if you disagree with this statement).

Taking a linear combination of the elements $u_1 + u_2 + \dots + u_k$ leads to $x = \sum\limits_{j = 1}^k \beta_j u_j \in span (U_1 \cup U_2 \cup \dots \cup U_k)$

Let's now go the other way and take $x = \sum\limits_{j = 1}^r \beta_j u_j \in span (U_1 \cup U_2 \cup \dots \cup U_k)$. Next we construct sets: let $K_1$ be the set of indices $j$ such that $u_j \in U_1$, $K_2$ be the set of indices $j$ not in $K_1$ such that $u_j \in U_2$ and so on up to $u_j \in U_k$

Given that $K_i$ sets are disjoint, $x = \sum\limits_{i = 1}^n \sum\limits_{j \in K_j} \beta_j u_j$ and $\sum\limits_{j \in K_i} \beta_j u_j \in U_i$, we get $x \in U_1 + U_2 + \dots + U_k$

How do you see it? :)

PS: For what kind of proofs is best to use induction though?

Are you sure that the $U_i$ are disjoint? Are they not just any subspaces?

What I might have tried to do is to take $x \in span(U_1 \cup \dots U_{k+1})$ and show that $x = u + u_{k+1}$, where $u \in span(U_1 \cup \dots U_{k})$ and $u_{k+1} \in U_{k+1}$.

Then the inductive step should follow. Induction should simplify things, although it's the same basic idea.

 

[JD_PM]

Are you sure that the $U_i$ are disjoint? Are they not just any subspaces?

A more detailed proof without using induction can be found here.

 

[PeroK]

A more detailed proof without using induction can be found here.

I still think that using induction simplifies things. In particular, all we really need to show is that:
$$span(U_1 \cup \dots \cup U_{k+1}) = span(U_1 \cup \dots \cup U_k) + U_{k+1} $$
The RHS is clearly a subset of the LHS, so we need to show that:
$$v \in span(U_1 \cup \dots \cup U_{k+1}) \ \Rightarrow \ v \in span(U_1 \cup \dots \cup U_k) + U_{k+1}$$
An outline of the proof is that for such a vector $v$, we take all the terms that involve vectors in $U_{k+1}$ and (using the fact that $U_{k+1}$ is a subspace) recognise that this gives a single element of $U_{k+1}$. We also recognise that what is left is an element of $span(U_1 \cup \dots \cup U_k)$.

You can formalise this easily. And this should be simpler than having all those different sets of indices.

 

[StoneTemplePython]

edit: better to just echo what PeroK said.

 

[JD_PM]

Thanks for the clarification @PeroK !

The RHS is clearly a subset of the LHS, so we need to show that:
$$v \in span(U_1 \cup \dots \cup U_{k+1}) \ \Rightarrow \ v \in span(U_1 \cup \dots \cup U_k) + U_{k+1}$$
An outline of the proof is that for such a vector $v$, we take all the terms that involve vectors in $U_{k+1}$ and (using the fact that $U_{k+1}$ is a subspace) recognise that this gives a single element of $U_{k+1}$. We also recognise that what is left is an element of $span(U_1 \cup \dots \cup U_k)$.

Let me check my understanding :)

OK so let us start by taking $v \in span(U_1 \cup \dots \cup U_{k+1})$. Based on the definition of span, $v = \sum\limits_{j = 1}^{k+1} \beta_j u_j = \sum\limits_{j = 1}^{k} \beta_j u_j + \beta_{k+1} u_{k+1}$. The first and second terms equal (by definition) to $span(U_1 \cup \dots \cup U_k)$ and $span(U_{k+1})$ respectively. Since $U_{k+1}$ is a subspace, it is closed under linear combinations so $span(U_{k+1}) \subseteq U_{k+1}$. But by definition of span, we also have $U_{k+1} \subseteq span(U_{k+1})$. Hence $U_{k+1} = span(U_{k+1})$ and indeed we see that $v \in span(U_1 \cup \dots \cup U_k) + U_{k+1}$

 

[PeroK]

Thanks for the clarification @PeroK !



Let me check my understanding :)

OK so let us start by taking $v \in span(U_1 \cup \dots \cup U_{k+1})$. Based on the definition of span, $v = \sum\limits_{j = 1}^{k+1} \beta_j u_j = \sum\limits_{j = 1}^{k} \beta_j u_j + \beta_{k+1} u_{k+1}$.

It's more general than than: $$v = \sum_{j = 1}^n \beta_jv_j$$where $v_j \in U_1 \cup \dots \cup U_{k+1}$. Now, we let $$u_{k+1} = \sum_j \beta_jv_j$$ where we sum over all $j$ where $v_j \in U_{k+1}$ and let $$u = \sum_j \beta_jv_j$$ where we sum over all $j$ where $v_j \notin U_{k+1}$. This gives us $$v = u + u_{k+1}$$, where $u \in span(U_1 \cup \dots \cup U_k)$ and $u_{k+1} \in U_{k+1}$, hence:
$$v \in span(U_1 \cup \dots \cup U_k) + U_{k+1}$$
That can be used in your inductive step.

Note also that the base case for $k = 1$ is that we have $span(U_1) = U_1$.