pset-3.tex

\documentclass[letterpaper]{article}

\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{hyperref}
\usepackage{geometry}
\usepackage{nth}

% Comment the following lines to use the default Computer Modern font
% instead of the Palatino font provided by the mathpazo package.
% Remove the 'osf' bit if you don't like the old style figures.
\usepackage[T1]{fontenc}
\usepackage[sc,osf]{mathpazo}

\newcommand*{\QED}{\hfill\ensuremath{\square}}%

% Set your name here
\def\name{Problem Set 3}


\geometry{
  body={6.5in, 8.5in},
  left=1.0in,
  top=1.25in
}

% Customize page headers
\pagestyle{myheadings}
\markright{\name}
\thispagestyle{empty}

% Custom section fonts
\usepackage{sectsty}
\sectionfont{\rmfamily\mdseries\Large}
\subsectionfont{\rmfamily\mdseries\itshape\large}

% Other possible font commands include:
% \ttfamily for teletype,
% \sffamily for sans serif,
% \bfseries for bold,
% \scshape for small caps,
% \normalsize, \large, \Large, \LARGE sizes.

% Don't indent paragraphs.
\setlength\parindent{0em}

\begin{document}

{\huge \name}

% Alternatively, print name centered and bold:
%\centerline{\huge \bf \name}

\vspace{0.25in}

Dev Dabke \\
MATH 501: Introduction to Algebraic Structures I \\
September 20, 2016 \\
Prof.\ Calderbank \\

\section{Question 1}
\label{sec:Question1}

\subsection{Part i}
\label{sub:1Parti}
Denote the conjugate by $ \phi : a \mapsto gxg^{-1} $ for $ g,\,x \in G $.
For $ a,\,b \in G $, $ \phi(a) = gag^{-1} $ and $ \phi(b) = gbg^{-1} $.
Now, we will take $ \phi(ab) $.
We see that $ \phi(ab) = gabg^{-1} $.
Now we take $ \phi(a)\phi(b) = gag^{-1}gbg^{-1} $.
By associativity, $ gag^{-1}gbg^{-1} = ga(g^{-1}g)bg^{-1} $.
By the definition of an inverse, see that $ g^{-1}g = 1 $.
By substitution, $ ga(g^{-1}g)bg^{-1} = ga1bg^{-1} $.
By the definition of the identity $ ga1bg^{-1} = gabg^{-1} $.
Fortunately, $ gabg^{-1} = \phi(ab) $.
Thus, $ \phi(a)\phi(b) = \phi(ab) $.
\QED{}

\subsection{Part ii}
\label{sub:1Partii}

First, let us prove a small result about $ \phi $, in particular that $ \phi(1) = 1 $.
$ \phi(1) = g1g^{-1} $ (by definition of $ \phi $).
Now, by the definition of the identity $ g1g^{-1} = gg^{-1} = 1 $.
Thus, $ \phi(1) = 1 $.
\\ \\
Next we show that by definition of an inverse, $ aa^{-1} = 1 $, and so by the fact that $ \phi(1) = 1 $, we can see that $ \phi(aa^{-1}) = 1 $.
By Question 1, Part i, we see that $ \phi(aa^{-1}) = \phi(a)\phi(a^{-1}) $.
Thus, we combine our statements and see that $ \phi(aa^{-1}) = 1 $ and $ \phi(aa^{-1}) = \phi(a)\phi(a^{-1}) $, and so $ \phi(a)\phi(a^{-1}) = 1 $.
Additionally, since $ a^{-1}a = 1 $, by symmetry, $ \phi(a^{-1})\phi(a) = 1 $.
\\ \\
Finally, since $ \phi(a)\phi(a^{-1}) = 1 $ and $ \phi(a^{-1})\phi(a) = 1 $, we know that $ \phi(a^{-1}) $ is the unique inverse of $ \phi(a) $.
\QED{}

\subsection{Part iii}
\label{sub:1Partiii}

