Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $V$ be a vector space of dimension $n$ and let $V_1,V_2,\ldots,V_k \subset V$ be subspaces of $V$. Assume that

\begin{eqnarray} \sum^{k}_{i=1} \dim(V_i) > n(k-1). \end{eqnarray}

To show that $\bigcap^{k}_{i=1}V_i \neq \{0\}$, what must be done? Also, could there be an accompanying schematic/diagram to show the architecture of the spaces' form; that is, something like what's shown here.

share|improve this question
    
I think there is a general outline as to what's going on here in Hoffman's "Linear Algebra" on page 209. I'm just having difficulty bringing everything together. –  Trancot Apr 18 '13 at 6:52
    
It certainly would be interesting to see a diagram of what exactly the subspace/vector space containment arragement looks like. Something like this. –  Trancot Apr 18 '13 at 6:57
    
Just curious: the Seirios's answer is perfect; but is it possible to show this proposition by the PIE? –  Taro Apr 18 '13 at 11:42
    
@Seirios Unfortunately, I'm most likely not allowed to use material too much outside my professor's closed-form lecture notes. –  Trancot Apr 18 '13 at 20:00
    
@Seirios If it is not too taxing, perhaps you could wind out what you've propounded in terms more native to the simple, elementary content of an honors linear algebra course. –  Trancot Apr 18 '13 at 20:05
show 3 more comments

5 Answers

up vote 4 down vote accepted
+50

Lemma: Let $W_1,\ \cdots,\ W_k\subset V$. Then $$\dim\left(\bigcap_{i=1}^{k}W_i\right)\ge \sum_{i=1}^k\dim(W_i) - (k-1)n$$ Proof: First, recall the following equation relating the dimension of the intersection to the dimension of the sum. $$\dim(W_1 + W_2) + \dim(W_1\cap W_2) = \dim(W_1) + \dim(W_2)$$ Since $W_1,\ W_2\subset V$ it follows that $W_1 + W_2\subseteq V$ and therefore $\dim(W_1+W_2)\le n$. We then have $$\dim(W_1 \cap W_2) \ge \dim(W_1) + \dim(W_2) - n$$ This is our base case. Let us proceed to prove via induction. Suppose the inequality holds for $k\ge 2$ and consider $k+1$. Then $$\dim\left(\bigcap_{i=1}^{k+1}W_i\right) = \dim\left(W_{k+1}\cap\bigcap_{i=1}^kW_i\right)$$ By the base case, the above satisfies $$\dim\left(W_{k+1}\cap\bigcap_{i=1}^kW_i\right) \ge \dim(W_{k+1}) + \dim\left(\bigcap_{i=1}^kW_i\right)-n$$ By the inductive hypothesis, we then have $$\dim(W_{k+1}) + \dim\left(\bigcap_{i=1}^kW_i\right)-n \ge \dim(W_{k+1}) + \left(\sum_{i=1}^k\dim(W_i) - (k-1)n\right) - n$$ Combining, we of course have $$\dim\left(\bigcap_{i=1}^{k+1}W_i\right) \ge \sum_{i=1}^{k+1}\dim(W_i) - kn$$ The proposition follows by mathematical induction. $\square$

Now your result immediately follows since $$\sum_{i=1}^k W_i > (k-1)n \implies \dim\left(\bigcap_{i=1}^k W_i\right) \ge \sum_{i=1}^k\dim(W_i) - (k-1)n > 0$$

share|improve this answer
    
+1 for elementary solution. BTW how do you come up with that lemma? Comparing the hypothesis and the conclusion? (Since I cannot feel the lemma is true intuitively.) –  Taro Apr 19 '13 at 1:36
    
@Taro I immediately had the idea of using the identity $$\dim(W) + \dim(V) = \dim(W\cap V) + \dim(W +V)$$ since it's one of the main results which relate vectors spaces to their intersection. The natural way to get rid of the $W+V$ term in the above is to bound it above by the dimension of the ambient space. That gives the case $k=2$. The generalization to $k>2$ is also quite natural I think. –  EuYu Apr 19 '13 at 1:56
    
Thank you for explanation. I also thought in that direction. For $k = 3$, it becomes $$\dim(V_1 \cap V_2 \cap V_3) = \dim(V) - \dim(V_1) - \dim(V_2) - \dim(V_3) + \dim(V_1 \cap V_2) + \dim(V_2 \cap V_3) + \dim(V_1 \cap V_3).$$ That's why I mentioned to the PIE in the comment. –  Taro Apr 19 '13 at 13:10
add comment

