Results 1 to 7 of 7

Thread: A problem in discrete geometry

  1. #1
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7

    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]
    Last edited by NonCommAlg; Feb 14th 2010 at 07:35 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Feb 2010
    Posts
    29
    Quote Originally Posted by NonCommAlg View Post
    [$\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 \}.$
    Last edited by lgstarn; Feb 13th 2010 at 12:51 PM. Reason: Fixing small logical error in W_i + W_j case
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by lgstarn View Post
    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.

    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Feb 2010
    Posts
    29
    Quote Originally Posted by NonCommAlg View Post
    i don't think this is a correct solution. you might need to look at it more carefully.
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by lgstarn View Post

    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$?!
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2008
    From
    Paris, France
    Posts
    1,174
    Quote Originally Posted by NonCommAlg View Post
    [$\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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Discrete Probiality problem
    Posted in the Statistics Forum
    Replies: 4
    Last Post: Nov 13th 2011, 10:24 PM
  2. Prerequisite for Discrete Differential Geometry
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: May 5th 2010, 10:19 AM
  3. Discrete Log Problem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Jun 17th 2008, 05:07 AM
  4. need help on this discrete problem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Feb 13th 2008, 09:52 PM
  5. Discrete Math/Geometry Question Help!
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Sep 12th 2007, 06:38 AM

Search Tags


/mathhelpforum @mathhelpforum