By assumption, $ \forall g \in G, \, gSg^{-1} \subseteq N $.
Thus for $ s_0,\, s_1 \in S $, we see that $ gs_0g^{-1},\, gs_1g^{-1} \in N $.
Since $ N $ is a subgroup and is thus closed over the group operator, $ gs_0g^{-1} gs_1g^{-1} \in N $.
By associativity and the definition of an inverse: $ gs_0g^{-1} gs_1g^{-1} = gs_0(g^{-1} g)s_1g^{-1} = gs_0s_1g^{-1} $.
Thus, we see that conjugates of arbitrary strings of elements in $ S $ also lie in $ N $.
\\ \\
By assumption, $ S $ is a generator for $ N $.
Thus, by the definition of a generator, we know that any element in $ N $ has a representation as an arbitrary string of the elements in $ S $.
Therefore, by the result we proved above, $ \forall n \in N,\, gng^{-1} \in N $.
This means that $ N $ is a normal subgroup of $ G $ by the definition of a normal subgroup.
\QED{}

\subsection{Part iv}
\label{sub:1Partiv}

We will start with the backwards direction.
\\ \\
First, note that by definition of a generator, and in particular a cyclic group, we know that all elements of $ N $ are expressed as arbitrary powers of $ x $.
In short: $ \forall n \in N, \, \exists k \in \mathbb{Z} : n = x^k $.
This follows directly from the definition of a generator and, in particular, a cyclic group.
Therefore, since for each $ g \in G $, $ \exists k \in \mathbb{Z} : gxg^{-1} = x^k $, we know that $ gxg^{-1} \in N $.
Now, define $ S = \{x\} $, i.e.\ let $ S $ be the set that contains only $ x $.
We see that by assumption, $ N $ is generated by $ \langle S \rangle $.
Furthermore, since $ gxg^{-1} \in N $, we immediately see that $ gSg^{-1} \subseteq N \, \forall g \in G $.
Thus, by our result in Part iii of this Question, we have that $ N $ is normal.
\\ \\
Now, we will prove the forwards direction.
\\ \\
By assumption, $ N $ is normal in $ G $.
Thus $ \forall g \in G,\, gxg^{-1} \in N $ by definition of a normal subgroup.
Now, since $ N $ is cyclic with generator $ \langle x \rangle $, we know that all elements in $ N $ must have a representation as an arbitrary power of $ x $.
In short: $ \forall n \in N, \, \exists k \in \mathbb{Z} : n = x^k $.
This follows directly from the definition of a generator and, in particular, a cyclic group.
Thus, since $ gxg^{-1} \in N $, we know that $ \exists k : gng^{-1} = x^k $.
Therefore, we can conclude that if $ N $ is normal in $ G $ given that $ N $ is the cyclic group generated by $ \langle x \rangle $, then for each $ g \in G $, $ gxg^{-1} = x^k $ for some $ k \in \mathbb{Z} $
\\ \\
Since we have proved both directions of this logical equivalence, we can conclude that: if N is the cyclic group $ \langle x \rangle $, then $ N $ is normal in $ G $ if and only if for each $ g \in G $, $ gxg^{-1} = x^k $ for some $ k \in \mathbb{Z} $.
\QED{}

\subsection{Part v}
\label{sub:1Partv}

