Card shuffle and nerdy things
You get together with your friends to play Poker. Five minutes into the game and you're, as always, kicked for cheating. You exit the room with four stolen cards. To kill time, you lay them out on a table in order and then shuffle them like below.
A math geek, you realize that there's some math in this. You're right! Indeed, a shuffle like this is called a permutation. First, we let the original deck be the set $C=\{2,3,4,5\}$, and the shuffled set is $C'=\{5,4,3,2\}$. Then the shuffled set $C'$ is called a permutation of $C$. If you haven't heard of set, think of it as a container that can contain not just numbers but any objects.
Matrix and Cycle representations of permutations
But what if you want to impress a friend with your permutation, but forget to bring a deck of cards? You'll need a way to abstractly represent this permutation. Here's what you're gonna do. You call the act of permuting / shuffling the set $\sigma$, and write something like:
$\sigma= \begin{pmatrix} 2&3&4&5 \\ 5&4&3&2 \end{pmatrix}$
This means that the card numbered $5$ occupies the position where card numbered $2$ is used to be and so on for other cards. But you can still get fancier. You can think of the shuffle $\sigma$ as a function that maps the set $C$ into itself. The shuffle $\sigma$ is a function (also known as mapping) because it assigns one value with another. We're all used to this $y=f(x)=x^2$. This assigns the number $x=2$ to the number $y=4$. Same thing with $\sigma$. Our shuffle $\sigma$ assigns $3$ to $4$ or we write $\sigma(3)=4$. We can display $\sigma$ in a more visual form like this.
Now we can be even cooler by representing the permutation in cycle form like so
The picture leads us to conjecture that every permutation is composed of disjoint cycles. "Disjoint" means that if we imagine each number as an island, the arrows between numbers as bridges connecting islands, then a cycle $A$ (a group of islands) is disjoint from another cycle $B$ if there's no way to get from an island in $A$ to one in $B$. "Cycle" means a group of islands, but not just any kind of group. It's a group of islands that looks like edges of a polygon. In other words, there are exactly $2$ bridges to an island.
Claim: Each permutation is composed of disjoint cycles
Proof:
We'll defer the proof to later article. Right now, just take it as a given.
Permutations as a group
Now returning back to the original event of shuffling 5 cards, we want to know in how many ways we get generate different shuffles. If you've read my article on choosing chair (link here for those didn't), you'll realize that the answer is $5!=120$. Now, we put $120$ shuffles into a set called $G$ (did I tell you that sets are very powerful, they can contain just everything from "tangible" objects like numbers to actions like shuffles?). We will prove that $G$ satisfies a certain bunch of rules that will earn $G$ the title group! (We're getting close to group theory now, yeah!). There are four properties that a group have to satisfy. And I'll explain each of them and check our permutations satisfy them along the way.
1. Closure under a binary operation
We want elements in our group to be able to interact with each other. We will define a binary operation $*$ on a set $X$ that will take two outputs to produce one output. "Binary operation" sounds fancy, but all it means is that it takes two to make one. For example, addition is a binary operation. $5+2=7$, so the addition takes two outputs $5$ and $2$ to produce $7$. Now that we have an operation on $X$, we need $X$ to be "closed" when applying the operation. That is, if $a,b$ is in $X$, then the output $a*b=c$ must be in $X$ as well.
For our permutation group $G$, we define the operation as function composition $\cdot$ in . So $\sigma_1 \cdot \sigma_2$ means that first do $\sigma_2$, then do $\sigma_1$ on the result. Take three cards for example. Define $\sigma_1= \begin{pmatrix} 1&2&3 \\ 1&3&2 \end{pmatrix}$ and $\sigma_2=\begin{pmatrix} 1&2&3 \\ 3&2&1 \end{pmatrix}$, then $\sigma_1 \cdot \sigma_2=\begin{pmatrix} 1&2&3 \\ 3&1&2 \end{pmatrix}$.
We readily see that a composition of two permutations is yet another permutation. So indeed $\sigma_1 \cdot \sigma_2 = \sigma_3 \in G$ for $\sigma_1, \sigma_2 \in G$.
2. Identity
Our group must contain an identity element called $e$ that is if $a \in G$ then $a.e=a$. In other words, $e$ is a "do-nothing element". In addition, we see $0$ is an identity because any number added with $0$ equals to the same number. In multiplication, $1$ is the identity, because $a.1=a$ for all $a$.
Checking
For permutations, you're better believe that identity exists. The identity is literally "do-nothing", just don't touch the cards and leave them unshuffled. In terms of function, it's the one that maps every element into itself like $e= \begin{pmatrix} 1&2&3 \\ 1&2&3 \end{pmatrix}$.
3. Inverse
This property requires that for each $a \in G$ there exists an inverse $a^{-1} \in G$ such that $a.a^{-1}=e$. In a sense, $a^{-1}$ is nemesis of $a$ that just undoes $a$.
Checking
We can easily see the existence of a permutation looking at the function picture
In the picture, $\sigma=\begin{pmatrix} 1&2&3 \\ 1&3&2 \end{pmatrix}$, and $\sigma^{-1}=\begin{pmatrix} 1&2&3 \\ 1&3&2 \end{pmatrix}$. In this case, $\sigma$ is its own inverse. An interested reader may find a proof that a bijection is invertible online (a permutation is a bijection).
This group requires that $(a \cdot b) \cdot c=a \cdot (b \cdot c)$. This means that we can group freely when carrying out the binary operation.
Checking
There's a slick and rather annoying way to see that $G$ in fact satisfies this property. First, consider $(a \cdot b) \cdot c$. Because of closure, $(a \cdot b) = d \in G$. So, $(a \cdot b) \cdot c = d \cdot c$. This means we carry out $c$ first and then $d$. But $d$ is $a \cdot b$, so the order of carrying out the permutations is $c$ first, $b$ second and then $a$. Now, consider $a \cdot (b \cdot c)$. Because of closure, let $b \cdot c = k \in G$. And $(b \cdot c)$ means that we carry out $k$ first and then $b$. We see readily that we also carry the permutation $a \cdot(b \cdot c)$ in the order: $c$ first, $b$ second and then $a$. This means that $(a \cdot b) \cdot c=a \cdot (b \cdot c)$, and $G$ is associative as claimed.
Cool, now that we've checked all $4$ properties, we can be assured that our permutations is a group. In fact, it's called a symmetry group $S_n$. Our original example of $4$ cards is $S_4$.
$a=\begin{pmatrix} 1&2&3 \\ 2&1&3 \end{pmatrix}$,
and
$b= \begin{pmatrix} 1&2&3 \\ 1&3&2 \end{pmatrix}$.
Clearly $a \cdot b \not = b \cdot a$. In fact,
$ b \cdot a = \begin{pmatrix} 1&2&3 \\ 2&3&1 \end{pmatrix}$
while
$b \cdot a =\begin{pmatrix} 1&2&3 \\ 3&1&2 \end{pmatrix}$
No comments:
Post a Comment