We prove that every permutation of a Cartesian product of two finite sets can be written as a composition of three permutations, the first of which only modifies the left projection, the second only the right projection, and the third again only the left projection, and three alternations is indeed the optimal number. We show that for two countably infinite sets, the corresponding optimal number of alternations, called the alternation diameter, is four. The notion of alternation diameter can be defined in any category. In the category of finite-dimensional vector spaces, the diameter is also three. For the category of topological spaces, we exhibit a single self-homeomorphism of the plane which is not generated by finitely many alternations of homeomorphisms that only change one coordinate. The results on finite sets and vector spaces were previously known in the context of memoryless computation.
Abstract We say that a reversible boolean function on n bits has alternation depth d if it can be written as the sequential composition of d reversible boolean functions, each of which acts only on the top n − 1 bits or on the bottom n − 1 bits. Moreover, if the functions on n − 1 bits are even, we speak of even alternation depth. We show that every even reversible boolean function of n ⩾ 4 bits has alternation depth at most 9 and even alternation depth at most 13.