Coset

File:Left cosets of Z 2 in Z 8.svg

Template:Mvar is the group <math>\mathbb{Z}/8\mathbb{Z}</math>, the integers mod 8 under addition. The subgroup Template:Mvar contains only 0 and 4. There are four left cosets of Template:Mvar: Template:Mvar itself, Template:Math, Template:Math, and Template:Math (written using additive notation since this is the additive group). Together they partition the entire group Template:Mvar into equal-size, non-overlapping sets. The index Template:Math is 4.

In mathematics, specifically group theory, a subgroup Template:Mvar of a group Template:Mvar may be used to decompose the underlying set of Template:Mvar 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 Template:Mvar. Furthermore, Template:Mvar itself is both a left coset and a right coset. The number of left cosets of Template:Mvar in Template:Mvar is equal to the number of right cosets of Template:Mvar in Template:Mvar. This common value is called the index of Template:Mvar in Template:Mvar and is usually denoted by Template:Math.

Cosets are a basic tool in the study of groups; for example, they play a central role in Lagrange's theorem that states that for any finite group Template:Mvar, the number of elements of every subgroup Template:Mvar of Template:Mvar divides the number of elements of Template:Mvar. Cosets of a particular type of subgroup (a normal subgroup) can be used as the elements of another group called a quotient group or factor group. Cosets also appear in other areas of mathematics such as vector spaces and error-correcting codes.

Definition

Let Template:Mvar be a subgroup of the group Template:Mvar whose operation is written multiplicatively (juxtaposition denotes the group operation). Given an element Template:Mvar of Template:Mvar, the left cosets of Template:Mvar in Template:Mvar are the sets obtained by multiplying each element of Template:Mvar by a fixed element Template:Mvar of Template:Mvar (where Template:Mvar is the left factor). In symbols these are, Template:Block indent The right cosets are defined similarly, except that the element Template:Mvar is now a right factor, that is, Template:Block indent

As Template:Mvar 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.<ref name=Rotman2006>Template:Harvnb</ref>

If the group operation is written additively, as is often the case when the group is abelian, the notation used changes to Template:Math or Template:Math, respectively.

