2.4 Subgroups

We start with the symmetric group of degree \(4\), the alternating group of degree \(4\), and the cyclic group of order 4.

S4 = replab.PermutationGroup.symmetric(4);
A4 = replab.PermutationGroup.alternating(4);
C4 = replab.PermutationGroup.cyclic(4);

Subgroup test

We can ask whether a group is a subgroup of another. Of course, both A4 and C4 are subgroups of S4.

A4.isSubgroupOf(S4)
C4.isSubgroupOf(S4)

ans = 1
ans = 1

But we remark that none of A4 and C4 is contained in the other one.

A4.isSubgroupOf(C4)
C4.isSubgroupOf(A4)

ans = 0
ans = 0

Group intersection

We just saw that A4 and C4 are not subgroups of each other. Let us see if they contain a common subgroup.

A4.intersection(C4)

ans =

Permutation group acting on 4 elements of order 2
            identity: [1, 2, 3, 4]
generator(1 or 'x1'): [3, 4, 1, 2]
    recognize.source: Cyclic group C(2) of order 2 < x | x^2 = 1 >

Observe that C4 contains all cyclic shifts of the elements [1 2 3 4]; but only shifting by an even number of elements leads to an even permutation. Thus the intersection contains two elements: the identity and the cyclic-shift-by-two [3 4 1 2].

RepLAB can compute the intersection of arbitrary groups as long as they have the same type. For example, it would be an error to compute the intersection of \(S_4\) and \(S_5\) defined as such:

S4 = replab.PermutationGroup.symmetric(4);
S5 = replab.PermutationGroup.symmetric(5);
S4.hasSameTypeAs(S5) % no! thus the following is an error
S4.intersection(S5)

ans = 0
error: assert (self.hasSameTypeAs (other)) failed
error: called from
    assert at line 99 column 11
    intersection at line 470 column 13

Subgroup leaving vector invariant

Permutations act on vectors by permuting their coordinates. For example, we define the action of a permutation on a row or column vector \(\vec{v}\):

h = [2 3 4 1];
v = [1.3 2.3 2.3 1.3];
v1 = v(h)

v1 =

   2.3000   2.3000   1.3000   1.3000

A priori, we could equally define the action of a permutation on a vector as v2(h) = v. For invariance under permutation, the choice does not matter. Formally, however, only v1 corresponds to the left action of h on v. We want a left action because of how we defined permutation composition.

Given a group \(G\), we are now looking for the subgroup of \(G\) that leaves \(\vec{v}\) invariant under permutation. This can be readily computed using the vectorStabilizer method.

When considering the symmetric group, this will be the group of order four that contains:

• the identity,

• the permutation of the first and last element,

• the permutation of the two middle elements,

• the permutation that swaps the first/last, and the two middle elements at the same time.

G = S4.vectorStabilizer(v)

G =

Permutation group acting on 4 elements of order 4
            identity: [1, 2, 3, 4]
generator(1 or 'x1'): [4, 2, 3, 1]
generator(2 or 'x2'): [1, 3, 2, 4]
    recognize.source: Klein four-group < a, x | a^2 = x^2 = x a x^-1 a^-1 = 1 >

One can of course start with another group than the symmetric group, and compute its subgroup leaving \(\vec{v}\) invariant. The result is then less obvious. For instance, if one starts with the alternating group, there is only one non-trivial element that satisfies the requirement.

H = A4.vectorStabilizer(v)

H =

Permutation group acting on 4 elements of order 2
            identity: [1, 2, 3, 4]
generator(1 or 'x1'): [4, 3, 2, 1]
    recognize.source: Cyclic group C(2) of order 2 < x | x^2 = 1 >

Setwise stabilizer

The setwise stabilizer is the subgroup that leaves a subset of the integer \(1, \ldots, n\) invariant, while not preserving necessarily their place inside the set. If we start from the group of all permutations acting on four elements, and require that the first two elements must stay in one of the first two positions, we can swap the first two elements, swap the last two elements, or do both.

S4.setwiseStabilizer([1 2])

ans =

Permutation group acting on 4 elements of order 4
            identity: [1, 2, 3, 4]
generator(1 or 'x1'): [2, 1, 3, 4]
generator(2 or 'x2'): [1, 2, 4, 3]
    recognize.source: Klein four-group < a, x | a^2 = x^2 = x a x^-1 a^-1 = 1 >

Pointwise stabilizer

The pointwise stabilzier is the subgroup that leaves every point of a set in place. If we start from the group of all permutations acting on four elements, and ask that the first two elements stay in place, we can only swap the two last elements.

S4.pointwiseStabilizer([1 2])

ans =

Permutation group acting on 4 elements of order 2
            identity: [1, 2, 3, 4]
generator(1 or 'x1'): [1, 2, 4, 3]
    recognize.source: Cyclic group C(2) of order 2 < x | x^2 = 1 >

Partition stabilizer

There are several conflicting notions of a partition in discrete mathematics. Here, a Partition is the description of the set \(\{1,\ldots,n\}\) as the union of disjoint subsets.

A partition can be created from blocks.

P = replab.Partition.fromBlocks({[1 2] [3 4]})

P =

Partition '12|34'
blockIndex: [1, 1, 2, 2]
    blocks: {[1, 2], [3, 4]}
         n: 4

Then, we can ask for the unordered partition stabilizer, i.e. the subgroup of a group that preserves the partition structure, but without necessarily keeping the blocks in their original place. This means we can reorder the elements inside a block, and permute blocks of the same size. For the partition above, this restricts permutations to the dihedral group:

S4.unorderedPartitionStabilizer(P)

ans =

Permutation group acting on 4 elements of order 8
            identity: [1, 2, 3, 4]
generator(1 or 'x1'): [2, 1, 3, 4]
generator(2 or 'x2'): [3, 4, 1, 2]
generator(3 or 'x3'): [1, 2, 4, 3]
    recognize.source: Dihedral group of order 8