Coset


In mathematics, specifically group theory, a subgroup of a group may be used to decompose the underlying set of into disjoint equal size pieces called cosets. There are two types of cosets, left cosets and right cosets. Cosets have the same number of elements as does. Furthermore, itself is a coset, which is both a left coset and a right coset. The number of left cosets of in is equal to the number of right cosets of in. The common value is called the index of in and is usually denoted by.
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, the number of elements of every subgroup of divides the number of elements of. Cosets of a particular type of 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 be a subgroup of the group whose operation is written multiplicatively. Given an element of, The left cosets of in are the sets obtained by multiplying each element of by a fixed element of . In symbols these are,
The right cosets are defined similarly, except that the element is now a right factor, that is,
As varies through the group, it would appear that many cosets would be generated. This is true, but the cosets are not all distinct. In fact, if two cosets of the same type have at least one element in common then they are identical as sets.
If the group operation is written additively, as is often the case when the group is abelian, the notation used changes to or, respectively.

First example

Let be the dihedral group of order six. Its elements may be represented by. In this group and. This is enough information to fill in the entire multiplication table:
Let be the subgroup. The left cosets of are:
Since all the elements of have now appeared in one of these cosets, generating any more can not give new cosets, since a new coset would have to have an element in common with one of these and therefore be identical to one of these cosets. For instance,.
The right cosets of are:
In this example, except for, no left coset is also a right coset.
Let be the subgroup. The left cosets of are and. The right cosets of are and. In this case, every left coset of is also a right coset of.

Properties

Because is a subgroup, it contains the group's identity element, with the result that the element belongs to the coset. If belongs to then. Thus every element of belongs to exactly one left coset of the subgroup.
The identity is in precisely one left or right coset, namely itself. Thus is both a left and right coset of itself.
Elements and belong to the same left coset of, that is, if and only if belongs to. More can be said here. Define two elements of, say and, to be equivalent with respect to the subgroup if belongs to. This is then an equivalence relation on and the equivalence classes of this relation are the left cosets of. 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 is an abelian group, then for every subgroup of and every element of. For general groups, given an element and a subgroup of a group, the right coset of with respect to is also the left coset of the conjugate subgroup with respect to, that is,.

Normal subgroups

A subgroup of a group is a normal subgroup of if and only if for all elements of the corresponding left and right cosets are equal, that is,. This is the case for the subgroup in the first example above. Furthermore, the cosets of in form a group called the quotient group or factor group.
If is not normal in, then its left cosets are different from its right cosets. That is, there is an in such that no element b satisfies. This means that the partition of into the left cosets of is a different partition than the partition of into right cosets of. This is illustrated by the subgroup in the first example above.
On the other hand, if the subgroup N is normal the set of all cosets form a group called the quotient group with the operation ∗ defined by. 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 has the same number of elements as itself. Furthermore, the number of left cosets is equal to the number of right cosets and is known as the index of in G, written as. Lagrange's theorem allows us to compute the index in the case where and are finite:
This equation also holds in the case where the groups are infinite, although the meaning may be less clear.

More examples

Integers

Let be the additive group of the integers, and the subgroup. Then the cosets of in are the three sets,, and, where. These three sets partition the set ℤ, so there are no other right cosets of. Due to the commutivity of addition and. That is, every left coset of is also a right coset, so is a normal subgroup.
This example may be generalized. Again let be the additive group of the integers,, and now let the subgroup, where is a positive integer. Then the cosets of in are the sets,,...,, where. There are no more than cosets, because. The coset is the congruence class of modulo. The subgroup is normal in, and so, can be used to form the quotient group the group of integers mod m.

Vectors

Another example of a coset comes from the theory of vector spaces. The elements 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, a subspace, and a fixed vector in, the sets
are called affine subspaces, and are cosets. 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 ℝ2. If is a line through the origin, then is a subgroup of the abelian group ℝ2. If is in ℝ2, then the coset is a line parallel to and passing through.

Matrices

Let be the multiplicative group of matrices,
and the subgroup of,
For a fixed element of consider the left coset
That is, the left cosets consist of all the matrices in having the same upper-left entry. This subgroup is normal in, but the subgroup
is not normal in.

As orbits of a group action

A subgroup of a group can be used to define an action of on in two natural ways. A right action, given by or a left action, given by. The orbit of under the right action is the left coset, while the orbit under the left action is the right coset.

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" appears for the first time in 1910 in a paper by G. A. Miller in the Quarterly Journal of Mathmatics. Various other terms have been used including the german Nebengruppen and conjugate group.
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 of a group of permutations induced two decompositions of . 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 instead of. 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.
Calling the coset the left coset of with respect to, while most common today, has not been universally true in the past. For instance, would call a right coset, emphasizing the subgroup being on the right.

An application from coding theory

A binary linear code is an -dimensional subspace of an -dimensional vector space over the binary field GF. As is an additive abelian group, is a subgroup of this group. Codes can be used to correct errors that can occur in transmission. When a codeword 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 into a standard array. A standard array is a coset decomposition of put into tabular form in a certain way. Namely, the top row of the array consists of the elements of, written in any order, except that the zero vector should be written first. Then, an element of with a minimal number of ones that does not already appear in the top row is selected and the coset of containing this element is written as the second row. 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 containing it is the next row. The process ends when all the vectors of have been sorted into the cosets.
An example of a standard array for the 2-dimensional code = in the 5-dimensional space is as follows:
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. 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 that a received word will be in. For an -dimensional code in an -dimensional binary vector space, a parity check matrix is an matrix having the property that ⊤ = if and only if is in. The vector ⊤ is called the syndrome of, 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.

Double cosets

Given two subgroups, and of a group, the double cosets of and in are the sets of the form. These are the left cosets of and right cosets of when and respectively.
Two double cosets and are either disjoint or identical. The set of all double cosets for fixed and form a partition of.
A double coset contains the complete right cosets of of the form, with an element of and the complete left cosets of of the form, with in.

Notation

Let be a group with subgroups and. Several authors working with these sets have developed a specialized notation for their work, where