From: rusin@math.niu.edu (Dave Rusin) Subject: Re: Problem with linear combinations of convex sets Date: 31 Dec 1999 07:45:31 GMT Newsgroups: sci.math,sci.math.research,sci.math.symbolic Keywords: global linearly independent complement In article <386A17DD.167EB0E7@rz.uni-karlsruhe.de>, Martin wrote: >Given $n-1$ convex compact subsets $K_i,\ i=1,\ldots,n-1$ >of $\R^n$ with the property that >$$\forall (x_1,\ldots,x_{n-1})\in K_1\times\ldots\times K_{n-1}: >\{x_1,\ldots,x_{n-1}\} \mbox{ is linearly independent.} >$$ > >Can I always find a fixed $x_n\in\R^n$ such that >$$\forall (x_1,\ldots,x_{n-1})\in K_1\times\ldots\times K_{n-1}: >\{x_1,\ldots,x_{n-1},x_n\}\mbox{ is linearly independent?} >$$ > >For $n=2$ and $n=3$ I could prove that such an $x_n$ exists, Let's try n=4, then. I think I have a counterexample for the simplest case, in which the K_i are just line segments. That situation can, except in degenerate cases, be reduced to one like this: K1 is the set of vectors [1,0,u,0] with |u| <= 1; K2 is the set of vectors [0,1,0,v] with |v| <= 1; K3 is the set of vectors [a,b,c,d]+t[e,f,g,h] with |t| <= 1. There are some conditions to be satisfied by abcdefgh to guarantee linear independence. I hope I have worked them out properly (I used techniques as below); I think it's sufficient to have |g+-e| < |c+-a| and |h+-f| < |d+-b|. Anyway, I chose a = 12, b = 7, c = 8, d = 4, e = 1, f = 5, g = 2, h = 3. Now, you seek a single vector x4=[X,Y,Z,W] such that {x1,x2,x3,x4} is a linearly independent set, for each choice of x_i in K_i. That's equivalent to requiring all these 4x4 determinants to be nonzero: [ 1 0 u 0 ] [ ] [ 0 1 0 v ] [ ] [a + t e b + t f c + t g d + t h] [ ] [ X Y Z W ] Well, that determinant is linear in t, so it certainly _does_ vanish for some t, for each u and v, no matter what X,Y,Z,W we pick; but that's OK as long as this t is not in the interval [-1,1]. So the condition which describes the appropriate vectors x4 is that for all v in [-1,1], for all u in [-1,1], | W c - X u v b - Z d + v Z b + a Y u v - Y v c - a u W + X u d | 1 < | ------------------------------------------------------------- | | Z h + v Y g - Z v f + e u W - e Y u v - X u h - W g + X u v f | Now, again, it is clear from linearity that (for every v) there will be some u which make this inequality false. As before this is fine as long as those u lie outside the interval [-1,1]. At a minimum, we see that this inequality must hold when u=0, and that the values of u which make the fraction = +1 or -1 must be outside the interval. Thus a necessary condition which must be satisfied by the vector x4 we seek is for all v in [-1,1], |(-Yvc-Zd+vZb+Wc)/(vYg+Zh-Zvf-Wg)| > 1, |(Zvf+Wg-Yvc-Zd+vZb+Wc-Zh-vYg)/(-aYv+aW+Xvf-vYe-Xh-Xd+Xvb+We)| > 1, |(Zvf+Wg+Yvc+Zd-vZb-Wc-Zh-vYg)/( aYv-aW+Xvf-vYe-Xh+Xd-Xvb+We)| > 1 Repeating this analysis once more we see that each condition "for all v, |A/B|>1" requires at least that "when v=0, |A/B|>1" and "when A=B, |v|>1" and "when A=-B, |v|>1". Thus the vector x4 we seek must make 9 fractions be larger than 1 in magnitude. Here they are for the particular abcdefgh I chose; I have normalized to W=1 for brevity: (4Z-8)/(-3Z+2), (10-7Z)/(13-7X), (6-Z)/(11-X), (7Z-10)/(12Z-10Y), (6-Z)/(6Y-2Z), (3+7Z-7X)/(12Z+3Y-12X), (7Z+7X-23)/(12Z-23Y+12X), (5+Z-X)/(2Z+5Y-2X), (17-Z-X)/(-2Z+17Y-2X) Well, now this is now straightforward: each inequality |A/B|>1 is satisfied in some regions bounded by a pair of planes. These planes partition the whole of XYZ space into a finite number of regions on which the signs of each |A/B|-1 are constant. Just check each region and see whether the inequalities hold or not. I did this rather primitively: Maple finds that the planes intersect in threes in a few hundred points (all in the box [-144,255]^3, if you want to sketch this!). None of these intersection points made all nine equalities hold, so if my analysis is correct, there are no vectors x4=[X,Y,Z,W] linearly independent of every choice of x1,x2,x3. (The closest I found was near X=-9.5906,Y=-1.3211, Z=-9.5901, for which each of the nine quotients exceeds 0.7571 in magnitude.) So unless I've been hasty, it looks like there is no x4 for this set K1,K2,K3 of three compact convex subsets of R^4. dave