![Left cosets of Z 2 in Z 8](https://upload.wikimedia.org/wikipedia/commons/d/d4/Left_cosets_of_Z_2_in_Z_8.svg)
In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, specifically
group theory
In abstract algebra, group theory studies the algebraic structures known as group (mathematics), groups.
The concept of a group is central to abstract algebra: other well-known algebraic structures, such as ring (mathematics), rings, field ...
, a
subgroup
In group theory, a branch of mathematics, given a group ''G'' under a binary operation ∗, a subset ''H'' of ''G'' is called a subgroup of ''G'' if ''H'' also forms a group under the operation ∗. More precisely, ''H'' is a subgroup ...
of a
group
A group is a number of persons or things that are located, gathered, or classed together.
Groups of people
* Cultural group, a group whose members share the same cultural identity
* Ethnic group, a group whose members share the same ethnic iden ...
may be used to decompose the underlying
set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
of into
disjoint, equal-size
subset
In mathematics, Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are ...
s called cosets. There are ''left cosets'' and ''right cosets''. Cosets (both left and right) have the same number of elements (
cardinality
In mathematics, the cardinality of a set is a measure of the number of elements of the set. For example, the set A = \ contains 3 elements, and therefore A has a cardinality of 3. Beginning in the late 19th century, this concept was generalized ...
) as does . Furthermore, itself 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 . This common value is called the
index
Index (or its plural form indices) may refer to:
Arts, entertainment, and media Fictional entities
* Index (''A Certain Magical Index''), a character in the light novel series ''A Certain Magical Index''
* The Index, an item on a Halo megastru ...
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
Finite is the opposite of infinite. It may refer to:
* Finite number (disambiguation)
* Finite set, a set whose cardinality (number of elements) is some natural number
* Finite verb, a verb form that has a subject, usually being inflected or marked ...
, the number of elements of every subgroup of divides the number of elements of . Cosets of a particular type of subgroup (a
normal subgroup
In abstract algebra, a normal subgroup (also known as an invariant subgroup or self-conjugate subgroup) is a subgroup that is invariant under conjugation by members of the group of which it is a part. In other words, a subgroup N of the group G i ...
) 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 space
In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called ''vectors'', may be added together and multiplied ("scaled") by numbers called '' scalars''. Scalars are often real numbers, but can ...
s and
error-correcting code
In computing, telecommunication, information theory, and coding theory, an error correction code, sometimes error correcting code, (ECC) is used for controlling errors in data over unreliable or noisy communication channels. The central idea is ...
s.
Definition
Let be a subgroup of the group whose operation is written multiplicatively (juxtaposition denotes the group operation). Given an element of , the left cosets of in are the sets obtained by multiplying each element of by a fixed element of (where is the left factor). 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 (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.
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
Cayley table Named after the 19th century British mathematician Arthur Cayley, a Cayley table describes the structure of a finite group by arranging all the possible products of all the group's elements in a square table reminiscent of an addition or multiplicat ...
:
Let be the subgroup . The (distinct) left cosets of are:
*,
*, and
*.
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:
*,
* , and
*.
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 .
Let be a subgroup of a group and suppose that , . The following statements are equivalent:
*
*
*
*
*
Properties
The disjointness of non-identical cosets is a result of the fact that if belongs to then . For if then there must exist an such that . Thus . Moreover, since is a group, left multiplication by is a bijection, and .
Thus every element of belongs to exactly one left coset of the subgroup ,
and is itself a left coset (and the one that contains the identity).
Two elements being in the same left coset also provide a natural
equivalence relation
In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation.
Each equivalence relation ...
. Define two elements of , and , to be equivalent with respect to the subgroup if (or equivalently if belongs to ). The
equivalence classes
In mathematics, when the elements of some set S have a notion of equivalence (formalized as an equivalence relation), then one may naturally split the set S into equivalence classes. These equivalence classes are constructed so that elements ...
of this relation are the left cosets of . As with any set of equivalence classes, they form a
partition
Partition may refer to:
Computing Hardware
* Disk partitioning, the division of a hard disk drive
* Memory partition, a subdivision of a computer's memory, usually for use by a single job
Software
* Partition (database), the division of a ...
of the underlying set. A coset representative is a
representative
Representative may refer to:
Politics
* Representative democracy, type of democracy in which elected officials represent a group of people
* House of Representatives, legislative body in various countries or sub-national entities
* Legislator, som ...
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
In mathematics, an abelian group, also called a commutative group, is a group in which the result of applying the group operation to two group elements does not depend on the order in which they are written. That is, the group operation is commut ...
, 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
In mathematics, especially group theory, two elements a and b of a group are conjugate if there is an element g in the group such that b = gag^. This is an equivalence relation whose equivalence classes are called conjugacy classes. In other ...
with respect to , that is, .
Normal subgroups
A subgroup of a group is a
normal subgroup
In abstract algebra, a normal subgroup (also known as an invariant subgroup or self-conjugate subgroup) is a subgroup that is invariant under conjugation by members of the group of which it is a part. In other words, a subgroup N of the group G i ...
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 Normal(s) or The Normal(s) may refer to:
Film and television
* ''Normal'' (2003 film), starring Jessica Lange and Tom Wilkinson
* ''Normal'' (2007 film), starring Carrie-Anne Moss, Kevin Zegers, Callum Keith Rennie, and Andrew Airlie
* ''Norma ...
in , then its left cosets are different from its right cosets. That is, there is an in such that no element 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. (''Some'' cosets may coincide. For example, if is in the
center
Center or centre may refer to:
Mathematics
*Center (geometry), the middle of an object
* Center (algebra), used in various contexts
** Center (group theory)
** Center (ring theory)
* Graph center, the set of all vertices of minimum eccentricity ...
of , then .)
On the other hand, if the subgroup is normal the set of all cosets forms 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 (or
cardinality
In mathematics, the cardinality of a set is a measure of the number of elements of the set. For example, the set A = \ contains 3 elements, and therefore A has a cardinality of 3. Beginning in the late 19th century, this concept was generalized ...
in the case of an
infinite
Infinite may refer to:
Mathematics
*Infinite set, a set that is not a finite set
*Infinity, an abstract concept describing something without any limit
Music
* Infinite (group), a South Korean boy band
*''Infinite'' (EP), debut EP of American m ...
) 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
An additive group is a group of which the group operation is to be thought of as ''addition'' in some sense. It is usually abelian, and typically written using the symbol + for its binary operation.
This terminology is widely used with structure ...
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
In mathematics, a binary operation is commutative if changing the order of the operands does not change the result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it. Most familiar as the name of ...
of addition and . That is, every left coset of is also a right coset, so is a normal subgroup. (The same argument shows that every subgroup of an Abelian group is normal.
)
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
In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his bo ...
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 space
In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called ''vectors'', may be added together and multiplied ("scaled") by numbers called '' scalars''. Scalars are often real numbers, but can ...
s. The elements (vectors) of a vector space form an
abelian group
In mathematics, an abelian group, also called a commutative group, is a group in which the result of applying the group operation to two group elements does not depend on the order in which they are written. That is, the group operation is commut ...
under
vector addition
In mathematics, physics, and engineering, a Euclidean vector or simply a vector (sometimes called a geometric vector or spatial vector) is a geometric object that has magnitude (or length) and direction. Vectors can be added to other vectors ac ...
. The
subspaces of the vector space are
subgroups
In group theory, a branch of mathematics, given a group ''G'' under a binary operation ∗, a subset ''H'' of ''G'' is called a subgroup of ''G'' if ''H'' also forms a group under the operation ∗. More precisely, ''H'' is a subgro ...
of this group. For a vector space , a subspace , and a fixed vector in , the sets
are called
affine subspace
In mathematics, an affine space is a geometric structure that generalizes some of the properties of Euclidean spaces in such a way that these are independent of the concepts of distance and measure of angles, keeping only the properties related ...
s, and are cosets (both left and right, since the group is abelian). In terms of 3-dimensional
geometric
Geometry (; ) is, with arithmetic, one of the oldest branches of mathematics. It is concerned with properties of space such as the distance, shape, size, and relative position of figures. A mathematician who works in the field of geometry is ca ...
vectors, these affine subspaces are all the "lines" or "planes"
parallel
Parallel is a geometric term of location which may refer to:
Computing
* Parallel algorithm
* Parallel computing
* Parallel metaheuristic
* Parallel (software), a UNIX utility for running programs in parallel
* Parallel Sysplex, a cluster of IBM ...
to the subspace, which is a line or plane going through the origin. For example, consider the
plane
Plane(s) most often refers to:
* Aero- or airplane, a powered, fixed-wing aircraft
* Plane (geometry), a flat, 2-dimensional surface
Plane or planes may also refer to:
Biology
* Plane (tree) or ''Platanus'', wetland native plant
* Planes (gen ...
. If is a line through the origin , then is a subgroup of the abelian group . If is in , 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
Action may refer to:
* Action (narrative), a literary mode
* Action fiction, a type of genre fiction
* Action game, a genre of video game
Film
* Action film, a genre of film
* ''Action'' (1921 film), a film by John Ford
* ''Action'' (1980 fil ...
of on in two natural ways. A ''right action'', given by or a ''left action'', given by . The
orbit
In celestial mechanics, an orbit is the curved trajectory of an object such as the trajectory of a planet around a star, or of a natural satellite around a planet, or of an artificial satellite around an object or position in space such as a p ...
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 Mathematics'' (vol. 41, p. 382). Various other terms have been used including the German ''Nebengruppen'' (
Weber
Weber (, or ; German: ) is a surname of German origin, derived from the noun meaning " weaver". In some cases, following migration to English-speaking countries, it has been anglicised to the English surname 'Webber' or even 'Weaver'.
Notable pe ...
) and ''conjugate group'' (
Burnside).
Galois was concerned with deciding when a given
polynomial equation
In mathematics, an algebraic equation or polynomial equation is an equation of the form
:P = 0
where ''P'' is a polynomial with coefficients in some field, often the field of the rational numbers. For many authors, the term ''algebraic equation' ...
was
solvable by radicals. A tool that he developed was in noting that a subgroup of a group of
permutation
In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or proc ...
s induced two decompositions of (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 instead of .
Camille Jordan
Marie Ennemond Camille Jordan (; 5 January 1838 – 22 January 1922) was a French mathematician, known both for his foundational work in group theory and for his influential ''Cours d'analyse''.
Biography
Jordan was born in Lyon and educated at ...
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 . 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'' (element of ) 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 (a received word could be any element of ) into a
standard array In coding theory, a standard array (or Slepian array) is a q^ by q^ array that lists all elements of a particular \mathbb_q^n vector space. Standard arrays are used to decode linear codes; i.e. to find the corresponding codeword for any received vec ...
. 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 (namely, the row is formed by taking the sum of this element with each element of directly above it). This element is called a
coset leader In coding theory, a coset leader is a word of minimum weight in any particular coset - that is, a word with the lowest amount of non-zero entries. Sometimes there are several words of equal minimum weight in a coset, and in that case, any one of tho ...
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 (with 32 vectors) 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
In coding theory, decoding is the process of translating received messages into codewords of a given code. There have been many common methods of mapping messages to codewords. These are often used to recover messages sent over a noisy channel, su ...
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 -dimensional code in an -dimensional binary vector space, a
parity check matrix In coding theory, a parity-check matrix of a linear block code ''C'' is a matrix which describes the linear relations that the components of a codeword must satisfy. It can be used to decide whether a particular vector is a codeword and is also used ...
is an matrix having the property that
if and only if
In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false.
The connective is bicondi ...
is in . The vector is called the ''syndrome'' of , and by
linearity
Linearity is the property of a mathematical relationship (''function'') that can be graphically represented as a straight line. Linearity is closely related to '' proportionality''. Examples in physics include rectilinear motion, the linear r ...
, 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 (which need not be distinct) 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 (in ) of the form , with an element of and the complete left cosets of (in ) 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
* denotes the set of left cosets of in .
* denotes the set of right cosets of in .
* denotes the set of double cosets of and in , sometimes referred to as ''double coset space''.
* denotes the double coset space of the subgroup in .
More applications
*Cosets of in are used in the construction of
Vitali set
In mathematics, a Vitali set is an elementary example of a set of real numbers that is not Lebesgue measurable, found by Giuseppe Vitali in 1905. The Vitali theorem is the existence theorem that there are such sets. There are uncountably many Vita ...
s, a type of
non-measurable set
In mathematics, a non-measurable set is a set which cannot be assigned a meaningful "volume". The mathematical existence of such sets is construed to provide information about the notions of length, area and volume in formal set theory. In Zerm ...
.
*Cosets are central in the definition of the
transfer
Transfer may refer to:
Arts and media
* ''Transfer'' (2010 film), a German science-fiction movie directed by Damir Lukacevic and starring Zana Marjanović
* ''Transfer'' (1966 film), a short film
* ''Transfer'' (journal), in management studies
...
.
*Cosets are important in computational group theory. For example,
Thistlethwaite's algorithm for solving
Rubik's Cube
The Rubik's Cube is a Three-dimensional space, 3-D combination puzzle originally invented in 1974 by Hungarians, Hungarian sculptor and professor of architecture Ernő Rubik. Originally called the Magic Cube, the puzzle was licensed by Rubik t ...
relies heavily on cosets.
*In geometry, a
Clifford–Klein form is a double coset space , where is a
reductive Lie group
In mathematics, a reductive group is a type of linear algebraic group over a field. One definition is that a connected linear algebraic group ''G'' over a perfect field is reductive if it has a representation with finite kernel which is a direct ...
, is a closed subgroup, and is a discrete subgroup (of ) that acts
properly discontinuously
In mathematics, a group action on a space is a group homomorphism of a given group into the group of transformations of the space. Similarly, a group action on a mathematical structure is a group homomorphism of a group into the automorphism g ...
on the
homogeneous space
In mathematics, particularly in the theories of Lie groups, algebraic groups and topological groups, a homogeneous space for a group ''G'' is a non-empty manifold or topological space ''X'' on which ''G'' acts transitively. The elements of ' ...
.
See also
*
Heap
Heap or HEAP may refer to:
Computing and mathematics
* Heap (data structure), a data structure commonly used to implement a priority queue
* Heap (mathematics), a generalization of a group
* Heap (programming) (or free store), an area of memory f ...
*
Coset enumeration In mathematics, coset enumeration is the problem of counting the cosets of a subgroup ''H'' of a group ''G'' given in terms of a presentation. As a by-product, one obtains a permutation representation for ''G'' on the cosets of ''H''. If ''H'' has ...
Notes
References
*
*
*
*
*
*
*
*
*
Further reading
*
External links
*
*
*
*
*
Illustrated examples*{{cite web, publisher=The Group Properties Wiki, work=groupprops, url=http://groupprops.subwiki.org/wiki/Coset, title=Coset
Group theory
de:Gruppentheorie#Nebenklassen