Coset
![](http://upload.wikimedia.org/wikipedia/commons/thumb/d/d4/Left_cosets_of_Z_2_in_Z_8.svg/220px-Left_cosets_of_Z_2_in_Z_8.svg.png)
In mathematics, specifically group theory, a subgroup H of a group G may be used to decompose the underlying set of G into disjoint, equal-size subsets called cosets. There are left cosets and right cosets. Cosets (both left and right) have the same number of elements (cardinality) as does H. Furthermore, H itself is both a left coset and a right coset. The number of left cosets of H in G is equal to the number of right cosets of H in G. This common value is called the index of H in G and is usually denoted by [G : H].
Cosets are a basic tool in the study of groups; for example, they play a central role in
Definition
Let H be a subgroup of the group G whose operation is written multiplicatively (juxtaposition denotes the group operation). Given an element g of G, the left cosets of H in G are the sets obtained by multiplying each element of H by a fixed element g of G (where g is the left factor). In symbols these are,
The right cosets are defined similarly, except that the element g is now a right factor, that is,
As g varies through the group, it would appear that many cosets (right or left) would be generated. Nevertheless, it turns out that any two left cosets (respectively right cosets) are either disjoint or are identical as sets.[1]
If the group operation is written additively, as is often the case when the group is abelian, the notation used changes to g + H or H + g, respectively.
First example
Let G be the dihedral group of order six. Its elements may be represented by {I, a, a2, b, ab, a2b}. In this group, a3 = b2 = I and ba = a2b. This is enough information to fill in the entire Cayley table:
∗ | I | a | a2 | b | ab | a2b |
---|---|---|---|---|---|---|
I | I | a | a2 | b | ab | a2b |
a | a | a2 | I | ab | a2b | b |
a2 | a2 | I | a | a2b | b | ab |
b | b | a2b | ab | I | a2 | a |
ab | ab | b | a2b | a | I | a2 |
a2b | a2b | ab | b | a2 | a | I |
Let T be the subgroup {I, b}. The (distinct) left cosets of T are:
- IT = T = {I, b},
- aT = {a, ab}, and
- a2T = {a2, a2b}.
Since all the elements of G have now appeared in one of these cosets, generating any more can not give new cosets; any new coset would have to have an element in common with one of these and therefore would be identical to one of these cosets. For instance, abT = {ab, a} = aT.
The right cosets of T are:
- TI = T = {I, b},
- Ta = {a, ba} = {a, a2b} , and
- Ta2 = {a2, ba2} = {a2, ab}.
In this example, except for T, no left coset is also a right coset.
Let H be the subgroup {I, a, a2}. The left cosets of H are IH = H and bH = {b, ba, ba2}. The right cosets of H are HI = H and Hb = {b, ab, a2b} = {b, ba2, ba}. In this case, every left coset of H is also a right coset of H.[2]
Let H be a subgroup of a group G and suppose that g1, g2 ∈ G. The following statements are equivalent:[3]
- g1H = g2H
- Hg1−1 = Hg2−1
- g1H ⊂ g2H
- g2 ∈ g1H
- g1−1g2 ∈ H
Properties
The disjointness of non-identical cosets is a result of the fact that if x belongs to gH then gH = xH. For if x ∈ gH then there must exist an a ∈ H such that ga = x. Thus xH = (ga)H = g(aH). Moreover, since H is a group, left multiplication by a is a bijection, and aH = H.
Thus every element of G belongs to exactly one left coset of the subgroup H,[1] and H is itself a left coset (and the one that contains the identity).[2]
Two elements being in the same left coset also provide a natural
Similar statements apply to right cosets.
If G is an
Normal subgroups
A subgroup N of a group G is a normal subgroup of G if and only if for all elements g of G the corresponding left and right cosets are equal, that is, gN = Ng. This is the case for the subgroup H in the first example above. Furthermore, the cosets of N in G form a group called the quotient group or factor group G / N.
If H is not normal in G, then its left cosets are different from its right cosets. That is, there is an a in G such that no element b satisfies aH = Hb. This means that the partition of G into the left cosets of H is a different partition than the partition of G into right cosets of H. This is illustrated by the subgroup T in the first example above. (Some cosets may coincide. For example, if a is in the center of G, then aH = Ha.)
On the other hand, if the subgroup N is normal the set of all cosets forms a group called the quotient group G / N with the operation ∗ defined by (aN) ∗ (bN) = abN. Since every right coset is a left coset, there is no need to distinguish "left cosets" from "right cosets".
Index of a subgroup
Every left or right coset of H has the same number of elements (or cardinality in the case of an infinite H) as H itself. Furthermore, the number of left cosets is equal to the number of right cosets and is known as the index of H in G, written as [G : H]. Lagrange's theorem allows us to compute the index in the case where G and H are finite:
More examples
Integers
Let G be the
This example may be generalized. Again let G be the additive group of the integers, Z = ({..., −2, −1, 0, 1, 2, ...}, +), and now let H the subgroup (mZ, +) = ({..., −2m, −m, 0, m, 2m, ...}, +), where m is a positive integer. Then the cosets of H in G are the m sets mZ, mZ + 1, ..., mZ + (m − 1), where mZ + a = {..., −2m + a, −m + a, a, m + a, 2m + a, ...}. There are no more than m cosets, because mZ + m = m(Z + 1) = mZ. The coset (mZ + a, +) is the
Vectors
Another example of a coset comes from the theory of
Matrices
Let G be the multiplicative group of matrices,[9]
As orbits of a group action
A subgroup H of a group G can be used to define an
History
The concept of a coset dates back to
Galois was concerned with deciding when a given
Calling the coset gH the left coset of g with respect to H, while most common today,[10] has not been universally true in the past. For instance, Hall (1959) would call gH a right coset, emphasizing the subgroup being on the right.
An application from coding theory
A binary linear code is an n-dimensional subspace C of an m-dimensional vector space V over the binary field GF(2). As V is an additive abelian group, C is a subgroup of this group. Codes can be used to correct errors that can occur in transmission. When a codeword (element of C) is transmitted some of its bits may be altered in the process and the task of the receiver is to determine the most likely codeword that the corrupted received word could have started out as. This procedure is called decoding and if only a few errors are made in transmission it can be done effectively with only a very few mistakes. One method used for decoding uses an arrangement of the elements of V (a received word could be any element of V) into a standard array. A standard array is a coset decomposition of V put into tabular form in a certain way. Namely, the top row of the array consists of the elements of C, written in any order, except that the zero vector should be written first. Then, an element of V with a minimal number of ones that does not already appear in the top row is selected and the coset of C containing this element is written as the second row (namely, the row is formed by taking the sum of this element with each element of C directly above it). This element is called a coset leader and there may be some choice in selecting it. Now the process is repeated, a new vector with a minimal number of ones that does not already appear is selected as a new coset leader and the coset of C containing it is the next row. The process ends when all the vectors of V have been sorted into the cosets.
An example of a standard array for the 2-dimensional code C = {00000, 01101, 10110, 11011} in the 5-dimensional space V (with 32 vectors) is as follows:
00000 | 01101 | 10110 | 11011 |
---|---|---|---|
10000 | 11101 | 00110 | 01011 |
01000 | 00101 | 11110 | 10011 |
00100 | 01001 | 10010 | 11111 |
00010 | 01111 | 10100 | 11001 |
00001 | 01100 | 10111 | 11010 |
11000 | 10101 | 01110 | 00011 |
10001 | 11100 | 00111 | 01010 |
The decoding procedure is to find the received word in the table and then add to it the coset leader of the row it is in. Since in binary arithmetic adding is the same operation as subtracting, this always results in an element of C. In the event that the transmission errors occurred in precisely the non-zero positions of the coset leader the result will be the right codeword. In this example, if a single error occurs, the method will always correct it, since all possible coset leaders with a single one appear in the array.
Double cosets
Given two subgroups, H and K (which need not be distinct) of a group G, the double cosets of H and K in G are the sets of the form HgK = {hgk : h an element of H, k an element of K}. These are the left cosets of K and right cosets of H when H = 1 and K = 1 respectively.[14]
Two double cosets HxK and HyK are either disjoint or identical.[15] The set of all double cosets for fixed H and K form a partition of G.
A double coset HxK contains the complete right cosets of H (in G) of the form Hxk, with k an element of K and the complete left cosets of K (in G) of the form hxK, with h in H.[15]
Notation
Let G be a group with subgroups H and K. Several authors working with these sets have developed a specialized notation for their work, where[16][17]
- G / H denotes the set of left cosets {gH : g in G} of H in G.
- H \ G denotes the set of right cosets {Hg : g in G} of H in G.
- K \ G / H denotes the set of double cosets {KgH : g in G} of H and K in G, sometimes referred to as double coset space.
- G // H denotes the double coset space H \ G / H of the subgroup H in G.
More applications
- Cosets of Q in R are used in the construction of Vitali sets, a type of non-measurable set.
- Cosets are central in the definition of the transfer.
- Cosets are important in computational group theory. For example, Thistlethwaite's algorithm for solving Rubik's Cuberelies heavily on cosets.
- In geometry, a properly discontinuously on the homogeneous spaceG / H.
See also
Notes
- ^ a b Rotman 2006, p. 156
- ^ a b Dean 1990, p. 100
- ^ "AATA Cosets". Archived from the original on 2022-01-22. Retrieved 2020-12-09.
- ^ Rotman 2006, p.155
- ^ Fraleigh 1994, p. 117
- ^ a b Fraleigh 1994, p. 169
- ^ Joshi 1989, p. 323
- ^ Rotman 2006, p. 155
- ^ Burton 1988, pp. 128, 135
- ^ a b Jacobson 2009, p. 52
- ^ Miller 2012, p. 24 footnote
- ^ The transpose matrix is used so that the vectors can be written as row vectors.
- ^ Rotman 2006, p. 423
- ^ Scott 1987, p. 19
- ^ a b Hall 1959, pp. 14–15
- ISBN 978-0-7923-5292-1
- S2CID 17839580
References
- Burton, David M. (1988), Abstract Algebra, Wm. C. Brown Publishers, ISBN 0-697-06761-0
- Dean, Richard A. (1990), Classical Abstract Algebra, Harper and Row, ISBN 0-06-041601-7
- Fraleigh, John B. (1994), A First Course in Abstract Algebra (5th ed.), Addison-Wesley, ISBN 978-0-201-53467-2
- Hall, Jr., Marshall (1959), The Theory of Groups, The Macmillan Company
- Jacobson, Nathan (2009) [1985], Basic Algebra I (2nd ed.), Dover, ISBN 978-0-486-47189-1
- Joshi, K. D. (1989), "§5.2 Cosets of Subgroups", Foundations of Discrete Mathematics, New Age International, pp. 322 ff, ISBN 81-224-0120-1
- Miller, G. A. (2012) [1916], Theory and Applications of Finite Groups, Applewood Books, ISBN 9781458500700
- Rotman, Joseph J. (2006), A First Course in Abstract Algebra with Applications (3rd ed.), Prentice-Hall, ISBN 978-0-13-186267-8
- Scott, W.R. (1987), "§1.7 Cosets and index", Group Theory, Courier Dover Publications, pp. 19 ff, ISBN 0-486-65377-3
Further reading
- ISBN 0-486-40922-8
External links
- Nicolas Bray. "Coset". MathWorld.
- Weisstein, Eric W. "Left Coset". MathWorld.
- Weisstein, Eric W. "Right Coset". MathWorld.
- Ivanova, O.A. (2001) [1994], "Coset in a group", Encyclopedia of Mathematics, EMS Press
- Coset at PlanetMath.
- Illustrated examples
- "Coset". groupprops. The Group Properties Wiki.