ABSTRACT
Circulant matrices can be multiplied with vectors efficiently. Let A := (ai,j) ∈ Rn×n be a circulant matrix and x := (x1, x2, . . . , xn)T ∈ R
n be a column-vector of length n ∈ N. We have
(Ax)i = n∑
ai,j xj (1 ≤ i ≤ n) . (5.33)
The circulant structure of A now gives ai,j = a(i−j mod n)+1,1 which leads to
(Ax)i = n∑
If we now define the n-periodic sequences a˜ := (a˜i)i∈Z, x˜ := (x˜i)i∈Z, containing the elements of the first column of A and the elements of the vector x, respectively, by
a˜i := a(i mod n)+1,1, x˜i := x(i mod n)+1, (5.35)
we can write the result of their discrete periodic convolution a˜ ∗ x˜ as
(a˜ ∗ x˜)i = n−1∑ j=0
a(i+1−j mod n)+1,1 xj = (Ax)i+1 (0 ≤ i ≤ n− 1) .
We can calculate the result of the matrix-vector product A x by a discrete periodic convolution of the vectors a and x, where a is the column-vector containing the first column of A. The Discrete Convolution Theorem tells that a discrete periodic convolution corresponds
to a component-wise multiplication in the frequency domain. If we now denote an application of the discrete Fourier transform (DFT) to a vector x by DFT (x) and analogously an application of the inverse transform (IDFT) by IDFT (x), we therefore get
