1
$\begingroup$

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

Improve this question
$\endgroup$
12
  • $\begingroup$ Any chance you want to edit the LaTeX symbols? $\endgroup$
    – Deane Yang
    Commented Jan 8, 2010 at 18:12
  • $\begingroup$ 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? $\endgroup$
    – Deane Yang
    Commented Jan 8, 2010 at 18:14
  • $\begingroup$ Sorry for the confusion. I do not usually use LaTeX. I cleaned up the LaTeX glitches. $\endgroup$
    – some_random_guy
    Commented Jan 8, 2010 at 18:15
  • $\begingroup$ @Deane: Cleaned up notation to indicate that the question relates to real spaces. $\endgroup$
    – some_random_guy
    Commented Jan 8, 2010 at 18:20
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Harald Hanche-Olsen
    Commented Jan 8, 2010 at 18:45

1 Answer 1

Reset to default
1
$\begingroup$

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?

Improve this answer
$\endgroup$
6
  • $\begingroup$ A clarification: Do you mean the transformation $u'\rightarrow u/v$ instead of $u \rightarrow vu$? $\endgroup$
    – some_random_guy
    Commented Jan 8, 2010 at 20:33
  • $\begingroup$ Yes, sorry. I've updated my answer. $\endgroup$
    – j.c.
    Commented Jan 8, 2010 at 20:48
  • $\begingroup$ 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. $\endgroup$
    – some_random_guy
    Commented Jan 8, 2010 at 21:29
  • $\begingroup$ 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. $\endgroup$
    – j.c.
    Commented Jan 8, 2010 at 21:40
  • $\begingroup$ 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.) $\endgroup$
    – some_random_guy
    Commented Jan 9, 2010 at 2:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .