Sunday, March 10, 2013

Describing structures by transformations

The automorphism group of a data structure transformations of that data structure that do not have any effect on it. The automorphism group of a list is the set of operations that map indexes to other indexes with equal value. We can enumerate all the orbits of this automorphism group on its parent symmetric group in order to enumerate all distinct permutations of the list.

Likewise, all graphs have an automorphism group of permutations that do not effect the underlying graph. Weak orderings have an automorphism group equivalent to that of a list, equivalence relations have an automorphism group that also includes exchanges of equally sized parts, and the automorphism group of an permutation is the set of all operations that commute with it.

Periodic sequences can be described by the effect of the rest operation on the sequence and finitely differentiable functions like sine and cosine can be described by the effect of differentiation on them. In this sense, the transformations on a data structure are important in both discrete and continuous mathematics.

No comments:

Post a Comment