Please Login to access more options.
|
Sun |
Mon |
Tue |
Wed |
Thu |
Fri |
Sat |
In class, we'll start with a few presentations.
- Br. Woodruff's "What is inquiry based learning."
- Nick will present number 5 from Wed.
- Alexander will present number 5 from Wed.
- Brennan's will present number 1.
- Joe will present number 2.
- Problem 3's answer is "welldone." We just have to find the inverse matrix. Brief discussion.
- Let's play the games on 4 and 5 as a class.
- Then we'll discuss the new problems.
Problem 8 (Automorphisms Of A Directed Square)
Consider the directed graph $\mathcal{G} = (V,A)$ shown below with vertex set $V = \{1,2,3,4\}$ and arrows (directed edges) $$A = \{(1,2),(2,3),(3,4),(4,1)\}.$$
- How would you define an automorphism of a directed graph?
- List all the automorphisms of this directed graph. You should have 4.
- Is there is an automorphism $a\in \aut(\mathcal{G})$ such that $a^2=a\circ a$ (the composition) is the identity automorphism, but $a$ is not the identity?
- Is there is an $a\in \aut(\mathcal{G})$ such that $a^3=a\circ a\circ a$ is the identity but $a$ is not the identity?
- Is there is an $a\in \aut(\mathcal{G})$ such that every other $b\in \aut(\mathcal{G})$ is of the form $b=a^n$ for some $n$?
- For every $a,b\in \aut(\mathcal{G})$, do we have $a\circ b = b\circ a$?
Please work on the next problem again. I would like you to come to class with a written proof that uses induction. Here's a different problem, but the proof technique is related.
Example
Provide a proof of the following claim.
- Claim: For every positive integer $n$, the sum of $n$ differentiable functions is differentiable.
Proof: We proceed by induction. We know that if $f_1$ is differentiable, then the sum $f_1$ is differentiable (this is the base case). If you are not happy with this base case, then we also know that if $f_1$ and $f_2$ are differentiable functions, then $f_1+f_2$ is a differentiable function (something we proved in first semester calculus). So we have shown that the claim is true if $n=1$ or $n=2$.
We now assume that the statement is true when $n=k$. So we know that if we have $n$ differentiable functions, then their sum is differentiable. We need to show that if $g_1, g_2, \ldots g_k,g_{k+1}$ are $k+1$ differentiable functions, then their sum $$s=g_1+g_2+\cdots+g_{n-1}+g_n+g_{n-1}$$ is differentiable. If we let $h_i=g_i$ for each $i$ between 1 and $k-1$, and then we combine the last two functions to give use $h_k=g_k+g_{k+1}$, then we have $k$ functions $h_1, h_2, \ldots h_k$ that are all differentiable. The last function $h_k$ is differentiable because it is the sum of two differentiable functions. So we now have $$ \begin{align*} s&=g_1+g_2+\cdots+g_{k-1}+(g_k+g_{k-1})\\ &h_1+h_2+\cdots+h_{k-1}+(h_k). \end{align*} $$ Since $s$ is the sum of $k$ differentiable functions, our induction assumption tells us it is differentiable. This shows that the sum of $k+1$ differentiable functions is differentiable.
We've now shown that if the claim is true for $n=k$, then the claim is true for $n=k+1$. By the principle of mathematical induction, our claim is true for each positive integer $n$.
Theorem (The Composition Of Permutations Is A Permutation)
Let $X$ be a set. Suppose that $\sigma_1, \sigma_2, \ldots,\sigma_k$ are permutations of $X$. Then the composition $\sigma_1\circ \sigma_2\circ \ldots\circ \sigma_k$ is a permutation of $X$.
Problem 11 (The Composition Of Permutations Is A Permutation)
Prove theorem (The Composition Of Permutations Is A Permutation). As some reminders, you may use the following facts that you proved in either Math 301 or Math 340. You may use these facts without proof.
- The composition of two injective functions is injective.
- The composition of two surjective functions is surjective.
- A function is a bijection if it is both injective (1 to 1) and surjective (onto). Hence, the composition of two bijective functions is a bijection.
- You might find induction helps you get from a composition of two bijective functions is bijective to the composition of $n$ bijective functions is bijective.
Problem 12 (Simple Matrix Encryption)
Consider the matrix $A = \begin{bmatrix} 2&1&-1\\ 5&2&-3\\ 0&2&1\end{bmatrix}$. Joe decides to send a message to Sam by encrypting the message with the matrix $A$. He first takes his message and converts it to numbers by replacing A with 1, B with 2, C with 3, and so on till replacing Z with 26. He uses a 0 for spaces. After replacing the letters with numbers, he breaks the message up into chunks of 3 letters. He then multiplies each chunk of 3 by the matrix $A$, resulting in a coded message. For example, to send the message "good job ben" he firsts converts the letters to the numbers and places them in a large matrix $M$ (top to bottom, left to right) $$ \left[ \begin{bmatrix}g\\o\\o\end{bmatrix}, \begin{bmatrix}d\\ \ \\ j\end{bmatrix},\begin{bmatrix}o\\b\\\ \end{bmatrix},\begin{bmatrix}b\\e\\n\end{bmatrix}\right] \rightarrow \left[\begin{bmatrix}7\\15\\15\end{bmatrix}, \begin{bmatrix}4\\0\\10\end{bmatrix},\begin{bmatrix}15\\2\\0\end{bmatrix},\begin{bmatrix}2\\5\\14\end{bmatrix}\right] = M= \begin{bmatrix} 7 & 4 & 15 & 2 \\ 15 & 0 & 2 & 5 \\ 15 & 10 & 0 & 14 \end{bmatrix} .$$ To encode the matrix, he computes $$AM = \begin{bmatrix} 14 & -2 & 32 & -5 \\ 20 & -10 & 79 & -22 \\ 45 & 10 & 4 & 24 \end{bmatrix}.$$ and then sends the numbers \([ [ 14, 20, 45], [ -2, -10, 10], [ 32, 79, 4], [ -5, -22, 24] ]\) to Sam. Sam uses the inverse of $A$ to decode the message.
- Use $A^{-1}$ to decode \([ [ 14, 20, 45],[ -2, -10, 10],[ 32, 79, 4],[ -5, -22, 24] ]\) and show the message is "good job ben."
- Decode the message \([[39, 89, 22],[20, 48, 4],[39, 88, 33]]\).
In linear algebra we took a small set of vectors and spanned the vectors to create vector spaces. The span of a set of vectors is the set of all linear combinations of the vectors. Recall that given a set of vectors $S=\{\vec v_1, \vec v_2,\ldots, \vec v_k\}$, a linear combination of these vectors was a sum of the form $$c_1\vec v_1+c_2\vec v_2+\cdots+c_k\vec v_k.$$ We defined the span of $S$ to be the set of all linear combinations of vectors in $S$.
Given a permutation, we've shown that we can use function composition to create new permutations. If $S$ is a set of permutations on $X$, we'd like to have a way to talk about combining the permutations. Instead of multiply by a scalar and adding, we'll decide how many times to repeated apply the function, and then compose different functions together.
Definition (Composition Combination Of Permutations)
Let $X$ be a set, and $S$ be a set of permutations of $X$.
- If $\sigma$ is a permutation of $X$, we'll use exponential notation to express repeated composition of $\sigma$. This gives us $\sigma^2=\sigma\circ \sigma$ and $\sigma^5=\sigma\circ\sigma\circ\sigma\circ\sigma\circ\sigma$, etc.
- We'll use negative exponents when we want to repeated apply an inverse, which gives us $\sigma^{-n}=\left(\sigma^{-1}\right)^n$.
- A composition combination of permutations in $S$ is a composition of the form $$\sigma_1^{n_1}\circ\sigma_2^{n_2}\circ\cdots\circ \sigma_k^{n_k},$$ where $k\in\mathbb{N}$, each $\sigma_i\in S$, and each $n_i\in \mathbb{Z}$ for $i\in \{1,2,3,\ldots,k\}$.
- The span of $S$, written $\text{span}(S)$ is the set of all composition combinations of permutations in $S$. We'll say that the set $S$ generates $\text{span}(S)$.
As an example, if $S=\{a,b,c,d\}$ is a set of permutations of $X$, then the composition $a^2\circ b^{-1}\circ c^3$ is a composition combination of permutations in $S$, and so are $d^{-3}$, $b^5\circ a^{-2}$, and more.
Problem 13 (Simple Shift Repetition Game)
Consider the set of simple shift permutations $H=\{\phi_n\mid n\in \mathbb{Z}\}$ on a 26 letter alphabet. We've shown that there are 26 different functions in this set. Consider the following game.
- The first player picks an element $\sigma_1\in H$. They then remove from $H$ the span of $\sigma_1$ (so everything generated by $\{\sigma_1\}$).
- The second player now chooses an element $\sigma_2\in H$ that hasn't yet been removed. They then remove from $H$ any element in the span of $\{\sigma_1,\sigma_2\}$. At this stage, any permutation that can be written as a composition combination of the permutations $\sigma_1$ and $\sigma_2$ has been removed.
- Players alternate taking turns, choosing an element $\sigma_k\in H$ that hasn't been removed in a previous stage, and then removing from $H$ any element in the span of $\{\sigma_1,\sigma_2,\ldots,\sigma_k\}$.
- Whoever take the last element of $H$ wins. The game can also be played as a misere game.
Answer the following questions.
- Player 1 takes $\phi_6$. Which elements should be removed from $H$
- Is there a way for player 1 to win on the first move? Explain.
- What's the largest number of turns that can occur in this game (so if neither player tries to win, how long can the game go on)?
- If we play this as a misere game, does player 1 have a winning strategy?
Problem 14(The Span Of A Simple Shift)
Suppose that our alphabet $S$ consists of only 12 letters $S=\{a,b,c,d,e,f,g,h,i,j,k,l\}$. Let $H_{12}=\{\phi_n\mid n\in \mathbb{Z}\}$ be the set of simple shift permutations on this 12 letter alphabet (we wrap around from $l$ to $a$).
- For each $n\in \{0,1,2,\ldots,11\}$, list the elements in $\text{span}(\{\phi_n\} ) $.
- For which $n$ does $\text{span}(\{\phi_n\})=H_{12}$.
- Make a conjecture about any patterns you see above and their relation to the size (12) of the alphabet.
- Whenever you make a conjecture, you should always test your conjecture on an example you have not yet considered. Pick another integer $k\neq 12,26$, and look at the set $H_k$ of simple shift permutations of an alphabet consisting of $k$ letters. Then check if your conjecture holds.
Reading Assignment and First Write Up
Start by reading The elements of Style for Proofs. For Monday, please pick one of the problems that we have discussed in class on either Wed or Fri, and write a solution. Use complete sentences and make sure you justify your work. Make sure that you use your own words to give your solutions. The goal of this portion of the course is to help you improve your own personal writing. When you have completed your problem and you are ready to submit it, please type [[!Submit]] (yes it has an exclamation point) at the bottom of the page. This will let me know that it is ready for grading.
For more problems, see AllProblems