Warren, Look in section 3.3 of the paper http://www.i.kyushu-u.ac.jp/~hatano/papers/isaac11-full.pdf . In it they give an algorithm for writing things as a sum of n+1 vertices in time n^2. Victor On Mon, Dec 28, 2015 at 10:21 PM, Warren D Smith <warren.wds@gmail.com> wrote:
Andy Latto: Another criterion for a "natural" method of accomplishing this is lack of preference among coordinate transformations, that is the writing-as-a-weighted-sum process commutes with permuting the coordinates. Does your conversion have this property?
--WDS: the conversion method I described yielding V=weighted sum of 2N-3 perm-vectors, plus some multiple of (1,1,1,...,1), is indeed invariant under permutations of V, in the sense if you permute V, then the perm vectors all get co-permuted and other than that everything is unaltered.
I claim -- and since Andy Latto seemed to disbelieve it, I'll explain why -- that any N-dimensional real vector V can be expressed as a weighted sum of N perm-vectors, each a permutation of (0,1,2,...,N-1), with all weights nonnegative; plus some multiple of (1,1,1,...,1), and this final coefficient might be negative.
Essentially, the argument is this. There are N! perm vectors. All lie on a hyperplane of fixed coordinate sum. Scale them up by some sufficiently large common scaling factor S. All now still lie on a hyperplane of fixed coordinate-sum (S times larger sum, in fact). They are the N! vertices of a certain convex polytope in N-1 dimensions. Since S was huge, V'=V+M*(1,1,1,...,1), where M is chosen to make V' lie on that same hyperplane, lies in the interior of their convex hull. Now it is well known that any point interior to a convex polytope in N-1 dimensions is a convex linear combination of N of its vertices. Q.E.D.
But it is not obvious to me what the "best" N vertices are to choose, nor how to find them efficiently.
The algorithm I gave used 2N-3 not N vertices, for any N>=2, but had the advantage of great speed and simplicity.
And actually, now that you made me write this, I see the above proof can be improved to show STRONGER THEOREM: any N-dimensional real vector V can be expressed as a weighted sum of N-1 perm-vectors, each a permutation of (0,1,2,...,N-1), with all weights nonnegative; plus some multiple of (1,1,1,...,1), and this final coefficient might be negative.
The improvement is to choose S just right so V' lies on the boundary of the polytope. This always is possible unless V was a multiple of (1,1,1,...,1) in which case we still win.
-- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun