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