DISPLACEMENT OPERATOR BASED DECOMPOSITIONS OF MATRICES USING CIRCULANTS OR OTHER GROUP MATRICES

We show how an arbitrary square matrix can be expressed as sums of products of circulant and upper or lower triangular Toeplitz matrices, and as sums of products of matrices derived from finite groups (group matrices) and matrices which are "close" to group matrices. The results obtained are interesting from several points of view: they lead to different methods for computing linear transforms using FFTs or fast convolution algorithms, to faster methods for solving Toeplitz systems, to potential methods for mapping linear transforms to parallel computer architectures with interconnection scheme given by the group graph of a finite group, and possibly to matrix theoretic methods for expressing relationship between finite groups. © 1990.