Linear Algebra - Group Theory

## Linear Algebra ### Group Theory **Def:** Let *G* be a non-empty set, any map *f*: *G* x *G* → *G* is called a binary operation on *G* or binary composition in *G*. **Group:** A non-empty set *G* together with an operation + is called a group, if the following conditions are satisfied: 1. **Cl...

## Linear Algebra ### Group Theory **Def:** Let *G* be a non-empty set, any map *f*: *G* x *G* → *G* is called a binary operation on *G* or binary composition in *G*. **Group:** A non-empty set *G* together with an operation + is called a group, if the following conditions are satisfied: 1. **Closure property**: i.e., ∀ *a*, *b* ∈ *G*, *a* x *b* ∈ *G* 2. **Associativity**: (*a* x *b*) x *c* = *a* x (*b* x *c*) ∀ *a*, *b*, *c* ∈ *G*. 3. **Existence of Identity**: There exists an element *e* ∈ *G* s.t. *a* x *e* or *e* x *a* = *a* ∀ *a* ∈ *G. 4. **Existence of Inverse**: i.e., for every *a*∈*G*, there exists an element *a' ∈ G* s.t. *a* x *a'* = *a'* x *a* = *e* ∀ *a* ∈ *G. Then *G* is called a group w.r.t *x*. **Algebraic structure:** (*I*N, +) A set with a composition. A group is always an algebraic structure. (*I*N, +) is not a group, because *a* ∈ *I*N *a* x *e* = *a* *e* = 0 ∈ *I*N (*I*N, -) is not a group because the inverse does not exist. **Q** *G* = {1, *i*, -1, -*i*}, w.r.t (*G*, *) So, this is a group **Q. Prove that all positive rational numbers form a group under the composition defined by:** *a* x *b* = *ab*/*2* (∀ *a*, *b* ∈ *Q*+) **Sol.** 1. **Closure**: ∀ *a*, *b* ∈ *Q*+, *a* x *b* = *ab*/*2* ∈ *Q*+ 2. **Associative**: Let *a*, *b*, *c* ∈ *Q*+ (*a* x *b*) x *c* = (*ab*/*2*) x *c* = (*ab*c)/*4* = *a* x (*b* x *c*) *a* (*bc*/*2*) = *a*(*bc*/*2*) = *a*(*bc*/*2*) ∴ Associativity holds in *Q*+. 3. **Existence of Identity**: ∀ *a* x *b* = *a* *a* x *b* = *a* *ab*/*2* = *a* *ab* = *2a* *b* = *2* ∈ *Q*+ ⇒ Rational No. 4. **Existence of Inverse**: ∀ *a* x *b* = *2* *ab*/*2* = *2* *ab*= *4* *b* = *4*/*a* ∈ *Q*+ **Q** 1. **Natural No:** *I*N 2. **Integers:** *Z* 3. **Rational No:** *Q* 4. **Real No:** *R* 5. **Complex No:** *C* **Abelian Group:** A group *G* within binary composition (*G*, *) is said to be Abelian if binary composition is commutative in *G*. i.e. *a* x *b* = *b* x *a* ∀ *a*, *b* ∈ *G*. **Q** *G* = {1, *ω*, *ω*²}, (*G, +) [1 + *ω* + *ω*² = 0 & 1 - *ω* *ω*² = 1] It is an Abelian group. **Q. Show that the set *G* = {..., -4*m*, -3*m*, -2*m*, -*m*, 0, *m*, *2m*, *3m*, *4m*, ...} of multiples of integers by a fixed integer '*m*' is a group w.r.t addition (+).** 1. **Closure**: Let *a*, *b* ∈ *G* *A* = *r*m & *b* = *s*m; *r*, *s* ∈ *Z*. *a* + *b* = (*r* + *s*)*m*. ∈ *G*. 2. **Associative**: Let *a*, *b*, *c*∈ *G*. Lit *a* = *r*₁*m*, *b* = *r*₂*m*, *c* = *r*₃*m*. *a* + (*b* + *c*) = *r*₁*m* + (*r*₂*m* + *r*₃*m*) (*a* + *b*) + *c* = (*r*₁*m* + *r*₂*m*) + *r*₃*m*. (*r*₁ + *r*₂ + *r*₃)*m* = (*r*₁ + *r*₂ + *r*₃)*m*. 3. **Identity**: Let *a* ∈ *G*. *a* = *r*m ∈ *G* *b* = -*r*m ∈ *G* *a* + *b* = 0, So it is a group. 4. **Inverse**: Let *a* ∈ *G* **Q. Show that the set of all positive rational numbers forms an Abelian group under the composition defied by:** *a* x *b* = *ab*/*4* **Q. Let 'R' be a set of all Real No. and *x* a binary composition on R defined by *a* x *b* = *a* + *b* + *ab*i* for *a*, *b* ∈ *R*. Also find the inverse of the identity element on *R*.** ### Properties of Group 1. **The identity element in a group is unique.** **Proof**: Let *e* & *e'* be two identity elements of group *G*. *G* = {..., *e*, *e'* ... } *e* x *e'* = *e'* *e = e'* *e'* x *e* = *e* *e = e'* 2. **The Inverse of each element of a group is unique.** **Proof**: Let *G* be a group with Identity *e'*. Let *a*∈ *G* be an element & *a* has two inverses say *b* and *c*. So- *a* x *b* = *b* x *a* = *e* - ① *a* x *c* = *c* x *a* = *e* - ② *b*(*a* x *c*) = *b* x *e* = *b* (*b* x *a*) x *c* = *e* x *c*. Since, *a*, *b*, *c* ∈ *G*. & associativity holds in *G*. ∴ *b* = *c*. 3. **Prove that (*ab*)**⁻¹** = *b*⁻¹*a*⁻¹** ∀ *a*, *b* ∈ *G*. i.e. inverse of product of two elements of a group *G*, is the product of the inverses taken in the reverse order. **Sol:** *G* → group. (*G*, *) (*G, *)¹ *a* x *a*⁻¹ *b* x *b*⁻¹ *ab* x (*ab*)⁻¹ *a*⁻¹ *b*⁻¹ (*ab*)⁻¹ (*ab*)⁻¹ = *b*⁻¹*a*⁻¹ **Proof**: *ab* (*a*⁻¹*b*⁻¹) = *a* (*b* *b*⁻¹)*a*⁻¹ = *a* *e* *a*⁻¹ = *a* *a*⁻¹ = *e* - ①. (*b*⁻¹*a*⁻¹) (*ab*) = *b*⁻¹ *a*⁻¹ (*a* *b*) = *b*⁻¹ *e* *b* = *b*⁻¹ *b* = *e* -② ∴ (*ab*)⁻¹ = *b*⁻¹*a*⁻¹ **# The inverse of an identity element is the identity itself** ∀ *a* ∈ *G* Then *e*⁻¹ = *e* **Q** (x² - 1) (x² + 1) = 0 (x² - 1) = 0, (x² + 1) = 0 x² = 1, x² = -1 x = ±1, x = ±√-1 = ±*i* *G* = {-1, 1, *i*, -*i*} **Identity**: |-1 | 1 | *i* | -*i*| |---|---|---|---:|---| |1| 1| -1| *i* | -*i*| |-1| -1 | 1 | -*i* | *i* | |*i*| *i* | -*i* | -1 | 1| |-i| -*i* | *i* | 1 | -1 | (1)¹ = 1 (-1)¹ = - 1 (*i*)¹ = -*i* (-*i*)¹ = *i* **# Addition and Multiplication Modulo:** → 3 + 8 = 1 - (Remainder) 23 + 10 = 5 **Multiplication modulo:** 5 x 4 = 5 = 1 3 x 8 = 4 23 x 10 = 6 **Q. Prove that *Z*₄ = {0, 1, 2, 3} is an Abelian group w.r.t add" modulo 4. *Z*₄ = {0, 1, 2, 3} **Composition Table:** |+|0 | 1| 2 | 3| |---|---|---|---|---| |0| 0 | 1 | 2 | 3 | |1| 1 | 2 | 3 | 0 | |2 | 2 | 3 | 0 | 1 | |3| 3 | 0 | 1 | 2 | ①**Closure**: All the elements in the table are elements of *Z*₄. ②**Associative**: (1 + 4₂ ) + 4₃ = 1 + (2 + 4₃) = 3 + 4₃ = 2 = 1 + 4(1) = 2 **# Composition Table** **Q. Show that the four fourth roots of unity form a group w.r.t multiplication.** **Sol.** Four roots of unity = {1, -1, *i*, -*i*} *G* = { 1, -1, *i*, -*i*}. ① **Closure**: Satisfied ② **Associativity**: - (1 x *i*) x (*i*) = 1 x (*i*²)= -1 - 1 x (*i* x *i*) = 1 x (-1) = -1 - 1 x (-*i*) = (-1) x (-*i*) = *i*. - (-*i*) x *i* = (-1) x *i* = -*i* ③ **Inverse**: - (1)⁻¹ = 1 - (-1)⁻¹ = -1 - (*i*)⁻¹ = -*i* - (-*i*)⁻¹ = *i* **Q. Show that the set of six transformations *f*₁, *f*₂, *f*₃, *f*₄, *f*₅, *f*₆, on the set of complex No. defined by *f*₁(z) = *z*, *f*₂(z) = 1, *f*₃(z) = 1 - *2z*, *f*₄(z) = *z*², *f*₅(z) = *z*⁻¹, *f*₆(z) = *2z*, forms a finite non-abelian group of order 6 w.r.t the composition known as the composition or product of two functions.** *G* = {*f*₁, *f*₂, *f*₃, *f*₄, *f*₅, *f*₆} <start_of_image> *(f*i* *f*j* )(z) = *(f*i* (*f*j*(z))) *f₁f₁*(z) = *f₁*(*f₁*(z)) = *z* *f₂f₃*(z) = *f₂*(*f₃*(z)) = *f₂*(1 - *2z*) = 1 - *2z* = *f₃* *f₁f₃*(z) = *f₁*(*f₃*(z)) = *f₁*(1 - *2z*) => 1 - *2z* = *f₃* *f₁f₄*(z) = *f₁*(*f₄*(z)) = *f₁*(*z*²) = *z*² = *f₄* *f₁f₅*(z) = *f₁*(*f₅*(z)) = *f₁*(*z*⁻¹) = *z*⁻¹ => *z*⁻¹ = *f₅* *f₁f₆*(z) = *f₁*(*f₆*(z)) = *f₁*(*2z*) = *2z* = *f₆* *f₂f₄*(z) = *f₂*(*f₄*(z)) = *f₂*(*z*²) = *z*² = *f₄* *f₂f₅*(z) = *f₂*(*f₅*(z)) = *f₂*(*z*⁻¹) = *z*⁻¹ => *z*⁻¹ = *f₅* *f₂f₆*(z) = *f₂*(*f₆*(z)) = *f₂*(*2z*) = *2z* = *f₆* *f₄f₄*(z) = *f₄*(*f₄*(z)) = *f₄*(*z*²) = *z*⁴ = (*z*²)² = *z*⁻¹ => *z*⁻¹ = *f₅* *f₁f₅*(z) = *f₁*(*f₅*(z)) = *f₁*(*z*⁻¹) = *z*⁻¹ = *z*⁻¹ => *z*⁻¹ = *f₅* *f₁f₆*(z) = *f₁*(*f₆*(z)) = *f₁*(*2z*) = *2z* = *f₆* *f₂f₆*(z) = *f₂*(*f₆*(z)) = *f₂*(*2z*) = *2z* = *f₆* **# Addition Modulo 'm':** *a* + *m* *b* for two integers *a* + *m* *b*, where *r* lies between 0 ≤ *r* < *m*, where *r* is the least non-negative integer (Remainder) when *a* + *b* is divided by *m*. 5 + 4 *7 = 6 5 * 5 *7 = 2 1. If *a* & *b* are two integers such that *a* - *b* is divisible by *m*, *m* is fixed the integer, then we write: *a* = *b* (mod *m*) and read as (*a* congruent to *b* mod (*m*)). **Q. Prove that the set *G*={0, 1, 2, 3, 4, 5} is a finite Abelian group of order 6 w.r.t. add” modulo 6.** **Sol.** *G*={0, 1, 2, 3, 4, 5} *G* = {0, 1, 2, 3, 4, 5}. (*G, +₆*) **Composition Table:** |+|0 | 1| 2 | 3| 4 | 5 | |---|---|---|---|---|---|---| |0| 0 | 1 | 2 | 3 | 4 | 5 | |1| 1 | 2 | 3 | 4 | 5 |0| |2 | 2 | 3 | 4 | 5 | 0 | 1| |3| 3 | 4 | 5 | 0 | 1 | 2 | |4 | 4 | 5 | 0 | 1 | 2 | 3 | |5| 5 | 0 | 1 | 2 | 3 | 4 | 1. **This is closure**: 2. **Associativity**: (*a* +₆ *b*) +₆ *c* = *a* +₆ (*b* +₆ *c*) → least +ve integer when (*a* + *b*) + *c* is divided by 6. => (*a* +₆ *b*) +₆ *c* = *a* +₆ *b* +₆ *c* 3. **Identity**: 0 ∈ *G*, 0 is the identity. 4. **Inverse**: - (0)⁻¹ = 0 - (1)⁻¹ = 5 - (2)⁻¹ = 4 - (3)⁻¹ = 3 - (4)⁻¹ = 2 - (5)⁻¹ = 1 5. **For Abelian group**: *a* +₆ *b* = *b* +₆ *a* Hence *G* is an Abelian group under addition. **# Multiplication: *X*₇ → {1, 2, 3, 4, 5, 6}** **Q. Prove that the set *G* = {1, 2, 3, 4, 5, 6} is a finite Abelian group of order 6 w.r.t. multiplication modulo 7.** *G* = {1, 2, 3, 4, 5, 6}. (*G, *) | | 1 | 2 | 3 | 4 | 5 | 6 | |---|---|---|---|---|---|---| |1 | 1 | 2 | 3 | 4 | 5 | 6 | |2 | 2 | 4 | 6 | 1 | 3 | 5 | |3 | 3 | 6 | 2 | 5 | 1 | 4 | |4 | 4 | 1 | 5 | 2 | 6 | 3 | |5 | 5 | 3 | 1 | 6 | 4 | 2 | |6 | 6 | 5 | 4 | 3 | 2 | 1 | 1. **Closure**: ∀ *a* ∈ *G*. 2. **Associativity**: (*a* x *b*) x *c* = *a* x (*b* x *c*) ⇒ *a* x *b* ∈ *G*. Yes it is satisfied. 3. **Identity**: 1 is the identity. 4. **Inverse**: - (1)⁻¹ = 1 - (2)⁻¹ = 4 - (3)⁻¹ = 5 - (4)⁻¹ = 2 - (5)⁻¹ = 3 - (6)⁻¹ = 6 5. **Commutative**: *a* x *b* = *b* x *a* Hence (*G, *) is an Abelian group. ### Quaternion Group: A group whose elements are *T*={±1, ±*i*, ±*j*, ±*k*} under multiplication where *i*, *j*, *k* are all unit vectors. *i*² = *j*² = *k*² = -1 *i* x *j* = -*j* x *i* = *k* *j* x *k* = -*k* x *j* = *i* *k* x *i* = -*i* x *k* = *j* *G*= | | | |---|---| |{1} | {0 1 |0 1 | | {0 -i | {0 0} {0 0 } {i 0 } {-i 0} { -1 0 } {0 0} {0 0} {0 -i} {0 i} {0 1} {0 -1} {0 0} {0 0} { 0 0} {0 0} { 0 0} | | {0 0} | { 0 0} | Let *G* = {*M*₁, ..., *M*₄₃}, under multiplication M *G* = {*M*₁, *M*₂, *M*₃, *M*₄, *M*₅, *M*₆, *M*₇, *M*₈} M₁ M₂ M₃ M₄ M₅ M₆ M₇ M₈ M₁ M₂ M₃ M₄ M₅ M₆ M₇ M₈ M₂ M₂ M₁ M₄ M₃ M₅ M₆ M₇ M₈ M₃ M₃ M₄ M₁ M₆ M₅ M₈ M₇ M₄ M₄ M₅ M₆ M₁ M₇ M₈ M₂ M₅ M₅ M₆ M₇ M₈ M₂ M₁ M₄ M₆ M₆ M₇ M₈ M₁ M₂ M₃ M₇ M₇ M₈ M₂ M₃ M₄ M₁ M₈ M₈ M₁ M₂ M₃ M₄ M₅ M₆ M₇ *M*₁ = |1 |0| |0| 1| *M*₂*M*₃ = | -1 |0| |0| 1| *x* |0| 0| *x* |0| 0| 0| *x* | {i 0| |0| 0| -1| *x* |0| 0| 0| *x* | {0| | 0 0 | 0| |0| 0| 0| *x* | {0| |0| 0| 0| *x* | {0| | 0 0 | 0| 0| *x* | |0 0 | 0| 0 | *x* | 0| |0 0 | 0| 0 | *x* | 0| |0| 0| 0| *x* | | 0| 0| 0| 0| 0 0| |0| 0| 0| 0| *x* |0| 0| 0| 0|*x* | |0| 0| 0| 0| *x* => *M*₁ = *M*₄ *M*₃*M*₄ = | 0 | 0 | |0| 0| *x* |0| 0| -1| *x* |0| 0| 0| *x* | { 0 0 | |0| 0| 0| *x* | *x* |0| 0| 0| *x* | *x* {0 0| |0| 0| 0| *x* | 0| *x* |0| 0| 0| *x* | 0| |0| 0| 0| *x* | 0| 0| |0| 0| 0| *x* | 0| 0| | 0| 0| 0| *x* | 0| 0| |0| 0| 0| *x* | 0| *x* |0| 0| 0| *x* | 0| 0| | 0 0 | 0| 0|*x* | 0| 0| |0| 0| 0| 0| 0| *x* |0| 0| 0| 0 | 0| *x* |0| 0| 0| 0| 0| *x* = *M*₁ → It is not commutative: *a* x *b* ≠ *b* x *a*. **Q. Show that the set of matrices *A*x = [ *cos*x *sin*x 0 -*sin*x *cos*x 0 0 0 1 ] where *x* is a real no. forms a group under matrix multiplication.** **Q. Show that the set of 4 transformations *f*₁, *f*₂, *f*₃, *f*₄ on the set of complex numbers defined by: *f*₁(z) = *z*, *f*₂(z) = -*z*, *f*₃(z) = 1, *f*₄(z) = -1 forms a finite Abelian group w.r.t composite composition (*f*1*f*2* = *f*1 o *f*2*)** **Q. Prove that the set {1, 3, 4, 5, 9} is an Abelian group under multiplication modulo 11.** *G₅* = {1, 3, 4, 5, 9} **Composition Table:** | ×₁₁| 1| 3 | 4 | 5 | 9 | |---|---|---|---|---|---| |1| 1| 3 | 4 | 5 | 9 | |3| 3| 9 | 1 | 4 | 5 | |4 | 4 | 1 | 5 | 9 | 3 | |5| 5 | 4 | 9 | 3 | 1 | |9| 9 | 5 | 3 | 1 | 4 | 1.**Closure:** Since all elements belong to the set *G*₅. Hence, it is satisfied 2. **Associative**: Let *a*, *b*, *c* ∈ *G*₅. *a* x₁₁ (*b* x₁₁ *c*) = 1 x₁₁ (3 x₁₁ 4) = 3 x₁₁ 4 =1 = 1 x₁₁ 12 = 1 3. **Identity**: 1 4. **Inverse**: - (1)⁻¹ = 1 - (3)⁻¹ = 4 - (4)⁻¹ = 3 - (5)⁻¹ = 9 - (9)⁻¹ = 5 5. **Commutative**: *a* x₁₁ *b* = *b* x₁₁ *a*. Given, *G*₅ = {*f*₁*f*₂, *f*₁*f*₃*f*₄*f*₅*f*₆} # Permutations Let *S* be a finite set having *n* distinct elements. Then, a one-one mapping of *S* onto itself is called a permutation of degree *n*. S = {*a*₁, **a*₂, *a*₃, ..., *a*n*} *f*: *S* onto *S* *f* *b* *e* *y* An element *a* ∈ *b* s.t. *f*(a) = *b* **Symbol:** *S* = { *b*₁, *b*₂, - - - *b*n} { *a*₁, *a*₂, - - - *a*n} *b*₁, *b*₂ - - - *b*n *f*g = | 1 |2 |3 |4 | |---|---|---|---| |2 | 3 | 4 |1 | *g* = | 1 |2 |3 | 4| |---|---|---|---| | 1 | 3 | 2 | 4 | For *S* having *n* elements, there exists *n*! permutations. *S* = {1, 2, 3}. 3! = 6. (1 2 3) (1 3 2) (1 2 3) (1 2 3) (1 3 2) (1 2 3) ### Identity Permutations *S* = {1, 2, 3} *S*₂ {*a*₁, *a*₂, *a*₃, .... *a*n} { *a*₁, *a*₂, - - - *a*n} ### Composite Permutation/ *f* = (2 1 3 4) *g* = (1 2 3 4) *f*(1) = 2 *f*(2) = 1 *f*(3) = 4 *f*(4) = 3 *g*(1) = 2 *g*(2) = 3 *g*(3) = 4 *g*(4) = 1 *f*g = *f* o *g*(1) = *f*(*g*(1)) = *f*(2) = 1 *f*g = *f* o *g*(2) = *f*(*g*(2)) = *f*(3) = 4 *f*g = *f* o *g*(3) = *f*(*g*(3)) = *f*(4) = 3 *f*g = *f* o *g*(4) = *f*(*g*(4)) = *f*(1) = 2 *f* and *g* are two permutation belong to *P*n then *f*g ∈ *P*n. *P*n = {set of all permutations of order *n*}. If *n* ≥ 4, *P*n ≥ 24. *f*, *g* ∈ *P*n *f*g ∈ *P*n **Prove that *P*n is a group but not an Abelian group, of order *n* w.r.t. composite of mappings as binary operation.** ### Inverse Permutation: *f* = (*b₁* *b₂* - - - *b*n) *f*⁻¹ = (*a₁* *a₂* - - - *a*n) *f*f*⁻¹ = (*a₁* *a₂* - - - *a*n) = *I* → **Closure**: Let *a*, *b* ∈ *G*. *ab* ∈ *G*. Hence its satisfied. →**Associative**: Let *a*, *b*, *c* ∈ *G*. ⇒ *a* x (*b* x *c*) = (*a* x *b*) x *c* => *abc* = *abc* *I* = => *abc* *I* = *abc* *I* →**Identity**: Let *a* ∈ *G*. ⇒ *a* x *e* = *a*. => *a* x *e*⁻¹ = *a*⁻¹ *e*⁻¹ *e* = *I* ∈ *G*. →**Inverse**: Let *a* ∈ *G*. ⇒ *a*⁻¹*a* = *e* *a* x *a*⁻¹ = *e* a⁻¹ ∈ *G*. ### Cyclic Permutations: Let *f* be a permutation of degree * n* on a set *S* having *n* distinct elements. Let it be possible to arrange *m* elements of the set *S* in a row in such a way that, - each element in the row follows it, the image of the last element is the first element and - the remaining *n - m* elements of *S* are unchanged by *f*. Then, *f* is called a cyclic permutation of the cycle of length *m* or *m* - cycle. *f* = | 1 | 2 | 5| 3| 6 | 4 | |---|---|---|---|---|---| | 2 | 4 | 5 | 1 | 6 | 3| ⇒ (1 2 4 3) (1 2 4 3) (1 2 3 4 5 6) (2 1 3 4 5 6) (3 6 4 2 5 1) **Q: Express cycle in form of permutations:** (1 3 4 2 6) (1 2 3 4 5 6) (3 6 4 2 5 1) (1 3 4 2 6 5) (3 4 2 6 1 5) (3 6 4 2 5 1) **# A cycle does not change by changing order of element, provided standard cyclic order is not changed.** (2 4 1 3) (2 4 1 3) **# Transposition:** A cycle of length 2 is called transposition. (1 2 3 4 5 6) (2 1 3 4 5 6) **# Multiplication of cycles:** (1 2 3) ( 5 6 4 1) |1 | 2 | 3 | 4 | 5 | 6 | |---|---|---|---|---|---| |2 | 3| 4| 5 | 6 | 1| |1 | 2 | 3 | 4 | 5 | 6 | |2 | 3 | 1| 4 | 5 | 6 | |2 | 3 | 4 | 5| 6 | 1 | (2 3 5 1 6 4) **Q. (1 3 2 5)