# A problem in discrete geometry

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

$\displaystyle \bigcap_{W \in \mathcal{B}} W \neq \{0 \}.$ Prove that $\displaystyle \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
[$\displaystyle \star$] Let $\displaystyle V$ be a finite dimensional vector space over some field $\displaystyle F$ and $\displaystyle \dim_F V=n.$ Let $\displaystyle \mathcal{A}$ be a finite set of subspaces of $\displaystyle V$ and suppose that for any $\displaystyle \mathcal{B} \subseteq \mathcal{A}$ with $\displaystyle |\mathcal{B}| \leq n$ we have

$\displaystyle \bigcap_{W \in \mathcal{B}} W \neq \{0 \}.$ Prove that $\displaystyle \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 $\displaystyle \dim V > 0$. If $\displaystyle \dim V = 0$, there is no subset of $\displaystyle \mathcal{B} \subseteq \mathcal{A}$ such that $\displaystyle |\mathcal{B}| \le 0$ (the null set and the trivial subspace are different animals). So in this case

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

Let's add the condition that the dimension of $\displaystyle 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 $\displaystyle \bigcap_{W \in \mathcal{A}} W = \{0 \}.$

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

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

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

Therefore, $\displaystyle \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 $\displaystyle \dim V > 0$.

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

so we don't need to assume that $\displaystyle n \neq 0.$ however, we do need to assume that $\displaystyle \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 $\displaystyle \bigcap_{W \in \mathcal{A}} W = \{0 \}.$

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

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

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

Therefore, $\displaystyle \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 $\displaystyle \alpha \in W_i$, there must be a $\displaystyle W_j$ such that $\displaystyle \alpha \not\in W_j$ for a $\displaystyle i \ne j$ because $\displaystyle \bigcap_{W \in \mathcal{A}} W = \{0 \}$ by assumption. Thus $\displaystyle \bigcap W_i + W_j = \{0 \}$. But since we can take $\displaystyle \mathcal{B} = W_i + W_j$ and $\displaystyle |\mathcal{B}| = 2 \le n$, we have $\displaystyle \bigcap_{W \in \mathcal{B}} W = \{0 \}$, a contradiction.

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

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

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

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

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

$\displaystyle \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 $\displaystyle \bigcap_{W\in\mathcal{A}} W = \{0\}$. We have to prove the existence of a subset $\displaystyle \mathcal{B}$ of $\displaystyle \mathcal{A}$ of cardinality at most $\displaystyle n$ such that $\displaystyle \bigcap_{W\in\mathcal{B}} W=\{0\}$.

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

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

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

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