Does an $n$ dimensional subspace intersect the $n$-facets of the unit cube? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T17:06:27Z http://mathoverflow.net/feeds/question/82908 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/82908/does-an-n-dimensional-subspace-intersect-the-n-facets-of-the-unit-cube Does an $n$ dimensional subspace intersect the $n$-facets of the unit cube? Dirk 2011-12-07T20:26:35Z 2011-12-07T23:16:08Z <p>Since my intuition for high dimensional geometry is not always right:</p> <p>Consider the unit cube in $\mathbb{R}^m$ and for $n\leq m$ denote by $F^n$ the union of the $n$-facets. For what numbers of $m$ and $n$ does any $n$-dimensional subspace of $\mathbb{R}^m$ intersect $F^n$?</p> <p>Extra: Consider the same question for $G^n$ = $F^n\setminus F^{n-1}$.</p> <p>(P.S: What kind geometry tag would be appropriate?)</p> http://mathoverflow.net/questions/82908/does-an-n-dimensional-subspace-intersect-the-n-facets-of-the-unit-cube/82909#82909 Answer by Igor Rivin for Does an $n$ dimensional subspace intersect the $n$-facets of the unit cube? Igor Rivin 2011-12-07T20:31:20Z 2011-12-07T20:31:20Z <p>The condition for the first question is: $2n \geq m.$</p> http://mathoverflow.net/questions/82908/does-an-n-dimensional-subspace-intersect-the-n-facets-of-the-unit-cube/82916#82916 Answer by Kevin P. Costello for Does an $n$ dimensional subspace intersect the $n$-facets of the unit cube? Kevin P. Costello 2011-12-07T23:16:08Z 2011-12-07T23:16:08Z <p>Here's a way of thinking about Igor's answer to the first part: </p> <p>Consider first a "generic" $n-$dimensional subspace defined by a system of $m-n$ equations. For any particular $n-$facet, being on that facet means you only have $n$ free variables. So if $n&lt; m-n$, there isn't really any hope to satisfy all the equations at once. </p> <p>Conversely, if you have a subspace satisfying $m-n \leq n$, you can imagine the following process. We will refer to a variable as <strong>fixed</strong> if its value is equal to $1$ or $-1$, and <strong>free</strong> otherwise.</p> <p>We start at the point $v=0$, at which point all variables are free. If at any point there are fewer than $m-n$ free variables, then there must be a $w \neq 0$ in the subspace which is equal to $0$ at all fixed variables (here we're using $m-n \leq n$). We can then replace $v$ by $v+\lambda w$, where $\lambda$ is chosen to be as large as possible subject to the constraint that we still lie in the hypercube. This new vector is still in the subspace, and has (at least) one more fixed variable than before. </p>