20131011

Please Login to access more options.

Today

For Friday, the prep is to work on the first 6 problems below. The seventh problem is there as an additional problem to work on if you finish the first 6. Problem 7 is the key problem needed to proving most of the facts we've conjectured about modular arithmetic.

In class, we'll start with those who have the Cayley graph problem from last time.

• Brennan - Put up the graphs on part 1, as well as why you know it's an isomorphism.
• Lilia - Draw the Cayley graph of $H_6$ generated by $\{\phi_2, \phi_3\}$.
• Bryce - Draw the Cayley graph of $K$ generated by $\{f_2,f_6\}$.
• Kinsey - Draw a Cayley graph of $S_3$ generated by the permutations $(1,2,3)$ and $(1,2)$.

I would like to refer to someone's typed version of (The Span Of A Set Of Integers Is Closed) from last time (so if Joe or Kinsey wants to type it, I would love to have you type your version up for this coming week's post, and then share it in class).

We've talked about automorphisms of graphs and directed graphs. We can similarly define automorphisms of colored directed graphs.

Definition (Automorphism Of A Colored Directed Graph)

Let $\mathcal{G}=(V,C,A)$ be a colored directed graph, where the vertex set is $V$ and the list of colored arrows is $A$, where each arrow in the list $A$ is assigned a unique color from $C$. An automorphism of a directed colored graph is a permutation $\sigma:V\to V$ of the vertex set such that $(x,y)$ is an arrow colored $c\in C$ if and only if $(\sigma(x),\sigma(y))$ is an arrow colored $c$. In other words, it's a permutation of $H$ that preserves the arrow and color structure of the graph.

A Cayley graph is a colored directed graph. We've drawn many Cayley graphs and noticed that they are highly symmetric. Every point has the same number of arrows leaving (and entering). Any pattern we see at one vertex appears at every other vertex. If you were to stand at any vertex and look outwards, the graph would appear the same from every point. This next problem has you show this. You'll show that if $s$ is one of the permutations used to create arrows, then the map $f_s:H\to H$ defined by $f_s(\sigma)=\sigma\circ s$ is an automorphism of the Cayley graph. Once you've shown that the graph looks the same by following one arrow, you can repeatedly apply this process to show that the graph looks the same by following any sequence of arrows.

Problem 41 (Translating By An Arrow In A Cayley Graph Is An Automorphism)

Let $X$ be a set and let $S$ be a set of permutations of $X$. Let $H=\text{span}(S)$ and let $\mathcal{G}$ be the Cayley graph $(H,S)$, so we know $(x,y)$ is an arrow colored $c_t$ where $t\in S$ if and only if $y=t \circ x$. Pick an element $s\in S$ (one of the elements used to create arrows). Prove that the function $f_s:H\to H$ defined by $f_s(\sigma)=\sigma\circ s$ is an automorphism of the Cayley graph. You must show the following three things:

1. The function $f_s$ is a permutation. (State the inverse and show it is the inverse.)
2. If $(x,y)$ is an arrow colored $c_t$, then $(f_s(x),f_s(y))$ is an arrow colored $c_t$. In other words, if $t\circ x=y$, then explain why $t\circ f_s(x) = f_s(y)$.
3. If $(f_s(x),f_s(y))$ is an arrow colored $c_t$, then $(x,y)$ is an arrow colored $c_t$.

Problem (Closed Under Function Composition)

Suppose that $H$ is a set of permutations of $X$. Suppose also that if $\alpha,\beta\in H$, then we must have $\alpha\circ \beta\in H$. Use induction to prove that for every $n\in \mathbb{N}$, if we know $\sigma_1,\sigma_2,\ldots,\sigma_n\in H$, then we must have $$\sigma_1\circ\sigma_2\circ\cdots\circ\sigma_n\in H.$$

In the previous problem we assumed that if if $\alpha,\beta\in H$, then we must have $\alpha\circ \beta\in H$. Any time a set $H$ of permutations satisfies this, we say that the set $H$ is closed under composition. Similarly we say that set is closed under taking inverse if $\alpha\in H$ implies $\alpha^{-1}\in H$. We've been saying that a set of permutations is closed (under composition combinations of permutation) when the set contains any composition combination of permutations of the set. This next problems shows a simpler way to prove that a set is closed, and it requires showing only that the set is closed under composition and closed under taking inverses.

Problem (Characterizing Closed Sets Of Permutations)

Let $H$ be a set of permutations of a set $X$. Suppose that $H$ satisifies the following 4 properties.

1. The identity function $id_X$ is in $H$.
2. If $\sigma\in H$, then so is $\sigma^{-1}$.
3. If $\alpha\in H$ and $\beta\in H$, then so is $\alpha\circ \beta\in H$.
4. If $\alpha,\beta,\gamma\in H$, then we have $\alpha\circ (\beta\circ \gamma) = (\alpha\circ \beta)\circ \gamma$.

Prove that $H$ is closed.

Definition (Binary Operation)

Let $G$ be a set. A binary operation on $G$ is a way of combining two elements of $G$ to obtain a new element in $G$. Formally, we just say that a binary operation $*$ is function $*:G\times G\to G$, and we use the notation $a*b$ to represent the function notation $*(a,b)$.