Let $ n \in N $ (by assumption, $ N = \{x \in G : |x| = m\} $).
We will begin by showing that $ \forall g \in G, \, |gng^{-1}| \leq m $.
\\ \\
First, note that $ {(gng^{-1})}^2 = (gng^{-1}) (gng^{-1}) = gn(g^{-1}g)ng^{-1} = gn^{2}g^{-1} $.
Therefore, more generally, $ {(gng^{-1})}^i = gn^{i}g^{-1} $.
Now, since $ n $ has order $ m $ by assumption, we see that $ gn^{m}g^{-1} = g1g^{-1} = 1 $.
Combining this result with the fact that $ {(gng^{-1})}^i = gn^{i}g^{-1} $, we can conclude that $ {(gng^{-1})}^m = 1 $.
This tells us that $ {(gng^{-1})} $ has order at most $ m $.
\\ \\
Next, we will prove that $ {(gng^{-1})} $ cannot have order less than $ m $, i.e.\ $ {(gng^{-1})} \geq m $.
To show this fact, we will use a proof by contradiction.
Suppose that $ |{(gng^{-1})}| = l < m $, i.e.\ $ {(gng^{-1})} $ has order $ l $ that is \textit{strictly} less than $ m $.
By definition of order, $ {(gng^{-1})}^{l} = 1 $.
By the fact that $ {(gng^{-1})}^i = gn^{i}g^{-1} $, we know that $ {(gng^{-1})}^{l} = gn^{l}g^{-1} = 1 $.
Taking $ gn^{l}g^{-1} = 1 $, we multiply both sides on the left by $ g^{-1} $ and on the right by $ g $ to yield:
$ g^{-1}(gn^{l}g^{-1})g = g^{-1}(1)g $.
Simplifying, we get that $ g^{-1}(gn^{l}g^{-1})g = (g^{-1}g)n^{l}(g^{-1}g) = n^l $ and that $ g^{-1}(1)g = 1 $.
By substitution: $ g^{-1}(gn^{l}g^{-1})g = g^{-1}(1)g $ becomes $ n^l = 1 $.
Thus, we see that $ n $ has order $ l $, which is a contradiction.
Therefore, we know that $ {(gng^{-1})} $ must have order \textit{at least} $ m $.
\\ \\
Since $ |{(gng^{-1})}| \leq m $ and $ |{(gng^{-1})}| \geq m $, we conclude that $ |{(gng^{-1})}| = m $ (by the trichotomy principle).
Since $ N $ is the subgroup of all elements of $ G $ that have order $ m $, we see that $ x \in N \implies gxg^{-1} \in N $.
Therefore, we conclude that $ N $ is normal of $ G $ by definition.
\QED{}

\section{Question 2}
\label{sec:Question2}

To prove this fact, we will note that $ pq $ and $ qp $ are in fact in the same conjugacy class.
In particular, note that $ pq $ conjugated with $ q $ is in fact $ qp $, i.e.\ $ q (pq) q^{-1} = qp (qq^{-1}) = qp $.
Similarly, $ qp $ conjugated with $ p $ is in fact $ pq $, i.e.\ $ p (qp) p^{-1} = pq (pp^{-1}) = pq $.
\\ \\
Conjugation in $ S_N $ is simply relabeling (cf.\ Lecture 6, Slide 7).
In short, we know that the structure of the cycles stays the same, but the actual elements in each cycle could be different.
Therefore, since $ pq $ and $ qp $ are in the same conjugacy class, we know that they must have cycles of equal sizes.

\section{Question 3}
\label{sec:Question3}

First, we will start by showing that we can generate any transposition in the form $ (1k) $, i.e.\ the permutation that swaps elements $ 1 $ and $ k $, but fixes all other elements.
Moreover, this permutation will be generated from the two given permutations (cycles): $ (12 \ldots N) $ and $ (12) $.
\\ \\
Let us start without loss of generality with the set of indices of the elements in a group $ G $ of order $ N $, i.e.\ $ S = \{1, 2, \ldots, N\} $.
Next, if we apply the permutation $ (12 \ldots N) $, the indices are now arranged $ \{N, 1, 2, \ldots, N - 1\} $.
Applying $ (12) $, we achieve $ \{1, N, 2, \ldots, N - 1\} $.
Again, we will apply $ (12 \ldots N) $ and then $ (12) $.
This gives us indices in the order $ \{1, N - 1, N, 2, N - 2\} $.
In short, we see that in general, applying $ (12 \ldots N) $ and then $ (12) $ fixes the first element and simply rotates the elements $ 2 $ through $ N $.
More formally, $ (12)(12 \ldots N) = (1)(2 \ldots N) $.
We can see this algebraically by noting that $ (12 \ldots N) = (12)(13)(14)\ldots(1N) $.
Then, $ (12)(12 \ldots N) = (12)[(12)(13)(14)\ldots(1N)] = (1)(2 \ldots N) $.
\\ \\
Thus, we can apply this permutation $ (1)(2 \ldots N) $ until we have rotated the indices such that $ k $ is immediately to the right of $ 1 $.
Our set of indices looks like $ \{1, k, k + 1, \ldots, N, 2, 3, \ldots, k - 1\} $.
Now, we can apply the $ (12) $ transformation to yield a set of indices that looks like $ \{k, 1, k + 1, \ldots, N, 2, 3, \ldots, k - 1\} $.
We can apply our permutation $ (1)(2 \ldots N) $ again to yield $ \{k, k - 1, 1, k + 1, \ldots, N, 2, 3, \ldots, k - 2 \} $.
In essence, we have put index $ 1 $ in position $ k $ while fixed $ k $.
Similarly, we can keep rotating our set by permutation $ (1)(2 \ldots N) $ until we arrive at $ \{k, 2, 3, \ldots, k - 1, 1, k + 1, \ldots, N\} $.
Thus, as is evident, we have swapped $ 1 $ and $ k $, i.e.\ created the transposition $ (1k) $ from $ (12 \ldots N) $ and $ (12) $.
\\ \\
Next, using some algebra we can generate $ (2l) $ for some index $ l $.
Particularly, $ (1l)(12)(1l) = (2l) $.
Since we have shown how to generate $ (1l) $ from $ (12) $ and $ (12 \ldots N) $, we now know that we can also generate $ (2l) $ from $ (12) $ and $ (12 \ldots N) $.
\\ \\
Now, we can put this all together.
We know that any generic transposition $ (kl) $ can be written $ (kl) = [(1k)(2l)](12)[(1k)(2l)] $ (cf.\ Lecture 5, Slide 6).
Thus, we know that any generic transposition can be generated from $ (12) $ and $ (12 \ldots N) $.
Additionally, since every permutation can be written as the product of disjoint cycles, and since every cycle can be written as the product of transpositions, we know that every permutation can be written as the product of transpositions (cf.\ Lecture 5, Slide 6).
Finally, since every permutation can be written as the product of transpositions, and since we have shown that we can generate any transposition using $ (12) $ and $ (12 \ldots N) $, we know that we can write any permutation using $ (12) $ and $ (12 \ldots N) $.
\\ \\
We will now formally finish the proof.
$ S_N $ is the set of all permutations of groups of $ N $ elements.
Thus, since we can write every permutation of $ N $ elements (some of which may fix an arbitrary number of elements) using the cycles $ (12) $ and $ (12 \ldots N) $, we can conclude that $ S_N $ is generated by $ \langle (12), (12 \ldots N) \rangle $.
\QED{}

