We investigate the dynamical behavior of compositions of affine transformations over finite fields from a linear algebraic perspective. For a prime power q and integers n > m ≥ 0 , we consider functions of the form F : F q n → F q n defined by F ( x ) = T ( x + B t f ( A x ) ) , where T : F q n → F q n , A : F q n → F q m , and B : F q n → F q n − m are full-rank linear transformations satisfying the orthogonality condition A B t = 0 , and f : F q m → F q n − m is an arbitrary function. This construction, introduced by Gravel and Panario (2019), extends any function f into a permutation over F q n and has applications in cryptographic schemes such as Feistel networks. Our main contribution is a complete characterization of cycle structures—the decomposition of the permutation into disjoint cycles—in terms of the spectral properties of T . When T is the identity matrix, we prove that the functional graph contains only cycles of length 1 and p (where p = char ( F q ) ), with the number of fixed points given by q n − m ⋅ | f − 1 ( 0 ) | . For general invertible T and constant functions f ( x ) = y , we establish that all cycle lengths are multiples of a minimal integer d determined by the column space of T d − I . Using the Jordan canonical form of T and Möbius inversion techniques, we derive explicit formulas for the number of elements in cycles of each length, showing that the possible cycle lengths have the form lcm ( S , d , p m ) where S is a subset of eigenvalue orders and m is bounded by Jordan block sizes. We extend these results to compositions of multiple linear extensions with different functions f j , proving that the cycle structure depends on the sum ∑ j = 1 ℓ f j and establishing formulas for cycle lengths in terms of greatest common divisors with the number of iterations. Our results reveal an intricate connection between the algebraic structure of linear transformations and the combinatorial properties of the resulting dynamical system.
Gravel et al. (Fri,) studied this question.