Groups.

Bézout’s identity. Let a and b be integers with greatest common divisor d. Then there exist integers x and y such that ax + by = d.

Consider that ab mod n is the unique integer r such that a·b = nq + r, where 0 ≤ r, n and a·b is ordinary multiplication.

A binary operation on a set G is a method, function, or correspondence that assigns to each ordered pair of elements of the set G a uniquely determined element of the set.For example, addition and multiplications are binary operation on ℕ, ℤ, and ℚ. On the other hand, division of integers is not a binary operation on ℤ.

A binary operation is simply a formula or method of combining the elements of a set, two at a time, in such a way that their combination is also a member of the set. This condition is called closure.

A division is not a binary operation on the set of natural ℕ, integer ℤ, rational ℚ, real ℝ and complex numbers ℂ.

For a binary set, a binary operation can be defined by a table using the following rule, (ith entry on the left)*(jth entry on the top) = (entry in the ith row and jth column of the table). Figure 1.c.  

Let M(ℝ) be the set of all matrices with real entries. Matrix addition is not a binary operation on M(ℝ) when the matrices do not have same dimension.

Let ∗ be a binary operation on S, H a subset of S (H ⊂ S). The subset H is closed under ∗ if ∀a, b ∈ H, we also have a ∗ b ∈ H. Examples: ℝ* (ℝ* ⊂ ℝ) is not closed under +: 3 + (-3) = 0 and 0 ∉ ℝ*; F(ℝ, ℝ), the set of all real-valued functions f having ℝ as domain, is closed under the binary operations +, -, ·, and ◦ (composition).

Group

A group is a set G together with a binary operation on G, denoted as ◦, ·, or simply omitted, such that the following three requirements or axioms are satisfied.

1. Associativity. The operation is associative; that is, (ab)c = a(bc) for all a, b, c in G.
2. Identity. There exist an element e (called the identity) in G such that, for every a in G, ae = ea = a for all a in G.
3. Inverses. For each element a in G, there exists an element b in G such that ab = ba = e. It is called the inverse of a andd is commonly denoted a^-1.

The definition of a group does not require that ab=ba for every pairs of elements a and b. If this additional condition holds, then the operation is said to be commutative, and the group is called an Abelian group.

Examples

• ℤ, ℚ, and ℝ are all groups under addition. The identity is 0 and -a is the inverse of a. (ℝ^*, ·) is a group. The identity is 1 and 1/a is the inverse.
• (ℤ, ·) is not a group because the only integers with inverses under multiplication are 1 and -1. As not all integers have inverses, e.g., 2 or 3, it follows that (ℤ, ·) is not a group.
• (ℚ⁺, ·). The identity is 0 and ¹⁄_a is the inverse of a.
• Irrational numbers under multiplication is not a group, e.g., $\sqrt{2}·\sqrt{2} = 2$, so it is not closed under multiplication.
• Z_n = {0, 1, 2, … n-1} is a group under addition modulo n. For j=0, the inverse is itself; for any j>0 in Z_n, the inverse of j is n-j.
• You can multiply elements of Z_n, but you do not obtain a group, e.g., 0 does not have a multiplicative inverse. An integer has a multiplicative inverse modulo n if and only if a and n are relative prime. Figure 1.b.  

Let n be an integer, suppose i is coprime to n, then αi + βn = 1 for some α, β ∈ Z by Bézout’s identity ⇒ αi = 1 - βn ⇒ αi≡1(mod n) and i is invertible.

Suppose that i is invertible, and i is not coprime to n, then i = da, n = db, for some d > 1 and αi = 1 + βn for some α, β ∈ Z ⇒ αda = 1 + βnb ⇒ d(αa -βb) = 1 ⇒ d = ±1 which is impossible since d > 1.

For each n > 1, we define U_n to be the set of all positive integers less than n that have a multiplicative inverse modulo n, that is, there is an element b∈ Z_n such that ab = 1. U_n = {a ∈ Z_n: a is relatively prime to n, a < n} = {a ∈ Z_n: gcd(k, n)=1}.

