20131009

Please Login to access more options.

Today

There are problems for Wed. The first 4 problems carry over from Monday. I knew that some of the problems you shared on Monday would take some time, so I figured that we would have some carry over. Many of the problems below are quite short.

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 (Inverting Function Composition)

Let $f:A\to B$, $g:B\to C$, and $h:C\to D$ be bijections.

1. Show that the inverse of $g\circ f$ is $f^{-1}\circ g^{-1}$. See the note below if you forgot how to prove something is the inverse.
2. What is the inverse of $h\circ g\circ f$? Remember to justify your claim.

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

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.

Problem 39.5 (Function Composition Is Associative)

Let $f:A\to B$, $g:B\to C$, and $h:C\to D$ be functions. Recall that $g\circ f:A\to C$ is a new function defined by $(g\circ f)(x) = g(f(x))$, i.e. first put $x$ into $f$ to obtain $f(x)$ and then put $f(x)$ into $g$ to obtain $g(f(x))$.

Prove that function composition is associative, i.e. show that $h\circ (g\circ f)=(h\circ g)\circ f$.

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

There are several problems already up for Friday. I'll try to always have a few problems up ahead of time.

For more problems, see AllProblems