6
$\begingroup$

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

  • 1
    here is a paper stating that $A$ is non-invertible precisely if $n$ is a multiple of $4$ as you stated: http://www.math.science.cmu.ac.th/thaijmath/vol%206%20no%202%202008/Vol6_No2_2008/Volume%206%20%282008%29%20Number%202%20%20331-336.pdf2012-11-11

3 Answers 3

3

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

  • 0
    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!2012-11-13
4

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.

3

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.