For n = 10, U₁₀ = {1, 3, 7, 9}. The Cayley table for U₁₀ is (Figure 1.a.)

It is a group under multiplication modulo n, called the multiplicative group of integers modulo n.

Let’s prove it.

1. a, b ∈ U_n, (ab)^-1=b^-1a^-1 because (ab)(b^-1a^-1)=a(bb^-1)a^-1 = aa^-1 = 1
2. 1 is the identity.
3. Associativity is inherited from Z_n.
4. Inverses works by definition.

• The dihedral group D₃ is the symmetry group of the equilateral triangle.

• Let V be a vector space over a field F. An automorphism is a bijective homomorphism that maps V to itself. The set of all automorphisms of V is denoted by Aut(V). Aut(V) = {φ:V→V: φ is lineal and bijective} is a group where the group operation is the composition. φ is a mapping that preserves the operations of vector addiction and scalar multiplication, that is, (λφ)(αv + βw) = α(λφ)v + β(λφ)w and (φ + φ’)(αv + βw) = α(φ + φ’)v +β(φ + φ’)w.

• $GL(2, ℝ) = \bigl\{ {{[\bigl(\begin{smallmatrix}a & b\\ c & d\end{smallmatrix}\bigr)]: a, b, c, d ∈ ℝ, ad - bc ≠ 0}} \bigr\}$ is the group of invertible 2 x 2 matrices with entries in ℝ and non-zero determinant.

The operation is defined as $[\bigl(\begin{smallmatrix}a_1 & b_1\\ c_1 & d_1\end{smallmatrix}\bigr)][\bigl(\begin{smallmatrix}a_2 & b_2\\ c_2 & d_2\end{smallmatrix}\bigr)]=[\bigl(\begin{smallmatrix}a_1a_2+b_1c_2 & a_1b_2+b1d_2\\ c_1a_2+d_1c_2 & c_1b_2+d_1d_2\end{smallmatrix}\bigr)]$

∀A, B ∈ GL(2, ℝ), det(AB)=det(A)*det(B)≠ 0, so AB∈ GL(2, ℝ), and therefore, it is closed under matrix multiplication. The identity is $[\bigl(\begin{smallmatrix}1 & 0\\ 0 & 1\end{smallmatrix}\bigr)]$; the inverse of $[\bigl(\begin{smallmatrix}a_1 & b_1\\ c_1 & d_1\end{smallmatrix}\bigr)]$ is $[\bigl(\begin{smallmatrix}\frac{d}{ad-bc} & \frac{-b}{ad-bc}\\ \frac{-c}{ad-bc} & \frac{a}{ad-bc}\end{smallmatrix}\bigr)]$.

• ℂ* = {a + bi : a, b ∈ R, a ≠ 0}, is the set of nonzero complex numbers. ℂ^* under the operation of multiplication forms a group. Its identity is 1, and $z^{-1}=\frac{a-bi}{a^{2}+b^{2}}$

Real numbers can be represented as point on a one-dimensional number line. Complex numbers, with their real and imaginary components, require a two dimensional complex-number plane. This complex number plane can also be represented with polar coordinates, so z = x + iy = r(cosθ + isenθ). r = |z| = $\sqrt{x^{2}+y^{2}}$, x = r cosθ, and y = rsinθ.

Definition. A group is finite if it has a finite number of elements. Otherwise, it is said to be infinite. The number of elements in a group G is called the order of the group, and is denoted by |G|, e.g., ℤ₁₀ and U₁₀ are finite group of orders 10 and 4 respectively; ℤ is an infinite group under addition.

Properties of Groups

Uniqueness of the identity. Let (G, ◦) be a group, then there is exactly one neutral element or identity e ∈ G such that eg = ge = g ∀g∈ G.

Proof. Let e, e’∈ G be neutral elements. Thus, ∀a ∈ G, we have ae = ea = a (i), ae’ = e’a = a (ii)
e’∈ G, e’e = ee’ = e’ (i)
e ∈ G, ee’ = e’e = e (ii). Thus, e = ee’ = e'.

