Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
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

3 Answers 3

up vote 3 down vote accepted

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

share|improve this answer
    
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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.