问题求解2019Spring

问题求解 2019Spring

4.1线性规划

In linear programming, we do not allow strict inequalities.

minimization linear program and maximization program

The simplex algorithm does not run in polynomial time in the worst case, but it is fairly efficient and widely used in practice.

We use two forms, standard and slack.

Informally, a linear program in standard form is the maximization of a linear function subject to linear inequalities, whereas a linear program in slack form is the maximization of a linear function subject to linear equalities.

We call the feasible region formed by the intersection of these half-spaces a simplex.

The simplex algorithm starts at some vertex of the simplex and performs a sequence of iterations. In each iteration, it moves along an edge of the simplex from a current vertex to a neighboring vertex whose objective value is no smaller than that of the current vertex(and usually is larger.) The simplex algorithm terminates when it reaches a local maximum, which is a vertex from which all neighboring vertices have a smaller objective value.

If we add to a linear program the additional requirement that all variables take on integer values, we have an integer linear program.

An arbitrary linear program need not have nonnegativity constraints, but standard form requires them.

We say that two maximization linear programs $L$ and $L'$ are equivalent if for each feasible solution $\bar{x}$ to $L$ with objective value $z$, there is a corresponding feasible solution $\bar{x}'$ to $L'$ with objective value $z$ and for each feasible solution $\bar{x}''$ to $L'$ with objective value $z$, there is a corresponding feasible solution $\bar{x}$ to $L$ with objective value $z$.(This definition does not imply a one-to-one correspondence between feasible solutions.)

How to convert linear programs into standard form?

如何添加非负限制的设计很精巧

How to convert linear programs into slack form?

We call $s$ a slack variable because it measures the slack, or the difference, between the left-hand and right-hand sides of equation.

We call the variables on the left-hand side of the equalities basic variables and those on the right-hand side nonbasic variables.

4.2 群论初步

Some definations

A symmetry of a geometric figure is a rearrangement of the figure preserving the arrangement of its sides and vertices as well as its distances and angles.

A map from the plane to itself preserving the symmetry of an object is called a rigid motion.

A binary operation or law of composition on a set $G$ is a function $G \times G \rightarrow G$ that assigns to each pair $(a,b) \in G \times G$ a unique element $a \circ b$, or $ab$ in $G$, called the composition of $a$ and $b$. A group $(G,\circ)$ is a set $G$ together with a law of composition $(a,b) \mapsto a \circ b$ that satisfies the following axioms.

associative: $(a \circ b) \circ c = a \circ (b \circ c)$
identity element: $e \circ a = a \circ e =a$
inverse element : $a \circ a^{-1} = a^{-1} \circ a =e$

A group $G$ with the property that $a \circ b = b \circ a$ for all $a,b \in G$ is called abelian or commutative. Groups not satisfying this property are said to be nonabelian or noncommutative.

A Cayley table .

Every nonzero $k$ does have an inverse in $Z_{n}$ if $k$ is relatively prime to $n$. Denote the set of all such nonzero elements in $Z_{n}$ by $U(n)$. Then $U(n)$ is a group called the **group of units** of $Z_{n}$ .

The set of invertible matrices forms a group called the general linear group.

A group is finite, or has finite order, if it contains a finite number of elements; otherwise, the group is said to be infinite or to have infinite order. The order of a finite group is the number of elements that it contains.

Basic Properties of Groups

Proposition 3.17. The identity element in a group $G$ is unique; that is, there exists only one element $e \in G$

such that $eg=ge=g$ for all $g \in G$.

Proposition 3.18. If $g$ is any element in a group $G$, then the inverse of $g$ , denoted by $g^{-1}$ , is unique.

Proposition 3.19 Let $G$ be a group. If $a,b \in G$, then $(ab)^{-1} = b^{-1}a^{-1}$.

Proposition 3.20. Let $G$ be a group. For any $a \in G$, $(a^{-1})^{-1}=a$.

Proposition 3.21 Let $G$ be a group and $a$ and $b$ be any two elements in $G$. Then the equations $ax=b$ and $xa=b$ have unique solutions in $G$.

Proposition 3.22. (right and left cancellation laws) If $G$ is a group and $a,b,c\in G$, then $ba=ca$ implies $b=c$ and $ab=ac$ implies $b=c$.

Theorem 3.23. In a group, the usual laws of exponents hold; that is, for all $g,h \in G$,

$g^m G^n = g^{m+n}$ for all $m,n \in Z$
$(g^m)^n = g^{mn}$ for all $m,n \in Z$
$(gh)^n = (h^{-1} g^{-1})^{-n}$ for all $n\in Z$. Furthermore, if $G$ is abelian, then $(gh)^n = g^n h^n$.

