1
$\begingroup$

I have a bunch of vectors $\mathbf v_i$ in $\mathbb R^n$. I would like to consider the cone $C$ spanned by these vectors, together with all the other vectors that can be obtained by permuting the entries of the $\mathbf v_i$:

$$C = \sum_{\substack{1 \leq i \leq n, \pi \in S_n \\ \alpha_{i,\pi} \geq 0}} \alpha_{i,\pi} \pi(v_i).$$

Then I would like to know the generators of $C$ (again just generators up to the $S_n$ action).

I have been doing this using the fourierMotzkin package in Macaulay2: I compute all the permuted vectors, take they cone they span, and then find the generators. However, I expect that my stupid algorithm is about $n!$ times slower than it needs to be, and I am starting to consider some cases where $n!$ is not insignificant. In practice I would like to do this for $n$ up to about $20$.

What's the right way to do this? (Extra points if it is already implemented in Macaulay2 or Sage.)

(Reason for the ag.algebraic-geometry tag: the question arises in studying the effective cone of divisors on some very symmetric variety.)

Improve this question
$\endgroup$
3
  • $\begingroup$ So if I understand correctly, for a given set of vectors $\{ v_i \}$ you want a set of vectors $\{w_k\}$ such that the set $\{\pi(w_k) | \pi \in S_n\}$ generates the cone $\{ \sum_i \alpha_i v_i | \alpha_i \geq 0 \}$? $\endgroup$
    – Vít Tuček
    Sep 18, 2015 at 18:25
  • $\begingroup$ Almost: I am looking at the cone given by all positive linear combinations of $\pi(v_i) : \pi \in S_n$. I want the $\pi(w_i)$ to generate the cone, but to be the minimal possible such set. $\endgroup$
    – user47305
    Sep 18, 2015 at 19:31
  • $\begingroup$ (I edited the question to clarify.) $\endgroup$
    – user47305
    Sep 18, 2015 at 20:56

1 Answer 1

Reset to default
0
$\begingroup$

Check out this software, it managed to solve a discrete case of a similar problem. I believe it can handle your version of the problem. https://www.normaliz.uni-osnabrueck.de/

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.