where - ( - on- ( - ( - ) the matrix is so-called vandermonde matrixand is clearly symmetric ( fmoreoverfn is in fact unitary matrix and hence its inverse is simply its complex conjugate fn thusf- / and we have that the inverse discrete fourier transform (idftis given by - -st ( xt = or in terms of matrices and vectorsx fe / observe that the idft of vector is related to the dft of its complex conjugate ysince / / consequentlyan idft can be computed via dft there is close connection between circulant matrices and the dft to make this connection concretelet be the circulant matrix corresponding to the vector cn and denote by the -th column of the discrete fourier matrix ft thenthe -th element of is - ( -kmod otk - cy ot( -yy= = ots |{zn- cy -ty -th element of = { ls hencethe eigenvalues of are lt cf with corresponding eigenvectors collecting the eigenvalues into the vector [ ln- ]fcwe therefore have the eigen-decomposition diag(lf/ consequentlyone can compute the circular convolution of vector [ an ]and [ cn- ]by series of dfts as follows construct the circulant matrix corresponding to thenthe circular convolution of and is given by ca proceed in four steps compute fa/ compute fc inverse discrete fourier transform