The symbol G/H is sometimes used for the set of (left) cosets {gH : g an element of G} (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 the quotient group formed from the cosets in the case where H is a normal subgroup of G.

First example

Let Template:Mvar be the dihedral group of order six. Its elements may be represented by Template:Math. In this group, Template:Math and Template:Math. This is enough information to fill in the entire Cayley table:

∗	Template:Mvar	Template:Mvar	Template:Math	Template:Mvar	Template:Mvar	Template:Math
Template:Mvar	Template:Mvar	Template:Mvar	Template:Math	Template:Mvar	Template:Mvar	Template:Math
Template:Mvar	Template:Mvar	Template:Math	Template:Mvar	Template:Mvar	Template:Math	Template:Mvar
Template:Math	Template:Math	Template:Mvar	Template:Mvar	Template:Math	Template:Mvar	Template:Mvar
Template:Mvar	Template:Mvar	Template:Math	Template:Mvar	Template:Mvar	Template:Math	Template:Mvar
Template:Mvar	Template:Mvar	Template:Mvar	Template:Math	Template:Mvar	Template:Mvar	Template:Math
Template:Math	Template:Math	Template:Mvar	Template:Mvar	Template:Math	Template:Mvar	Template:Mvar

Let Template:Mvar be the subgroup Template:Math. The (distinct) left cosets of Template:Mvar are:

• Template:Math,
• Template:Math, and
• Template:Math.

Since all the elements of Template:Mvar 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, Template:Math.

The right cosets of Template:Mvar are:

• Template:Math,
• Template:Math , and
• Template:Math.

In this example, except for Template:Mvar, no left coset is also a right coset.

Let Template:Mvar be the subgroup Template:Math. The left cosets of Template:Mvar are Template:Math and Template:Math. The right cosets of Template:Mvar are Template:Math and Template:Math. In this case, every left coset of Template:Mvar is also a right coset of Template:Mvar.<ref name=Dean>Template:Harvnb</ref>

Let Template:Mvar be a subgroup of a group Template:Mvar and suppose that Template:Math, Template:Math. The following statements are equivalent:<ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref>

• Template:Math
• Template:Math
• Template:Math
• Template:Math
• Template:Math

Properties

The disjointness of non-identical cosets is a result of the fact that if Template:Mvar belongs to Template:Math then Template:Math. For if Template:Math then there must exist an Template:Math such that Template:Math. Thus Template:Math. Moreover, since Template:Math is a group, left multiplication by Template:Mvar is a bijection, and Template:Math.

Thus every element of Template:Math belongs to exactly one left coset of the subgroup Template:Math,<ref name=Rotman2006 /> and Template:Math is itself a left coset (and the one that contains the identity).<ref name=Dean />

Two elements being in the same left coset also provide a natural equivalence relation. Define two elements of Template:Mvar, Template:Mvar and Template:Mvar, to be equivalent with respect to the subgroup Template:Mvar if Template:Math (or equivalently if Template:Math belongs to Template:Mvar). The equivalence classes of this relation are the left cosets of Template:Mvar.<ref>Template:Harvnb</ref> As with any set of equivalence classes, they form a partition of the underlying set. A coset representative is a representative in the equivalence class sense. A set of representatives of all the cosets is called a transversal. 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.

If Template:Math is an abelian group, then Template:Math for every subgroup Template:Math of Template:Math and every element Template:Mvar of Template:Math. For general groups, given an element Template:Mvar and a subgroup Template:Math of a group Template:Math, the right coset of Template:Math with respect to Template:Mvar is also the left coset of the conjugate subgroup Template:Math with respect to Template:Mvar, that is, Template:Math.

Normal subgroups

A subgroup Template:Math of a group Template:Math is a normal subgroup of Template:Math if and only if for all elements Template:Mvar of Template:Math the corresponding left and right cosets are equal, that is, Template:Math. This is the case for the subgroup Template:Mvar in the first example above. Furthermore, the cosets of Template:Math in Template:Math form a group called the quotient group or factor group Template:Math.

If Template:Math is not normal in Template:Math, then its left cosets are different from its right cosets. That is, there is an Template:Mvar in Template:Math such that no element Template:Mvar satisfies Template:Math. This means that the partition of Template:Math into the left cosets of Template:Math is a different partition than the partition of Template:Math into right cosets of Template:Math. This is illustrated by the subgroup Template:Mvar in the first example above. (Some cosets may coincide. For example, if Template:Mvar is in the center of Template:Math, then Template:Math.)

On the other hand, if the subgroup Template:Math is normal the set of all cosets forms a group called the quotient group Template:Math with the operation Template:Math defined by Template:Math. Since every right coset is a left coset, there is no need to distinguish "left cosets" from "right cosets".

Index of a subgroup

{{#invoke:Labelled list hatnote|labelledList|Main article|Main articles|Main page|Main pages}} Every left or right coset of Template:Math has the same number of elements (or cardinality in the case of an infinite Template:Math) as Template:Math itself. Furthermore, the number of left cosets is equal to the number of right cosets and is known as the index of Template:Math in G, written as Template:Math. Lagrange's theorem allows us to compute the index in the case where Template:Math and Template:Math are finite: <math display="block">|G| = [G : H]|H|.</math> This equation can be generalized to the case where the groups are infinite.

More examples

Integers

Let Template:Math be the additive group of the integers, Template:Math and Template:Math the subgroup Template:Math. Then the cosets of Template:Math in Template:Math are the three sets Template:Math, Template:Math, and Template:Math, where Template:Math. These three sets partition the set Template:Math, so there are no other right cosets of Template:Mvar. Due to the commutivity of addition Template:Math and Template:Math. That is, every left coset of Template:Mvar is also a right coset, so Template:Mvar is a normal subgroup.<ref>Template:Harvnb</ref> (The same argument shows that every subgroup of an Abelian group is normal.<ref name=Fraleigh>Template:Harvnb</ref>)

This example may be generalized. Again let Template:Math be the additive group of the integers, Template:Math, and now let Template:Math the subgroup Template:Math, where Template:Mvar is a positive integer. Then the cosets of Template:Math in Template:Math are the Template:Mvar sets Template:Math, Template:Math, ..., Template:Math, where Template:Math. There are no more than Template:Mvar cosets, because Template:Math. The coset Template:Math is the congruence class of Template:Mvar modulo Template:Mvar.<ref>Template:Harvnb</ref> The subgroup Template:Math is normal in Template:Math, and so, can be used to form the quotient group Template:Math the group of [[Integers mod n|integers mod Template:Math]].

Vectors

Another example of a coset comes from the theory of vector spaces. The elements (vectors) of a vector space form an abelian group under vector addition. The subspaces of the vector space are subgroups of this group. For a vector space Template:Math, a subspace Template:Math, and a fixed vector Template:Math in Template:Math, the sets <math display="block">\{\mathbf{x} \in V \mid \mathbf{x} = \mathbf{a} + \mathbf{w}, \mathbf{w} \in W\}</math> are called affine subspaces, and are cosets (both left and right, since the group is abelian). In terms of 3-dimensional geometric 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 the plane Template:Math. If Template:Mvar is a line through the origin Template:Mvar, then Template:Mvar is a subgroup of the abelian group Template:Math. If Template:Mvar is in Template:Math, then the coset Template:Math is a line Template:Math parallel to Template:Mvar and passing through Template:Mvar.<ref>Template:Harvnb</ref>

Matrices

Let Template:Mvar be the multiplicative group of matrices,<ref>Template:Harvnb</ref> <math display="block">G = \left \{\begin{bmatrix} a & 0 \\ b & 1 \end{bmatrix} \colon a, b \in \R, a \neq 0 \right\},</math> and the subgroup Template:Mvar of Template:Mvar, <math display="block">H= \left \{\begin{bmatrix} 1 & 0 \\ c & 1 \end{bmatrix} \colon c \in \mathbb{R} \right\}.</math> For a fixed element of Template:Mvar consider the left coset <math display="block">\begin{align} \begin{bmatrix} a & 0 \\ b & 1 \end{bmatrix} H = &~ \left \{\begin{bmatrix} a & 0 \\ b & 1 \end{bmatrix}\begin{bmatrix} 1 & 0 \\ c & 1 \end{bmatrix} \colon c \in \R \right\} \\ =&~ \left \{\begin{bmatrix} a & 0 \\ b + c & 1 \end{bmatrix} \colon c \in \mathbb{R}\right\} \\ =&~ \left \{\begin{bmatrix} a & 0 \\ d & 1 \end{bmatrix} \colon d \in \mathbb{R}\right\}. \end{align}</math> That is, the left cosets consist of all the matrices in Template:Mvar having the same upper-left entry. This subgroup Template:Mvar is normal in Template:Mvar, but the subgroup <math display="block">T= \left \{\begin{bmatrix} a & 0 \\ 0 & 1 \end{bmatrix} \colon a \in \mathbb{R} - \{0\} \right\}</math> is not normal in Template:Mvar.

As orbits of a group action

{{#invoke:Labelled list hatnote|labelledList|Main article|Main articles|Main page|Main pages}}

A subgroup Template:Mvar of a group Template:Mvar can be used to define an action of Template:Mvar on Template:Mvar in two natural ways. A right action, Template:Math given by Template:Math or a left action, Template:Math given by Template:Math. The orbit of Template:Mvar under the right action is the left coset Template:Mvar, while the orbit under the left action is the right coset Template:Mvar.<ref name=Jacobson>Template:Harvnb</ref>

History

The concept of a coset dates back to Galois'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 the Quarterly Journal of Pure and Applied Mathematics (vol. 41, p. 382). Various other terms have been used including the German Nebengruppen (Weber) and conjugate group (Burnside).<ref>Template:Harvnb</ref> (Note that Miller abbreviated his self-citation to the Quarterly Journal of Mathematics; this does not refer to the journal of the same name, which did not start publication until 1930.)

Galois was concerned with deciding when a given polynomial equation was solvable by radicals. A tool that he developed was in noting that a subgroup Template:Mvar of a group of permutations Template:Mvar induced two decompositions of Template:Mvar (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 over Template:Mvar instead of Template:Mvar. 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.<ref name=Fraleigh />

Calling the coset Template:Mvar the left coset of Template:Mvar with respect to Template:Mvar, while most common today,<ref name=Jacobson /> has not been universally true in the past. For instance, Template:Harvtxt would call Template:Mvar a right coset, emphasizing the subgroup being on the right.

An application from coding theory

{{#invoke:Labelled list hatnote|labelledList|Main article|Main articles|Main page|Main pages}} A binary linear code is an Template:Mvar-dimensional subspace Template:Mvar of an Template:Mvar-dimensional vector space Template:Mvar over the binary field Template:Math. As Template:Mvar is an additive abelian group, Template:Mvar is a subgroup of this group. Codes can be used to correct errors that can occur in transmission. When a codeword (element of Template:Mvar) 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 Template:Mvar (a received word could be any element of Template:Mvar) into a standard array. A standard array is a coset decomposition of Template:Mvar put into tabular form in a certain way. Namely, the top row of the array consists of the elements of Template:Mvar, written in any order, except that the zero vector should be written first. Then, an element of Template:Mvar with a minimal number of ones that does not already appear in the top row is selected and the coset of Template:Mvar 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 Template:Mvar 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 Template:Mvar containing it is the next row. The process ends when all the vectors of Template:Mvar have been sorted into the cosets.

An example of a standard array for the 2-dimensional code Template:Math in the 5-dimensional space Template:Mvar (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 Template:Mvar. 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 an Template:Mvar-dimensional code Template:Mvar in an Template:Mvar-dimensional binary vector space, a parity check matrix is an Template:Math matrix Template:Mvar having the property that Template:Math if and only if Template:Math is in Template:Mvar.<ref>The transpose matrix is used so that the vectors can be written as row vectors.</ref> The vector Template:Math is called the syndrome of Template:Math, and by linearity, 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.<ref>Template:Harvnb</ref>

Double cosets

{{#invoke:Labelled list hatnote|labelledList|Main article|Main articles|Main page|Main pages}} Given two subgroups, Template:Math and Template:Math (which need not be distinct) of a group Template:Math, the double cosets of Template:Math and Template:Math in Template:Math are the sets of the form Template:Math. These are the left cosets of Template:Math and right cosets of Template:Math when Template:Math and Template:Math respectively.<ref>Template:Harvnb</ref>

Two double cosets Template:Math and Template:Math are either disjoint or identical.<ref name=Hall>Template:Harvnb</ref> The set of all double cosets for fixed Template:Mvar and Template:Mvar form a partition of Template:Mvar.

A double coset Template:Math contains the complete right cosets of Template:Mvar (in Template:Mvar) of the form Template:Math, with Template:Mvar an element of Template:Mvar and the complete left cosets of Template:Mvar (in Template:Mvar) of the form Template:Math, with Template:Mvar in Template:Mvar.<ref name=Hall />

Notation

Let Template:Math be a group with subgroups Template:Math and Template:Math. Several authors working with these sets have developed a specialized notation for their work, where<ref>Template:Citation</ref><ref>Template:Citation</ref>

• Template:Math denotes the set of left cosets Template:Math of Template:Math in Template:Math.
• Template:Math denotes the set of right cosets Template:Math of Template:Math in Template:Math.
• Template:Math denotes the set of double cosets Template:Math of Template:Math and Template:Math in Template:Math, sometimes referred to as double coset space.
• Template:Math denotes the double coset space Template:Math of the subgroup Template:Mvar in Template:Mvar.

More applications

• Cosets of Template:Math in Template:Math 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 Cube relies heavily on cosets.
• In geometry, a Clifford–Klein form is a double coset space Template:Math, where Template:Math is a reductive Lie group, Template:Math is a closed subgroup, and Template:Math is a discrete subgroup (of Template:Math) that acts properly discontinuously on the homogeneous space Template:Math.

See also

• Heap
• Coset enumeration

References

• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation

Further reading

• Template:Citation

External links

• {{#invoke:Template wrapper|{{#if:|list|wrap}}|_template=cite web

|_exclude=urlname, _debug, id |url = https://mathworld.wolfram.com/{{#if:Coset%7CCoset.html}} |title = Coset |author = Nicolas Bray |website = MathWorld |access-date = |ref = Template:SfnRef }}

• {{#invoke:Template wrapper|{{#if:|list|wrap}}|_template=cite web

|_exclude=urlname, _debug, id |url = https://mathworld.wolfram.com/{{#if:LeftCoset%7CLeftCoset.html}} |title = Left Coset |author = Weisstein, Eric W. |website = MathWorld |access-date = |ref = Template:SfnRef }}

• {{#invoke:Template wrapper|{{#if:|list|wrap}}|_template=cite web

|_exclude=urlname, _debug, id |url = https://mathworld.wolfram.com/{{#if:RightCoset%7CRightCoset.html}} |title = Right Coset |author = Weisstein, Eric W. |website = MathWorld |access-date = |ref = Template:SfnRef }}

• Template:Springer
• Template:PlanetMath
• Illustrated examples
• {{#invoke:citation/CS1|citation

|CitationClass=web }}