Results 1 to 7 of 7

Math Help - A problem in discrete geometry

  1. #1
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7

    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]
    Last edited by NonCommAlg; February 14th 2010 at 08: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
    [ \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 \}.
    Last edited by lgstarn; February 13th 2010 at 01: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 \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.

    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.
    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 \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?!
    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
    [ \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<n 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.
    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 |\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.
    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: November 13th 2011, 11:24 PM
  2. Prerequisite for Discrete Differential Geometry
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: May 5th 2010, 11:19 AM
  3. Discrete Log Problem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: June 17th 2008, 06:07 AM
  4. need help on this discrete problem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 13th 2008, 10:52 PM
  5. Discrete Math/Geometry Question Help!
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: September 12th 2007, 07:38 AM

Search Tags


/mathhelpforum @mathhelpforum