Reduce the Problem: Permutations and Modulo Arithmetic

# Reduce the Problem: Permutations and Modulo Arithmetic

We’ve all seen permutations before. If you have ten distinct items, and rearrange them on a shelf, you’ve just performed a permutation. A permutation is actually a function that is performing the arrangement on a set of labeled objects. For simplicity, we can just number the objects and work with permuting the numbers.

If we just look at the object numbers $1,\ldots,n$, then we can just call the set of the first $n$ integers under the operation permutation forms the symmetric group $S_{n}$. These groups are so famous they get their own name. These groups are structurally similar to many other groups that the study of these runs throughout mathematics. Here we’ll take a look at permutations in a bit more depth and see that a certain type of permutation called a cycle behaves exactly the same as integers under modulo arithmetic.

## Notation: how do we look at permutations?

Permutations of integers are done by a function $\alpha$ that maps some $i$ in $\{1,2,\ldots,n\}$ to another $j$ in $\{1,2,\ldots,n\}$. Every number in the set must get mapped somewhere in the set, though the permutation can hold some, all, or no numbers fixed. All numbers that stay fixed gives us the identity permutation, which we will call $\epsilon$

We use a certain kind of notation for permutations that looks like this example of a permutation of the numbers 1, 2, and 3.

$$\begin{pmatrix}1&2&3\\2&3&1\end{pmatrix}$$ The original order is on top. The permutation is what rearranges the fruit. We just choose to work with the numbers because we can do lots more with it

The top row is the original set in order. The numbers in the bottom row beneath each top number tell you where the permutation sends each original number. So, the above permutation maps $1 \to 2$, $2 \to 3$, and $3 \to 1$

## Multiple permutations

Now, “products” of permutations work like compositions of functions. You perform the first permutation, and then the next permutation is performed on the result of the first. When we do this, we work right to left, just like in composition of functions.

Quick example: if $f(x)=x+5$ and $g(x) = 2x$, then $f(g(x))$ is calculated by first applying $g$, then inserting that result into $f$. So,

$$f(g(2)) = f(2\cdot2) = 2\cdot2 + 5 = 9$$

Now, let’s suppose we have two permutations on the integers $\{1,2,3\}$: $\alpha = \begin{pmatrix}1&2&3\\2&3&1\end{pmatrix}$ and $\beta = \begin{pmatrix}1&2&3\\1&3&2\end{pmatrix}$. What is $\beta\alpha$?

We can simply follow a chain. Take 1 for a start. If we apply the permutation $\alpha$, and then the permutation $\beta$, where does 1 end up?

Well, $\alpha(1) = 2$. Now we apply $\beta$ to the result of $\alpha$ acting on 1, which is $\alpha(1) = 2$. Then

$$\beta\alpha(1) = \beta(\alpha(1)) =\beta(2) = 3$$

So after applying these two permutations, 1 is sent to 3. We can do this for the other two numbers, and we get that

$$\beta\alpha =\begin{pmatrix}1&2&3\\1&3&2\end{pmatrix}\begin{pmatrix}1&2&3\\2&3&1\end{pmatrix} =\begin{pmatrix}1&2&3\\3&2&1\end{pmatrix}$$

## Cycles

Now we’ll introduce another concept and notation-that of cycles. A cycle is written just using parentheses instead of the larger notation we used before1.

The cycle $(123)$ denotes exactly that. Reading left to right, 1 maps to 2, 2 maps to 3, and 3 cycles back around to 1. So $(123)$ is actually just another way of expressing $\alpha = \begin{pmatrix}1&2&3\\2&3&1\end{pmatrix}$

One other note about the shorthand: every permutation on $n$ integers can be written as the product of these disjoint cycles.2 (134) and (25) are disjoint cycles. We’re going to study powers of a single cycle. Powers of cycles work just like powers of numbers: just as $2^3$ is $2\cdot2\cdot2$, $(134)^{3} = (134)(134)(134)$3

## Examples of Powers of Cycles

Let’s take an example of a cycle: $\alpha = (123)$ and just compute some powers of it.

$$\alpha^{2} =(123)(123)=\begin{pmatrix}1&2&3\\2&3&1\end{pmatrix}\begin{pmatrix}1&2&3\\2&3&1\end{pmatrix}=\begin{pmatrix}1&2&3\\3&1&2\end{pmatrix}=(132)$$

Now, $\alpha^{3} = \alpha\alpha^{2}$ (again note that we apply another “round” of permutations on the left), and can be calculated in a similar way:

$$\alpha^{3} = (123)(132)=\begin{pmatrix}1&2&3\\1&2&3\end{pmatrix}=\epsilon$$

