Let $A_{i}$, $B_{i}$ be a sequence of circulant matrices of size $n \times n$.
We know that $\sum_{i=1}^{n}A_{i}B_{i}$ can be calculated in quadratic time (use FFT to diagonalize and add the diagonal matrices and apply IFFT).
Supposing $D$ is an arbitrary diagonal matrix (for simplicity, let $r$ be $n$th root of unity and consider the diagonal elements as all distinct powers less than $n$ of $r$).
What is the complexity of $\sum_{i=1}^{n}A_{i}DB_{i}$? I suspect it to be quadratic since I am including the same diagonal matrix($O(n)$ terms) in each term.
Consider $R$ a circulant matrix of size $n \times n$ with first row made of distinct powers less than $n$ of $r$. Let $X_{i}$ and $Y_{i}$ for $i=1\rightarrow n$ be full-rank diagonal matrices.
What is the complexity of $\sum_{i=1}^{n}X_{i}RY_{i}$? Again I suspect this to be quadratic.
The matrices $D$ and $R$ that are defined with respect to $r$ is artificial. I am looking for the case of general diagonal $D$ and general full-rank circulant $R$.