Symmetry-based matrix factorization (Q597055)

A symmetry of a given matrix \(M\) is given by a pair \((\phi, \psi)\) of representations of the same group \(G\) such that \[ \phi(g) \cdot M = M \cdot \psi(g), \qquad \forall g \in G. \] This paper studies symmetries, where \(\phi\) and \(\psi\) are restricted to one of the following types of representations: permutations, monomials (also called generalized permutations), and direct sums of (irreducible) permutations. If a matrix \(M\) possesses a nontrivial symmetry of the types above, it is shown how \(M\) can be decomposed into a short product of sparse matrices. This in turn admits the derivation of fast algorithms for performing matrix-vector-multiplications with \(M\). As an application of this general theoretical framework, (known) fast algorithms for discrete Fourier, discrete cosine, Hartley and Haar transforms are derived. Note that a limitation of such an approach is that the obtained algorithm is restricted to a specific matrix \(M\) of fixed dimension. Nevertheless, this framework is certainly useful to gain intuition for constructing more general algorithms which apply to whole classes of matrices, possibly of varying dimensions.