Prove that 0 is in the convex hull of points chosen from each orthant












2












$begingroup$


If we arbitrarily choose a point from each orthant in $mathbb{R}^n$, that is we choose $2^n$ points in total, how do we prove that 0 is in the convex hull of these $2^n$ points? It seems obvious, but when I sit down and start thinking about it, I couldn't definitely find a set of $lambda_i, i = 1,2,cdots,2^n$ such that $0 leq lambda_i leq 1, sum_i lambda_i = 1$ and $0 = sum_i lambda_i x_i$, where $x_i, i = 1,2,cdots,2^n$ are any set of points satisfying the condition.






convex-analysis convex-geometry convex-hulls







share|cite|improve this question









$endgroup$

















    2












    $begingroup$


    If we arbitrarily choose a point from each orthant in $mathbb{R}^n$, that is we choose $2^n$ points in total, how do we prove that 0 is in the convex hull of these $2^n$ points? It seems obvious, but when I sit down and start thinking about it, I couldn't definitely find a set of $lambda_i, i = 1,2,cdots,2^n$ such that $0 leq lambda_i leq 1, sum_i lambda_i = 1$ and $0 = sum_i lambda_i x_i$, where $x_i, i = 1,2,cdots,2^n$ are any set of points satisfying the condition.






    convex-analysis convex-geometry convex-hulls







    share|cite|improve this question









    $endgroup$















      2












      2








      2





      $begingroup$


      If we arbitrarily choose a point from each orthant in $mathbb{R}^n$, that is we choose $2^n$ points in total, how do we prove that 0 is in the convex hull of these $2^n$ points? It seems obvious, but when I sit down and start thinking about it, I couldn't definitely find a set of $lambda_i, i = 1,2,cdots,2^n$ such that $0 leq lambda_i leq 1, sum_i lambda_i = 1$ and $0 = sum_i lambda_i x_i$, where $x_i, i = 1,2,cdots,2^n$ are any set of points satisfying the condition.






      convex-analysis convex-geometry convex-hulls







      share|cite|improve this question









      $endgroup$




      If we arbitrarily choose a point from each orthant in $mathbb{R}^n$, that is we choose $2^n$ points in total, how do we prove that 0 is in the convex hull of these $2^n$ points? It seems obvious, but when I sit down and start thinking about it, I couldn't definitely find a set of $lambda_i, i = 1,2,cdots,2^n$ such that $0 leq lambda_i leq 1, sum_i lambda_i = 1$ and $0 = sum_i lambda_i x_i$, where $x_i, i = 1,2,cdots,2^n$ are any set of points satisfying the condition.






      convex-analysis convex-geometry convex-hulls




      convex-analysis convex-geometry convex-hulls






      share|cite|improve this question













      share|cite|improve this question











      share|cite|improve this question




      share|cite|improve this question










      asked 4 hours ago









      Sean IanSean Ian

      885




      885






















          2 Answers
          2






          active

          oldest

          votes


















          4












          $begingroup$

          Induct on dimension.



          In the $n=1$ base case, you have a positive number and a negative number; $0$ can be represented as a convex combination of them.



          For $n>1$: Given your $2^n$ points, one from each orthant, divide them into 2 sets of size $2^{n-1}$, where the first set has points whose last coordinates are positive and the second set where the last coordinates are negative. By the inductive hypothesis there is a convex combo of the first set of points such that the first $n-1$ coordinates vanish, and similarly for the second set. The last coordinates of these two convex combos are positive and negative, so there is a convex combo of them that is zero.






          share|cite|improve this answer











          $endgroup$





















            2












            $begingroup$

            Take in pairs the points that differ in sign for the coordinate $n$ (and only that one) and form the convex combinations such that that coordinate is cancelled.



            Now you have $2^{n-1}$ points in each orthants of the diminished space.



            The results holds because the convex combination of linear combinations is a convex combination.



            enter image description here






            share|cite|improve this answer











            $endgroup$













              Your Answer





              StackExchange.ifUsing("editor", function () {
              return StackExchange.using("mathjaxEditing", function () {
              StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
              StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
              });
              });
              }, "mathjax-editing");

              StackExchange.ready(function() {
              var channelOptions = {
              tags: "".split(" "),
              id: "69"
              };
              initTagRenderer("".split(" "), "".split(" "), channelOptions);

              StackExchange.using("externalEditor", function() {
              // Have to fire editor after snippets, if snippets enabled
              if (StackExchange.settings.snippets.snippetsEnabled) {
              StackExchange.using("snippets", function() {
              createEditor();
              });
              }
              else {
              createEditor();
              }
              });

              function createEditor() {
              StackExchange.prepareEditor({
              heartbeatType: 'answer',
              autoActivateHeartbeat: false,
              convertImagesToLinks: true,
              noModals: true,
              showLowRepImageUploadWarning: true,
              reputationToPostImages: 10,
              bindNavPrevention: true,
              postfix: "",
              imageUploader: {
              brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
              contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
              allowUrls: true
              },
              noCode: true, onDemand: true,
              discardSelector: ".discard-answer"
              ,immediatelyShowMarkdownHelp:true
              });


              }
              });














              draft saved

              draft discarded


















              StackExchange.ready(
              function () {
              StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3091194%2fprove-that-0-is-in-the-convex-hull-of-points-chosen-from-each-orthant%23new-answer', 'question_page');
              }
              );

              Post as a guest















              Required, but never shown

























              2 Answers
              2






              active

              oldest

              votes








              2 Answers
              2






              active

              oldest

              votes









              active

              oldest

              votes






              active

              oldest

              votes









              4












              $begingroup$

              Induct on dimension.



              In the $n=1$ base case, you have a positive number and a negative number; $0$ can be represented as a convex combination of them.



              For $n>1$: Given your $2^n$ points, one from each orthant, divide them into 2 sets of size $2^{n-1}$, where the first set has points whose last coordinates are positive and the second set where the last coordinates are negative. By the inductive hypothesis there is a convex combo of the first set of points such that the first $n-1$ coordinates vanish, and similarly for the second set. The last coordinates of these two convex combos are positive and negative, so there is a convex combo of them that is zero.






              share|cite|improve this answer











              $endgroup$


















                4












                $begingroup$

                Induct on dimension.



                In the $n=1$ base case, you have a positive number and a negative number; $0$ can be represented as a convex combination of them.



                For $n>1$: Given your $2^n$ points, one from each orthant, divide them into 2 sets of size $2^{n-1}$, where the first set has points whose last coordinates are positive and the second set where the last coordinates are negative. By the inductive hypothesis there is a convex combo of the first set of points such that the first $n-1$ coordinates vanish, and similarly for the second set. The last coordinates of these two convex combos are positive and negative, so there is a convex combo of them that is zero.






                share|cite|improve this answer











                $endgroup$
















                  4












                  4








                  4





                  $begingroup$

                  Induct on dimension.



                  In the $n=1$ base case, you have a positive number and a negative number; $0$ can be represented as a convex combination of them.



                  For $n>1$: Given your $2^n$ points, one from each orthant, divide them into 2 sets of size $2^{n-1}$, where the first set has points whose last coordinates are positive and the second set where the last coordinates are negative. By the inductive hypothesis there is a convex combo of the first set of points such that the first $n-1$ coordinates vanish, and similarly for the second set. The last coordinates of these two convex combos are positive and negative, so there is a convex combo of them that is zero.






                  share|cite|improve this answer











                  $endgroup$



                  Induct on dimension.



                  In the $n=1$ base case, you have a positive number and a negative number; $0$ can be represented as a convex combination of them.



                  For $n>1$: Given your $2^n$ points, one from each orthant, divide them into 2 sets of size $2^{n-1}$, where the first set has points whose last coordinates are positive and the second set where the last coordinates are negative. By the inductive hypothesis there is a convex combo of the first set of points such that the first $n-1$ coordinates vanish, and similarly for the second set. The last coordinates of these two convex combos are positive and negative, so there is a convex combo of them that is zero.







                  share|cite|improve this answer














                  share|cite|improve this answer



                  share|cite|improve this answer








                  edited 3 hours ago

























                  answered 4 hours ago









                  kimchi loverkimchi lover

                  9,95131128




                  9,95131128























                      2












                      $begingroup$

                      Take in pairs the points that differ in sign for the coordinate $n$ (and only that one) and form the convex combinations such that that coordinate is cancelled.



                      Now you have $2^{n-1}$ points in each orthants of the diminished space.



                      The results holds because the convex combination of linear combinations is a convex combination.



                      enter image description here






                      share|cite|improve this answer











                      $endgroup$


















                        2












                        $begingroup$

                        Take in pairs the points that differ in sign for the coordinate $n$ (and only that one) and form the convex combinations such that that coordinate is cancelled.



                        Now you have $2^{n-1}$ points in each orthants of the diminished space.



                        The results holds because the convex combination of linear combinations is a convex combination.



                        enter image description here






                        share|cite|improve this answer











                        $endgroup$
















                          2












                          2








                          2





                          $begingroup$

                          Take in pairs the points that differ in sign for the coordinate $n$ (and only that one) and form the convex combinations such that that coordinate is cancelled.



                          Now you have $2^{n-1}$ points in each orthants of the diminished space.



                          The results holds because the convex combination of linear combinations is a convex combination.



                          enter image description here






                          share|cite|improve this answer











                          $endgroup$



                          Take in pairs the points that differ in sign for the coordinate $n$ (and only that one) and form the convex combinations such that that coordinate is cancelled.



                          Now you have $2^{n-1}$ points in each orthants of the diminished space.



                          The results holds because the convex combination of linear combinations is a convex combination.



                          enter image description here







                          share|cite|improve this answer














                          share|cite|improve this answer



                          share|cite|improve this answer








                          edited 3 hours ago

























                          answered 3 hours ago









                          Yves DaoustYves Daoust

                          126k671223




                          126k671223






























                              draft saved

                              draft discarded




















































                              Thanks for contributing an answer to Mathematics Stack Exchange!


                              • Please be sure to answer the question. Provide details and share your research!

                              But avoid …



                              • Asking for help, clarification, or responding to other answers.

                              • Making statements based on opinion; back them up with references or personal experience.


                              Use MathJax to format equations. MathJax reference.


                              To learn more, see our tips on writing great answers.




                              draft saved


                              draft discarded














                              StackExchange.ready(
                              function () {
                              StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3091194%2fprove-that-0-is-in-the-convex-hull-of-points-chosen-from-each-orthant%23new-answer', 'question_page');
                              }
                              );

                              Post as a guest















                              Required, but never shown





















































                              Required, but never shown














                              Required, but never shown












                              Required, but never shown







                              Required, but never shown

































                              Required, but never shown














                              Required, but never shown












                              Required, but never shown







                              Required, but never shown







                              -

                              Popular posts from this blog

                              Why is a white electrical wire connected to 2 black wires?

                              Image
                              1 I just opened my ceiling light to replace it with another mount. I see a white wire connected to 2 black wires, is that right? The middle switch controls this ceiling light. electrical ceiling light share | improve this question asked 4 hours ago konyak konyak 108 4 New contributor konyak is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct. ...
                              Read more

                              Waikiki

                              Image
                              Denne artikkelen kan ha godt av ein språkvask , som reinskar opp målføringa og/eller innfører same språkstilen overalt. Denne artikkelen kan ha godt av ei opprydding for å nå ein høgare standard og/eller for å verta i tråd med standardoppsettet. Sjå korleis du redigerer ei side og stilmanualen for hjelp. Waikiki Land   USA Stat Hawaii Stad Honolulu Wikimedia Commons: Waikiki Utsyn over Waikiki Waikīkī er ein bydel i Honolulu, sør på øya Oahu, som er ei av Hawaii-øyane. Waikīkīstranda er ein av dei meste berømte strendene i verda. Waikīkī strekkjer seg langs stillehavskysten og har ei rekkje velrenommerte hotell. Bydelen er Hawaii-turismens høyborg. På Waikīkī Beach står ei statue av den lokale sportsstjerna Duka Kahanamoku. Kjelder | Denne artikkelen bygger på «Waikiki» frå Wikipedia på bokmål, den 4. november 2018. Denne artikkelen manglar kjelder eller referansar . Hjelp Wikipedia med å finna truverdige kjelder...
                              Read more

                              What are all the squawk codes?

                              Image
                              2 $begingroup$ I love aviation and I love learning new things about it. I was wondering if anyone knew all of the squawk codes and in particular what squawk 7500 means. squawk-codes share | improve this question edited 15 mins ago Jamiec ♦ 14.8k 4 60 91 asked 5 hours ago Zac Callaghan Zac Callaghan 11 2 New contributor Zac Callaghan is a new co...
                              Read more