\section{Question 4}
\label{sec:Question4}

First, we will prove that the commutator is normal.
To prove this, we need to show that $ g^{-1} x^{-1} y^{-1} x y g $ is also in $ N $.
To begin, we use the fact that $ g^{-1} x^{-1} y^{-1} x y g = g^{-1} x^{-1} 1 y^{-1} 1 x 1 y g $.
Substituting $ 1 = g g^{-1} $, we yield $ g^{-1} x^{-1} 1 y^{-1} 1 x 1 y g = g^{-1} x^{-1} (g g^{-1}) y^{-1} (g g^{-1}) x (g g^{-1}) y g $.
By associativity, $ g^{-1} x^{-1} (g g^{-1}) y^{-1} (g g^{-1}) x (g g^{-1}) y g = (g^{-1} x^{-1} g) (g^{-1} y^{-1} g) (g^{-1} x g) (g^{-1} y g) $.
Now, where $ w = (g^{-1} x g) $ and $ z = (g^{-1} y g) $, $ w^{-1} = (g^{-1} x^{-1} g) $ and $ z^{-1} = (g^{-1} y^{-1} g) $.
Thus, $ (g^{-1} x^{-1} g) (g^{-1} y^{-1} g) (g^{-1} x g) (g^{-1} y g) = w^{-1} z^{-1} w z $.
Therefore, we see that $ (g^{-1} x^{-1} g) (g^{-1} y^{-1} g) (g^{-1} x g) (g^{-1} y g) \in N $.
By that fact and the equality
$$ g^{-1} x^{-1} y^{-1} x y g = (g^{-1} x^{-1} g) (g^{-1} y^{-1} g) (g^{-1} x g) (g^{-1} y g) $$
we can conclude that $ g^{-1} x^{-1} y^{-1} x y g \in N $.
Thus, by definition, $ N $ is a normal subgroup of $ G $.
\QED{}
\\ \\
Next, we will prove that the quotient group $ G / N $ is abelian.
By definition of a quotient group, $ (aN)(bN) = abN $.
Now, $ G / N $ being abelian can be expressed as $ (aN)(bN) = (bN)(aN) $.
We can show three logically equivalent statements:
$$ (aN)(bN) = (bN)(aN) \iff abN = baN \iff a^{-1}b^{-1}abN = N $$
$ (aN)(bN) = (bN)(aN) \iff abN = baN $ is true by definition of the group operator of a quotient group.
$ abN = baN \iff a^{-1}b^{-1}abN = N $ follows directly from the fact that the inverse of $ a $ and that of $ b $ must be in $ N $ by the definition of a subgroup; we simply then multiply by $ a^{-1}b^{-1} $ on the left side.
Thus, to prove that $ G / N $ is abelian, we only need to show that $ a^{-1}b^{-1}abN = N $.
Allow $ n = a^{-1}b^{-1}ab $.
By assumption, $ n \in N $.
Thus, we are asking if $ nN = N $, which is true by the closure of subgroups.
Thus, $ a^{-1}b^{-1}abN = N $.
Since $ (aN)(bN) = (bN)(aN) \iff a^{-1}b^{-1}abN = N $ and we just proved that $ a^{-1}b^{-1}abN = N $ holds, we know that $ (aN)(bN) = (bN)(aN) $.
This proves that, by definition, the quotient group $ G / N $ is abelian.
\QED{}
\\ \\
Finally, we can prove last statement that the commutator must be in all normal subgroups $ H $ such that the quotient group $ G / H $ is abelian.
By the fact that $ G / H $ is abelian, we know that $ \forall a,\,b \in G, \, (aH)(bH) = (bH)(aH) $.
Using the quotient group operator, it follows that $ abH = baH $.
Now, since the inverse of $ a $ and that of $ b $ must be in $ H $ by definition of a subgroup, we know that $ abH = baH \implies a^{-1}b^{-1}abH = H $.
Here, we will take the liberty to let $ n = a^{-1}b^{-1}ab $ to avoid writing this tedious expression over and over again.
Therefore, we can write $ nH = H $.
At any rate, we see that $ n \in N $ by assumption (i.e.\ the definition of the commutator).
The next step is to then demonstrate that $ n \in H $.
\\ \\
Note that $ 1 \in H $ by definition of a subgroup.
Since $ nH = H $ and $ 1 \in H $, we can see that $ n1 \in H $.
Since $ n1 = 1 $, we conclude that $ n \in H $.
\\ \\
We have shown that all elements in the form $ n = a^{-1}b^{-1}ab $ are in $ H $.
To formally complete the proof, we must demonstrate that all elements of $ N $ are, in fact, in $ H $.
Since $ N $ is the subgroup of $ G $ generated by $ \langle n \rangle $, we know that all other elements of $ N $ must be arbitrary powers of $ n $.
By the closure of a subgroup, if $ n \in H $, then $ n^i \in H : i \in \mathbb{Z}^{+} \setminus 0 $.
Thus, we can finally conclude that the commutator subgroup $ N $ is contained in every normal subgroup $ H $ for which the quotient group $ G / H $ is abelian.
\QED{}

