On inverting circulant matrices

The elements of the inverse of a circulant matrix having only three non-zero elements in each row (located in cyclically adjacent columns) are derived analytically from the solution of a recurrence equation. Expressing any circulant as a product containing these three-element-type circulants then provides an algorithm for inverting circulants in general. Extension is also made to deriving generalized inverses of certain singular circulants.