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~
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this communityActually, 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~
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.