\section{Question 5}
\label{sec:Question5}

\subsection{Part i}
\label{sub:5Parti}

This matrix is an incidence matrix, which means that each row describes a node in the graph, and each column describes a particular edge.
Moreover, we can see that if a particular node $ i $ has a particular edge $ j $, then the entry $ A_{i, j} $ will be $ 1 $.
Now that we understand how the graph translates into a matrix, we can look at how the partitions of rows and columns correspond to disjoint subsets of nodes and edges.
\\ \\
In particular, the first subset of rows describes the ``outer ring'' of nodes in the graph.
The second subset of rows corresponds to the ``inner ring'' of nodes.
\\ \\
Now, we notice that there are fifteen edges in the graph.
These edges can be logically grouped into three subsets: the first subset is the edges that connect only the outer ring of nodes.
The second subset corresponds to the edges that connect the outer ring of nodes to the inner ring of nodes.
The third subset corresponds to the edges that connect the inner ring of nodes.
Correspondingly, we can see that the first, second, and third partitions of columns correspond to the first, second, and third subsets of edges as described above.
\QED{}

\subsection{Part ii}
\label{sub:5Partii}

First, let us look at a linear combination of the row vectors of this matrix.
To prove linear independence, we would need to show that $ \Sigma_{i = 1}^{10} (c_i \vec{v_i}) = \vec{0} \implies c_i = 0 \, \forall i $.
As an experiment, let us simply sum up all of the the rows vectors, in short with all of the coefficients as $ 1 $.
Since we are in $ \mathbb{Z}_2 $, we yield the row vector:
$$ [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] $$
Since our linear combination of these vectors gives us the zero vector, but not all of the coefficients were $ 0 $, we know that these vectors must be linearly dependent.
\\ \\
Now, excluding the last vector, let us try this exercise again.
We will try to find coefficients such that $ \Sigma_{i = 1}^{9} (c_i \vec{v_i}) = \vec{0} $.
Note that the there is a $ 1 $ in the \nth{8}, \nth{14}, and \nth{15} columns that do not have another $ 1 $ above or below.
Therefore, these components of our sum vector will always be non-zero, unless the coefficients for the \nth{3}, \nth{6}, and \nth{9} vectors are $ 0 $, i.e.\ $ c_3 = c_6 = c_9 = 0 $.
Since those vectors have coefficients $ 0 $, any vector with a $ 1 $ in a particular column whose corresponding $ 1 $ was in the \nth{3}, \nth{6}, or \nth{6} vector must also have coefficient $ 0 $; otherwise, they too would contribute values in those particular columns.
If we keep applying this procedure, we can see that all coefficients must be $ 0 $, which proves that these $ 9 $ vectors are linearly independent.
\QED{}