Subgroups

We define a subgroup $H$ of a group $G$ to be a subset $H$ of $G$ such that when the group operation of $G$ is restricted to $H$, $H$ is a group in its own right.

Every group has at least two subgroups. The subgroup $H={e}$ of a group $G$ is called the trivial subgroup. A subgroup that is a proper subset of $G$ is called a proper subgroup.

Some Subgroup Theorems

Proposition 3.30 A subset $H$ of $G$ is a subgroup if and only if it satisfies the following conditions.

The identity of $e$ of $G$ is in $H$.
If $h_1,h_2 \in H$, thne $h_1h_2 \in H$.
If $h \in H$, then $h^{-1} \in H$.

Proposition 3.31 Let $H$ be a subset of a group $G$. Then $H$ is a subgroup of $G$ if and only if $H \not= \emptyset$, and whenever $g,h \in H$ then $gh^{-1}$ is in $H$.

Cyclic Subgroups

Theorem 4.3 Let $G$ be a group and $a$ be any element in $G$. Then the set $ = { a^k : k \in Z }$ is a subgroup of $G$. Furthermore, $$ is the smallest subgroup of $G$ that contains $a$.

For $a\in G$, we call $$ the cyclic subgroup generated by $a$. If $G$ contains some element $a$ such that $G=$, then $G$ is a cyclic group. In this case $a$ is a generator of $G$. If $a$ is an element of a group $G$, we define the order of $a$ to be the smallest positive integer $n$ such that $a^n =e$, and we write $|a|=n$. If there is no such integer $n$, we say that the order of $a$ is inifinte and write $|a|= \infty$ to denote the order of $a$.

Theorem 4.9. Every cyclic group is abelian.

Theorem 4.10 Every subgroup of a cyclic group is cyclic.

Corollary 4.11 The subgroups of $Z$ are exactly $nZ$ for $n=0,1,2,….$

Proposition 4.12 Let $G$ be a cyclic group of order $n$ and suppose that $a$ is a generator for $G$. Then $a^k=e$ if and only if $n$ divides $k$.

Theorem 4.13 Let $G$ be a cyclic group of order $n$ and suppose that $a \in G$ is a generator of the group. If $b= a^k$, then the order of $b$ is $n/d$, where $d=gcd(k,n)$.

Corollary 4.14 The generators of $Z_n$ are the integers $r$ such that $1 \le r < n$ and $gcd(r,n)=1$.

置换群与拉格朗日定理

In general, the permutations of a set $X$ form a group $S_X$. If $X$ is a finite set, we can assume $X={1,2,…,n}$. In this case we write $S_n$ instead of $S_X$. We call this group the symmetric group on $n$ letters.

Theorem 5.1 The symmetric group on $n$ letters, $S_n$ is a group with $n!$ elements, where the binary operation is the composition of maps.

A subgroup of $S_n$ is called a permutation group.

Permutation multiplication is not usually commutative.

A permutation $\sigma \in S_X$ is a cycle of length $k$ if there exist elements $a_1, a_2, …, a_k \in X$ such that $ \sigma(a_1)=a_2,\sigma(a_2)=a_3,…,\sigma(a_k)=a_1 $ and $\sigma(x)=x$ for all other elements $x \in X$. We will write $(a_1,a_2,..,a_k)$ to denote the cycle $\sigma$.

Cycles are the building blocks of all permutations.

Two cycles in $S_X$ , $\sigma = (a_1, a_2,…,a_k)$ and $\tau = (b_1,b_2,…,b_l)$, are disjoint of $a_i \not= b_i$ for all $i$ and $j$.

Proposition 5.8. Let $\sigma$ and $\tau$ be two disjoint cycles in $S_X$. Then $\sigma \tau = \tau \sigma$.

Theorem 5.9 Every permutation in $S_n$ can be written as the product of disjoint cycles.

Transpositions

The simplest permutation is a cycle of length $2$. Such cycles are called transpositions. Since $(a_1,a_2,…,a_n)=(a_1a_n)(a_1 a_{n-1})…(a_1a_3)(a_1a_2)$

Proposition 5.12. Any permutation of a finite set containing at least two elements can be written as the product of transpositions.

No permutation can be written as the product of both an even number of transpositions and an odd number of transpositions.

Lemma 5.14 If the identity is written as the product of $r$ transpositions, $id = \tau_1 \tau_2 \cdot \cdot \cdot \tau_r , $ then $r$ is an even number. (Proof need to be understood)

