# A problem in discrete geometry

• Feb 13th 2010, 11:18 AM
NonCommAlg
A problem in discrete geometry
[ $\star$] Let $V$ be a finite dimensional vector space over some field $F$ and $\dim_F V=n.$ Let $\mathcal{A}$ be a finite set of the subspaces of $V$ and suppose that for any $\emptyset \neq \mathcal{B} \subseteq \mathcal{A}$ with $|\mathcal{B}| \leq n$ we have

$\bigcap_{W \in \mathcal{B}} W \neq \{0 \}.$ Prove that $\bigcap_{W \in \mathcal{A}} W \neq \{0 \}.$

[From now on I'll rate the problems that I give in here. It starts with one star, which means "fairly easy", and goes up to 5 stars, which means "unfairly difficult"! haha]
• Feb 13th 2010, 12:29 PM
lgstarn
Quote:

Originally Posted by NonCommAlg
[ $\star$] Let $V$ be a finite dimensional vector space over some field $F$ and $\dim_F V=n.$ Let $\mathcal{A}$ be a finite set of subspaces of $V$ and suppose that for any $\mathcal{B} \subseteq \mathcal{A}$ with $|\mathcal{B}| \leq n$ we have

$\bigcap_{W \in \mathcal{B}} W \neq \{0 \}.$ Prove that $\bigcap_{W \in \mathcal{A}} W \neq \{0 \}.$

[From now on I'll rate the problems that I give in here. It starts with one star, which means "fairly easy", and goes up to 5 stars, which means "unfairly difficult"! haha]

First, I think you need to add to your problem that $\dim V > 0$. If $\dim V = 0$, there is no subset of $\mathcal{B} \subseteq \mathcal{A}$ such that $|\mathcal{B}| \le 0$ (the null set and the trivial subspace are different animals). So in this case

$\bigcap_{W \in \mathcal{A}} W = \{0 \}.$

Let's add the condition that the dimension of $V$ be positive and prove that instead.

Not sure if this is the easiest way to do things, but I'll try a contradiction. Assume for the purposes of contradiction $\bigcap_{W \in \mathcal{A}} W = \{0 \}.$

First, there are no trivial subspaces $W$ in $\mathcal{A}$, as if there were, we would take $\mathcal{B} = \{W\} \subseteq \mathcal{A}$ with $|\mathcal{B}| = 1$ and we have $\bigcap_{W \in \mathcal{B}} W = \{0 \},$ a contradiction.

There must also exist at least two elements in $\mathcal{A}$ because if there were only one, we could again take $\mathcal{B} = \mathcal{A}$ with $|\mathcal{B}| = 1$ and, from our assumption about $\mathcal{A}$, we have $\bigcap_{W \in \mathcal{B}} W = \{0 \}$, a contradiction.

Now, if we take any $\alpha \in W_i$, there must be a $W_j$ such that $\alpha \not\in W_j$ for a $i \ne j$ because $\bigcap_{W \in \mathcal{A}} W = \{0 \}$ by assumption. Thus $\bigcap W_i + W_j = \{0 \}$. But since we can take $\mathcal{B} = W_i + W_j$ and $|\mathcal{B}| = 2 \le n$, we have $\bigcap_{W \in \mathcal{B}} W = \{0 \}$, a contradiction.

Therefore, $\bigcap_{W \in \mathcal{A}} W \ne \{0 \}.$
• Feb 14th 2010, 07:40 PM
NonCommAlg
Quote:

Originally Posted by lgstarn
First, I think you need to add to your problem that $\dim V > 0$.

not really! if the conditions of our problem are not satisfied, then the claim will be true. remember, if $p$ is false, then $p \Longrightarrow q$ is true.

so we don't need to assume that $n \neq 0.$ however, we do need to assume that $\mathcal{B} \neq \emptyset.$ i just added this condition.

Quote:

Not sure if this is the easiest way to do things, but I'll try a contradiction. Assume for the purposes of contradiction $\bigcap_{W \in \mathcal{A}} W = \{0 \}.$

First, there are no trivial subspaces $W$ in $\mathcal{A}$, as if there were, we would take $\mathcal{B} = \{W\} \subseteq \mathcal{A}$ with $|\mathcal{B}| = 1$ and we have $\bigcap_{W \in \mathcal{B}} W = \{0 \},$ a contradiction.

There must also exist at least two elements in $\mathcal{A}$ because if there were only one, we could again take $\mathcal{B} = \mathcal{A}$ with $|\mathcal{B}| = 1$ and, from our assumption about $\mathcal{A}$, we have $\bigcap_{W \in \mathcal{B}} W = \{0 \}$, a contradiction.

Now, if we take any $\alpha \in W_i$, there must be a $W_j$ such that $\alpha \not\in W_j$ for a $i \ne j$ because $\bigcap_{W \in \mathcal{A}} W = \{0 \}$ by assumption. Thus $\bigcap W_i + W_j = \{0 \}$. But since we can take $\mathcal{B} = W_i + W_j$ and $|\mathcal{B}| = 2 \le n$, we have $\bigcap_{W \in \mathcal{B}} W = \{0 \}$, a contradiction.

Therefore, $\bigcap_{W \in \mathcal{A}} W \ne \{0 \}.$
i don't think this is a correct solution. you might need to look at it more carefully. (Nod)
• Feb 14th 2010, 11:23 PM
lgstarn
Quote:

Originally Posted by NonCommAlg
i don't think this is a correct solution. you might need to look at it more carefully. (Nod)

I assume you are right that I made a mistake somewhere! I'm an applied guy so I'm not very good at this pure stuff. But I don't see where I made my error (well, to be honest, I didn't look very hard). Could you drop me a hint?

Thanks. (Nerd)
• Feb 15th 2010, 12:21 AM
NonCommAlg
Quote:

Originally Posted by lgstarn

Now, if we take any $\alpha \in W_i$, there must be a $W_j$ such that $\alpha \not\in W_j$ for a $i \ne j$ because $\bigcap_{W \in \mathcal{A}} W = \{0 \}$ by assumption. Thus $\bigcap W_i + W_j = \{0 \}$. But since we can take $\mathcal{B} = W_i + W_j$ and $|\mathcal{B}| = 2 \le n$, we have $\bigcap_{W \in \mathcal{B}} W = \{0 \}$, a contradiction.

Therefore, $\bigcap_{W \in \mathcal{A}} W \ne \{0 \}.$

so you let $\mathcal{A}=\{W_1, \cdots , W_m \}$ and you assume that $\bigcap_{i=1}^m W_i = \{0 \}.$ then you say that for any $1 \leq i \leq m,$ and $\alpha \in W_i,$ there exists some $1 \leq j \leq m$ such that $\alpha \notin W_j.$ no problem so far.

but then you say $\bigcap (W_i + W_j) = \{ 0 \}.$ the question is that this intersection is exactly over which $i,j$ and why is the intersection 0? then you say take $\mathcal{B}=W_i + W_j,$ which has no meaning

and i guess you meant $\mathcal{B}=\{W_i + W_j \}$? again, what are these $i,j$ and why $|\mathcal{B}|=2$?!
• Feb 15th 2010, 07:58 AM
Laurent
Quote:

Originally Posted by NonCommAlg
[ $\star$] Let $V$ be a finite dimensional vector space over some field $F$ and $\dim_F V=n.$ Let $\mathcal{A}$ be a finite set of the subspaces of $V$ and suppose that for any $\emptyset \neq \mathcal{B} \subseteq \mathcal{A}$ with $|\mathcal{B}| \leq n$ we have

$\bigcap_{W \in \mathcal{B}} W \neq \{0 \}.$ Prove that [tex]\bigcap_{W \in \mathcal{A}

[From now on I'll rate the problems that I give in here. It starts with one star, which means "fairly easy", and goes up to 5 stars, which means "unfairly difficult"! haha]

An efficient but not very clean solution; there must be a way to make it nicer.

Spoiler:

Assume $\bigcap_{W\in\mathcal{A}} W = \{0\}$. We have to prove the existence of a subset $\mathcal{B}$ of $\mathcal{A}$ of cardinality at most $n$ such that $\bigcap_{W\in\mathcal{B}} W=\{0\}$.

For every $W\in\mathcal{A}$, choose a linear map $f_W:V\to V$ such that $\ker f_W=W$ (some projection on a complement subspace, for instance). Finally, let us introduce the linear map $f:V\to V^{\mathcal{A}}$ given by $f=(f_W)_{W\in \mathcal{A}}$. Its kernel is $\{0\}$ due to the assumption, hence $f$ is injective, and its image has dimension $n$. Consider a matrix of $f$, consisting in piling up the matrices of $f_W$ ( $W\in\mathcal{A}$); then we can find $n$ independent rows. Let $W_1,\ldots,W_m$ be the subspaces corresponding to these rows ( $m if two rows come from the same "submatrix"). The map $(f_{W_1},\ldots,f_{W_m})$ has rank $n$ by the previous choice, hence its kernel (i.e. $\bigcap_{i=1}^m W_i$) is $\{0\}$. This concludes.
• Feb 15th 2010, 07:58 PM
NonCommAlg
my solution:

Spoiler:
by induction over $|\mathcal{A}|$. there is nothing to prove if $|\mathcal{A}| \leq n.$ suppose $\mathcal{A}=\{W_1, \cdots , W_m \}, \ m > n,$ and put $W'_j=\bigcap_{i \neq j} W_i.$ by the induction hypothesis $W'_j \neq \{0\},$ for all $1 \leq j \leq m.$

so for any $1 \leq j \leq m,$ there exists some $0 \neq w_j \in W'_j.$ since $m > n,$ the set $\{w_1, \cdots , w_m \}$ is linearly dependent. thus there exists $1 \leq k \leq m$ such that $w_k=\sum_{i \neq k} c_iw_i,$ for some

$c_i \in F.$ but, by definition, if $i \neq k,$ then $w_i \in W_k$ and so $w_k \in W_k.$ we also have that $w_k \in W'_k \subseteq W_i,$ for all $i \neq k.$ therefore $0 \neq w_k \in \bigcap_{i=1}^m W_i$ and we're done.