\subsection{Part iii}
\label{sub:5Partiii}
To prove this fact, let us begin by looking at the two subset of nodes.
\\ \\
Suppose that we only have the outer ring of nodes.
Take the edge that connects $ (3,4) $ and $ (1,2) $.
If the weight for this edge is $ 1 $, we know that both edges $ (3,4) $ and $ (1,2) $ must have exactly one other edge, also with weight $ 1 $ to have a valid codeword.
Since we are only considering the outer ring of nodes, we see that each of these nodes only have one other edge; these edges are the ones that connect $ (3,4) $ and $ (1,5) $; and $ (1,2) $ and $ (3,5)$.
Thus, these edges must also have weight $ 1 $.
Continuing this process, we see that, in fact, in this pentagon, we know that if one edge has weight $ 1 $, then the weight of all edges must be $ 1 $.
\\ \\
Now suppose we only have the inner ring of nodes.
If we make one edge have weight $ 1 $, then again by following the edges, to have a valid codeword, all the edges must have weight $ 1 $.
Therefore, we can see that intuition that edges of weight $ 1 $ must exist in a cycle of length at least $ 5 $ for this graph.
\\ \\
For a more rigorous proof, we will begin by noting that any valid, non-zero codeword must, in fact, be a cycle of edges of weight $ 1 $.
Now, since there are no self-loops, i.e.\ and edge that connects a node to itself, we know there are no cycles of length $ 1 $.
Since no pair of nodes have two edges between them (by the structure of the graph, evident from the picture), we know that there are no cycles of length $ 2 $.
\\ \\
Furthermore, we can easily see that no two nodes are connected to the same node.
In short, there are no ``triangles'' in this graph.
This can be seen by inspecting every pair of nodes.
However, we can also see this by considering the two subsets of nodes.
If we look at two nodes in the outer ring, we can clearly see that there is no third node in the outer ring that they can connect to.
Then, we can see that each of these two nodes only connects to one inner node, and no two outer nodes connect to the same inner node.
Therefore, two outer nodes cannot both be connected to the same node.
Symmetrically, two inner nodes cannot connect to the same node, since they clearly do not connect to any common inner node, and cannot connect to the same outer node.
Finally, we will look at a pair of nodes, where one node is in the inner ring and the other node is in the outer ring.
If these two nodes are connected, we quickly see that the rest of the edges of the outer node are only to other outer nodes, and the rest of the edges of the inner node are only to other inner nodes.
Therefore, we can see that there are no cycles of length $ 3 $.
\\ \\
Finally, we can see that there are no ``quadrilaterals'' in this graph, i.e.\ there are no cycles of length $ 4 $.
We can make a similar argument as before.
There are no four outer nodes nor four inner nodes that are connected.
Now, let us consider the case where we look at three outer nodes and one inner node.
To form a quadrilateral, the inner node would have to connect to two exactly nodes.
However, it can only connect to one outer node.
Similarly, if we have one outer node and three inner nodes, we also know that the outer node cannot connect to more than one inner node.
Now, consider the case where we have two outer nodes and two inner nodes.
Since an inner node can connect to exactly one outer node and an outer node can connect to exactly one inner node, we know that any quadrilateral formed with two outer nodes and two inner nodes must have the structure where the two inner nodes connect and the two outer nodes connect.
However, the two inner nodes to which two connected outer nodes connect themselves do not connect.
That was an incredibly confusing statement, so let us break it down.
It is obvious that the inner nodes and the outer nodes are isomorphic, where each inner node is connected to a unique outer node, and vice versa.
Suppose outer node $ o_1 $ connects to inner node $ i_1 $ and outer node $ o_2 $ and inner node $ i_2 $.
If $ o_1 $ and $ o_2 $ are connected, then $ i_1 $ and $ i_2 $ cannot be connected.
Similarly, if $ i_1 $ and $ i_2 $ are connected, then $ o_1 $ and $ o_2 $ cannot be connected.
Thus, we have proved, exhaustively, that there are no cycles of size $ 4 $.
\\ \\
Clearly, there exist cycles of length $ 5 $ (e.g.\ the case where the edges that connect just outer nodes take weight $ 1 $).
Therefore, the minimal cycle length is $ 5 $.
In the case where the edges that connect just the outer nodes take weight $ 1 $ and every other edge weight is $ 0 $, we have a valid codeword.
The weight of this particular codeword is $ 5 $ by definition of the weight of a codeword.
Therefore, the minimal non-zero weight is $ 5 $.
By Theorem 4.2, the minimum distance $ d $ of a binary linear code is just the minimum weight of a non-zero codeword (cf. Lecture 4, Slide 6).
Thus, the minimum distance between codewords is $ 5 $ since the minimum weight of a non-zero codeword is $ 5 $.
\QED{}

