Relationship between the Path Graph, $P_v$ and the Cycle Graph, $C_{2v}$

Question

In Daniel A. Spielman's book Spectral and Algebraic Graph Theory,
(http://cs-www.cs.yale.edu/homes/spielman/sagt/sagt.pdf) on page 54, he notes the following relationship between a Path and a Cycle graph.

$$(I_n\text{ }\text{ }I_n)L_{R_{2n}}\begin{pmatrix} I_n\\ I_n \end{pmatrix}=2L_{P_n}$$ I'm assuming the following that if $n=2$, $$(I_n\text{ }\text{ }I_n)=\begin{bmatrix} 1 & 0 & 1 & 0\\ 0 & 1 & 0 & 1 \end{bmatrix} \text{ and } \begin{pmatrix} I_n\\ I_n \end{pmatrix}=\begin{bmatrix} 1 & 0 \\ 0 & 1 \\ 1 & 0 \\ 0 & 1 \end{bmatrix}$$ Am I right in makin this assumption?

I tried to replicate this in Mathematica with n=2, but instead of $2L_{P_2}$ I got $4L_{P_n}$. I'm not sure where I am going wrong, other than perhaps not understanding what $(I_n\text{ }\text{ }I_n)$ means.

Answer 1

With the usual vertex numbering of $C_n$ and $C_{2n}$, you are correct, and in general you will get $2 L(C_n)$ as the algebraic result here.

That's because the multiplication we're doing has the result of identifying vertices $i$ and $i+n$ for $i=1, 2, \dots, n$. If you identify opposite vertices of $C_{2n}$, you get a multigraph on vertices $\overline{1}, \dots, \overline{n}$ that has two copies of every edge of $C_n$.

For $n=2$, $C_2$ can only be interpreted as a multigraph that itself is a doubled $P_2$, so instead of $2 L(C_2)$ you get $4L(P_2)$, but that's an exception.

---

What the proof in this textbook does is number the vertices of $C_{2n}$ differently, so that it's not always opposite vertices that are identified. Another way to do this is to use the usual vertex ordering, but do a different identification: if vertices of $C_{2n}$ are numbered $1, 2, \dots, 2n$ around the cycle, to identify vertex $i$ with vertex $2n+1-i$.

The result of this identification is a multigraph with vertex set $\overline{1}, \dots, \overline{n}$, with two edges between $\overline{i}$ and $\overline{i+1}$ and loops at $\overline{1}$ and $\overline{n}$. The loops don't contribute to the Laplacian matrix, and the rest of the graph is a doubled $P_n$, so then we do get the result we wanted.

Instead of $\begin{bmatrix}I_n & I_n\end{bmatrix}$, we get this algebraically by using $\begin{bmatrix}I_n & \operatorname{rev}(I_n)\end{bmatrix}$, where $\operatorname{rev}(I_n)$ reverses the rows (or the columns) of the identity matrix.

We can use Mathematica to check that the algebra works out in both cases as follows:

ii[n_] := Join[IdentityMatrix[n], IdentityMatrix[n]]
irevi[n_] := Join[IdentityMatrix[n], Reverse@IdentityMatrix[n]]

Transpose[ii[10]].KirchhoffMatrix[CycleGraph[20]].ii[10] == 
    2 KirchhoffMatrix[CycleGraph[10]] (* True *)

Transpose[irevi[10]].KirchhoffMatrix[CycleGraph[20]].irevi[10] == 
    2 KirchhoffMatrix[PathGraph[Range[10]]] (* True *)

(Here, KirchhoffMatrix is what Mathematica calls the Laplacian.)