Factoring matrices into the product of circulant and diagonal matrices (Q744956)

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 factoring \(A\) into the product of circulant and diagonal matrices converts into the problem of factoring \(p\) (the unique polynomial over diagonal matrices of degree \(n-1\) at most such that \(p(P)=A\), with \(P\) a cyclic shift and \(P_1=P_2=I\)) into linear factors. Finally, a conjecture on the optimal number of factors is made together with related Fourier compression problems.