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

Suppose that you have vectors $a_{1},...,a_{m}$ in $\mathbb{R}^n$. Can you take $n$ among them, let $v_{1},...,v_{n}$ such that $a_{1},...,a_{m}$ belong to the convex hull of $(cn)v_{1},-(cn)v_{1},...,(cn)v_{n},-(cn)v_{n}$ for some constant $c$?

My idea was to use gram-schmidt process where at step $i$ I choose the vector $u_{i}$ with the maximum euclidean norm. The answer would be those $a_{i}$'s that maximize the at each step the euclidean norm. Any ideas? Thanks

share|improve this question
    
Even for the case where we have that $(c⋅n)v_{1},−(c⋅n)v_{1},...,(c⋅n)v_{n},−(c⋅n)v_{n}$ might help. Thanks! –  user31317 Feb 10 '13 at 10:30
1  
Except of Anton the others didn't understand the question i guess. First of all $c$ must be independent of $n$. Also you may assume that $a_{1},...,a_{m}$ span $R^n$ and then you have to find (if there exist) $n$ (as the dimension) vectors $v_{1},...,v_{n}$ s.t that $a_{1},...,a_{m}$ belong to the convex hull of $(c\sqrt{n})v_{1},-(c\sqrt{n})v_{1},...,$. Anton the fact is the number of initial vectors is $m = O(n^2)$, so I want sparse number of them... Thanks again! –  user31317 Feb 11 '13 at 0:32
1  
Can you do this for $m=n+1$? –  Anton Petrunin Feb 11 '13 at 2:18
1  
Sure since $a_{1},...,a_{n+1}$ span $R^n$ we get that \lambda_{1}a_{1}+...+\lambda_{n} a_{n} + \lambda_{n+1}a_{n+1} =0 where the scalars are not all zero. Then divide by the one with maximum absolute value, let max the index: a_{max} = \sum_{i\neq max} \frac{\lambda_{i}}{\lambda_{max}}a_{i} with |\frac{\lambda_{i}}{\lambda_{max}}|\leq 1. Hence $a_{max}$ can be written as a convex combination of $nv_{1}-nv_{1},...,nv_{n},-nv_{n}$. Actually I want to solve it (If i can) for $(c\cdot n)v_{1},-(c\cdot)nv_{1},...$ –  user31317 Feb 11 '13 at 7:07
    
I changed my answer. –  Anton Petrunin Feb 11 '13 at 19:41

3 Answers 3

up vote 3 down vote accepted

Take $v_1,v_2,\dots,v_n$ which span parallelepiped of maximal volume. If $$a_i=x_1\cdot v_1+\dots+x_n\cdot v_n$$ then $|x_k|\le 1$, otherwise exchanging $v_k$ to $a_i$ will increase the volume. Hence $a_i$ belongs to the convex hull of $\{\pm n\cdot v_{i}\}$; i.e. $c=1$.


Below is the original answer to the original question.

If you agree to choose $N=\tfrac{n{\cdot}(n+1)}{2}$ points then you can get $c=1$.

Take the ellipsoid of smallest volume which contains all $\{a_i\}$. You may assume that ${a_i\}$ is in generic position, in this case at most $N$ of the points lie on the boundary of ellipsoid; take them as $\{v_i\}$. If one of $a_i$ does not lie in the convex hull of $\{\pm\sqrt{n}\cdot v_i\}$ then you can decrease the volume of the ellipsoid, by pushing it in one direction and expanding in all the orthogonal directions.

share|improve this answer
    
Anton: The last version does not work since some $|x_k|$ could be (much) larger than $1$ and some (much) smaller. It is easy to construct examples with $n=2$ and $m=3$. –  Misha Feb 11 '13 at 22:33
2  
@Misha: I do not think you are right; if $|x_i|>1$ once then you can increase the volume. –  Anton Petrunin Feb 12 '13 at 5:53
1  
@Anton: Can you explain why by exchanging $u_{k}$ and $a_{i}$ the volume is increased? –  user31317 Feb 12 '13 at 10:06
    
Observe that $v_{1},...,v_{n}$ are not orthonormal... –  user31317 Feb 12 '13 at 10:18
1  
The volume is the absolute value of determinant of matrix $A$ which has as columns the vectors $u_{1},...,u_{n}$. If you change $u_{1}$ with $a_{i} = x_{1}u_{1}+...+x_{n}u_{n}$ (let $|x_{1}|\geq 1$) then the volume of the new parallelepiped will be $|x_{1}||det(A)|$ is that right? I believe you are correct!!! –  user31317 Feb 12 '13 at 10:29

This reduces to the problem of finding a set of linearly independent vectors with maximum cardinality. There are in general many such sets, but any of them is a solution if you pick $c$ large enough. Then the convex hull is an $n$-orthoplex (AKA cross-polytope). If you make $c$ big, it will include any set of points in the span of the set, including on particular $a_1,...,a_m$. Some googling reveals that an algorithm for finding such a set is here.

Or are you trying to produce a solution with minimum $c$? This is a much more interesting question, by which I mean that I don't know the answer (:-).

share|improve this answer
1  
I think the question is whether a constant $c$ exists for which a solution is possible for all choices of $m$, $n$, $a_1,\ldots,a_m$. –  Yoav Kallus Feb 10 '13 at 16:13

This is just to say that I don't think choosing the vectors with the maximum Euclidean norm will suffice. In the example below, the two longest vectors (red) are collinear, and the hull derived from them—regardless of $c$—will be a line segment, which cannot contain the original (green) points.
           Hull Vectors

share|improve this answer
    
the idea is to choose pairs $\pm v_i$ of maximal norm, IMHO... –  Dima Pasechnik Feb 10 '13 at 14:44
    
@Dima: Would not this example still lead to collinear $v_i$? –  Joseph O'Rourke Feb 10 '13 at 15:47

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.