Interesting notion here. Now we’re back to the identity permutation. That means if we multiply the cycle $(123)$ on the left of the identity permutation $\epsilon$, we just get $(123)$. In other words, $(123)^{4} = (123)$. Then that means $(123)^{5} = (123)(123)^{4} = (123)(123) = (123)^{2}$, and $(123)^{6} = \epsilon$. Our powers of this cycle form another “cycle” that’s starting to look awfully similar to something we’ve seen before: modulo addition.

## Modulo addition and our permutations

The great thing about studying algebra is that by studying the structure of things, we can observe that two groups that looked totally unrelated actually behave very similarly. Notice that the power of a cycle of length 3, like the ones we computed above, “start over” at powers that are multiples of 3: $(123)^{3} = (123)^{6} = \epsilon$. So if we paired the cycle $(123)$ with 1, $(123)^{2}$ with 2, and $(123)^{3}$ with 0, then the behavior of this cycle under its “permutation multiplication” is identical to the behavior of $\mathbb{Z}_{3}$, the integers modulo 3, that we have previously discussed.

To extend a bit further, since we can obvious take more powers of the cycle $(123)$ than just stopping at 3, if we wanted to make the correspondence to $\mathbb{Z}_{3}$, all powers of $(123)$ that are multiples of 3 (which evaluate to the identity permutation) would correspond to 0 (the identity element under modulo addition). The powers of $(123)$ that leave a remainder of 3 when you divide the power by 3 would behave like $1 \in \mathbb{Z}_{3}$, and the powers of $(123)$ that leave a remainder of 2 would match with $2 \in \mathbb{Z}_{3}$

To write this mathematically, we can actually map the set of all powers of $(123)$ or any cycle of length 34 to $\mathbb{Z}_{3}$

Let $n$ be the power of a cycle of length 3, which we will now call $(a_{1}a_{2}a_{3})$ to generalize. Then $(a_{1}a_{2}a_{3})^{n}$ maps to $n \bmod 3$. With this, we’ve connected the two groups and learned that powers of cycles of length 3 act just like integers modulo 3.

## One more extension

We just discovered that cycles of length 3 under powers (multiplying by itself) act just like integers modulo 3 under modulo addition. The next question we can ask is:

### Does this hold true for cycles of any length?

That is, if we have a cycle of length $s$, does it behave like integers modulo $s$? In fact, it does. We’re going to get a little more general here, so stick with me.

Take a generic cycle of length $s$, and call it $\beta = (b_{1}b_{2}\ldots b_{s})$ where each $b_{i}$ is some number or element in the permutation cycle. Then we’re going to start describing distinct powers of this $\beta$ and watch what happens.

\begin{aligned}\beta &=\begin{pmatrix}b_{1}&b_{2}&b_{3}&\ldots&b_{s}\\b_{2}&b_{3}&b_{4}&\ldots & b_{1}\end{pmatrix}\\\beta^{2} &=\begin{pmatrix}b_{1}&b_{2}&b_{3}&\ldots&b_{s}\\b_{3}&b_{4}&b_{5}&\ldots & b_{2}\end{pmatrix}\\\beta^{3} &=\begin{pmatrix}b_{1}&b_{2}&b_{3}&\ldots&b_{s}\\b_{4}&b_{5}&b_{6}&\ldots & b_{3}\end{pmatrix}\\&\vdots\\\beta^{s-1} &=\begin{pmatrix}b_{1}&b_{2}&b_{3}&\ldots&b_{s}\\b_{s}&b_{1}&b_{2}&\ldots & b_{s-1}\end{pmatrix}\\\beta^{s} &=\begin{pmatrix}b_{1}&b_{2}&b_{3}&\ldots&b_{s}\\b_{1}&b_{2}&b_{3}&\ldots & b_{s}\end{pmatrix}=\epsilon\end{aligned}

If this looks intimidating, just follow what $b_{1}$ gets permuted to as you take more powers. applying one $\beta$ to $b_{1}$ gives $\beta(b_{1}) = b_{2}$. Then $\beta^{2}(b_{1}) = \beta(\beta(b_{1})) = \beta(b_{2}) = b_{3}$. Next, $\beta^{3}(b_{1}) = b_{4}$. Now we start noticing the pattern, just as we did for the cycles of length 3: $\beta^{n}(b_{1}) = b_{1+n}$ while $n < s$, the length of our cycle. Then $\beta^{s}(b_{1}) = b_{1}$ again and we’re now starting over.

