The inversion of a circulant matrix (Q1062724)

A method of inverting a circulant matrix and an expression for the inversion of a circulant matrix are obtained. Let \(A=(A_{uv})\) \((u,v=0,1,...,m-1)\) be a block matrix of order m where the \(A_{uv}'s\) are \(n\times n\) matrices. A is called a circulant matrix if \(A_{uv}=A_{(m-u+v)mod m}\) \((u,v=0,1,...,m-1)\). Let \(\Omega =(\Omega_ 0^{ij})\) where \(\Omega_ 0^{ij}=\exp (2\pi lji/m)E_ n/\sqrt{m}\) \((l,j=0,1,...,m-1)\) in which \(E_ n\) is the unit matrix of order n. Section 2 proves the theorem: For a circulant matrix A one always has \(\Omega^*A\Omega =C\) where C is a quasi-diagonal matrix of order m, and \(C_ l=\sqrt{m}\sum^{m-1}_{k=0}\Omega_ 0^{lk}A_ k\). Section 3 presents a method of inverting the circulant matrix A and gives the expression of \(A^{-1}\) as follows: \(A^{-1}=(B_{uv})\) where \(B_{uv}=B_{(m-u+v)mod m}\) in which \(B_ r=(1/m)\sum^{m- 1}_{u=0}\exp (-2\pi rui)C_ u^{-1}\) \((r=0,1,...,m-1)\). The last section applies the method to an important example which occurs in cubic spline interpolations with periodic boundary conditions.