On Sun, Dec 27, 2015 at 3:10 PM, Warren D Smith <warren.wds@gmail.com> wrote:
A "permutation vector" shall mean an N-vector whose entries are some permutation of (0,1,2,3,...,N-1). For example (4,2,1,3,0).
Let V be an N-dimensional real vector.
I want "the natural method" for converting V into a weighted sum of permutation vectors plus some multiple of the all-1 vector.
E.g: I have a simple way to convert V into a weighted sum of at most 2N-2 perm-vectors plus some multiple of the all-1-vector, which takes O(N) operations if V is pre-sorted, and all weights automatically are nonnegative.
Even assuming the coordinates of V are non-negative, this is not in general possible. What does your algorithm yield when asked to write (1, 10) as a positive linear combination of (1, 2), (2, 1), and (1, 1)? 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 converion have this property? Andy