Wednesday, 15 September 2010

linear algebra - Is the direction of the longest line of a polytope unique?

I think the answer to your question is yes. edit: NO



First I'll set some notation. Assume that $X$ is rank $m$. I'll denote by $L$ the m-dimensional plane defined by $X u = y$. Subscripts will denote components of vectors. Instead of $u_{max}$ I'll use $v$. I'll denote by $A_{v}$ the hypercube $0leq u_ileq v$ for $1leq ileq p$. The problem as stated is about the intersection between $A_v$ and $L$, which is a polytope I'll call $P_v$.



We can rescale the coordinates by taking $urightarrow vu'$ so that $A_v$ has side length 1 in the $u'$ coordinates. Under this transformation, $L$ keeps its orientation but is shifted. In particular, $L$ is now defined by $X (vu')=y$, or $X u'=y'$ where $y' = 1/v*y$. As $v$ gets larger and larger, $y'$ gets closer and closer to the origin. Note that if $y$ were the zero vector, your problem is scale invariant and hence has a positive answer.



If $y$ was not the zero vector, then to understand what $P_v$ looks like for large $v$, we need to understand how a slice through the hypercube behaves very close to one of its vertices. Is there a result (for convex polytopes in general?) that tells us that the "shape" of a slice is stable to small translations of the slicing plane when we're close to a vertex? I haven't found any counter-examples in the low-dimensional cases I've (unsystematically) tried.



edit: I spoke way to soon. Consider a plane slicing through the 3-dimensional cube such that the plane makes right angles with the top and bottom faces of the cube. In general the intersection will be a rectangle whose aspect ratio changes and becomes skinnier and skinnier as the plane gets closer to a vertex. The direction of the longest segment in this rectangle (either of the diagonals) obviously does not stabilize. But is there a positive result lurking here for suitably "generic" planes?

No comments:

Post a Comment