most recent 30 from http://mathoverflow.net 2013-05-22T02:15:02Z http://mathoverflow.net/feeds/question/111824 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/111824/how-to-solve-a-system-of-equations-over-permutations Jack 2012-11-08T15:47:38Z 2012-12-06T16:22:00Z

<p>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$.</p> <p>What should be $l$ to make it theoretically possible? How computationally hard would be to recover the matrix?</p>

http://mathoverflow.net/questions/111824/how-to-solve-a-system-of-equations-over-permutations/111829#111829 Will Sawin 2012-11-08T16:05:03Z 2012-11-08T16:05:03Z

<p>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.</p> <p>This will produce all $n!$ permutations. There are many different matrices with this description, so all are indistinguishable.</p>