Multiply circulant matrix by usual vector

Question

I found nice way to multiply circulant matrix by a usual vector (page 2):

http://web.mit.edu/18.06/www/Spring17/Circulant-Matrices.pdf

It means that I can find $\vec{y} = C\vec{x}$ in the following way (example in Python):

"""
I want to multiply the following matrix
            [[1, 2, 3],
             [3, 1, 2],
             [2, 3, 1]]
by vector [1, 2, 3]
"""
import numpy as np

# first raw of the circulant
c = [1, 2, 3]
# vector
x = [1, 2, 3]

# circular convolution 
y = np.fft.ifft(np.fft.fft(c) * np.fft.fft(x))

The result I obtained in this way is array([13.+0.j, 13.+0.j, 10.+0.j]) but the actual result that can be obtained by straight matrix-vector multiplication is array([14, 11, 11]). Why these results are different?

Answer 1

So guys, I found the answer. These results are different becase the multiplication of circulant matrix by vector is not circular convolution.

It's easy to prove that $$ \mathbf{y}=\hat{C}\mathbf{x}=DFT[DFT[\mathbf{c}]*IDFT[\mathbf{x}]] $$ where $\mathbf{c}$ is the first row of the circulant matrix, $DFT[\cdot]$ denotes discrete Fourier transform, and $*$ is component-wise multiplication (Hadamart product).

To prove that, use properties of diagonalizable matrices and DFT-related properties of circulants matrices.

Let it remain as an exercise :)