enter image description here

Actually, I don't quite understand the question. What does $a_{i,j}$ means? Is it the element in the matrix from row i and column j?

Can anyone give me an example? Better use another matrix because I do want to solve this question myself. Thanks~


closed as off-topic by fkraiem, Biv, Maarten Bodewes, e-sushi Jan 23 '17 at 9:57

  • This question does not appear to be about cryptography within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 3
    $\begingroup$ I'm voting to close this question as off-topic because it is about general mathematics. $\endgroup$ – fkraiem Jan 23 '17 at 1:24
  • $\begingroup$ I would not go as far as to down vote but this question does not belong to crypto.SE but more to maths.SE $\endgroup$ – Biv Jan 23 '17 at 1:27

Regarding your question on what does $a_{i,j}$ mean, no! The element $a_{i,j}$ actually represent the element in the $i$th cycle at position $j$. This is not really standard notation and I find it a bad idea, personally since it induces in error.

So it means that for instance if you have a permutation denoted as $$ \pmatrix{1&2&3\\1&3&2}$$ what does the permutation do? It simply maps $\sigma(1)=1,\; \sigma(2)=3, \;\sigma(3)=2$.

Now you want to rewrite it using "cycle notation", so you look for cycles: one maps to one, which maps to... one, so you have found a first cycle: $(1)$.

Now, $2$ maps to $3$ and $3$ maps to $2$, so you have a second cycle: $\pmatrix{2& 3}$.

And you can rewrite$$ \pmatrix{1&2&3\\1&3&2}$$ as being $$ \pmatrix{1} \pmatrix{2 & 3} $$ BUT! According to the definition, elements which do not appear in the notation are supposed to cycle on themselves, that what the $\sigma(a_{i,j})=a_{i,j}$ part means. So we can drop the $\pmatrix{1}$ and we get simply: $\pmatrix{2 & 3} $

Note that the cycle $\pmatrix{2 & 3}$ is equivalent to $\pmatrix{3 & 2}$, so it is best to use a convention like "writing the smallest one first".

Now take a more complex permutation: $$ \pmatrix{1&2&3&4&5&6\\1&4&2&3&6&5}$$ then you have more cycles, since now $\sigma(5)=6$ and $\sigma(6)=5$, and I also changed other things we end up with those cycles: $$\pmatrix{2 & 4 & 3} \pmatrix{5 & 6} $$ Where the $\pmatrix{1}$ is dropped, since it cycle on itself.

Basically to determine the cycles, you take the first element of your permutation and you apply $\sigma$ to it until you get a cycle, then you do the same for the next element not yet used in a cycle and so on until you've got all the cycles.

  • $\begingroup$ This seems like the normal cycle we did in math. Is there some special meaning for the mod notation (in the 4-th line from the question)? $\endgroup$ – yashirq Jan 23 '17 at 0:33
  • $\begingroup$ The $mod n_i$ is there simply so that the indices actually cycles too, so that the written definition is correct. I've actually made a little mistake yesterday, I was too quick to answer "yes" to your question. I've edited my answer so that now everything is correct, but the $a_{i,j}$ actually mean "the element in cycles $i$ at position $j$". Sorry for that. $\endgroup$ – Lery Jan 23 '17 at 18:43

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