Inmathematics, specificallygroup theory, asubgroupH of agroupG may be used to decompose the underlyingset ofG intodisjoint, equal-sizesubsets calledcosets. There areleft cosets andright cosets. Cosets (both left and right) have the same number of elements (cardinality) as doesH. Furthermore,H itself is both a left coset and a right coset. The number of left cosets ofH inG is equal to the number of right cosets ofH inG. This common value is called theindex ofH inG and is usually denoted by[G :H].
Cosets are a basic tool in the study of groups; for example, they play a central role inLagrange's theorem that states that for anyfinite groupG, the number of elements of every subgroupH ofG divides the number of elements ofG. Cosets of a particular type of subgroup (anormal subgroup) can be used as the elements of another group called aquotient group or factor group. Cosets also appear in other areas of mathematics such asvector spaces anderror-correcting codes.
LetH be a subgroup of the groupG whose operation is written multiplicatively (juxtaposition denotes the group operation). Given an elementg ofG, theleft cosets ofH inG are the sets obtained by multiplying each element ofH by a fixed elementg ofG (whereg is the left factor). In symbols these are,
Theright cosets are defined similarly, except that the elementg is now a right factor, that is,
Asg 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 isabelian, the notation used changes tog +H orH +g, respectively.
The symbolG/H is sometimes used for the set of (left) cosets {gH :g an element ofG} (see below for a extension to right cosets and double cosets). However, some authors (including Dummit & Foote and Rotman) reserve this notation specifically for representing thequotient group formed from the cosets in the case whereH is anormal subgroup ofG.
LetG be thedihedral group of order six. Its elements may be represented by{I,a,a2,b,ab,a2b}. In this group,a3 =b2 =I andba =a2b. This is enough information to fill in the entireCayley 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 |
LetT be the subgroup{I,b}. The (distinct) left cosets ofT are:
Since all the elements ofG 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 ofT are:
In this example, except forT, no left coset is also a right coset.
LetH be the subgroup{I,a,a2}. The left cosets ofH areIH =H andbH = {b,ba,ba2}. The right cosets ofH areHI =H andHb = {b,ab,a2b} = {b,ba2,ba}. In this case, every left coset ofH is also a right coset ofH.[2]
LetH be a subgroup of a groupG and suppose thatg1,g2 ∈G. The following statements are equivalent:[3]
The disjointness of non-identical cosets is a result of the fact that ifx belongs togH thengH =xH. For ifx ∈gH then there must exist ana ∈H such thatga =x. ThusxH = (ga)H =g(aH). Moreover, sinceH is a group, left multiplication bya is a bijection, andaH =H.
Thus every element ofG belongs to exactly one left coset of the subgroupH,[1] andH is itself a left coset (and the one that contains the identity).[2]
Two elements being in the same left coset also provide a naturalequivalence relation. Define two elements ofG,x andy, to be equivalent with respect to the subgroupH ifxH =yH (or equivalently ifx−1y belongs toH). Theequivalence classes of this relation are the left cosets ofH.[4] As with any set of equivalence classes, they form apartition of the underlying set. Acoset representative is arepresentative in the equivalence class sense. A set of representatives of all the cosets is called atransversal. There are other types of equivalence relations in a group, such as conjugacy, that form different classes which do not have the properties discussed here.
Similar statements apply to right cosets.
IfG is anabelian group, theng +H =H +g for every subgroupH ofG and every elementg ofG. For general groups, given an elementg and a subgroupH of a groupG, the right coset ofH with respect tog is also the left coset of theconjugate subgroupg−1Hg with respect tog, that is,Hg =g(g−1Hg).
A subgroupN of a groupG is anormal subgroup ofG if and only if for all elementsg ofG the corresponding left and right cosets are equal, that is,gN =Ng. This is the case for the subgroupH in the first example above. Furthermore, the cosets ofN inG form a group called thequotient group or factor groupG / N.
IfH is notnormal inG, then its left cosets are different from its right cosets. That is, there is ana inG such that no elementb satisfiesaH =Hb. This means that the partition ofG into the left cosets ofH is a different partition than the partition ofG into right cosets ofH. This is illustrated by the subgroupT in the first example above. (Some cosets may coincide. For example, ifa is in thecenter ofG, thenaH =Ha.)
On the other hand, if the subgroupN is normal the set of all cosets forms a group called the quotient groupG / 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".
Every left or right coset ofH has the same number of elements (orcardinality in the case of aninfiniteH) asH itself. Furthermore, the number of left cosets is equal to the number of right cosets and is known as theindex ofH inG, written as[G :H].Lagrange's theorem allows us to compute the index in the case whereG andH are finite:This equation can be generalized to the case where the groups are infinite.
LetG be theadditive group of the integers,Z = ({..., −2, −1, 0, 1, 2, ...}, +) andH the subgroup(3Z, +) = ({..., −6, −3, 0, 3, 6, ...}, +). Then the cosets ofH inG are the three sets3Z,3Z + 1, and3Z + 2, where3Z +a = {..., −6 +a, −3 +a,a, 3 +a, 6 +a, ...}. These three sets partition the setZ, so there are no other right cosets ofH. Due to thecommutativity of additionH + 1 = 1 +H andH + 2 = 2 +H. That is, every left coset ofH is also a right coset, soH is a normal subgroup.[5] (The same argument shows that every subgroup of an Abelian group is normal.[6])
This example may be generalized. Again letG be the additive group of the integers,Z = ({..., −2, −1, 0, 1, 2, ...}, +), and now letH the subgroup(mZ, +) = ({..., −2m, −m, 0,m, 2m, ...}, +), wherem is a positive integer. Then the cosets ofH inG are them setsmZ,mZ + 1, ...,mZ + (m − 1), wheremZ +a = {..., −2m +a, −m +a,a,m +a, 2m +a, ...}. There are no more thanm cosets, becausemZ +m =m(Z + 1) =mZ. The coset(mZ +a, +) is thecongruence class ofa modulom.[7] The subgroupmZ is normal inZ, and so, can be used to form the quotient groupZ / mZ the group ofintegers modm.
Another example of a coset comes from the theory ofvector spaces. The elements (vectors) of a vector space form anabelian group undervector addition. Thesubspaces of the vector space aresubgroups of this group. For a vector spaceV, a subspaceW, and a fixed vectora inV, the setsare calledaffine subspaces, and are cosets (both left and right, since the group is abelian). In terms of 3-dimensionalgeometric vectors, these affine subspaces are all the "lines" or "planes"parallel to the subspace, which is a line or plane going through the origin. For example, consider theplaneR2. Ifm is a line through the originO, thenm is a subgroup of the abelian groupR2. IfP is inR2, then the cosetP +m is a linem′ parallel tom and passing throughP.[8]
LetG be the multiplicative group of matrices,[9]and the subgroupH ofG,For a fixed element ofG consider the left cosetThat is, the left cosets consist of all the matrices inG having the same upper-left entry. This subgroupH is normal inG, but the subgroupis not normal inG.
A subgroupH of a groupG can be used to define anaction ofH onG in two natural ways. Aright action,G ×H →G given by(g,h) →gh or aleft action,H ×G →G given by(h,g) →hg. Theorbit ofg under the right action is the left cosetgH, while the orbit under the left action is the right cosetHg.[10]
The concept of a coset dates back toGalois's work of 1830–31. He introduced a notation but did not provide a name for the concept. The term "co-set" apparently appears for the first time in 1910 in a paper by G. A. Miller in theQuarterly Journal of Pure and Applied Mathematics (vol. 41, p. 382). Various other terms have been used including the GermanNebengruppen (Weber) andconjugate group (Burnside).[11] (Note that Miller abbreviated his self-citation to theQuarterly Journal of Mathematics; this does not refer to thejournal of the same name, which did not start publication until 1930.)
Galois was concerned with deciding when a givenpolynomial equation wassolvable by radicals. A tool that he developed was in noting that a subgroupH of a group ofpermutationsG induced two decompositions ofG (what we now call left and right cosets). If these decompositions coincided, that is, if the left cosets are the same as the right cosets, then there was a way to reduce the problem to one of working overH instead ofG.Camille Jordan in his commentaries on Galois's work in 1865 and 1869 elaborated on these ideas and defined normal subgroups as we have above, although he did not use this term.[6]
Calling the cosetgH theleft coset ofg with respect toH, while most common today,[10] has not been universally true in the past. For instance,Hall (1959) would callgH aright coset, emphasizing the subgroup being on the right.
A binary linear code is ann-dimensional subspaceC of anm-dimensional vector spaceV over the binary fieldGF(2). AsV 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 acodeword (element ofC) 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 corruptedreceived word could have started out as. This procedure is calleddecoding 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 ofV (a received word could be any element ofV) into astandard array. A standard array is a coset decomposition ofV put into tabular form in a certain way. Namely, the top row of the array consists of the elements ofC, written in any order, except that the zero vector should be written first. Then, an element ofV with a minimal number of ones that does not already appear in the top row is selected and the coset ofC containing this element is written as the second row (namely, the row is formed by taking the sum of this element with each element ofC directly above it). This element is called acoset 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 ofC containing it is the next row. The process ends when all the vectors ofV have been sorted into the cosets.
An example of a standard array for the 2-dimensional codeC = {00000, 01101, 10110, 11011} in the 5-dimensional spaceV (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 ofC. 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.
Syndrome decoding can be used to improve the efficiency of this method. It is a method of computing the correct coset (row) that a received word will be in. For ann-dimensional codeC in anm-dimensional binary vector space, aparity check matrix is an(m −n) ×m matrixH having the property thatxHT =0if and only ifx is inC.[12] The vectorxHT is called thesyndrome ofx, and bylinearity, every vector in the same coset will have the same syndrome. To decode, the search is now reduced to finding the coset leader that has the same syndrome as the received word.[13]
Given two subgroups,H andK (which need not be distinct) of a groupG, thedouble cosets ofH andK inG are the sets of the formHgK = {hgk :h an element ofH,k an element ofK}. These are the left cosets ofK and right cosets ofH whenH = 1 andK = 1 respectively.[14]
Two double cosetsHxK andHyK are either disjoint or identical.[15] The set of all double cosets for fixedH andK form a partition ofG.
A double cosetHxK contains the complete right cosets ofH (inG) of the formHxk, withk an element ofK and the complete left cosets ofK (inG) of the formhxK, withh inH.[15]
LetG be a group with subgroupsH andK. Several authors working with these sets have developed a specialized notation for their work, where[16][17]