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 Lagrange's theorem that states that for any finite group G, the number of elements of every subgroup H of G divides the number of elements of G. 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.
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.
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.
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:
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:
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]
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 equivalence relation. Define two elements of G, x and y, to be equivalent with respect to the subgroup H if xH = yH (or equivalently if x−1y belongs to H). The equivalence classes of this relation are the left cosets of H. [4] 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 G is an abelian group, then g + H = H + g for every subgroup H of G and every element g of G. For general groups, given an element g and a subgroup H of a group G, the right coset of H with respect to g is also the left coset of the conjugate subgroup g−1Hg with respect to g, that is, Hg = g(g−1Hg).
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".
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: This equation can be generalized to the case where the groups are infinite.
Let G be the additive group of the integers, Z = ({..., −2, −1, 0, 1, 2, ...}, +) and H the subgroup (3Z, +) = ({..., −6, −3, 0, 3, 6, ...}, +). Then the cosets of H in G are the three sets 3Z, 3Z + 1, and 3Z + 2, where 3Z + a = {..., −6 + a, −3 + a, a, 3 + a, 6 + a, ...}. These three sets partition the set Z, so there are no other right cosets of H. Due to the commutivity of addition H + 1 = 1 + H and H + 2 = 2 + H. That is, every left coset of H is also a right coset, so H 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 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 congruence class of a modulo m. [7] The subgroup mZ is normal in Z, and so, can be used to form the quotient group Z / mZ the group of integers mod m.
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 V, a subspace W, and a fixed vector a in V, the sets 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 R2. If m is a line through the origin O, then m is a subgroup of the abelian group R2. If P is in R2, then the coset P + m is a line m′ parallel to m and passing through P. [8]
Let G be the multiplicative group of matrices, [9] and the subgroup H of G, For a fixed element of G consider the left coset That is, the left cosets consist of all the matrices in G having the same upper-left entry. This subgroup H is normal in G, but the subgroup is not normal in G.
A subgroup H of a group G can be used to define an action of H on G in two natural ways. A right action, G × H → G given by (g, h) → gh or a left action, H × G → G given by (h, g) → hg. The orbit of g under the right action is the left coset gH, while the orbit under the left action is the right coset Hg. [10]
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). [11] (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 H of a group of permutations G induced two decompositions of G (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 H instead of G. 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 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.
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.
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 n-dimensional code C in an m-dimensional binary vector space, a parity check matrix is an (m − n) × m matrix H having the property that xHT = 0 if and only if x is in C. [12] The vector xHT is called the syndrome of x, 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. [13]
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]
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]
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 commutative. With addition as an operation, the integers and the real numbers form abelian groups, and the concept of an abelian group may be viewed as a generalization of these examples. Abelian groups are named after Niels Henrik Abel.
A quotient group or factor group is a mathematical group obtained by aggregating similar elements of a larger group using an equivalence relation that preserves some of the group structure. For example, the cyclic group of addition modulo n can be obtained from the group of integers under addition by identifying elements that differ by a multiple of and defining a group structure that operates on each such class as a single entity. It is part of the mathematical field known as group theory.
In mathematics, given two groups, (G,∗) and (H, ·), a group homomorphism from (G,∗) to (H, ·) is a function h : G → H such that for all u and v in G it holds that
In mathematics, a Lie algebra is a vector space together with an operation called the Lie bracket, an alternating bilinear map , that satisfies the Jacobi identity. In other words, a Lie algebra is an algebra over a field for which the multiplication operation is alternating and satisfies the Jacobi identity. The Lie bracket of two vectors and is denoted . A Lie algebra is typically a non-associative algebra. However, every associative algebra gives rise to a Lie algebra, consisting of the same vector space with the commutator Lie bracket, .
In mathematics, a group is a set with an operation that associates an element of the set to every pair of elements of the set and satisfies the following constraints: the operation is associative, it has an identity element, and every element of the set has an inverse element.
In group theory, a branch of mathematics, a subset of a group G is a subgroup of G if the members of that subset form a group with respect to the group operation in G.
In the mathematical field of group theory, Lagrange's theorem states that if H is a subgroup of any finite group G, then |H| is a divisor of |G|, i.e. the order of every subgroup H divides the order of group G.
In mathematics, topological groups are the combination of groups and topological spaces, i.e. they are groups and topological spaces at the same time, such that the continuity condition for the group operations connects these two structures together and consequently they are not independent from each other.
In mathematics, especially group theory, two elements and of a group are conjugate if there is an element in the group such that This is an equivalence relation whose equivalence classes are called conjugacy classes. In other words, each conjugacy class is closed under for all elements in the group.
In abstract algebra, a cyclic group or monogenous group is a group, denoted Cn, that is generated by a single element. That is, it is a set of invertible elements with a single associative binary operation, and it contains an element g such that every other element of the group may be obtained by repeatedly applying the group operation to g or its inverse. Each element can be written as an integer power of g in multiplicative notation, or as an integer multiple of g in additive notation. This element g is called a generator of the group.
In mathematics, more specifically in the field of group theory, a solvable group or soluble group is a group that can be constructed from abelian groups using extensions. Equivalently, a solvable group is a group whose derived series terminates in the trivial subgroup.
In mathematics, the orthogonal group in dimension n, denoted O(n), is the group of distance-preserving transformations of a Euclidean space of dimension n that preserve a fixed point, where the group operation is given by composing transformations. The orthogonal group is sometimes called the general orthogonal group, by analogy with the general linear group. Equivalently, it is the group of n × n orthogonal matrices, where the group operation is given by matrix multiplication (an orthogonal matrix is a real matrix whose inverse equals its transpose). The orthogonal group is an algebraic group and a Lie group. It is compact.
In physics and mathematics, the Lorentz group is the group of all Lorentz transformations of Minkowski spacetime, the classical and quantum setting for all (non-gravitational) physical phenomena. The Lorentz group is named for the Dutch physicist Hendrik Lorentz.
In mathematics, specifically group theory, the index of a subgroup H in a group G is the number of left cosets of H in G, or equivalently, the number of right cosets of H in G. The index is denoted or or . Because G is the disjoint union of the left cosets and because each left coset has the same size as H, the index is related to the orders of the two groups by the formula
In mathematics, the adjoint representation of a Lie group G is a way of representing the elements of the group as linear transformations of the group's Lie algebra, considered as a vector space. For example, if G is , the Lie group of real n-by-n invertible matrices, then the adjoint representation is the group homomorphism that sends an invertible n-by-n matrix to an endomorphism of the vector space of all linear transformations of defined by: .
In algebra, a group ring is a free module and at the same time a ring, constructed in a natural way from any given ring and any given group. As a free module, its ring of scalars is the given ring, and its basis is the set of elements of the given group. As a ring, its addition law is that of the free module and its multiplication extends "by linearity" the given group law on the basis. Less formally, a group ring is a generalization of a given group, by attaching to each element of the group a "weighting factor" from a given ring.
In mathematics, the Heisenberg group, named after Werner Heisenberg, is the group of 3×3 upper triangular matrices of the form
In group theory, a field of mathematics, a double coset is a collection of group elements which are equivalent under the symmetries coming from two subgroups, generalizing the notion of a single coset.
In mathematics, a unipotent elementr of a ring R is one such that r − 1 is a nilpotent element; in other words, (r − 1)n is zero for some n.
The direct sum is an operation between structures in abstract algebra, a branch of mathematics. It is defined differently, but analogously, for different kinds of structures. As an example, the direct sum of two abelian groups and is another abelian group consisting of the ordered pairs where and . To add ordered pairs, we define the sum to be ; in other words addition is defined coordinate-wise. For example, the direct sum , where is real coordinate space, is the Cartesian plane, . A similar process can be used to form the direct sum of two vector spaces or two modules.