wheredenoting the -dimensional column vector of zeros by we have that - - - - clearlythe matrix is (sparsetoeplitz matrix circulant matrix is special toeplitz matrix which is obtained from vector by circularly permuting its indices as followsc cn- cn- ( cn- cn- cn- cn- note that is completely determined by the elements of its first columnc to illustrate how structured matrices allow for faster matrix computationsconsider solving the linear systeman xn an for xn [ xn ]where an [ an ]and an- an- an- an : - an- an- ( is real-valued symmetric positive-definite toeplitz matrix (so that it is invertiblenote that the entries of an are completely determined by the right-hand side of the linear equationvector an as we shall see shortly in example the solution to the more general linear equation an xn bn where bn is arbitrarycan be efficiently computed using the solution to this specific system an xn an obtained via special recursive algorithm (algorithm belowfor every the toeplitz matrix ak satisfies ak pk ak pk where pk is permutation matrix that "flipsthe order of elements -rows when premultiplying and columns when post-multiplying for example where circulant matrix