# Orders of coordinates in a linear subspace

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?

• is $R= \mathbb{R}$? – mdave16 May 28 '17 at 23:26
• @mdave16 yes. Corrected. – Jeremy K May 28 '17 at 23:56
• 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. – mm8511 May 29 '17 at 0:29
• @mm8511 Yes, but even this approach will take quite a while for large $n$. – Jeremy K May 29 '17 at 0:37
• 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. – mm8511 May 29 '17 at 0:45