MATH 415 Lecture 8

« previous | Thursday, September 19, 2013 | next »

First Test: October 8 (Tuesday)

Direct Products

(a.k.a. Cartesian product)

Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S = S_1 \times S_2 \times \dots \times S_n = \prod_{i=1}^n S_i} . Then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (s_1, s_2, \ldots, s_n) \in S} , where $s_{i}\in S_{i}$.

The cardinality of a product is the same as the product of cardinalities

$|S|=|S_{1}|\,|S_{2}|\,\dots \,|S_{n}|$

We are interested in the product of groups. Let $G=G_{1}\times \dots \times G_{n}$, and $g,h\in G$. Let's define our operation as follows:

$g\,h=(g_{1}\,h_{1},g_{2}\,h_{2},\ldots ,g_{n}\,h_{n})$.

Our operation is associative: $(f\,g)\,h=f\,(g\,h)=(f_{1}\,g_{1}\,h_{1},\ldots f_{n}\,g_{n}\,h_{n})$

Our group contains an identity element: $e=(e_{G_{1}},e_{G_{2}},\ldots ,e_{G_{n}})$

All elements of our group are invertable: $g^{-1}=(g_{1}^{-1},g_{2}^{-1},\ldots ,g_{n}^{-1})$.

Alternate Notation: Direct Sums

If the groups of our product are abelian, then we can compute the direct sum of our groups:

$G=G_{1}\oplus G_{2}\oplus \dots \oplus G_{n}$

• $g+h=(g_{1}+h_{1},\ldots ,g_{n}+h_{n})$
• $e=(0,\ldots ,0)$

(note that this is analogous to the direct product of our groups)

The reason we use this is because all abelian groups are isomorphic to an integer group over modular addition.

Example

$\mathbb {Z} _{2}\times \mathbb {Z} _{3}$ can be reexpressed as $\mathbb {Z} _{2}\oplus \mathbb {Z} _{3}$.

The elements of this new group are:

$\left\{(0,0);(0,1);(0,2);(1,0);(1,1);(1,2)\right\}\,\!$

We claim that $\mathbb {Z} _{2}\oplus \mathbb {Z} _{3}\simeq \mathbb {Z} _{6}$.

We can use $(1,1)$ as our generator for all elements of the group, and the justification follows because there is only one cyclic group of order $n=6$, and it is isomorphic to $\mathbb {Z} _{6}$.

Now if we take $\mathbb {Z} _{2}\oplus \mathbb {Z} _{2}$ or $\mathbb {Z} _{3}\oplus \mathbb {Z} _{3}$, these direct sums are not cyclic because there are no generators that will give all elements.

In the first case, $\mathbb {Z} _{2}\oplus \mathbb {Z} _{2}=V$ is called a Klein group.

Theorem 11.5

Theorem. The group $\mathbb {Z} _{m}\times \mathbb {Z} _{n}$ is cyclic and is isomorphic to $\mathbb {Z} _{m\,n}$ if and only if $m$ and $n$ are relatively prime.

Proof. First assume $\gcd {(m,n)}=1$. Then $a=(1,1)\in \mathbb {Z} _{m}\oplus \mathbb {Z} _{n}$ is a generator. We know that the order of $a$ is the minimum $k$ such that $k\,a=e=(0,0)$. $k\,a=(k,k)=(0,0)$, so

${\begin{aligned}k&\equiv 0{\pmod {m}}\\k&\equiv 0{\pmod {n}}\\\end{aligned}}$

From number theory, we know that if $\gcd {(m,n)}=1$, then the smallest $k$ satisfying the equivalences above is $k=m\,n$. This is good because if the order of $(1,1)$ is $m\,n$, then it generates the whole group $\mathbb {Z} _{m}\times \mathbb {Z} _{n}$

Assume $\gcd {(m,n)}=d$ for $d>1$, then ${\frac {m\,n}{d}}$ is divisible by both $m$ and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} . Thus for any claimed generator Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a = (r,s) \in \mathbb{Z}_m \times \mathbb{Z}_n} , we have Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k = \frac{m\,n}{d}} . So Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k(r,s) = \left( \frac{m\,n}{d}\,r, \frac{m\,n}{d} \, s \right)} , where both components are equivalent to 0 mod Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} , respectively. Therefore the order of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} must be at most Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{m\,n}{d}} and cannot generate the whole group.

Corollary. The group Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{Z}_{m_1} \times \mathbb{Z}_{m_2} \times \dots \times \mathbb{Z}_{m_n}} is cyclic and isomorphic to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{Z}_{m_1 \, m_2 \, \dots \, m_n}} if and only if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \gcd{(m_i, m_j)} = 1} for all Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle j} such that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i \ne j} .

Example

Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (p_1)^{n_1} \, (p_2)^{n_2} \, \dots \, (p_r)^{n_r}} be the prime factorization of an integer Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} . Then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{Z}_n \simeq \mathbb{Z}_{(p_1)^{n_1}} \times \dots \times \mathbb{Z}_{(p_r)^{n_r}}} .

In a specific case, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{Z}_{72} \simeq \mathbb{Z}_{2^3} \times \mathbb{Z}_{3^2} = \mathbb{Z}_8 \times \mathbb{Z}_9} because Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 72 = 2^3 \cdot 3^2} .

Theorem 11.9

Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (a_1, a_2, \ldots, a_n) \in \prod_{i=1}^n G_i} , and let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_i} be of finite order Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r_i} in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G_i} . Then the order of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (a_1, \ldots, a_n) \in \prod_{i=1}^n G_1} is equal to the least common multiple of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r_1, \ldots, r_n} .

In other words, we are looking for a Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} such that

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a^k = (a_1^k, a_2^k, \ldots, a_n^k) = (e_1, e_2, \ldots, e_n) \,\!}

The theorem above claims that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} is the least common multiple of the orders of the contained elements.

Proof. We have Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r_i \mid k} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_i^k = e_i} in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G_i} .

Example

What is the order of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (8,4,10) \in \mathbb{Z}_{12} \times \mathbb{Z}_{60} \times \mathbb{Z}_{24}}

• Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 8 \in \mathbb{Z}_{12}} has order Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{12}{\gcd{(8,12)}} = \frac{12}{4} = 3}
• Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 4 \in \mathbb{Z}_{60}} has order Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{60}{\gcd{(4,60)}} = \frac{60}{4} = 15}
• Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 10 \in \mathbb{Z}_{24}} has order Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{24}{\gcd{(10,24)}} = \frac{24}{2} = 12}

Therefore the order of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (8,4,10)} is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \lcm{(3,15,12)} = 60} .

Internal Direct Product

Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \overline{G}_i = \left\{ \left( e_1, \ldots, e_{i-1}, a_i, e_{i+1}, \ldots, e_n \right) ~\mid~ a_i \in G_i \right\}} be a subset of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G = \prod_{i=0}^n G_i} .

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \overline{G}_i} is a subgroup of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} .

Furthermore, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \overline{G}_i} is isomorphic to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G_i} with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi(e_1, \ldots, e_{i-1}, a_i, e_{i+1}, \ldots, e_n) = a_i} .

We call Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G = \prod_{i=1}^n \overline{G}_i} the internal direct product, and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G = \prod_{i=1}^n G_i} the external direct product.