Math 441 - Abstract Algebra - Solution - TheSpanOfASetOfPermutationsIsClosedBen

Please Login to access more options.

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

Solution

Let $S$ be a set of permutations. Let's start by recalling some definitions, before we start the proof. Recall that $\beta \in \text{span}(S)$ means that we can write $\beta$ in the form $$\beta = \alpha_1^{k_1}\circ \alpha_2^{k_2}\circ\cdots \circ\alpha_n^{k_n}$$ for some $n\in\mathbb{N}$, where $\alpha_1,\alpha_2,\ldots,\alpha_n\in S$ and $k_1,k_2,\ldots,k_n\in \mathbb{Z}$. In other words, we can write $\beta$ as composition of elements of $S$, raised to powers. On the other hand, notice that $\gamma\in \text{span}(\text{span}(S))$ means that we can write $\gamma$ in the form $$\gamma = \beta_1^{j_1}\circ \beta_2^{j_2}\circ\cdots \circ\beta_m^{j_m}$$ for some $m\in\mathbb{N}$, where $\beta_1,\beta_2,\ldots,\beta_m\in \text{span}(S)$ and $j_1,j_2,\ldots,j_m\in \mathbb{Z}$. In other words, we can write $\gamma$ a composition of elements of $\text{span}(S)$, raised to powers. For simplicity, we'll use the letter $\beta$ throughout the rest of this proof when we are referring to elements of $\text{span}(S)$, and we'll use $\alpha$ to refer to elements of the original set $S$.

We need to prove that $\text{span}(S)= \text{span}(\text{span}(S))$. Since these are both sets, we must prove that $\text{span}(S)\subseteq \text{span}(\text{span}(S))$ and $\text{span}(\text{span}(S))\subseteq \text{span}(S)$. The first fact is quite simple to prove. Suppose $\beta\in \text{span}(S)$. Then notice that $\beta=\beta^1$ is an element of $\text{span}(\text{span}(S))$, as it is a composition of elements of $\text{span}(S)$, raised to powers. This completes the proof that $\text{span}(S)\subseteq \text{span}(\text{span}(S))$.

We now prove $\text{span}(\text{span}(S))\subseteq \text{span}(S).$ Let $\gamma\in \text{span}(\text{span}(S))$. This means that $$\gamma = \beta_1^{j_1}\circ \beta_2^{j_2}\circ\cdots \circ\beta_m^{j_m}$$ for some $m\in\mathbb{N}$, where $\beta_1,\beta_2,\ldots,\beta_m\in \text{span}(S)$ and $j_1,j_2,\ldots,j_m\in \mathbb{Z}$. The key here is to notice that $\beta_1,\beta_2,\ldots,\beta_m\in \text{span}(S)$. Since we know $\beta_1\in \text{span}(S)$, we can write $\beta_1$ as a composition of elements of $S$, raised to powers. The notation here gets quite messy, but basically the fact that $\beta_1\in \text{span}(S)$ means we have $$\beta_1 = \alpha_{1,1}^{k_{1,1}}\circ \alpha_{1,2}^{k_{1,2}}\circ\cdots \circ\alpha_{1,n}^{k_{1,n}}$$ for some $n\in\mathbb{N}$, where $\alpha_{1,1},\alpha_{1,2},\ldots,\alpha_{1,n}\in S$ and $k_{1,1},k_{1,2},\ldots,k_{1,n}\in \mathbb{Z}$. In a similar fashion, we can obtain a similar expression for each $\beta_i$, obtaining $$\beta_i = \alpha_{i,1}^{k_{i,1}}\circ \alpha_{i,2}^{k_{i,2}}\circ\cdots \circ\alpha_{i,n}^{k_{i,n}},$$ where $\alpha_{i,1},\alpha_{i,2},\ldots,\alpha_{i,n}\in S$ and $k_{i,1},k_{i,2},\ldots,k_{i,n}\in \mathbb{Z}$. Note that the same $n$ was used for each $\beta_i$, which might not be true. Inserting some compositions by the identity, as needed, allows us to assume, without loss of generality, that each expression above has the same number of factors $n$.

Now that we've defined all the terms, we just use substitution to compute $$\begin{align} \gamma &= \beta_1^{j_1}\circ \beta_2^{j_2}\circ\cdots \circ\beta_m^{j_m}\\ &=\left(\alpha_{1,1}^{k_{1,1}}\circ \alpha_{1,2}^{k_{1,2}}\circ\cdots \circ\alpha_{1,n}^{k_{1,n}}\right)^{j_1}\circ \left(\alpha_{2,1}^{k_{2,1}}\circ \alpha_{2,2}^{k_{2,2}}\circ\cdots \circ\alpha_{2,n}^{k_{2,n}}\right)^{j_2}\circ \cdots \left(\alpha_{m,1}^{k_{m,1}}\circ \alpha_{m,2}^{k_{m,2}}\circ\cdots \circ\alpha_{m,n}^{k_{m,n}}\right)^{j_m}. \end{align}$$ This almost looks like an element of $\text{span}(S)$. The only thing that remains is to examine what the powers $j_i$ do in this problem. Let's examine $j_1$ first, as the other powers are dealt with in a similar fashion. We will consider three cases, namely $j_1=0$, $j_1>0$, and $j_1<0$. If $j_1=0$, then the expression $\left(\alpha_{1,1}^{k_{1,1}}\circ \alpha_{1,2}^{k_{1,2}}\circ\cdots \circ\alpha_{1,n}^{k_{1,n}}\right)^{j_1}$ is the identity, or alternately $\beta_1^{j_1}=\alpha_{1,1}^0$ (something in $S$ raised to a power). If $j_1>0$, then we know $$\left(\alpha_{1,1}^{k_{1,1}}\circ \alpha_{1,2}^{k_{1,2}}\circ\cdots \circ\alpha_{1,n}^{k_{1,n}}\right)^{j_1} =\underbrace{ \left(\alpha_{1,1}^{k_{1,1}}\circ \alpha_{1,2}^{k_{1,2}}\circ\cdots \circ\alpha_{1,n}^{k_{1,n}}\right)\circ\cdots\circ \left(\alpha_{1,1}^{k_{1,1}}\circ \alpha_{1,2}^{k_{1,2}}\circ\cdots \circ\alpha_{1,n}^{k_{1,n}}\right) }_{\text{repeated $j_1$ times}}.$$ If $j_1<0$, first note that the inverse of a composition is the composition of the inverses, written in reverse order. This means that $$\left(\alpha_{1,1}^{k_{1,1}}\circ \alpha_{1,2}^{k_{1,2}}\circ\cdots \circ\alpha_{1,n}^{k_{1,n}}\right)^{-1} = \alpha_{1,n}^{-k_{1,n}}\circ \cdots\circ \alpha_{1,2}^{-k_{1,2}}\circ \alpha_{1,1}^{-k_{1,1}},$$ which means we have $$\left(\alpha_{1,1}^{k_{1,1}}\circ \alpha_{1,2}^{k_{1,2}}\circ\cdots \circ\alpha_{1,n}^{k_{1,n}}\right)^{j_1} =\underbrace{ \left(\alpha_{1,n}^{-k_{1,n}}\circ \cdots\circ \alpha_{1,2}^{-k_{1,2}}\circ \alpha_{1,1}^{-k_{1,1}}\right)\circ\cdots\circ \left(\alpha_{1,n}^{-k_{1,n}}\circ \cdots\circ \alpha_{1,2}^{-k_{1,2}}\circ \alpha_{1,1}^{-k_{1,1}}\right) }_{\text{repeated $|j_1|$ times}}.$$ In all three cases for $j_1$, notice that we have a composition of elements of $S$, raised to integer powers. Repeat this with $\beta_2$, $\beta_3$, and so on. Once we have completely finished replacing each $\beta_i$ with a composition of elements of $S$, raised to powers, then we will have finally written $\gamma$ as a composition combination of elements in $S$, which shows $\gamma\in \text{span}(S)$. This completes the proof that $\text{span}(\text{span}(S))\subseteq \text{span}(S)$, and so finishes the proof that $\text{span}(\text{span}(S))=\text{span}(S)$. We have shown that $\text{span}(S)$ is closed.