Do the same thing for any other element in the permutation. Follow it through the powers of $\beta$ and notice that $\beta^{n}(b_{j}) = b_{j+n}$ for any generic $j$. Now, when we take powers of the cycle that are larger than $s$, we just “start over again”. So $\beta^{s+1} = \beta$, $\beta^{s+2} = \beta^{2}$, and so forth. So $\beta^{n} = \beta^{n\mod s}$ in general, whether $n \geq s$ or $n < s$

Now that means we have made the same observation in general that we did for cycles of length 3. We can map powers of cycles of any length $s$ to integers modulo $s$, and both groups will behave the same way, with the same “starting over” property we observed in modulo arithmetic.

## Conclusion

What you’ve just discovered is a mathematical phenomenon called an isomorphism. We’ll discuss the formalities of this in another post. In a nutshell, an isomorphism is the mapping that lets us connect two groups that behave the same way, even if their elements and respective operations have nothing to do with each other. Picture it like two people running with the same stride length and form. Even if they are running in different locations or opposite directions, they’re still behaving the same way. Two things that are structurally and behaviorally equivalent, mathematically, are called isomorphic. We just proved (albeit a bit informally) that $\mathbb{Z}_{s}$, is isomorphic to permutation cycles of length $s$

Modulo arithmetic is much easier to compute than powers of permutations, so if we want to study how they work, we can actually study an isomorphic group that is simpler to get the same results. As a more tangible example, molecular structures and symmetries can get really icky to study and play with. There are simpler groups that are isomorphic to these structures and their symmetries that make their study much easier. For instance, instead of having to build a model and study what happens if you rotate it twice and reflect it across its vertical symmetry once, we can map those actions to a simpler algebraic structure with a simpler multiplication, calculate the result, then map it back using the isomorphism.

Abstract mathematics allows us to strip the more complex “fluff” from a problem and reduce it to its skeleton. By looking at the skeletons, we can study the problem’s mechanics more simply, and even reduce the problem to an isomorphic one that has been previously solved. #### Footnotes

1. I said once that mathematicians were lazy. We hate writing more than we have to.
2. Disjoint – a number that shows up in one cycle doesn’t show up in another
3. Remember that we apply the permutations from right to left
4. Numbers are just labels in permutations. If we have a cycle of length 3 that isn’t (123), say (489), the behavior is still the same. We can just “label” 4 as the first in the cycle, 8 as the second, and 9 as the third and be right back with what we already know

## 16 thoughts on “Reduce the Problem: Permutations and Modulo Arithmetic”

1. An Engineer says:

You wrote a great article with good examples that help a non-mathematician like me learn more about a subject I’m not trained in. Thanks!

2. Bob says:

Very nice. Just a quick note: it looks like you write “(134)³ = (134)(134)(134)³”, which is false, because the final ³ is a footnote marker rather than a mathematical exponent. You might want to move the footnote to another part of the sentence to avoid this.

3. Ginny Maria says:

After reading your blog post, I browsed your website a bit and noticed you aren’t having good traffic for your website in Google as you could be. I possess a handful of blogs myself, and I think you should take a look at https://seowebsitetraffic.net/order/, just google it. You’ll find it’s a very lovely help that can bring you a lot more visitors and improve your sales. Keep up the quality posts.

4. JerrellBig says:

Hello. I have checked your themathcitadel.com and i see you’ve got some duplicate content so probably it is the reason that you don’t
rank high in google. But you can fix this issue fast. There is a tool that creates articles like human, just search in google: miftolo’s tools

5. bbcuvuvdrcm8c5schmx72m3a5 says:

Spot on with this write-up, I actually think this web site wants far more consideration. I’ll most likely be again to learn much more, thanks for that info.

6. Peter Mundz says:

viagra quanto costa

7. Kathlene Zarlengo says:

I have been absent for a while, but now I remember why I used to love this web site. Thank you, I’ll try and check back more frequently. How frequently you update your site?

8. Laverne Firpi says:

What i do not realize is in truth how you are no longer actually a lot more smartly-liked than you may be now. You are so intelligent. You understand therefore significantly on the subject of this topic, made me in my view believe it from so many varied angles. Its like men and women don’t seem to be interested except it¡¦s one thing to do with Girl gaga! Your own stuffs great. Always maintain it up!

9. Barry Banez says:

I keep listening to the rumor talk about receiving free online grant applications so I have been looking around for the top site to get one. Could you advise me please, where could i acquire some?

10. Roselyn Washler says:

Is anyone aware of the deadline for the Mills & Co Training Contract Application? God Bless you this Christmas season

11. Dennis Schloemann says:

I know this if off topic but I’m looking into starting my own blog and was curious what all is required to get set up? I’m assuming having a blog like yours would cost a pretty penny? I’m not very internet savvy so I’m not 100 positive. Any recommendations or advice would be greatly appreciated. Thanks