MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 (or at least some of its elements) from $P_1,...,P_l$.

What should be $l$ to make it theoretically possible? How computationally hard would be to recover the matrix?

share|cite|improve this question

It is never theoretically possible to recover the matrix with certainty. Suppose the first row consists of permutations sending 1 to each of the n other elements, the second row consists of permutations fixing 1 and sending 2 to each of the n-1 elements that aren't 1, and so on. You might have to reverse the order you multiply the permutations in.

This will produce all $n!$ permutations. There are many different matrices with this description, so all are indistinguishable.

share|cite|improve this answer
I agree. but would the problem become easyer if you know the cell numbers where permutations are taken from? i.e. for each permutation $P_i$ that you have you know the cell numbers $x_{i1}, x_{i2},...,x_{in}$ that were used for calculating $P_i=x_{i1} \cdot x_{i2}...x_{in}$ then you could make a system of equations $P1=x_{11} \cdot x_{12}...x_{1n}$ ... $Pl=x_{l1} \cdot x_{l2}...x_{ln$}$ and if $l$ is big enough you probably could solve the system? if yes then how big should it be? – Jack Nov 9 '12 at 13:27

Your Answer


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

Not the answer you're looking for? Browse other questions tagged or ask your own question.