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$).

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$.)
