How to Find the Inverse of a Circulant Matrix

A circulant matrix is completely determined by one row: every subsequent row is a cyclic shift of the preceding row. The useful fact is that circulant matrices are diagonalized by the discrete Fourier transform (DFT). This turns matrix inversion into $n$ scalar divisions.

The inverse, when it exists, is itself circulant. The main task is therefore to determine when the matrix is invertible and compute the first row of its inverse.

Define the circulant matrix and its polynomial

Let

$$C=\begin{pmatrix} c_0&c_1&c_2&\cdots&c_{n-1}\\ c_{n-1}&c_0&c_1&\cdots&c_{n-2}\\ c_{n-2}&c_{n-1}&c_0&\cdots&c_{n-3}\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ c_1&c_2&c_3&\cdots&c_0 \end{pmatrix}.$$

Associate with its first row the polynomial

$$p(z)=c_0+c_1z+c_2z^2+\cdots+c_{n-1}z^{n-1}.$$

Let

$$\omega_m=e^{2\pi i m/n},\qquad m=0,1,\ldots,n-1,$$

be the $n$th roots of unity. The eigenvalues of $C$ are

$$\lambda_m=p(\omega_m)=\sum_{k=0}^{n-1}c_k\omega_m^k.$$

Thus, the eigenvalues are exactly the discrete Fourier transform of the first row.

Invertibility criterion

The matrix $C$ is invertible if and only if every eigenvalue is nonzero:

$$C\text{ is invertible} \iff p(\omega_m)\ne 0\quad\text{for every }m=0,\ldots,n-1.$$

Equivalently, $p(z)$ and $z^n-1$ have no common root. This gives a quick test without calculating a determinant.

When the matrix is invertible, its inverse has eigenvalues

$$\frac{1}{p(\omega_m)},$$

because the eigenvalues of an inverse matrix are the reciprocals of the original nonzero eigenvalues.

Formula for the inverse

Write the first row of $C^{-1}$ as

$$(d_0,d_1,\ldots,d_{n-1}).$$

Then the coefficients are obtained using the inverse DFT:

$$d_r=\frac{1}{n}\sum_{m=0}^{n-1}\frac{\omega_m^{-r}}{p(\omega_m)}, \qquad r=0,1,\ldots,n-1.$$

Therefore,

$$C^{-1}=\operatorname{circ}(d_0,d_1,\ldots,d_{n-1}).$$

The same result can be expressed polynomially. Define

$$q(z)=d_0+d_1z+\cdots+d_{n-1}z^{n-1}.$$

Then $q$ is the unique polynomial of degree less than $n$ satisfying

$$p(z)q(z)\equiv 1\pmod{z^n-1}.$$

In practical terms, multiply $p(z)q(z)$ and reduce every $z^n$ to $1$; the result must be $1$.

Worked example

Consider

$$C=\begin{pmatrix} 2&1&0\\ 0&2&1\\ 1&0&2 \end{pmatrix}.$$

Its first row gives

$$p(z)=2+z.$$

The cube roots of unity are $1$, $\omega$, and $\omega^2$, where $\omega^3=1$ and $\omega\ne1$. The eigenvalues are

$$2+1=3, \qquad 2+\omega, \qquad 2+\omega^2.$$

None is zero, so $C$ is invertible.

To find the first row of the inverse, seek

$$q(z)=d_0+d_1z+d_2z^2$$

such that

$$(2+z)q(z)\equiv1\pmod{z^3-1}.$$

Try

$$q(z)=\frac{1}{9}(4-2z+z^2).$$

Indeed,

$$\begin{aligned} (2+z)(4-2z+z^2) &=8-4z+2z^2+4z-2z^2+z^3\\ &=8+z^3\\ &\equiv9\pmod{z^3-1}. \end{aligned}$$

Hence

$$q(z)=\frac{4}{9}-\frac{2}{9}z+\frac{1}{9}z^2,$$

so

$$C^{-1}=\begin{pmatrix} \frac49&-\frac29&\frac19\\ \frac19&\frac49&-\frac29\\ -\frac29&\frac19&\frac49 \end{pmatrix}.$$

Direct multiplication confirms that $CC^{-1}=I$.

A computational procedure

For a large matrix, use the following algorithm:

1. Read the first row $(c_0,\ldots,c_{n-1})$.
2. Compute its DFT, obtaining $\lambda_m=p(\omega_m)$.
3. Check whether any $\lambda_m$ is zero or numerically very close to zero.
4. Replace each eigenvalue by $1/\lambda_m$.
5. Apply the inverse DFT.
6. Use the resulting vector as the first row of $C^{-1}$.

Using fast Fourier transforms, this can be done in approximately $O(n\log n)$ operations rather than the $O(n^3)$ work of ordinary dense matrix inversion. For numerical calculations, if all eigenvalues are nonzero but the smallest is very small in magnitude compared with the largest, the matrix may be poorly conditioned; for a circulant matrix, $\kappa_2(C)=\max_m|\lambda_m|/\min_m|\lambda_m|$.

Common mistakes

Confusing cyclic-shift conventions

Some authors define a circulant matrix using left shifts rather than right shifts. The eigenvalue formula may then use $\omega_m^{-k}$ instead of $\omega_m^k$. The invertibility criterion is unchanged, but the displayed first row of the inverse may be reversed cyclically.

Checking only the row sum

The value $p(1)=c_0+\cdots+c_{n-1}$ is only one eigenvalue. A nonzero row sum does not guarantee invertibility; all $n$ values $p(\omega_m)$ must be nonzero.

Assuming every circulant matrix is invertible

For example, the all-ones matrix has first-row polynomial

$$p(z)=1+z+\cdots+z^{n-1}.$$

This polynomial vanishes at every nontrivial $n$th root of unity, so the matrix is singular for $n>1$.

Forgetting that the inverse remains circulant

Once one row of $C^{-1}$ has been found, the other rows are obtained by the same cyclic shifts. There is no need to compute every entry independently.