## Abstract

A generic matrix $$A\in \,\mathbb {C}^{n \times n}$$A∈^{Cn×n} is shown to be the product of circulant and diagonal matrices with the number of factors being $$2n-1$$2n-1 at most. The demonstration is constructive, relying on first factoring matrix subspaces equivalent to polynomials in a permutation matrix over diagonal matrices into linear factors. For the linear factors, the sum of two scaled permutations is factored into the product of a circulant matrix and two diagonal matrices. Extending the monomial group, both low degree and sparse polynomials in a permutation matrix over diagonal matrices, together with their permutation equivalences, constitute a fundamental sparse matrix structure. Matrix analysis gets largely done polynomially, in terms of permutations only.

Original language | English |
---|---|

Pages (from-to) | 1018-1033 |

Number of pages | 16 |

Journal | Journal of Fourier Analysis and Applications |

Volume | 21 |

Issue number | 5 |

DOIs | |

Publication status | Published - 26 Mar 2015 |

MoE publication type | A1 Journal article-refereed |

## Keywords

- Circulant matrix
- Diagonal matrix
- Matrix factoring
- Multiplicative Fourier compression
- Polynomial factoring
- Sparsity structure