In mathematics, especially in the area of modern algebra known as combinatorial group theory, Nielsen transformations are certain automorphisms of a free group which are a non-commutative analogue of row reduction and one of the main tools used in studying free groups (Fine, Rosenberger & Stille 1995).
and Dehn twists for mapping class groups of closed surfaces.
An elementary Nielsen transformation maps an ordered basis
are determined by the image of a basis, the elementary Nielsen transformations correspond to a finite subset of the automorphism group
Hence, Nielsen transformation can alternatively be defined simply as the action of an automorphism of
Transformations of the first kind are analogous to row permutations.
Transformations of the second kind correspond to scaling a row by an invertible scalar.
Transformations of the third kind correspond to row additions (transvections).
is generated by transpositions, one sees from the chain of elementary Nielsen transformations of type 2 and 3:
, one can alternatively restrict attention to only four operations: When dealing with groups that are not free, one instead applies these transformations to finite ordered subsets of a group.
In this situation, compositions of the elementary transformations are called regular.
The image under a Nielsen transformation (elementary or not, regular or not) of a generating set of a group G is also a generating set of G. Two generating sets are called Nielsen equivalent if there is a Nielsen transformation taking one to the other (beware this is not an equivalence relation).
If the generating sets have the same size, then it suffices to consider compositions of regular Nielsen transformations.
The dihedral group of order 10 has two Nielsen equivalence classes of generating sets of size 2.
The modern proof relies on the fact that a group (finitely generated or not) is free, if and only if it is the fundamental group of a graph (finite or not).
It relies on the notion of a Nielsen reduced generating set, which roughly means one for which there is not too much cancellation in products.
The paper shows that every finite generating set of a subgroup of a free group is (singularly) Nielsen equivalent to a Nielsen reduced generating set, and that a Nielsen reduced generating set is a free basis for the subgroup, so the subgroup is free.
This proof is given in some detail in (Magnus, Karrass & Solitar 2004, Ch 3.2).
In (Nielsen 1924), it is shown that the elementary Nielsen transformations generate the full automorphism group of a finitely generated free group.
This is also described in standard textbooks such as (Magnus, Karrass & Solitar 2004, p. 131, Th 3.2).
This is known to be intractable in general, even though there is a finite sequence of elementary Tietze transformations taking the presentation to the trivial presentation if and only if the group is trivial.
For these groups, there is a conjecture that the required transformations are quite a bit simpler (in particular, do not involve adding or removing relators).
The Andrews–Curtis conjecture is that the relators of any balanced presentation of the trivial group are equivalent to a set of trivial relators, stating that each generator is the identity element.
In the textbook (Magnus, Karrass & Solitar 2004, pp.
131–132), an application of Nielsen transformations is given to solve the generalized word problem for free groups, also known as the membership problem for subgroups given by finite generating sets in free groups.
A particularly important special case of the isomorphism problem for groups concerns the fundamental groups of three-dimensional knots, which can be solved using Nielsen transformations and a method of J. W. Alexander (Magnus, Karrass & Solitar 2004, Ch 3.4).
The "product replacement algorithm" simply uses randomly chosen Nielsen transformations in order to take a random walk on the graph of generating sets of the group.
One version of the algorithm, called "shake", is: The generating set used during the course of this algorithm can be proved to vary uniformly over all Nielsen equivalent generating sets.
Also, the elements of generating sets need be uniformly distributed (for instance, elements of the Frattini subgroup can never occur in a generating set of minimal size, but more subtle problems occur too).
Most of these problems are quickly remedied in the following modification called "rattle", (Leedham-Green & Murray 2002): To understand Nielsen equivalence of non-minimal generating sets, module theoretic investigations have been useful, as in (Evans 1989).