# Proof that $\dim(U_1+U_2) = \dim U_1 + \dim U_2 - \dim(U_1\cap U_2)$

Lemma 1: If the subspace $U_1$ is spanned by $L$ and $U_2$ by $H$ then $\text{span}(L\cup H) = U_1 + U_2$

Linear Independence Lemma: If $(v_1,...,v_m)$ is linearly dependent in V then there exists $j \in \{2,...m\}$ such that:

a. $v_j \in \text{span}(v_1,...,v_{j-1})$

b. If the j-th term is removed from $(v_1,...,v_m)$ the span of the remaining list equals $\text{span}(v_1,...,v_m)$.

Proof of Theorem: For two subspaces $U$ and $W$ spanned by $(u_1,...,u_m)$ and $(w_1,...,w_n)$ respectively we have (by lemma 1) that $U+W$ is is spanned by $S=(u_1,...,u_m,w_1,...,w_n)$.

Assume that S is linearly independent. Then $U \cap W = 0$ and $\dim(U+W) = m+n = \dim(U) + \dim(W)$ so the identity holds.

Assume that S is linearly dependent. By the linear dependence lemma, there is a $w_i$ in S such that we can remove $w_i$ from S and we will still span $U+W$. We can continue this process until S is linearly independent and therefore a basis of $U+W$. Let $b$ be the number of elements that we removed from S. We have $\dim (U+W) = m+n-b$. By the linear independence lemma, every element we removed from S could be written as a linear combination of other elements in S, therefore each element we removed from S would have to be included in $U\cap W$. So $\dim(U\cap W)=b$ So the identity reduces to $m+n-b=m+n-b$. Q.E.D

This is a theorem in my textbook that the author took a different approach to prove. I'm worried about how true the claim "By the linear independence lemma, every element we removed from S could be written as a linear combination of other elements in S, therefore each element we removed from S would have to be included in $U\cap W$." is and the validity of lemma 1. If anyone could confirm my proof or find the flaw that would be great. Thank you.

• you need a proof for lemma 1 ou what exactly ? – Hamza Jul 13 '16 at 22:35
• I would like a verification of the whole proof @Hamza – orange_juice Jul 13 '16 at 22:36

The statement that each element we removed from $S$ is an element of $U \cap W$ is false. For example, let $L = \{u_1 = (1,0,0), u_2 = (1,0,1)\}$ and $H = \{w_1 = (0,1,1), w_2=(0,1,-1)\}$. Here $L\cup H$ spans the whole space $R^3$, $U \cap W$ is the space generated by $e_3 = (0,0,1)$, but its basis is not part of $L \cup H$.

This a simple proof of the equality:

Let $\Phi: U_1\times U_2\to U_1+U_2,\; (u_1,u_2)\mapsto u_1+u_2$. Then $\Phi$ is a linear transformation and $\operatorname{Im}\Phi=U_1+U_2$ and $\ker \Phi$ is isomorphic to $U_1\cap U_2$. Hence the rank-nullity theorem applied to $\Phi$ gives the desired equality.

• Unfortunately I'm not quite at that level. Could you address the proof I provide specifically? Thank you. – orange_juice Jul 13 '16 at 22:04
• Been trying to reach you, and any other interested parties! chat.stackexchange.com/rooms/43593/… – amWhy Aug 15 '16 at 19:20
• How do you get the $-\dim(U_1\bigcap U_2)$ from $\dim \ker(\Phi)$? – Pedro Gomes Jul 13 '17 at 18:41
• Could you please explain me how you went from $\dim \ker(\Phi)$ to $\dim \ker(\Phi)$? – Pedro Gomes Jul 14 '17 at 11:25

Instead of complicating the argument using induction, you may argue as follows: let $\mathcal B$ be a basis of $U_1 \cap U_2$. Extend $\mathcal B$ to bases $\mathcal B_1$ and $\mathcal B_2$ of $U_1$ and $U_2$, respectively. Then, by the inclusion-exclusion principle, we have

$$| \mathcal B_1 \cup \mathcal B_2 | = |\mathcal B_1| + |\mathcal B_2| - |\mathcal B_1 \cap \mathcal B_2|$$

where the horizontal bars denote set cardinality. I claim that $\mathcal B = \mathcal B_1 \cap \mathcal B_2$. Indeed, the inclusion $\mathcal B \subseteq \mathcal B_1 \cap \mathcal B_2$ is obvious from construction. The reverse inclusion follows since $\mathcal B_1 \cap \mathcal B_2$ is linearly independent, therefore its cardinality is at most $|\mathcal B|$. Showing that $\mathcal B_1 \cup \mathcal B_2$ is linearly independent is left as an exercise. Now, translating this equality into dimensions gives

$$\dim(U_1 + U_2) = \dim(U_1) + \dim(U_2) - \dim(U_1 \cap U_2)$$

which was to be shown.