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  <ae53@rz.uni-karlsruhe.de> 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