# Multiplication of circulant matrices with a diagonal matrix

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$$.

## 1 Answer

This problem is essentially equivalent to matrix multiplication. Let's look at $\sum_{i=1}^{n}X_{i}RY_{i}$ first, where $X_i$ and $Y_i$ are diagonal matrices. If $A$ is the matrix with the diagonal entries of $X_i$ as the $i$-th column, and $B$ is the matrix with the diagonal entires of $Y_i$ as the $i$-th row, then the entry-wise product of $AB$ and $R$ is equal to $\sum_{i=1}^{n}X_{i}RY_{i}$. If all entries of $R$ are non-zero (even if it should not be full rank), then $AB$ can be reconstructed from $\sum_{i=1}^{n}X_{i}RY_{i}$. Hence the computational complexity of this problem is identical to the computational complexity of matrix multiplication.

For the case $\sum_{i=1}^{n}A_{i}DB_{i}$, where $A_i$ and $B_i$ are circulant matrices, we first have to apply FFT to $A_i$, $B_i$ and $D$, to get back to the case $\sum_{i=1}^{n}X_{i}RY_{i}$. We need $2n+1$ FFTs of size $n$ for this, so this adds $n^2\log n$ to the complexity.
Also in this case, it can happen that the FFT of $D$ has only very few non-zero entries. In this special case, the complexity will be quadratic times the number of non-zero entries. This can happen, if the i-th entry on the diagonal of $D$ is $r^i$, where $r$ is the $n$th root of unity. But already when $D$ has the same entries but permuted arbitrarily, the FFT of $D$ will not be sparse (in general).