# The inverse of the adjacency matrix of an undirected cycle

Is there an expression for $A^{-1}$, where $A_{n \times n}$ is the adjacency matrix of an undirected cycle $C_n$, in terms of $A$?

I want this expression because I want to compute $A^{-1}$ without actually inverting $A$. As one answer suggests, $A$ is non-invertible for certain values of $n$ (namely when $n$ is a multiple of $4$).

-
here is a paper stating that $A$ is non-invertible precisely if $n$ is a multiple of $4$ as you stated: math.science.cmu.ac.th/thaijmath/vol%206%20no%202%202008/… – Julian Kuelshammer Nov 11 '12 at 23:44

Since the graph is circularly symmetric, once you find one column of $A^{-1}$, the rest are obtained by simple rotation. It's actually very easy to formulate this as a graph labelling problem: single out one vertex $v$, and try to label each vertex of $C_n$ with a real number so that $v$'s two neighbours sum to $1$ and the neighbours of every other vertex sum to $0$.

If you think about it, such a labelling corresponds to exactly the column of $A^{-1}$ that corresponds to $v$.

You'll find that when $n$ is divisible by $4$ you end up with a contradiction, but in every other case there is a pattern that works depending on whether $n$ is $1$, $2$ or $3$ mod $4$. (Hint: satisfy the first requirement by labelling both of $v$'s neighbours with $\tfrac12$.)

-
As in my answer, the matrix is not invertible if $n=4$, but you seem to be suggesting it's not invertible whenever $n$ is divisible by $4$, whereas I think $n=4$ is the only noninvertible example (assuming $n\ge3$). Have I misunderstood what you have written? – Gerry Myerson Nov 13 '12 at 5:35
@GerryMyerson Yes, all multiples of $4$ are singular. It's easy to see that the discrete Fourier modes $(\omega^i)_i$ form a basis of eigenvectors for any circulant matrix (here $\omega$ ranges over $n$th roots of unity). The eigenvalues of $C_n$ are therefore of the form $\omega + 1/\omega = 2 \Re \omega$, which can be zero iff $4\mid n$. – Erick Wong Nov 13 '12 at 7:06
Yes, of course, you are right. I thought I knew a formula for the eigenvalues of a circulant, and when I applied it to $n=8$ it didn't give me zero, so I guess I don't know a formula after all. Thanks! – Gerry Myerson Nov 13 '12 at 12:10

For $n=4$, the matrix in question is $$\pmatrix{0&1&0&1\cr1&0&1&0\cr0&1&0&1\cr1&0&1&0\cr}$$ which is patently noninvertible.

-

There is a paper called "On inverting circulant matrices" by S.R. Searle, doi 10.1016/0024-3795(79)90007-7. It is related to your question, but I am not educated enough to condense it to a simple formulae for your precise case. Moreover it has three nonzero elements in each row column.

-