La inversa de la matriz de adyacencia de un ciclo no dirigido

Question

¿Existe una expresión para $A^{-1}$ , donde $A_{n \times n}$ es la matriz de adyacencia de un ciclo no dirigido $C_n$ en términos de $A$ ?

Quiero esta expresión porque quiero calcular $A^{-1}$ sin invertir realmente $A$ . Como sugiere una respuesta, $A$ no es invertible para ciertos valores de $n$ (es decir, cuando $n$ es un múltiplo de $4$ ).

Answer 1

Para $n=4$ la matriz en cuestión es $$\pmatrix{0&1&0&1\cr1&0&1&0\cr0&1&0&1\cr1&0&1&0\cr}$$ que es evidentemente no invertible.

Answer 2

Hay un artículo llamado "On inverting circulant matrices" de S.R. Searle, doi 10.1016/0024-3795(79)90007-7 . Está relacionado con tu pregunta, pero no tengo la suficiente formación para condensarlo en una fórmula sencilla para tu caso concreto. Además, tiene tres elementos no nulos en cada columna de la fila.

Answer 3

Como el gráfico es circularmente simétrico, una vez que se encuentra una columna de $A^{-1}$ El resto se obtiene por simple rotación. En realidad, es muy fácil formularlo como un problema de etiquetado de grafos: señalar un vértice $v$ y tratar de etiquetar cada vértice de $C_n$ con un número real para que $v$ Los dos vecinos de la empresa suman $1$ y los vecinos de cualquier otro vértice suman $0$ .

Si se piensa en ello, tal etiquetado corresponde exactamente a la columna de $A^{-1}$ que corresponde a $v$ .

Verá que cuando $n$ es divisible por $4$ se termina con una contradicción, pero en todos los demás casos hay un patrón que funciona dependiendo de si $n$ es $1$ , $2$ o $3$ mod $4$ . (Sugerencia: satisfaga el primer requisito etiquetando ambos $v$ de los vecinos con $\tfrac12$ .)