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~

  • 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.