Version 3 of Group theory and permutations

Updated 2015-03-17 05:45:01 by SEH

Arjen Markus (2 june 2005) Group theory is a very powerful tool in mathematics - it belongs to the field of algebra. You can do all kinds of (mathematically) useful things with it - just pick up any book on the subject.

It is surprisingly simple to use Tcl to do group-theoretical computations, like determining the set of elements generated by one or more "typical" elements - the generators.

In the script below I use permutations as the generators of some group and determine what (sub)group of the complete symmetric group they generate. It is a mere toy, compared to what can be done!

Note: I have not tried to optimise the computations nor do I do any error checking.

``` # group_perm.tcl --
#     Small experiment with group theory and permutations
#

# group --
#     Generate the group from the given generators
# Arguments:
#     args      List of permutations, each one a generator
# Result:
#     List of elements of the group
#
proc group {args} {
if { [llength \$args] > 1 } {
set generator [lindex \$args 0]
set result    [eval group [lrange \$args 1 end]]
set new       1
while { \$new } {
set new      0
set expanded \$result
foreach e \$result {
set eleft  [combine \$e \$generator]
set eright [combine \$generator \$e]
if { [lsearch \$expanded \$eleft] < 0 } {
lappend expanded \$eleft
set new 1
}
if { [lsearch \$expanded \$eright] < 0 } {
lappend expanded \$eright
set new 1
}
}
set result \$expanded
}
} else {
set generator [lindex \$args 0]
set result    [list \$generator]
set enext     \$generator
set new 1
while { \$new } {
set new 0
set enext [combine \$generator \$enext]
if { [lsearch \$result \$enext] < 0 } {
lappend result \$enext
set new 1
}
}
}
return \$result
}

# combine --
#     Combine two permutations
# Arguments:
#     p         First permutation
#     q         Second permutation (applied first)
# Result:
#     Permutation p.q
#
proc combine {p q} {
set result {}
foreach e \$q {
lappend result [lindex \$p \$e]
}
return \$result
}

# main --
#    A few simple tests
#
puts "Simple exchange - applied twice gives identity:"
set p {0 2 1}
puts [combine \$p \$p]
puts "Cycle of 3 - applied three times gives identity:"
set p {1 2 0}
puts [combine \$p \$p]
puts [combine [combine \$p \$p] \$p]
puts "Cycle of 3 - with inverse gives identity:"
set q {2 0 1}
puts [combine \$p \$q]

#
# Now the heavier stuff: create a (sub)group
#
puts "Simple subgroup of S3:"
puts [group {0 2 1}]
puts "S3 complete:"
puts [group {1 2 0} {0 2 1}]
puts "Subgroup of S4:"
puts [group {1 0 2 3} {0 2 1 3}]
puts "S4 complete:"
puts [group {1 0 2 3} {1 2 3 0}]```

Magnus is a free and open source Computer Algebra system in Infinite Group Theory, written in C/C++ with a Tcl/Tk front end . It is used worldwide to research problems in Infinite Group Theory.

 Category Mathematics