Theorem 5.15 If a permutation $\sigma$ can be expressed as the product of an even number of transpositions, then any other product of transpositions equaling $\sigma$ must also contain an even number of transpositions. Similarly, if $\sigma$ can be expressed as the product of an odd number of transpositions, then any other product of transpositions equaling $\sigma$ must also contain an odd number of transpositions.

My comment on the proof of 5.14: The fact that the inverse of $\sigma$ is $\sigma_m \cdot \cdot \cdot \sigma_1$ confuses me some time. By introducing the fact that two identity transpositions equals to the identity, it is much clear. Also note that the inverse of any transposition is itself.

We define a permutation to be even if it can be expressed as an even number of transpostions and odd if it can be expressed as an odd number of transpositions.

The Alternating Groups

One of the most important subgroups of $S_n$ is the set of all even permutations, $A_n$. The group $A_n$ is called the alternating group on $n$ letters.

Theorem 5.16 The set $A_n$ is a subgroup of $S_n$.

Proposition 5.17 The number of even permutations in $S_n, n>2$, is equal to the number of odd permutations; hence, the order of $A_n$ is $n!/2$ .

Dihedral Groups

For $n=3,4,…,$, we define the $n$th dihedral group to be the group of rigid motions of a regular $n$-gon.

Theorem 5.20. The dihedral group, $D_n$, is a subgroup of $S_n$ of order $2n$.

Theorem 5.23. The group $D_n$ , $n \ge 3$, consists of all products of two elements $r$ and $s$, satisfying the relations $r^n=1, s^2=1, srs=r^{-1}$.

Proposition 5.27. The group of rigid motions of a cube contains $24$ elements.

Theorem 5.28. The group of rigid motions of a cube is $S_4$.

Cosets

Let $G$ be a group and $H$ a subgroup of $G$. Define a left coset of $H$ with representative $g \in G$ to be the set $gH = { gh : h \in H }$. Right cosets can be defined similarly by $Hg = { hg:h \in H }$.

Lemma 6.3. Let $H$ be a subgroup of a group $G$ and suppose that $g_1,g_2 \in G$. The following conditions are equivalent.

$g_1 H = g_2 H$
$H g_1^{-1} = H g_2^{-1}$
$g_1 H \subset g_2 H $
$g_2 \in g_1 H$
$ g_1^{-1} g_2 \in H$.

Theorem 6.4 Let $H$ be a subgroup of a group $G$. Then the left cosets of $H$ in $G$ partition $G$. That is, the group $G$ is the disjoint union of the left cosets of $H$ in $G$.

Let $G$ be a group and $H$ be a subgroup of $G$. Define the index of $H$ in $G$ to be the number of left cosets of $H$ in $G$. We will denote the index by $[G:H]$.

Theorem 6.8. Let $H$ be a subgroup of a group $G$. The number of left cosets of $H$ in $G$ is the same as the number of right cosets of $H$ in $G$.

Proposition 6.9. Let $H$ be a subgroup of $G$ with $g \in G$ and define a map $\phi : H \rightarrow gH$ by $\phi(h) = gh$. The map $\phi$ is bijective; hence, the number of elements in $H$ is the same as the number of elements in $gH$.

Theorem 6.10 Lagrange. Let $G$ be a finite group and let $H$ be a subgroup of $G$. Then $|G|/|H|=[G:H]$ is the number of distinct left cosets in $G$. In particular, the number of elements in $H$ must divide the number of elements in $G$.

Corollary 6.11. Suppose that $G$ is a finite group and $g \in G$. Then the order of $g$ must divide the number of elements in $G$.

Corollary 6.12 Let $|G|=p$ with $p$ a prime number. Then $G$ is cyclic and any $g \in G$ such that $g\not= e$ is a generator.

Corollary 6.13. Let $H$ and $K$ be subgroups of a finite group $G$ such that $G \supset H \supset K.$ Then $[G:K]=[G:H][H:K].$

Proposition 6.15 The group $A_4$ has no subgroup of order $6$.

Theorem 6.16. Two cycles $\tau$ and $\mu$ in $S_n$ have the same length if and only if there exists $a \sigma \in S_n$ such that $\mu = \sigma \tau \sigma^{-1}$.

Fermat’s and Euler’s Theorems

The Euler $\phi$ -function is the map $\phi:N \rightarrow N$ defined by $\phi(n)=1$ for $n=1$, and, for $n>1$, $\phi(n)$ is the number of positive integers $m$ with $1 \le m < n$ and $gcd(m,n)=1$.

Theorem 6.17. Let $U(n)$ be the group of units in $Z_n$. Then $|U(n)| = \phi(n)$.

