Shuffling matrices, Kronecker product and Discrete Fourier Transform

• Published in: Discrete Applied Mathematics 2017-12, Vol.233, p.1-18
• Main Authors: D’Angeli, Daniele, Donno, Alfredo
• Format: Article
• Language: English
• Subjects: Applied mathematics; Combinatorial analysis; Discrete Fourier Matrix; Fourier transforms; Kronecker product; Perfect shuffle; Permutations; Rooted tree; Shuffling matrix
• ISSN: 0166-218X; 1872-6771
• DOI: 10.1016/j.dam.2017.08.018

We define and investigate a family of permutations matrices, called shuffling matrices, acting on a set of N=n1⋯nm elements, where m≥2 and ni≥2 for any i=1,…,m. These elements are identified with the vertices of the mth level of a rooted tree with branch indices (n1,…,nm). Each of such matrices is induced by a permutation of Sym(m) and it turns out that, in the case in which one considers the cyclic permutation (1…m), the corresponding permutation is the classical perfect shuffle. We give a combinatorial interpretation of these permutations in terms of lexicographic order of the vertices of the tree. This allows us to describe their fixed points. We show that our permutation matrices can be used to let the Kronecker product of matrices commute or, more generally, rearrange in an arbitrary order. Moreover, we show that the group generated by such permutations does depend only on the branch indices of the tree, but it is independent from their order. In the case in which such indices coincide, we prove that the corresponding group is a copy of Sym(m) inside Sym(nm). Finally, we give an application of shuffling matrices in the context of the Discrete Fourier Transform.