1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$ – Jack Nov 9 '12 at 13:27

Your Answer

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

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