Theorem 6.18 Euler’s Theorem. Let $a$ and $n$ be integers such that $n>0$ and $gcd(a,n)=1$. Then $a^{\phi(n)} \equiv 1$(mod $n$).

Theorem 6.19. Fermat’s Little Theorem. Let $p$ be any prime number and suppose that $ p \nmid a$ ($p$ does not divide $a$). Then $a^{p-1} \equiv 1$ (mod $p$). Furthermore, for any integer $b$, $b^p \equiv b$ (mod $p$).

群同态基本定理与正规子群

Isomorphisms

Two groups $(G, \cdot )$ and $(H, \circ)$ are isomorphic if there exists a one-to-one and onto map $\phi : G \rightarrow H$ such that the group operation is preserved; that is, $\phi (a \cdot b) = \phi(a) \circ \phi (b)$ for all $a$ and $b$ in $G$. If $G$ is isomorphic to $H$, we write $G \cong H$. The map $\phi$ is called an isomorphism.

Theorem 9.6. Let $\phi : G \rightarrow H$ be an isomorphism of two subgroups. Then the following statements are true.

$\phi^{-1}: H \rightarrow G$ is an isomorphism.
$|G| = |H|.$
If $G$ is abelian, then $H$ is abelian.
If $G$ is cyclic, then $H$ is cyclic.
If $G$ has a subgroup of order $n$, then $H$ has a subgroup of order $n$.

Theorem 9.7. All cyclic groups of infinite order are isomorphic to $Z$.

Theorem 9.8. If $G$ is a cyclic group of order $n$, then $G$ is isomorphic to $Z_n$.

Corollary 9.9. If $G$ is a group of order $p$, where $p$ is a prime number, then $G$ is isomorphic to $Z_p$.

Theorem 9.10. The isomorphism of groups determines an equivalence relation on the class of all groups.

Theorem 9.12 Cayley. Every group is isomorphic to a group of permutations.

The isomorphism $g \mapsto \lambda_g$ is known as the left regular representation of $G$.

External Direct Products

If $(G, \cdot)$ and $(H,\circ)$ are groups, then we can make the Cartesian product of $G$ and $H$ into a new group. As a set, our group is just the ordered pairs $(g,h) \in G \times H$ where $g \in G$ and $h \in H$. We can define a binary operation on $G \times H$ by $(g_1,h_1)(g_2,h_2) = (g_1 \cdot g_2, h_1 \cdot h_2)$.

Proposition 9.13. Let $G$ and $H$ be groups. The set $G \times H$ is a group under the operation $(g_1,h_2)(g_2,h_2) = (g_1g_2, h_1h_2)$ where $g_1,g_2 \in G$ and $h_1,h_2 \in H$.

The group $G \times H$ is called the external direct product of $G$ and $H$.

Theorem 9.17. Let $(g,h) \in G \times H$. If $g$ and $h$ have finite orders $r$ and $s$ respectively, then the order of $(g,h)$ in $G \times H$ is the least common multiple of $r$ and $s$.

Corollary 9.18. Let $(g_1, …, g_n) \in \prod G_i$. If $g_i$ has finite order $r_i$ in $G_i$, then the order of $(g_1,…,g_n) \in \prod G_i$ is the least common multiple of $r_1,…,r_n$.

Theorem 9.21. The group $Z_m \times Z_n$ is isomorphic to $Z_{mn}$ if and only if $gcd(m,n)=1$.

Corollary 9.22. Let $n_1,…,n_k$ be positive integers. Then $\prod\limits_{i=1}^{k}Z_{n_i} \cong Z_{n_1…n_k}$ if and only if $gcd(n_i,n_j)=1$ for $i \not= j$.

Corollary 9.23. If $m = p_1^{e_1} \cdot \cdot \cdot p_k^{e_k}$, where the $p_is$ are distinct primes, then $Z_m \cong Z_{p_1 ^{e_1}} \times \cdot \cdot \cdot \times Z_{p_k^{e_k}}$.

Internal Direct Products

Let $G$ be a group with subgroups $H$ and $K$ satisfying the following conditions.

$G = H K = {hk: h\in H , k \in K}$;
$H \cap K = {e}$;
$hk=kh$ for all $k \in K$ and $h \in H$.

Then $G$ is the internal direct product of $H$ and $K$.

Theorem 9.27. Let $G$ be the internal direct product of subgroups $H$ and $K$. Then $G$ is isomorphic to $H \times K$. Then $G$ is isomorphic to $H \times K$.