\subsection{Part iii}
\label{sub:5Partiii}

\section{Question 6}
\label{sec:Question6}

\subsection{Part i}
\label{sub:6Parti}

First, let us take all proper subgroups of finite group $ G $ that contain $ H $.
Since $ G $ is finite, we know that there is a finite number of its proper subgroups.
Thus, there must also be a finite number of proper subgroups of $ G $ that also contain $ H $.
If there are no proper subgroups of $ G $ that contain $ H $, then we know that $ H $ is in fact maximal by definition.
\\ \\
Now consider the case where there exists some proper subgroup $ H' $ that contains $ H $.
We can now consider all proper subgroups of $ G $ that contain $ H' $.
Again, if there are no proper subgroups of $ G $ that contain $ H' $, then $ H' $ is maximal and also contains $ H $.
If there are proper subgroups of $ G $ that contain $ H' $, select one $ H'' $.
\\ \\
Since $ G $ is finite and thus has finitely many subgroups, we can continue this process until we reach some subgroup $ H^{(n)} $ for which there are no proper subgroups that contain it.
It is thus, by definition, maximal.
Since each $ H^{(i)} $ contains $ H^{(i - 1)} $, we know that $ H^{(n)} $ ultimately contains $ H $.
Thus, if $ H $ is a proper subgroup of a finite group $ G $, then there is a maximal subgroup of $ G $ containing $ H $.
\QED{}

\subsection{Part ii}
\label{sub:6Partii}

For a particular Dihedral group $ D_N $, the subgroup $ S $ that contains all rotations of $ D_N $ is generated by $ \langle y | y^N = 1 \rangle $.
Now, we know that $ D_N $ also contains a reflection $ z $, and that furthermore, all elements are either arbitrary powers of $ y $ or arbitrary powers of $ y $ times $ z $, i.e.\ $ y^{i}z $.
Thus, we can immediately see that $ S $ includes half of all transformations, i.e.\ $ |D_N| / |S| = 2 $.
This also demonstrates that $ S $ is a proper subgroup of $ D_N $, i.e.\ $ S \neq D_N $.
\\ \\
We will now show $ S $ is maximal.
Suppose that there exists a $ T $ that is a subgroup of $ D_N $, but contains $ S $.
By Lagrange's Theorem, $ |T| $ divides $ |D_N| $, but also the order of $ |S| $ has to divide $ |T| $.
We write $ |D_N| / |T| = a $
Thus, $ |T| / |S| = b $.
Putting these equations together, $ |D_N| / |S| = ab $.
However, $ |D_N| / |S| = 2 $, so we know that $ ab = 2 $.
However, $ 2 $ is prime.
Therefore, $ a = 1, \, b = 2 $ or $ a = 2, \, b = 1 $.
If $ a = 1 $, then $ |D_N| = |T| $, and then $ T = D_N $ because $ T $ is a subgroup of $ D_N $.
If $ b = 1 $, then $ |T| = |S| $, and then $ T = S $ because $ S $ is a subgroup of $ T $
Therefore, we can conclude that $ S $ must be maximal because there is no subgroup of $ D_N $ that contains $ S $.
\QED{}

