2
$\begingroup$

Let$M$ be an$n \times m$ matrix, with$1, \dots, m$ in the first row,$m+1, \dots, 2m$ in the second row, etc.

$$M = \left[\begin{array}{c}1 & 2 & \dots & m \\m+1 & m+2 & \dots & 2m \\& & \dots & \\(n-1)m + 1 & (n-1)m + 2 & \dots & nm\end{array}\right]$$

I want to shuffle this matrix using only two kinds of operations:

  • Column shifts, where a shift of column$j$ by$s$ moves the element at$(i, j)$ to$(i + s \bmod{n}, j)$, for$i \in [n]$.
  • Row shifts, where a shift of row$i$ by$s$ moves each element at$(i, j)$ to$(i, j+s\bmod{m})$, for$j \in [m]$.

(A row / column shift affectsone row / column, not all of them.)

My goal is not necessarily to achieve a full shuffle; rather, it is to ensure that any$n$ elements are equally likely to be in the same column. (However, correlations across columns - where perhaps$n$ elements$y_1, \dots, y_n$ share a column iff elements$x_1, \dots, x_n$ share a column - are allowed.)

How many random shifts (column / row shifts with random$s$) do I need to perform before my matrix is "shuffled enough" (as described above)? What is the minimal shuffling algorithm (which columns$j$ and rows$i$ do I randomly shift)?

Any hints to relevant literature would be appreciated. Thank you in advance!

askedMar 20 at 7:58
So Ya's user avatar
$\endgroup$
2
  • $\begingroup$Full shuffle: every permutation is equally likely. Elements 1 and 2 can get to the same column if e.g. we shift column 2 by $1$, and then shift row 2 by $m-1$.$\endgroup$CommentedMar 21 at 1:40
  • $\begingroup$Just a small example: I worked out the poset for the $2 \times 2$ case, which is really $S_4$ with generators $(12),(34),(13),(24)$. The ranks have sizes $1, 4, 10, 8, 1$ with the "long matrix" $\{\{4,3\},\{2,1\}\}$ on top. For this case, note that you'll always be at level 0, 2, or 4 with an even number of moves (calling $\{\{1,2\},\{3,4\}\}$ level 0), the permutations in $A_4$. So, with any number of moves, here you'll always be toggling between even or odd permutations, although your sense of "shuffled enough" might still be achieved.$\endgroup$CommentedMar 21 at 13:16

0

You mustlog in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.