Uniqueness of Inverses. Let (G, ◦) be a group, then there is a unique element b in G such that ab = ba = 2.

Proof. Let a ∈ G, a^-1, a’^-1 be inverses of a, a^-1 ≠ a^’-1, aa^-1=a^-1a=e and a^-1 ≠ a’^-1, aa^-1=a^-1a=e, aa’^-1=a’^-1a=e

aa^-1 = a^-1a ⇒ a’^-1(aa^-1) = a’^-1(a^-1a) ⇒ [Associativity] (a’^-1a)a^-1 = a’^-1(a^-1a) ⇒ ea^-1 = a’^-1e ⇒ [Identity] a^-1 = a’^-1.

Proposition 2. Let (G, ◦) be a semigroup (it is closed and associative) with an identity such that, ba = e that is, every element of S has a left inverse with respect to its identity. Then ab = e, that is, b is also a right inverse.

Proof. ba = e ⇒ (ba)b = eb ⇒ [Associativity & Identity] b(ab) = b ⇒ [b has a left inverse, b^-1] b^-1b (ab) = b^-1b = e ⇒ ab = e.

Proposition. The inverse of the inverse of a group element is the element itself, that is (a^-1)^-1 = a and (ab)^-1 = b^-1a^-1.

Proof. The first part is just reinterpreting the equation aa^-1 = a^-1a = e.

ab(b^-1a^-1) = ⇒ [Associativity] a(bb^-1)a^-1 = aa^-1 = e.

(b^-1a^-1)ab = ⇒ [Associativity] b^-1(a^-1a)b = b^-1b = e.

Cancellation property. Let G be a group, a, b, and c ∈ G. Then, the following hold:
Left cancellation law. If ab = ac ⇒ b = c.
Right cancellation law. If ba = ca ⇒ b = c.

Proof. ab = ac ⇒ a^-1(ab) = a^-1 (ac) ⇒ [Associativity] (a^-1a)b = (a^-1a)c ⇒ b = c.

The proof of the right cancellation law is analogous.

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

Proof: First, let’s show the existence of at least one solution. a^-1b is a solution of ax=b. We leve the proof of xa=b as an exercise.

a(a^-1b) = [by associativity law] (aa^-1)b = [by definition of inverses, a^-1] eb = b.

To show uniqueness, let’s assume that we have two solutions y₁ and y₂.

ay₁ = b = ay₂ ⇒ ay₁ = ay₂ ⇒ a^-1(ay₁) = a^-1(ay₂) ⇒ [by associativity law] (a^-1a)y₁ = (a^-1a)y₂ ⇒ [by definition of inverses, a^-1] ey₁ = ey₂ ⇒ y₁ = y₂

Notation. Let G be a group and a and element of G, then we define a⁰ = e. For n ∈ ℕ, aⁿ = a·a···a, n times, and a^-n = a^-1·a^-1···a^-1, n times.

The Laws of exponent for groups. Let (G,⋅) be a group and let a ∈ G. If m and n are integers, then a^m⋅aⁿ=a^m+n, (a^m)ⁿ=a^mn, and (ab)ⁿ=(b^-1a^-1)^-n. Futhermore, if G is abelian, then (ab)ⁿ=(b^-1a^-1)-n = aⁿbⁿ

Let’s prove a^m⋅aⁿ=a^m+n and (a^m)ⁿ=a^mn.

a^m⋅aⁿ = a·a···a · a·a···a, m and n times respectively = a·a···a, m + n times = a^m+n.

(a^m)ⁿ= a·a···a (m times) · a·a···a (m times) ··· a·a···a (m times), n copies of a·a···a = a·a···a (mn times) = a^mn

Notation. When a group is Abelian, addition notation is often used, e.g., a+b, 0 as e, -a is the inverse of a, na instead of aⁿ = a + a +… + a (n times), and so on.