Theorem 9.29. Let $G$ be the internal direct product of subgroups $H_i$, where $i = 1,2,…,n$. Then $G$ is isomorphic to $\prod_i H_i$.

Normal Subgroups

A subgroup $H$ of a group $G$ is normal in $G$ if $gH = Hg$ for all $g \in G$.

Theorem 10.3. Let $G$ be a group and $N$ be a subgroup of $G$. Then the following statements are equivalent.

The subgroup $N$ is normal in $G$.
For all $g \in G$, $g N g^{-1} \subset N$.
For all $g \in G$, $gNg^{-1} = N$.

Factor Groups

If $N$ is a normal subgroup of a group $G$, then the cosets of $N$ in $G$ form a group $G/N$ under the operation $(aN)(bN)=abN$. This group is called the factor or quotient group of $G$ and $N$.

Theorem 10.4. Let $N$ be a normal subgroup of a group $G$. The cosets of $N$ in $G$ form a group $G/N$ of order $[G:N]$.

The Simplicity of the Alternating Group

Of special interest are groups with no nontrivial normal subgroups. Such groups are called simple groups.

Lemma 10.8. The alternating group $A_n$ is generated by $3-$cycles for $n \ge 3$.

Lemma 10.9. Let $N$ be a normal subgroup of $A_n$, where $n \ge 3$. If $N$ contains a $3-$cycle, then $N=A_n$.

Lemma 10.10. For $n \ge 5$, every nontrivial normal subgroup $N$ of $A_n$ contains a $3-$ cycle.

Theorem 10.11. The alternating group, $A_n$, is simple for $n \ge 5$.

Group Homomorphisms

A homomorphism between groups $(G, \cdot)$ and $(H, \circ)$ is a map $\phi: G \rightarrow H$ such that $\phi(g_1 \cdot g_2) = \phi(g_1) \circ \phi(g_2)$ for $g_1, g_2 \in G$. The range of $\phi$ in $H$ is called the homomorphic image of $\phi$.

Proposition 11.4. Let $\phi : G_1 \rightarrow G_2$ be a homomorphism of groups. Then

If $e$ is the identity of $G_1$, then $\phi(e)$ is the identity of $G_2$;
For any element $g \in G_1$, $\phi(g^{-1}) = [\phi(g)]^{-1}$;
If $H_1$ is a subrgoup of $G_1$, then $\phi(H_1)$ is a subrgoup of $G_2$;
If $H_2$ is a subgroup of $G_2$, then $\phi^{-1}(H_2) = {g \in G_1 : \phi(g) \in H_2}$ is a subgroup of $G_1$. Furthermore, if $H_2$ is normal in $G_2$, then $\phi^{-1}(H_2)$ is normal in $G_1$.

Let $\phi: G \rightarrow H$ be a group homomorphism and suppose that $e$ is the identity of $H$. By Proposition 11.4, $\phi^{-1}({e})$ is a subrgoup of $G$. This subgroup is called the kernel of $\phi$ and will be denoted by ker $\phi$.

Theorem 11.5. Let $\phi : G \rightarrow H$ be a group homomorphism. Then the kernel of $\phi$ is a normal subgroup of $G$.

The Isomorphism Theorems

Let $H$ be a normal subgroup of $G$. Define the natural or canonical homomorphism $\phi : G \rightarrow G/H$ by $\phi(g) = g H$.

Theorem 11.10 First Isomorphism Theorem. If $\psi : G \rightarrow H$ is a group homomorphism with $K = ker \psi$, then $K$ is normal in $G$. Let $\phi: G \rightarrow G/K$ be the canonical homomorphism. Then there exists a unique isomorphism $\eta : G/K \rightarrow \psi(G)$ such that $\psi = \eta \phi$

Theorem 11.12 Second Isomorphism Theorem. Let $H$ be a subgroup of a group $G$ (not necessarily normal in $G$) and $N$ a normal subgroup of $G$. Then $HN$ is a subgroup of $G$, $H \cap N$ is a normal subgroup of $H$, and $H/ H \cap N \cong HN/N$.

Theorem 11.13 Correspondence Theorem. Let $N$ be a normal subgroup of a group $G$. Then $H \mapsto H/N$ is a one-to-one correspondence between the set of subgroups $H$ containing $N$ and the set of subgroups of $G/N$. Furthermore, the normal subgroups of $G$ containing $N$ correspond to normal subgroups of $G/N$.

Theorem 11.14 Third Isomorphism Theorem. Let $G$ be a group and $N$ and $H$ be normal subgroups of $G$ with $N \subset H.$ Then $G/H \cong \frac{G/N}{H/N}$.