\subsection{Part iii}
\label{sub:6Partiii}

We will begin by proving the forwards direction.
First, note that the converse of Lagrange's Theorem holds for cyclic groups, in that each factor of the order of $ G $ must indeed correspond to a subgroup.
Consider $ H = \langle x^p \rangle $ (which must exist since all elements in $ G $ take the form of arbitrary powers of $ x $).
Next, we see that if $ N $ is prime, then we cannot in fact find a $ p $ that non-trivially divides $ N $, then there are only two subgroups: $ G $ itself and the subgroup that contains just the identity.
$ H $ would then have to be the group that contains just the identity, to satisfy the condition that $ G \neq H $.
Thus, $ H = \langle x^N \rangle $ and since $ N $ is prime, we are done.
Let us now consider the case where $ N $ is not prime.
The order of $ H $ is $ N / p $ by Lagrange's Theorem.
This is true because $ x^{p^{N / p}} = x^N = 1 $, so the group must have order at most $ N / p $.
But if the order of the group were less than $ N / p $, then there would exist some number $ b < N / p : x^{p^{b}} = 1 $, which would violate the relation of the cyclic group $ C_N $ (i.e.\ $ |x| = N $).
Now, suppose that H is generated by $ \langle x^p \rangle $ with $ p $ not prime.
If $ p $ is not prime, then there exist two non-identity factors $ a, b : ab = p $.
Thus, we know that $ N / a > N / p $, which would imply by the converse of Lagrange's Theorem that there is a subgroup that contains $ H $ of order $ N / a $, which means that $ H $ is not maximal.
\\ \\
Alternatively, we can use a proof by contradiction that avoids having to use the fact that the converse of Lagrange's Theorem holds for cyclic groups.
By assumption $ H $ is maximal, which means that it is a proper subgroup of $ G $ and also no other proper subgroup of $ G $ contains $ H $.
By the form of a cyclic group, $ H = \langle x^p \rangle $ and $ p $ must divide $ N $ by Langrange's Theorem.
Suppose that $ p $ is not prime.
Since $ p $ is not prime, we know that there is indeed some factors of $ p $ that we denote $ a, b : a \neq 1, \, b \neq 1 $.
Thus, $ H = \langle x^{ab} \rangle $.
Now take $ S = \langle x^{a} \rangle $.
$ S $ clearly contains $ H $.
Now pick some $ c $ that is smaller than $ b $.
We know that $ x^{ac} $ is in $ S $, but not in $ H $.
Thus, $ H $ is not maximal, which is a contradiction.
Therefore, $ p $ must be prime.
\\ \\
We can now prove the backwards direction.
By assumption, $ H = \langle x^p \rangle $ where $ p $ is prime and divides $ N $.
The order of $ H $ is $ N / p $, by what we outlined above.
Now, if we inspect the lattice of this group, we will try to find some subgroup that contains $ H $.
However, there can be no proper subgroup that contains $ H $, since it would have to have order $ a $ greater than $ N / p $, but also still divide $ N $, but have $ a \neq N $, which is impossible since $ p $ is prime.
Thus, $ H $ must be maximal.
\\ \\
To formally complete the proof, we see that we have proven that subgroup $ H $ being maximal implies that it is generated by $ \langle x^p \rangle $ with $ p $ prime, and that for subgroup $ H = \langle x^p \rangle $ with $ p $ prime, that $ H $ must be maximal.
We can conclude that given cyclic group $ G = \langle x \rangle $ of order $ N \geq 1 $, a subgroup $ H $ is maximal if and only if $ H = \langle x^p \rangle $ for some prime $ p $ dividing $ N $.

\QED{}

\end{document}