For $1 \leq i \leq k$, let $p_i : V \to V/V_i$ be the canonical projection. Now, consider the morphism $\varphi = p_1 \times \dots \times p_k : V \to \prod\limits_{i=1}^k V/V_i$; notice that $\text{ker}(\varphi)= \bigcap\limits_{i=1}^k V_i$.

But $\dim \big( \prod\limits_{i=1}^k V/V_i \big) = \sum\limits_{i=1}^k \left( \dim(V)-\dim(V_i) \right)<n$. Therefore, $\varphi$ cannot be injective, hence $\bigcap\limits_{i=1}^k V_i \neq \{0\}$.

share|improve this answer
    
Perhaps you could be more explicit. –  Trancot Apr 18 '13 at 6:50
1  
@Trancot : what do you mean ? How could it be made “more explicit” than this ? I do not think it can. –  Ewan Delanoy Apr 18 '13 at 7:27
    
@Trancot: Is there something you don't understand? –  Seirios Apr 18 '13 at 7:45
    
@Seirios Yes, well, no. I wouldn't say "not understand," but maybe "not familiar yet." I have to do a bit more combing through textbooks and the like to see what you're really saying. –  Trancot Apr 18 '13 at 8:10
    
@Trancot: If you want, you can take $p_i : V \to W_i$, where $V= V_i \oplus W_i$ and then $\varphi : V \to \prod\limits_{i=1}^k W_i$. It is equivalent. –  Seirios Apr 18 '13 at 8:15
show 4 more comments

First write the equation in the form $$ n>\sum_{i=1}^k\bigl(n-\dim V_i\bigr) $$ so that you can get some idea of what it really says: the codimensions of the subspaces $V_i$ add up to less than the dimension of the whole space. Now the codimension of a subspace gives the number of linear equations needed to define the subspace. If we choose such a set of equations for each subspace $V_i$, and take together all equations thus obtained, we have fewer equations than $n=\dim V$. This means (by the rank-nullity theorem if you like) that there is some nonzero vector that satisfies all equations at once. This vector lies in $\bigcap_{i=1}^kV_i$.

Added, to address comments by OP. To obtain from the inequality given in the question the one I gave above, first write the right hand side of the former as $nk-n$, then the term $nk$ as $\sum_{i=1}n$, now move the summation on the left to the right hand side, integrating its terms $\dim V_i$ as $-\dim V_i$ into the summation just created, and finally move the term $-n$ to the left, becoming $n$. The inequality remains a strict "$>$" throughout these manipulations. As for the fact that the codimension of a subspace equals the number of equations needed to define it, that is a basic fact from linear algebra: if you got a list of homogeneous linear equations (right hand side is $0$), then each new equation decreases the dimension of the solution space by $1$, unless it is linearly dependent of the previous equations, in which case one can drop the new equation. If you want a more formal argument for this, choose a basis of $d=\dim V_i$ vectors for the subspace $V_i$, extend it by $n-d$ more vectors to a basis of the whole space (incomplete basis theorem); then consider the $n$ coordinate functions for this basis, and the $n-d$ equations setting the last $n-d$ coordinates to $0$, which gives a system whose solution is precisely $V_i$.

share|improve this answer
    
Don't you mean $\leq$ the dimension of the whole space? –  Trancot Apr 18 '13 at 21:22
    
or anyone else reading this comment, could you explain how the summation equation reduces to this? –  Trancot Apr 18 '13 at 21:29
    
Could you expound on your comment "Now the codimension of a subspace gives the number of linear equations needed to define the subspace," please? –  Trancot Apr 18 '13 at 21:53
add comment

Hint: take complements. That is, pick vector spaces $W_i$ with $\dim(W_i) + \dim(V_i) = n$ and $W_i \cap V_i = \{0\}$.

EDIT: thanks, Ted

share|improve this answer
    
Should be $W_i \cap V_i = \{0\}$. –  Ted Apr 12 '13 at 3:11
    
@Ted, Oops, and thanks! –  user66345 Apr 12 '13 at 3:20
2  
I really don't see what you could do with subspaces $W_i$. Unless you consider the projections onto the $W_i$ parallel to the $V_i$ and combine them to a linear map to the external direct sum of the $W_i$ (a rather non-obvious thing to do, it is really not clear that you hinted at this), in which case the argument reduces to that of Serios. –  Marc van Leeuwen Apr 18 '13 at 6:56
add comment

Hint: Can you do the case where $k = 2$? Then try induction on $k$, that involves replacing $V_1,V_2$ by $V_1 \cap V_2$, using the identity $\dim( V_1 + V_2) + \dim V_1 \cap V_2 = \dim V_1 + \dim V_2$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.