3 ms·

the important bit is you have to unscramble in reverse order of the scrambling. Unscrambling the columns and then unscrambling the rows would lead to smooth gib

by dastbe 10y ago

the important bit is you have to unscramble in reverse order of the scrambling. Unscrambling the columns and then unscrambling the rows would lead to smooth gibberish.

barrkel 10y ago
No. Column scrambling doesn't affect row ordering and row scrambling doesn't affect column ordering. They are literally orthogonal. You can't tell, from a scrambled matrix, whether the rows or the columns were scrambled first. Here's a more explicit breakdown: (0,0) (1,0) (2,0) (0,1) (1,1) (2,1) (0,2) (1,2) (2,2) Column scrambling: swap 1&2: (0,0) (2,0) (1,0) (0,1) (2,1) (1,1) (0,2) (2,2) (1,2) Now row scrambling: swap 0&1: (0,1) (2,1) (1,1) (0,0) (2,0) (1,0) (0,2) (2,2) (1,2) Notice how the x coordinates still all match along the vertical, and y coordinates still all match along the horizontal. Let's try it in the other order, row first: (0,1) (1,1) (2,1) (0,0) (1,0) (2,0) (0,2) (1,2) (2,2) And columns: (0,1) (2,1) (1,1) (0,0) (2,0) (1,0) (0,2) (2,2) (1,2) It's the same result irrespective of the order.
- kmill 10y ago
  Another way to think of it is that permuting rows corresponds to multiplying a matrix on the left by a permutation matrix, and permuting columns, on the right. Since matrix multiplication is associative, they commute!
  - evincarofautumn 10y ago
    Yet another way to think of it is that a matrix is an encoding of a linear (or affine) function, matrix multiplication is composition of such functions, and since composition is associative, they commute. :)
- dastbe 10y ago
  Thanks! my mental model was incorrect.
robinhouston 10y ago
Interestingly enough, that isn’t true. The operations of row-shuffling and column-shuffling commute, so you can do them in either order. You can try it yourself, if you’ve cloned the repo. Here are the commands to reconstruct first by columns and then by rows: git checkout double-shuffling make images/double_shuffled/blue-hour-paris.png bin/compute_scores mkdir tmp bin/compute_scores --cols images/double_shuffled/blue-hour-paris.png > tmp/cols.tsp bin/lkh.sh tmp/cols.tsp tmp/cols.tour bin/reconstruct_image.py --cols tmp/cols.tour images/double_shuffled/blue-hour-paris.png > tmp/cols-unshuffled.png bin/compute_scores --rows tmp/cols-unshuffled.png > tmp/rows.tsp bin/lkh.sh tmp/rows.tsp tmp/rows.tour bin/reconstruct_image.py --rows tmp/rows.tour tmp/cols-unshuffled.png > tmp/reverse-unshuffled.png

by dastbe 10y ago

the important bit is you have to unscramble in reverse order of the scrambling. Unscrambling the columns and then unscrambling the rows would lead to smooth gibberish.

barrkel 10y ago

No. Column scrambling doesn't affect row ordering and row scrambling doesn't affect column ordering. They are literally orthogonal. You can't tell, from a scrambled matrix, whether the rows or the columns were scrambled first. Here's a more explicit breakdown: (0,0) (1,0) (2,0) (0,1) (1,1) (2,1) (0,2) (1,2) (2,2) Column scrambling: swap 1&2: (0,0) (2,0) (1,0) (0,1) (2,1) (1,1) (0,2) (2,2) (1,2) Now row scrambling: swap 0&1: (0,1) (2,1) (1,1) (0,0) (2,0) (1,0) (0,2) (2,2) (1,2) Notice how the x coordinates still all match along the vertical, and y coordinates still all match along the horizontal. Let's try it in the other order, row first: (0,1) (1,1) (2,1) (0,0) (1,0) (2,0) (0,2) (1,2) (2,2) And columns: (0,1) (2,1) (1,1) (0,0) (2,0) (1,0) (0,2) (2,2) (1,2) It's the same result irrespective of the order.

kmill 10y ago
Another way to think of it is that permuting rows corresponds to multiplying a matrix on the left by a permutation matrix, and permuting columns, on the right. Since matrix multiplication is associative, they commute!
- evincarofautumn 10y ago
  Yet another way to think of it is that a matrix is an encoding of a linear (or affine) function, matrix multiplication is composition of such functions, and since composition is associative, they commute. :)
dastbe 10y ago
Thanks! my mental model was incorrect.

robinhouston 10y ago

Interestingly enough, that isn’t true. The operations of row-shuffling and column-shuffling commute, so you can do them in either order. You can try it yourself, if you’ve cloned the repo. Here are the commands to reconstruct first by columns and then by rows: git checkout double-shuffling make images/double_shuffled/blue-hour-paris.png bin/compute_scores mkdir tmp bin/compute_scores --cols images/double_shuffled/blue-hour-paris.png > tmp/cols.tsp bin/lkh.sh tmp/cols.tsp tmp/cols.tour bin/reconstruct_image.py --cols tmp/cols.tour images/double_shuffled/blue-hour-paris.png > tmp/cols-unshuffled.png bin/compute_scores --rows tmp/cols-unshuffled.png > tmp/rows.tsp bin/lkh.sh tmp/rows.tsp tmp/rows.tour bin/reconstruct_image.py --rows tmp/rows.tour tmp/cols-unshuffled.png > tmp/reverse-unshuffled.png