Factoring matrices into the product of circulant and diagonal matrices
type: Item
instance of: scholarly article
title: Factoring matrices into the product of circulant and diagonal matrices
zbMATH Open document ID: 1327.15028
author: Marko Huhtanen
author: Allan Perämäki
published in: The Journal of Fourier Analysis and Applications
publication date: 2015-10-12T00:00:00Z
review text: This paper deals with decomposing a square complex matrix into circulant and diagonal factors. A complex \(n \times n\) circulant matrix \(C\) takes the form \[ C=\left( \begin{matrix} c_0 & c_{n-1} & c_{n-2} & \cdots & c_2 & c_1 \\ c_1 & c_0 & c_{n-1} & \cdots & c_3 & c_2 \\ c_2 & c_1 & c_0 & \cdots & c_4 & c_3 \\ \vdots & \vdots & \vdots & &\vdots & \vdots \\ c_{n-2}& c_{n-3} & c_{n-4} & \cdots & c_0 & c_{n-1} \\ c_{n-1}& c_{n-2} & c_{n-3} & \cdots & c_1 & c_0 \end{matrix} \right). \] This matrix is fully specified by one vector \(u\) which appears as the first column of \(C\). The remaining columns of \(C\) are each cyclic permutations of the vector \(u\) with offset equal to the column index. There exists a result, motivated by applications in optimal image processing, stating that any complex matrix \(A \in \mathbb{C}^{n \times n}\) is the product of circulant and diagonal matrices. In this paper, the authors show that the number of factors is \(2n-1\) at most. The proof is constructive, depending on first factoring matrix subspaces equivalent to polynomials in a permutation matrix over diagonal matrices into linear factors, which is achieved by solving structured systems of polynomial equations. Such subspaces are shown to constitute a fundamental sparse matrix structure of polynomial type extending, for example, band matrices. Then for the linear factors, a decomposition for the sum of two PD matrices (the product of a permutation and a diagonal matrix) into the product of a circulant matrix and two diagonal matrices is derived. The authors suggest a polynomial structure in permutations in order to extend the set of sums of two PD matrices in a way which admits factoring. Let \(P\) be a permutation matrix and denote by \(p\) a polynomial over diagonal matrices. Define matrix subspaces of \(\mathbb{C}^{n \times n}\) as \[ P_1 \{ p(P) : \mathrm{deg}(p) \leq j \} P_2, \] with fixed permutations \(P_1\) and \(P_2\). With this representation, the problem of factor…
Mathematics Subject Classification ID: 15A23
Mathematics Subject Classification ID: 12D05
Mathematics Subject Classification ID: 65F50
Mathematics Subject Classification ID: 65T50
zbMATH DE Number: 6493290
zbMATH Keywords: circulant matrix
zbMATH Keywords: factorization of matrices
zbMATH Keywords: polynomial factoring
zbMATH Keywords: sparsity structure
zbMATH Keywords: multiplicative Fourier compression
zbMATH Keywords: diagonal matrix
reviewed by: Juan Ramón Torregrosa Sánchez
MaRDI profile type: Publication
full work available at URL: s00041-015-9395-0
OpenAlex ID: W1981479685
cites work: Pinching, Trimming, Truncating, and Averaging of Matrices
cites work: Combinatorial Matrix Theory
cites work: Preconditioning techniques for large linear systems: A survey
cites work: Preconditioning highly indefinite and nonsymmetric matrices
cites work: Q5340151
cites work: Q3208805
cites work: The Design and Use of Algorithms for Permuting Large Entries to the Diagonal of Sparse Matrices
cites work: Maximality of the monomial group
cites work: Q5689624
cites work: Approximating ideal diffractive optical systems
cites work: The product of matrix subspaces
cites work: Factoring in the metaplectic group and optics
cites work: Q4308102
cites work: Some speed-ups and speed limits for real algebraic geometry
cites work: Q4787522
cites work: Decomposing a matrix into circulant and diagonal factors
cites work: Q3752523
DOI: 10.1007/S00041-015-9395-0
description: scientific article; zbMATH DE number 6493290