Please Login to access more options.
|
Sun |
Mon |
Tue |
Wed |
Thu |
Fri |
Sat |
Here's what we'll do today.
- Split into small groups immediately.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
| Front | Caley | Carla | Megan | Caley | Justin | Carla | |
| Left | Tim | Cassie | Bryce | Bryce | Nick | Laura | |
| Back | Lilia | Kimberly | Joe | Alexander | Lilia | Alexander | |
| Right | Terry | Li | Brennan | Li | Brennan | Kinsey |
- Rapidly share what you did on #1. Show how you got your inverse for $n=10$ and $n=11$. Then move on. (Five min tops)
- Present #3. You only need to show the last 2 parts. (Five min tops)
- Present #6. You only need to show the last part. (Five min tops)
- Present #2. Draw the Cayley graphs. (10 min)
- Present #5. Make sure you write sentences, and if you make a claim, justify it. (10 min)
- Half of the groups will present 4, half will present 7. (15 min)
- We'll end class with a discussion of these. (10 min)
The first few problems we will work on are carry overs from Wednesday. Here they are:
Problem 28 (Computing Multiplicative Inverses For Small N)
To use modular arithmetic in matrix encryption, we must be able to find the modular multiplicative inverse of $a \mod n$. For each $n\leq 13$ and $a\in \mathbb{Z}_n$, we now compute the inverse of $a\mod n$ or explain why it does not have one.
- Why does $0\mod n$ never have an inverse?
- What is the multiplicative inverse of $1\mod n$?
- For $n=3$, what is the multiplicative inverse of $a=2$.
- For $n=4$, show that 2 does not have an inverse by computing $2\cdot 0$, $2\cdot 1$, $2\cdot 2$, and $2\cdot 3$ all modulo $4$. What is $3^{-1}\mod 4$?
- For each $n$ between 5 and 13, create a table that shows the inverse of each $a\in \mathbb{Z}_n$. List the elements of $\mathbb{Z}_n$ along the top row, and beneath each element list the multiplicative inverse, or cross off the number if there is no multiplicative inverse.
When you are done you should have a list of the elements of $U(n)$ for each $n$ up to 13, as well as the inverse of each element in $U(n)$. Do you see any patterns?
For $n=9$, you should obtain a table somewhat similar to the following table.
| $a$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| $a^{-1}$ | x | 1 | 5 | x | 7 | 2 | x | 4 | 8 |
If $X$ is a set, and $S$ is a set of permutations of $X$, then we can create a Caley graph for the span of $S$. Here's a formal definition.
Definition (Cayley Graph Of A Span Of Permutations)
Let $X$ be a set. Let $S$ be a set of permutations of $X$. Then a Cayley graph of $H=\text{span} (S)$ generated by $S$, which we'll write as $(H,S)$, is a colored directed graph that satisfies the the following three properties:
- The vertex set is $\text{span} (S)$. Each vertex corresponds to a permutation.
- Each element $s \in S$ is assigned a unique color which we'll denote by $c_s$.
- For each color $c_s$, and each vertex $\sigma$, we draw the colored arrow $(\sigma ,s \circ \sigma)$.
Most of the time we assume that $S$ does not contain the identity. However, if it does contain the identity, then we just draw a colored loop $(\sigma,\sigma)$ at each vertex.
We've done this with several automorphism groups of graphs, as well as simple shift permutation groups.
Problem 30 (Cayley Graphs Of Two Automorphism Groups)
Consider the two graphs below. Let $L$ be the automorphism group of the graph on the left, and let $R$ be the automorphism group of the graph on the right.
We listed the automorphisms of the graph in Problem (Automorphisms On Several Graphs With 4 Vertices).
- For the graph on the left, use disjoint cycle notation to state two automorphisms $\alpha,\beta\in L$ so that $\text{span}(\{\alpha,\beta\})=L$. Then draw the Cayley graph of $L$ generated by $\{\alpha,\beta\}$, i.e. the Cayley graph $(L,\{\alpha,\beta\})$.
- For the graph on the right, use disjoint cycle notation to state two automorphisms $\alpha,\beta\in R$ so that $\text{span}(\{\alpha,\beta\})=R$. Then draw the Cayley graph of $R$ generated by $\{\alpha,\beta\}$, i.e. the Cayley graph $(R,\{\alpha,\beta\})$.
If $X$ is a set, and $S$ is a set of permutations of $X$, then we already know how to create the span of $S$. In general, the span of $S$ will include more permutations than what we started with. However, sometimes we won't be able to obtain any new permutations by spanning $S$. When this happens, we say that the set of permutations is closed (under function composition). Here's a formal defintion.
Definition (A Closed Set Of Permutations)
We say that a set of permutations is closed if the set $S$ is equal to its span, so notionally we write $$S=\text{span}{(S)}.$$ In other words, we say that $S$ is closed if the set $S$ already contains every composition combination of permutations of elements in $S$.
The next problem has you prove some relationships between a set of permutations $S$ and its span.
Problem 32 (Relationship Between S And Its Span)
Let $S$ be a set of permutations of $X$.
- Prove that $S\subseteq \text{span}(S)$. In other words, we know that $S$ is always contained in its span; the span might be larger.
- Prove that if $\text{span}(S)\subseteq S$, then $S$ is closed.
- If $T\subseteq S$, then show that $\text{span}(T)\subseteq\text{span}(S)$.
To show that $S\subseteq \text{span}(S)$ we must show that if $\sigma\in S$, then we have $\sigma\in \text{span}(S)$. So let $\sigma\in S$. The definition of span is $$\text{span}(S)=\{\sigma_1^{n_1}\circ \sigma_2^{n_2}\circ \cdots \circ \sigma_k^{n_k}\mid k\in \mathbb{N}, \text{ with } \sigma_i\in S \text{ and } n_i\in \mathbb{Z} \text{ for } i\in \{1,2,\ldots,k\}\ \}.$$ We need to show that we can pick a $k$ and then some values of $\sigma_i\in S$ and $n_i\in \mathbb{Z}$ so that $$\sigma= \sigma_1^{n_1}\circ \sigma_2^{n_2}\circ \cdots \circ \sigma_k^{n_k}.$$ If we let $k=1$, and we let $\sigma_1=\sigma$ and we let $n_1=1$, then we have $$\sigma= \sigma^{1}.$$ This shows that we can write $\sigma$ as a permutation combination of permutations in $S$, and hence $\sigma\in \text{span}(S)$. Because we've show that if $\sigma\in S$, then we have $\sigma\in \text{span}(S)$, this means that $S\subseteq \text{span}(S)$.
In linear algebra, we looked at collections of vectors, and then spanned them to obtain vector spaces. Every vector space was the span of a collection of vectors. Every vector in the vector space could be written as a linear combination of the vectors used to span the span. In addition, a vector space is closed under linear combinations. This means that span of a vector space is itself. We've defined the exact same structure, but now with permutations of $X$. The next problem asks you to show that the span of a set of permutations is closed.
Problem 24 (The Span Of A Set Of Permutations Is Closed)
Let $S$ be a set of permutations of $X$. Show that $\text{span}(S)$ is closed. In other words, show that once you form the span of a set $S$ of permutations of $X$, you cannot obtain any new permutations by spanning the span. For this reason, we'll often refer to $\text{span}(S)$ as the closure of $S$.
Hint: You might want to let $H=\text{span}(S)$. We then need to show that $H=\text{span}(H)$, or that $\text{span}(S) = \text{span}(H)$. From the previous problem we already know that $H\subseteq \text{span}(H)$. We just need to show that $\text{span}(H)\subseteq \text{span}(S)$. So we need to show if $\sigma\in \text{span}(H)$ (it's a permutation combination of elements in $H$ namely $$\sigma = \sigma_1^{n_1}\circ \sigma_2^{n_2}\circ \cdots \circ \sigma_k^{n_k}$$ where $k\in \mathbb{N}$ with $\sigma_i\in H$ and $n_i\in \mathbb{Z}$ for $i\in \{1,2,\ldots,k\}$), then we must have $\sigma\in \text{span}(S)$ (it's a permutation combination of elements in $S$). Can you explain why each $\sigma_i$ above can be written as a permutation combination of elements in $S$?
Definition (Integer Linear Combination Of Integers)
Let $a_1, a_2, \ldots, a_k$ be $k$ integers.
- An integer linear combination of these integers is an expression of the form $$c_1a_1+c_2 a_2+ \cdots+c_k a_k$$ where each coefficient $c_i$ is an integer.
- The span of the set of integers $\{a_1, a_2, \ldots, a_k\}$ is the set of all possible integer linear combinations of these integers, namely $$\text{span}(\{a_1, a_2, \ldots, a_k\})=\text{span}(a_1, a_2, \ldots, a_k)=\{c_1a_1+c_2 a_2+ \cdots+c_k a_k\mid c_i\in \mathbb{Z} \text{ for }1\leq i\leq k\}.$$ For ease of notation, we'll often leave off the set notation when spanning a set of integers.
- If the set $S$ of integers is infinite, then we still define the span of $S$ to be the set of all integer linear combinations of integers in $S$. Hence we know $x\in S$ if and only if there exists a natural number $k$ such that $x=c_1a_1+c_2 a_2+ \cdots+c_k a_k$ where $a_i\in S$ and $c_i\in \mathbb{Z}$ for $1\leq i\leq k$.
- When there are only two integers, we'll often use $a$ and $b$ as the integers, and $s$ and $t$ as the coefficients. So the set of all integer linear combinations of $a$ and $b$ is $$\text{span}(a,b) = \{sa+tb\mid s,t\in\mathbb{Z}\}.$$
Problem 33 (Integer Linear Combination Practice)
Complete the following.
- Compute the span of $3$, i.e. make a list of the elements in this set. In general, what is the span of a single integer $a$? (We know it by a different name.)
- What is $\text{span}(4,6)$? List the elements. Find a single number $a$ so that $\text{span}(a)=\text{span}(4,6)$.
- What is $\text{span}(4,5)$?
- Let $S=\{a_1,a_2,\ldots,a_k\}$ be a set of integers. Show that if $c\in \text{span}(S)$, then so is every multiple of $c$.
We've seen a lot of relationships in class about modular arithmetic, inverses mod n, simple shift encryption schemes, and more. The next problem makes a connection between some of these. We'll connect it to even more next time.
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.
- The integer $a$ has a multiplicative inverse mod $n$
- We have $1\in \text{span}(a,n)$. In other words, we can write 1 as a linear combination of $a$ and $n$.
- 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.
We've seen two parts of this in class. The only part left is to show that (3) implies (1). So if $\text{span}(S)=\mathbb{Z}$, show that $a$ has a modular multiplicative inverse. We'll finish this up in small groups.
Problem 15(Division Algorithm Proof)
Prove the Division algorithm.
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:
- 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)$.
- 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$.)
- 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$.)
For more problems, see AllProblems