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 Xu=y. Subscripts will denote components of vectors. Instead of umax I'll use v. I'll denote by Av the hypercube 0lequileqv for 1leqileqp. The problem as stated is about the intersection between Av and L, which is a polytope I'll call Pv.



We can rescale the coordinates by taking urightarrowvu so that Av 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 Xu=y where y=1/vy. 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 Pv 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