Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given a system of equations

$P_{1} = x_{11} \cdot x_{12} \cdot \ldots \cdot x_{1n}$


$P_{l} = x_{l1} \cdot x_{l2} \cdot \ldots \cdot x_{ln}$


  1. $P_{i} \in S_{n}$ are permutations over $n$ elements

  2. the number of variables $x_{ij}$ is $m$ (precisely $m=n(n-3)/2$)

  3. variable $x_{ij}$ (the $j$-th variable of the $i$-th equation) can appear in another equations only as a $j$-th variable.

  4. $x_{ij} \neq e$


  1. How to find a solution to the above system?
  2. What is the number of equations that will lead to a single solution?
share|improve this question
Can you provide an example of this? I think your question is too general as stated. –  john mangual Oct 9 '12 at 13:34
Imagine you have a $n \times n$ matrix filled in with permutations over $n$ elements. Now you pick one permutation from each row randomly starting from the first row and by multiplying them get a permutation $P_{1}$. You repeat this until you get $l$ distinct permutations. Now you want to recover the matrix from $P_{1},...,P_{l}$. What should be $l$ to make it theoretically possible? How computationally hard would be to recover the matrix? –  jack Oct 10 '12 at 9:38

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.