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)