Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

The question pertains to a polytope that is generated by the intersection of an affine subspace with a hypercube in $p$ dimensions.

The affine subspace is given by:

$X \mbox{ u} = y$

where

$u$ ∈ $\mathbb{R}^p$.

$X$ is a $m$ × $p$ matrix with $m$ < $p$ and

$y$ is a $m$ dimensional vector.

The hypercube is given by:

$0$ ≤ $u$ ≤ $u_{max}$

The longest line of this polytope is clearly one of the lines that join the vertices of the polytope. My question is:

Is the direction of the longest line independent of $u_{max} \mbox{&nbsp}$ for some $u_{max}$ ≥ u* ?

Some simulations I did in Matlab indicates that the answer to the above question is yes but I am not sure if this will hold in general. I am assuming of course that the polytope actually resides in the hypercube defined by $0$ ≤ $u$ ≤ $u_{max}$.

Any pointers to relevant literature in applied math or some approaches to answer the question would be very helpful.

Thanks

share|improve this question
    
Any chance you want to edit the LaTeX symbols? –  Deane Yang Jan 8 '10 at 18:12
    
Sorry for the dumb question but I work only on vector spaces over the reals: This appears to be a question on a finite discrete space of some sort? –  Deane Yang Jan 8 '10 at 18:14
    
Sorry for the confusion. I do not usually use LaTeX. I cleaned up the LaTeX glitches. –  some_random_guy Jan 8 '10 at 18:15
    
@Deane: Cleaned up notation to indicate that the question relates to real spaces. –  some_random_guy Jan 8 '10 at 18:20
1  
Pointwise ordering is the only that makes sense here. I.e., $u\le v$ means $u_i\le v_i$ for each $i$. The terminology is off here, though: Hyperplanes are unbounded (and of dimension one less than the containing space). We are looking at a polytope which is the intersection of an affine subspace with the standard hypercube in $\mathbb{R}^p$. –  Harald Hanche-Olsen Jan 8 '10 at 18:45
show 7 more comments

1 Answer

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 $0\leq u_i\leq v$ for $1\leq i\leq 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 $u\rightarrow 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?

share|improve this answer
    
A clarification: Do you mean the transformation $u'\rightarrow u/v$ instead of $u \rightarrow vu$? –  some_random_guy Jan 8 '10 at 20:33
    
Yes, sorry. I've updated my answer. –  j.c. Jan 8 '10 at 20:48
    
How about this: Define $S$ as the set of points where $L$ intersects the half-planes defined by $u'_i = 0$ and u'_j >= 0 for all $j$ not equal to $i$. I guess we are done if we can show that for some $v > v^*$ all the points in the set $S$ are less than $1$. The above would suggest that $P_v$ lies entirely in the hypercube and hence 'retains' its shape. Does that make sense? ps; I am unable to edit my comments after posting. I hope the above is clear. –  some_random_guy Jan 8 '10 at 21:29
    
I've updated my answer to show that the answer to your question is no. For planes L which approach only one vertex, I still think the answer is yes. @Srikant, I'm not sure what you mean exactly. P_v is defined to be the intersection of the hypercube A_v (unit hypercube in the rescaled coordinates) with L, so it always lies in a hypercube... Considering the boundaries of P_v as you suggested might be a good approach though. –  j.c. Jan 8 '10 at 21:40
    
Never mind my comment reg $P_v$. The argument does not work. However, I am confused about why you think a rectangle that is perpendicular to the top and the bottom faces of a cube becomes skinnier as $v$ increases. Such a plane will always have the same shape irrespective of the value of $v$. As $v$ increases, the plane shifts towards the origin but retains its orientation. (Note: The longest line is not unique as either diagonal is a longest line but that is a different issue.) –  some_random_guy Jan 9 '10 at 2:41
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.