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.
Theorem is also known previously: the number @math of alternations needed for a product of length @math (which can be obtained from Theorem ) can be found in @cite_7 @cite_2 (for a larger class of modules). It turns out that @math is not optimal at least for finite fields: in [Theorem 2.1] CaFaGa14a it is proved that for over a finite field the optimal number of alternations for a product of length @math is @math .
@cite_7 @cite_2
1569126060 2101732749
We investigate the computation of mappings from a set S n to itself with in situ programs , that is using no extra variables than the input, and performing modifications of one component at a time. We consider several types of mappings and obtain effective computation and decomposition methods, together with upper bounds on the program length (number of assignments). Our technique is combinatorial and algebraic (graph coloration, partition ordering, modular arithmetics). For general mappings, we build a program with maximal length 5n *** 4, or 2n *** 1 for bijective mappings. The length is reducible to 4n *** 3 when |S | is a power of 2. This is the main combinatorial result of the paper, which can be stated equivalently in terms of multistage interconnection networks as: any mapping of 0,1 n can be performed by a routing in a double n -dimensional Benes network. Moreover, the maximal length is 2n *** 1 for linear mappings when S is any field, or a quotient of an Euclidean domain (e.g. *** s ***). In this case the assignments are also linear, thereby particularly efficient from the algorithmic viewpoint. The in situ trait of the programs constructed here applies to optimization of program and chip design with respect to the number of variables, since no extra writing memory is used. In a non formal way, our approach is to perform an arbitrary transformation of objects by successive elementary local transformations inside these objects only with respect to their successive states. We investigate the computation of mappings from a set S^n to itself with "in situ programs", that is using no extra variables than the input, and performing modifications of one component at a time, hence using no extra memory. In this paper, we survey this problem introduced in previous papers by the authors, we detail its close relation with rearrangeable multicast networks, and we provide new results for both viewpoints. A bijective mapping can be computed by 2n-1 component modifications, that is by a program of length 2n-1, a result equivalent to the rearrangeability of the concatenation of two reversed butterfly networks. For a general arbitrary mapping, we give two methods to build a program with maximal length 4n-3. Equivalently, this yields rearrangeable multicast routing methods for the network formed by four successive butterflies with alternating reversions. The first method is available for any set S and practically equivalent to a known method in network theory. The second method, a refinment of the first, described when |S| is a power of 2, is new and allows more flexibility than the known method. For a linear mapping, when S is any field, or a quotient of an Euclidean domain (e.g Z sZ for any integer s), we build a program with maximal length 2n-1. In this case the assignments are also linear, thereby particularly efficient from the algorithmic viewpoint, and giving moreover directly a program for the inverse when it exists. This yields also a new result on matrix decompositions, and a new result on the multicast properties of two successive reversed butterflies. Results of this flavour were known only for the boolean field Z 2Z.