Big View Home Login Edit History Recent Changes
HomePage Current Problems All Problems Pictures ProblemsByWeek List of Problems List of Definitions List of Theorems List of Conjectures All Recent changes (use this to find a page that may have been lost)	Solution The Span Of A Set Of Permutations Is Closed Ben Please Login to access more options. 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$. Solution Let $S$ be a set of permutations. Let's start by recalling some definitions, before we start the proof. Recall that $\beta \in \text{span}(S)$ means that we can write $\beta$ in the form $$\beta = \alpha_1^{k_1}\circ \alpha_2^{k_2}\circ\cdots \circ\alpha_n^{k_n}$$ for some $n\in\mathbb{N}$, where $\alpha_1,\alpha_2,\ldots,\alpha_n\in S$ and $k_1,k_2,\ldots,k_n\in \mathbb{Z}$. In other words, we can write $\beta$ as composition of elements of $S$, raised to powers. On the other hand, notice that $\gamma\in \text{span}(\text{span}(S))$ means that we can write $\gamma$ in the form $$\gamma = \beta_1^{j_1}\circ \beta_2^{j_2}\circ\cdots \circ\beta_m^{j_m}$$ for some $m\in\mathbb{N}$, where $\beta_1,\beta_2,\ldots,\beta_m\in \text{span}(S)$ and $j_1,j_2,\ldots,j_m\in \mathbb{Z}$. In other words, we can write $\gamma$ a composition of elements of $\text{span}(S)$, raised to powers. For simplicity, we'll use the letter $\beta$ throughout the rest of this proof when we are referring to elements of $\text{span}(S)$, and we'll use $\alpha$ to refer to elements of the original set $S$. We need to prove that $\text{span}(S)= \text{span}(\text{span}(S))$. Since these are both sets, we must prove that $\text{span}(S)\subseteq \text{span}(\text{span}(S))$ and $\text{span}(\text{span}(S))\subseteq \text{span}(S)$. The first fact is quite simple to prove. Suppose $\beta\in \text{span}(S)$. Then notice that $\beta=\beta^1$ is an element of $\text{span}(\text{span}(S))$, as it is a composition of elements of $\text{span}(S)$, raised to powers. This completes the proof that $\text{span}(S)\subseteq \text{span}(\text{span}(S))$. We now prove $\text{span}(\text{span}(S))\subseteq \text{span}(S).$ Let $\gamma\in \text{span}(\text{span}(S))$. This means that $$\gamma = \beta_1^{j_1}\circ \beta_2^{j_2}\circ\cdots \circ\beta_m^{j_m}$$ for some $m\in\mathbb{N}$, where $\beta_1,\beta_2,\ldots,\beta_m\in \text{span}(S)$ and $j_1,j_2,\ldots,j_m\in \mathbb{Z}$. The key here is to notice that $\beta_1,\beta_2,\ldots,\beta_m\in \text{span}(S)$. Since we know $\beta_1\in \text{span}(S)$, we can write $\beta_1$ as a composition of elements of $S$, raised to powers. The notation here gets quite messy, but basically the fact that $\beta_1\in \text{span}(S)$ means we have $$\beta_1 = \alpha_{1,1}^{k_{1,1}}\circ \alpha_{1,2}^{k_{1,2}}\circ\cdots \circ\alpha_{1,n}^{k_{1,n}}$$ for some $n\in\mathbb{N}$, where $\alpha_{1,1},\alpha_{1,2},\ldots,\alpha_{1,n}\in S$ and $k_{1,1},k_{1,2},\ldots,k_{1,n}\in \mathbb{Z}$. In a similar fashion, we can obtain a similar expression for each $\beta_i$, obtaining $$\beta_i = \alpha_{i,1}^{k_{i,1}}\circ \alpha_{i,2}^{k_{i,2}}\circ\cdots \circ\alpha_{i,n}^{k_{i,n}},$$ where $\alpha_{i,1},\alpha_{i,2},\ldots,\alpha_{i,n}\in S$ and $k_{i,1},k_{i,2},\ldots,k_{i,n}\in \mathbb{Z}$. Note that the same $n$ was used for each $\beta_i$, which might not be true. Inserting some compositions by the identity, as needed, allows us to assume, without loss of generality, that each expression above has the same number of factors $n$. Now that we've defined all the terms, we just use substitution to compute $$\begin{align} \gamma &= \beta_1^{j_1}\circ \beta_2^{j_2}\circ\cdots \circ\beta_m^{j_m}\\ &=\left(\alpha_{1,1}^{k_{1,1}}\circ \alpha_{1,2}^{k_{1,2}}\circ\cdots \circ\alpha_{1,n}^{k_{1,n}}\right)^{j_1}\circ \left(\alpha_{2,1}^{k_{2,1}}\circ \alpha_{2,2}^{k_{2,2}}\circ\cdots \circ\alpha_{2,n}^{k_{2,n}}\right)^{j_2}\circ \cdots \left(\alpha_{m,1}^{k_{m,1}}\circ \alpha_{m,2}^{k_{m,2}}\circ\cdots \circ\alpha_{m,n}^{k_{m,n}}\right)^{j_m}. \end{align}$$ This almost looks like an element of $\text{span}(S)$. The only thing that remains is to examine what the powers $j_i$ do in this problem. Let's examine $j_1$ first, as the other powers are dealt with in a similar fashion. We will consider three cases, namely $j_1=0$, $j_1>0$, and $j_1<0$. If $j_1=0$, then the expression $\left(\alpha_{1,1}^{k_{1,1}}\circ \alpha_{1,2}^{k_{1,2}}\circ\cdots \circ\alpha_{1,n}^{k_{1,n}}\right)^{j_1}$ is the identity, or alternately $\beta_1^{j_1}=\alpha_{1,1}^0$ (something in $S$ raised to a power). If $j_1>0$, then we know $$\left(\alpha_{1,1}^{k_{1,1}}\circ \alpha_{1,2}^{k_{1,2}}\circ\cdots \circ\alpha_{1,n}^{k_{1,n}}\right)^{j_1} =\underbrace{ \left(\alpha_{1,1}^{k_{1,1}}\circ \alpha_{1,2}^{k_{1,2}}\circ\cdots \circ\alpha_{1,n}^{k_{1,n}}\right)\circ\cdots\circ \left(\alpha_{1,1}^{k_{1,1}}\circ \alpha_{1,2}^{k_{1,2}}\circ\cdots \circ\alpha_{1,n}^{k_{1,n}}\right) }_{\text{repeated $j_1$ times}}.$$ If $j_1<0$, first note that the inverse of a composition is the composition of the inverses, written in reverse order. This means that $$\left(\alpha_{1,1}^{k_{1,1}}\circ \alpha_{1,2}^{k_{1,2}}\circ\cdots \circ\alpha_{1,n}^{k_{1,n}}\right)^{-1} = \alpha_{1,n}^{-k_{1,n}}\circ \cdots\circ \alpha_{1,2}^{-k_{1,2}}\circ \alpha_{1,1}^{-k_{1,1}},$$ which means we have $$\left(\alpha_{1,1}^{k_{1,1}}\circ \alpha_{1,2}^{k_{1,2}}\circ\cdots \circ\alpha_{1,n}^{k_{1,n}}\right)^{j_1} =\underbrace{ \left(\alpha_{1,n}^{-k_{1,n}}\circ \cdots\circ \alpha_{1,2}^{-k_{1,2}}\circ \alpha_{1,1}^{-k_{1,1}}\right)\circ\cdots\circ \left(\alpha_{1,n}^{-k_{1,n}}\circ \cdots\circ \alpha_{1,2}^{-k_{1,2}}\circ \alpha_{1,1}^{-k_{1,1}}\right) }_{\text{repeated $\|j_1\|$ times}}.$$ In all three cases for $j_1$, notice that we have a composition of elements of $S$, raised to integer powers. Repeat this with $\beta_2$, $\beta_3$, and so on. Once we have completely finished replacing each $\beta_i$ with a composition of elements of $S$, raised to powers, then we will have finally written $\gamma$ as a composition combination of elements in $S$, which shows $\gamma\in \text{span}(S)$. This completes the proof that $\text{span}(\text{span}(S))\subseteq \text{span}(S)$, and so finishes the proof that $\text{span}(\text{span}(S))=\text{span}(S)$. We have shown that $\text{span}(S)$ is closed. Tags Change these as needed. Week4 Ben Complete When you are ready to submit this written work for grading, add the phrase [[!Submit]] to your page. This will tell me that you have completed the page (it's past rough draft form, and you believe it is in final draft form). Don't type [[!Submit]] on a rough draft. If I put [[!NeedsWork]] on your page, then your job is to review what I've written, address any comments made, and then delete all the comments I made. When you have finished reviewing your work, leave [[!NeedsWork]] on your page and type [[!Submit]]. (Both tags will show up). This tells me you have addressed the comments. I'll mark your work with [[!Complete]] after you have made appropriate revisions. Edit Page History Source Attach File Backlinks List Group Page last modified on October 14, 2018, at 02:56 AM
skin config pmwiki-2.2.142

The Span Of A Set Of Permutations Is Closed Ben

Problem 24 (The Span Of A Set Of Permutations Is Closed)

Solution

Tags