5
$\begingroup$

Let $X$ be a linear subspace of $\mathbb{R}^n$. For how many permutations $p$ on ${1,...,n}$ does there exists $x$ in $X$ with $x_{p(1)} < x_{p(2)} < ... < x_{p(n)}$?

We can test each permutation by solving a linear program, but this is time consuming when $n$ is large. Is there a quicker way to solve this problem, or at least approximate the solution?

$\endgroup$
  • $\begingroup$ is $R= \mathbb{R}$? $\endgroup$ – mdave16 May 28 '17 at 23:26
  • $\begingroup$ @mdave16 yes. Corrected. $\endgroup$ – Jeremy K May 28 '17 at 23:56
  • $\begingroup$ You probably already thought of this, but it would probably be faster to use branch and bound along with the linear programming approach i.e. find $x\in X$ satisfying $x_{i_1}<x_{i_2}<...<x_{i_k}$ for all subsets $\{i_1,\dots,i_k\}$ of $\{1,\dots , n\}$, pruning when you fail to find a solution. $\endgroup$ – mm8511 May 29 '17 at 0:29
  • $\begingroup$ @mm8511 Yes, but even this approach will take quite a while for large $n$. $\endgroup$ – Jeremy K May 29 '17 at 0:37
  • $\begingroup$ agreed... just a thought, every subspace of $R^n$ with dimension $k$ is (in a sense) isomorphic to the space spanned by some subset of $k$ standard basis vectors. For the standard basis vectors counting the number of permutations is easy. There are $k!$ (just weight them according to the permutation you need). This leads me to think that it should be proportional to the dimension of the subspace. $\endgroup$ – mm8511 May 29 '17 at 0:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.