You've been using binary operations your whole life.

Problem 39 (Binary Operation Introduction)

In which of the following scenarios do we have a binary operation on a set $G$. Justify your answers.

1. Addition $a+b$ of integers.
2. Multiplication $A\cdot B$ of 3 by 3 matrices.
3. The dot product $\vec u\cdot \vec v$ of two dimensional vectors.
4. The cross product $\vec u\times \vec v$ of three dimensional vectors.
5. The scalar product $c\cdot \vec v$.
6. Composition $f\circ g$ of permutations on the same set $X$.
7. Composition $f\circ g$ of functions from $X$ to $Y$.

Up to this point in the semester, we've been focusing solely on sets of permutations. Every element was a function, which often required keeping track of a bunch of information that wasn't necessary. Spanning a set of permutations gave us closed sets of permutations. We found that there are 4 key properties of a set of closed permutations. Let's now drop the requirement that we have permutations, and instead focus on sets, together with a binary operation, that satisfy these 4 properties. We call a set with these properties a group.

Definition (Group)

Let $G$ be a nonempty set, and let $*$ be a binary operation on $G$, which means for every $x,y\in G$ we have $x*y\in G$ $\textbf{[Closure]}$. The structure $\mathbb{G} = (G,*)$ is called a $\textdef{group}$ if the following hold.

1. $\textbf{[Associativity]}$ For all $x,y,z\in G$ we have $(x* y)* z = x* (y* z)$.
2. $\textbf{[Identity]}$ There is an $e\in G$ such that for all $x\in G$ we have $x * e = e* x = x$.
3. $\textbf{[Inverses]}$ For all $x\in G$ there is a $y\in G$ such that $x* y = y* x = e$.

We usually simply write $G$ when referring to the entire structure $\mathbb{G}=(G,*)$. The element $e$ from the second point is called the $\textdef{identity}$. The element $y$ from the third point is called the $\textdef{inverse}$ of $x$ and is usually denoted $x^{-1}$. One often simply writes $xy$ in place of $x*y$, and for every positive integer $n$, we'll write $x^n$ as shorthand for $x* x* \cdots * x$ ($n$ times).

We've already seen many groups throughout the semester. In the problem Characterizing Closed Sets Of Permutations, we showed that any closed set of permutations is a group. Since the span of any set of permutations is closed, then every time we span a set of permutations, we end up with a group. All of the patterns you have discovered about simple shift permutations, automorphisms of graphs, and more, we will be able to transfer to your understanding of abstract groups. Let's look an example, namely a group of matrices that we used before to encrypt messages.

Problem 40 (General Linear Group Introduction)

We've used matrices mod $5$ to encrypt a simple message. The set of possible 2 by 2 matrices mod $5$ that we can use as an encryption key is an important set in cryptography. It's called a general linear group and written $\text{GL}(2,\mathbb{Z}_5)$. We can generalize this to $m$ by $m$ matrices mod $n$ and write $\text{GL}(m,\mathbb{Z}_n)$, though generally we require that $n$ be a prime. With each of the problems below, a single sentence or two is enough to answer the question.

1. If we want $A$ to serve as a valid matrix for encryption, what must we require about $A$? One sentence is fine.
2. If $A\in \text{GL}(2,\mathbb{Z}_5)$, show that $A^{-1}\in \text{GL}(2,\mathbb{Z}_5)$.
3. If $A\in \text{GL}(2,\mathbb{Z}_5)$ and $B\in \text{GL}(2,\mathbb{Z}_5)$, why is $AB\in \text{GL}(2,\mathbb{Z}_5)$?
4. Prove that if we know for some integer $k$ that $A_1,A_2,A_3,\ldots,A_k \in \text{GL}(2,\mathbb{Z}_5)$, then we know $A_1A_2A_3\cdots A_k\in \text{GL}(2,\mathbb{Z}_5)$.
5. Is $\text{GL}(2,\mathbb{Z}_5)$ a group? (Which of the group properties did we not show above? Are they true?)
6. Do your arguments above hold when considering $\text{GL}(m,\mathbb{Z}_n)$ for every $m,n \in \mathbb{N}$ such that $n\geq 2$? A conjecture with a reasonable justification (not a complete a proof) is fine in this part.

In the definition of a group, it said that there exists an element $e\in G$ such that $ex=xe=e$ for each $x\in G$. It refers to this element as the identity. Could there be two such elements? Similarly, could an element have two inverses? The next problem has you show that the identity and inverses are unique.

Problem 41 (The Identity And Inverses Are Unique)

Suppose that $(G,\cdot)$ is a group.

1. Prove that the identity of the group is unique.
2. Prove that if $x\in G$, then the inverse of $x$ is unique.

Problem 42 (The GCD Theorem Proof)

Prove the GCD Theorem.

Theorem (The GCD Theorem)

Let $a$ and $b$ be nonzero integers. The greatest common divisor of $a$ and $b$ is an integer linear combination of $a$ and $b$, or symbolically we have $\gcd(a,b)\in\text{span}(a,b)$. In addition, the smallest positive integer linear combination of $a$ and $b$ is $\gcd(a,b)$.

For more problems, see AllProblems