# How to solve a system of equations over permutations?

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?

-

## 1 Answer

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.

-
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