20161007

Please Login to access more options.

Today

Problem 34 (When Does An Integer Have A Modular Multiplicative Inverse)

Let $a$ and $n$ be integers, with $n>1$. Show that the following are equivalent.

1. The integer $a$ has a multiplicative inverse mod $n$
2. We have $1\in \text{span}(a,n)$. In other words, we can write 1 as a linear combination of $a$ and $n$.
3. We have $\text{span}(a,n)=\mathbb{Z}$. Remember that $\text{span}(a,n) = \{sa+tn\mid s,t\in\mathbb{Z}\}.$

Remember, to show that three things are equivalent you must show that each implies the other. One way to do this is show that 1 implies 2, then show that 2 implies 3, and then show that 3 implies 1. Then each implies the other.

The two problems above, together with much of our work from the previous weeks, leads us to one of the biggest theorems in number theory. We'll prove this theorem later in the semester.

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)$.

Corollary (When Are Two Numbers Relatively Prime)

Two nonzero numbers $a$ and $b$ are relatively prime (i.e. their greatest common divisor is 1) if and only if there exists $s$ and $t$ such that $sa+tb=1$.

Problem 35 (Connecting Multiples And Spans Of Integers)

Suppose that $a$ and $b$ are integers.

1. Prove that if $a$ is a multiple of $b$, then we must have $\text{span}(a)\subseteq\text{span}(b)$.
2. Is the converse of the statement above true or false? Make sure you prove your result.

Problem 36 (Permutations of $U(n)$)

Suppose $n$ is an integer greater than 1 and let $X=U(n)$, so the set of integers mod $n$ that have a multiplicative inverse mod $n$. For each $a\in U(n)$, we can define a permutation of $U(n)$ by $f_a(x)=xa\pmod n$ for each $x\in U(n)$. This problem asks you to show that this is indeed a permutation of $U(n)$. This requires that you show the following:

1. For each integer $n\geq 2$, show that if $a\in U(n)$ and $x\in U(n)$, then the product $f_a(x)=xa\pmod n\in U(n)$. This shows that $f_a:U(n)\to U(n)$ is a map from $U(n)$ to $U(n)$.
2. Given $n\geq 2$ and $a\in U(n)$, show that $f_a$ is one-to-one. (As a reminder, one-to-one means that if $f_a(x)=f_a(y)$, then $x=y$.)
3. Given $n\geq 2$ and $a\in U(n)$, show that $f_a$ is onto. (As a reminder, onto means that if $y\in U(n)$, then there exists $x\in U(n)$ such that $f_a(x)=y$.)

Problem 37 (Three Similar Cayley Graphs From Different Contexts)

This problem asks you to draw 3 Cayley graphs. Each Cayley graph should only have 4 vertices.

1. Draw a Cayley graph for the set $H_4$ of simple shift permutations of $X=\{1,2,3,4\}$ using the generating set $S=\{\phi_1\}$.
2. Then draw a Cayley graph for the span of the permutation $(1,4,3,2)$, which we wrote in disjoint cycle notation.
3. Then draw a Cayley graph for $\{f_a\mid a\in U(5)\}$ using the generating set $S=\{f_2\}$. Remember that $f_a$ is a permutation of $U(5)$ defined by $f_a(x)=xa\pmod 5$.
4. What do you notice about these Cayley graphs?

The three graphs from the previous problem look very similar, so much so that we could obtain one from the other if we just relabeled the vertex sets. This suggests that in some sense these graphs are the same. We now introduce a formal way to talk about when two graphs are the same.

Definition (Isomorphic Graphs)

Let $G$ and $H$ be two graphs, where we use $V(G)$ and $V(H)$ to denote the vertex sets. A function $f:V(G)\to V(H)$ is called an isomorphism of graphs $G$ and $H$ if $f$ is a bijection and $\{x,y\}$ is an edge of $G$ if and only if $\{f(x),f(y)\}$ is an edge of $H$ (see Wikipedia).

• We call this function $f$ an isomorphism because it "preserves the edge structure" in the graph. In general the word isomorphism refers to a bijection that preserves some kind of structure.
• If there exists an isomorphism of graphs between $G$ and $H$, then we say that $G$ and $H$ are isomorphic.
• If $G$ and $H$ are directed graphs, then an isomorphism of directed graphs would preserve the arrow structure.
• If the directed graphs $G$ and $H$ are colored, then an isomorphism also preserves the color structure, in the sense that $(a,b)$ and $(c,d)$ share the same color if and only if $(f(a),f(b))$ and $(f(c),f(d))$ share the same color.

Problem 38 (Introduction To Cayley Graph Isomorphisms)

Let $H_6 = \{\phi_0,\phi_1,\ldots,\phi_5\}$ be the set of simple shift permutations on an alphabet with 6 letters. Let $K=\{f_a\mid a\in U(7)\}$ be the set of permutations $f_a:U(7)\to U(7)$ defined by $f_a(x)=xa\pmod 7$. Let $S_3$ be the set of all permutations on $X=\{1,2,3\}$.

1. Draw the Cayley graph of $H_6$ generated by $\{\phi_1\}$. Then draw the Cayley graph of $K$ generated by $\{f_3\}$. Finally show that the function $g:H_6\to K$ defined by $$ g(\phi_0)=f_1, g(\phi_1)=f_3, g(\phi_2)=f_2, g(\phi_3)=f_6, g(\phi_4)=f_4, g(\phi_5)=f_5, $$ is an isomorphism of Cayley graphs.
2. Draw the Cayley graph of $H_6$ generated by $\{\phi_2, \phi_3\}$. Then draw the Cayley graph of $K$ generated by $\{f_2,f_6\}$. Do you believe these two Cayley graphs are isomorphic? You can just give a heuristic argument, rather than a formal proof.
3. Let $S_3$ be the set of all permutations on $X=\{1,2,3\}$. We've already shown this set has 6 permutations. Draw a Cayley graph of $S_3$ generated by the permutations $(1,2,3)$ and $(1,2)$. Do you think that this Cayley graph is isomorphic to any of the Cayley graphs above? Why?

Just as we defined a set of permutations to be closed under composition combinations of permutations, we can define a set of integers to be closed under integer linear combinations of integers. We'll say that a nonempty set $S$ of integers is closed (under integer linear combinations) if the span of the set $S$ equals the original set $S$, so again we have $S=\text{span}(S)$. The proof of the following fact should be very similar to one you have already shown.

Problem 39 (The Span Of A Set Of Integers Is Closed)

Let $S$ be a nonempty set of integers. Prove that $\text{span}(S)$ is closed under integer linear combinations.

Let's now return to permutations. The following problem has you show that a closed set of permutations has 4 properties. Later, we'll show that any set of permutations with these 4 properties is a closed set of permutations. Once we've shown this, we'll have characterized exactly what it means to be a closed set of permutations. From this characterization we'll define what it means to be a "group."

Problem 40 (Properties Of Closed Sets Of Permutations)

Let $H$ be a nonempty closed set of permutations of a set $X$.

1. Show that the identity function $id_X$ is in $H$.
2. Show that if $\sigma\in H$, then so is $\sigma^{-1}$.
3. Show that if $\alpha\in H$ and $\beta\in H$, then $\alpha\circ \beta\in H$.
4. Show that if $\alpha,\beta,\gamma\in H$, then $\alpha\circ (\beta\circ \gamma) = (\alpha\circ \beta)\circ \gamma$.

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 $\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 permutations) when the set contains any composition combination of permutations in 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.

For more problems, see AllProblems