Proof. Let \(u \in C_i\). Since \(G\) is \(d\)-regular, \(u\) has exactly \(d\) out-neighbours distributed across the cells, with \(b_{ij}\) of them falling in \(C_j\), so \(\sum_{j=1}^{r} b_{ij} = d\) for all \(i\). Now fix \(C_j\). Let \(|C_1| = |C_2| = \cdots = |C_r|=\alpha\), each of the \(\alpha\) vertices in \(C_j\) has in-degree \(d\), so the total number of directed edges entering \(C_j\) is \(\alpha d\). Each cell \(C_i\) contributes exactly \(\alpha\,b_{ij}\) directed edges into \(C_j\), so \(\sum_{i=1}^{r} \alpha\,b_{ij} = \alpha d,\) we get \(\sum_{i=1}^{r} b_{ij} = d\) for all \(j\). Hence both row and column sums equal \(d\), and \(G/\pi\) is \(d\)-regular. ◻

Proof. \((\Rightarrow)\) By the equitability of \(\pi\), we have \(AQ=Q\tilde{A}\). Since by Corollary 1, the quotient graph \(G/\pi\) is \(d\)-regular. We have \(\left(\sum_{j=1}^d P_j\right) Q = Q \left(\sum_{j=1}^d \widetilde{P}_j\right)\). Assume \(P_j Q = Q\widetilde{P}_j\) for each \(j = 1,\ldots,d\). Then \[\label{permuatation} \sum_{j=1}^{d} E_{jj} \otimes P_j Q = \sum_{j=1}^{d} E_{jj} \otimes Q\widetilde{P}_j.\tag{4}\] Applying \((I_d \otimes Q^\top)\) on the left of  4 and using \(Q^\top Q = I_{|\pi|}\), we obtain \[\label{quotient95permutation} \sum_{j=1}^{d} E_{jj} \otimes Q^\top P_j Q = \sum_{j=1}^{d} E_{jj} \otimes \widetilde{P}_j.\tag{5}\] Hence by  5 the quotient shift matrix satisfies \[\widetilde{S} = \sum_{j=1}^d E_{jj} \otimes (Q^\top P_j Q) = \sum_{j=1}^d (E_{jj} \otimes Q^\top)\, S\, (E_{jj} \otimes Q) = (I_d \otimes Q^\top)\, S\, (I_d \otimes Q).\]

\((\Leftarrow)\) Assume \((I_d \otimes Q^\top)\,S\,(I_d \otimes Q) = \widetilde{S}\). Expanding via the mixed-product property and using the linear independence of \(\{E_{jj}\}\), we obtain \[Q^\top P_j Q = \widetilde{P}_j \qquad \text{for each } j.\] Left-multiplying by \(Q\) gives \(QQ^\top P_j Q = Q\widetilde{P}_j\). Since \(\pi\) is equitable, by Lemma 1 the projector \(QQ^\top\) commutes with each \(P_j\), that is, \(QQ^\top P_j = P_j QQ^\top\). Therefore \[P_j Q = Q\widetilde{P}_j, \qquad j = 1,\ldots,d. \qquad\] ◻

Proof. Recall that \(\widetilde{S} = \sum_{j=1}^d E_{jj} \otimes \widetilde{P}_j\). Using the orthogonality of the coin-basis projectors, \(E_{jj}E_{kk} = \delta_{jk}E_{jj}\), we compute \[\widetilde{S}^2 = \sum_{j=1}^d \sum_{k=1}^d (E_{jj}E_{kk}) \otimes (\widetilde{P}_j\widetilde{P}_k)= \sum_{j=1}^d E_{jj} \otimes \widetilde{P}_j^2.\] \((\Rightarrow)\) Suppose \(\widetilde{S}^2 = I_{d|\pi|}\), that is, \[\sum_{j=1}^d E_{jj} \otimes \widetilde{P}_j^2 = \sum_{j=1}^d E_{jj} \otimes I_{|\pi|}.\] Since the matrices \(\{E_{jj}\}_{j=1}^d\) are linearly independent, we may equate the \(j\)-th block on each side to conclude \(\widetilde{P}_j^2 = I_{|\pi|}\) for all \(j = 1, \ldots, d\).

\((\Leftarrow)\) Suppose \(\widetilde{P}_j^2 = I_{|\pi|}\) for all \(j = 1, \ldots, d\). Then \[\widetilde{S}^2 = \sum_{j=1}^d E_{jj} \otimes \widetilde{P}_j^2 = \sum_{j=1}^d E_{jj} \otimes I_{|\pi|} = I_d \otimes I_{|\pi|} = I_{d|\pi|}.\] This completes the proof. ◻

Proof. Fix \(\ell \in \{1, \ldots, d\}\). Since \(P_\ell\) is a permutation matrix, \(G_\ell\) is \(1\)-regular, each vertex \(v \in V\) has exactly one outgoing arc \((v, P_\ell(v))\), so \(A(\mathrm{LD}(G_\ell)) = P_\ell\). By Lemma 3, the arc cells \(C'_{ij}\) form an equitable partition of \(\mathrm{LD}(G_\ell)\). Any arc \((v_i, P_\ell(v_i)) \in C'_{ik}\) has its unique out-neighbor \((P_\ell(v_i), P_\ell^2(v_i))\) in \(C'_{ks}\), so the out-neighbor count into \(C'_{\ell s}\) equals \(1\) if \(\ell = k\) and \(0\) otherwise, independent of the arc chosen. Since \(\pi\) is equitable and \(P_\ell\) is consistent with the arc structure, \(P_\ell\) maps each cell \(C_k\) \((k \in \{1,\ldots,r\})\) entirely into a single cell \(C_{\sigma_\ell(k)}\), defining a well-defined permutation \(\sigma_\ell\) on \(\{1, \ldots, r\}\), and \(\widetilde{P}_\ell\) is the corresponding \(r \times r\) permutation matrix. For the \(k\)-th column \(Q_k\) of \(Q\), since \(P_\ell\) maps \(C_k\) bijectively onto \(C_{\sigma_\ell(k)}\) with \(|C_k| = |C_{\sigma_\ell(k)}| = m\), we have \(P_\ell\, Q_k = Q_{\sigma_\ell(k)} = Q\,\widetilde{P}_\ell\, e_k.\) Since this holds for every \(k \in \{1, \ldots, r\}\), we conclude \[\label{eq:shunt-intertwine} P_\ell Q = Q\widetilde{P}_\ell.\tag{6}\]  ◻

Proof. Let \((v_i, v_p)\) be any arc of \(G\) lying in cell \(T_p\), and let \(T_q\) be any cell of \(\tau\), where \(1\le p,q\le 2n\). We count the neighbors of \((v_i, v_p)\) in \(T_q\) inside \(LD(G)\). By definition of the line digraph, an arc \((v_\ell, v_m)\) is adjacent to \((v_i, v_p)\) in \(LD(G)\) if and only if \(v_\ell = v_p\). Therefore the neighbors of \((v_i,v_p)\) lying in \(T_q\) are exactly \(S \;=\; \{(v_\ell, v_m) \in T_q : v_\ell = v_p\}.\) By construction, every arc in \(T_q\) has terminal vertex \(v_q\), so every arc in \(T_q\) has the form \((v_\ell, v_q)\) for some \(v_\ell\). Imposing \(v_\ell = v_p\) reduces \(S\) to \(S \;=\; \{(v_p, v_q) \in T_q\} \;=\; \{(v_p, v_q) \in E(G)\}.\) Hence \[\label{eq9520} |S| \;=\; A_{pq},\tag{7}\] where \(A_{pq}\) is the \((p,q)\)-entry of the adjacency matrix \(A\) of \(G\). Since \(|S| = A_{pq}\) depends only on \(p\) and \(q\), and not on the particular arc \((v_i, v_p)\) chosen within \(T_p\), every arc in \(T_p\) has exactly \(A_{pq}\) neighbors in \(T_q\). This holds for all \(1\le p,q\le 2n\), so \(\tau\) is an equitable partition of \(LD(G)\).

Now let \(Q_\tau\) be the normalized characteristic matrix of \(\tau\). For any equitable partition the standard identity gives \[\label{eq9521} A_{LD(G)}\,Q_\tau \;=\; Q_\tau\,B,\tag{8}\] where \(B\) is the quotient matrix with \((p,q)\)-entry equal to the number of neighbors in \(T_q\) of any arc in \(T_p\). Thus from 7 , we have \[B_{pq} \;=\; |S| \;=\; A_{pq} \qquad \text{for all } 1\le p,q\le 2n,\] so \(B = A\). Substituting in 8 gives \[A_{LD(G)}\,Q_\tau \;=\; Q_\tau\,A.\] ◻

Proof. The proof follows the same argument as the proof of Lemma 4. ◻

Proof. The result follows directly from the preceding Lemma 4 and Lemma 5. The first isomorphism \[LD(G)/\tau \cong G\] is established by the construction of the arc partition \(\tau\), where arcs are grouped according to their terminal vertices. Similarly, the second isomorphism \[LD(G/\pi)/\sigma \cong G/\pi\] follows from the corresponding induced arc partition \(\sigma\) on the quotient graph. This construction shows that forming the line digraph and then taking the corresponding arc partition yields a graph isomorphic to the original graph (or its quotient), completing the proof. ◻

Proof. Since \(\pi\) is an equitable vertex partition of \(G\), there exists a normalized characteristic matrix \(Q\) such that \[\label{eq:vertex} AQ = Q\widetilde{A},\tag{13}\] where \(A\) is the adjacency matrix of \(G\) and \(\widetilde{A}\) is the quotient matrix of \(G/\pi\). Since \(\sigma\) is an equitable arc partition of \(L(G/\pi)\), there exists a normalized characteristic matrix \(\widetilde{Q}\) such that \[\label{eq:arc} A_{LD(G/\pi)}\,\widetilde{Q} = \widetilde{Q}\,\widetilde{A},\tag{14}\] where \(\widetilde{A}\) is the quotient matrix of \(G/\pi\) by Theorem 8. Now suppose \(LD(G/\pi)\cong G\), so that \(A_{LD(G/\pi)}=A\). Substituting into Equation 14 gives \(A\widetilde{Q} = \widetilde{Q}\,\widetilde{A}.\) Comparing with Equation 13 , both \(Q\) and \(\widetilde{Q}\) satisfy the same Equation, and since the normalized characteristic matrix of an equitable partition is unique, we conclude that \[Q = \widetilde{Q}.\] For the converse, \(Q = \widetilde{Q}\) does not imply \(LD(G/\pi) \cong G\) in general. As a counterexample, see Example 21. ◻

Proof. (a) Since \(Q_{\tau}^{\top}Q_{\tau} = I\), by Equations 9 and 10 , we have \[R Q_{\tau} = (2Q_{\tau}(\widetilde{Q} \widetilde{Q}^\top)Q_{\tau}^{\top} - I)Q_{\tau} = Q_{\tau}(2\widetilde{Q} \widetilde{Q}^\top - I) = Q_{\tau}\widetilde{R}.\] (b) By Lemma 2 and Corollary 4, and using \(Q_{\tau} = I_d \otimes \widetilde{Q},\quad Q=\widetilde{Q}\), we have

\[\widetilde{U} = \widetilde{S} \widetilde{R} = (I_d \otimes \widetilde{Q}^\top)\, S\, (I_d \otimes \widetilde{Q})\, \widetilde{R}=Q_\tau SQ_\tau \widetilde{R}.\] Using part (a), we have \[\widetilde{U} = Q_\tau^{\top} U Q_\tau.\] By Lemma 1, \(Q_\tau Q_\tau^{\top}\) commutes with \(U\), and hence \(\operatorname{Im}(Q_\tau)\) is invariant under \(U\). This gives \(U Q_\tau = Q_\tau \widetilde{U}\). Applying this relation inductively yields \[\label{eq:Uk-intertwine} U^k Q_\tau = Q_\tau \widetilde{U}^k \quad \text{for all } k \geq 0.\tag{15}\] Multiplying both sides of 15 on the left by \(Q_\tau^{\top}\) and using the isometry property \(Q_\tau^{\top}Q_\tau = I\), we obtain \[Q_\tau^{\top}\, U^k\, Q_\tau = \widetilde{U}^k \quad \text{for all } k \geq 0.\] ◻

Proof. Since \(\operatorname{Im}(Q_\tau)\) is \(U\)–invariant and \(Q_\tau\) has orthonormal columns, we have the basic relation from Proposition 10 for all \(k\ge0\), \[\label{eq4644620} \widetilde{U}^k = Q_\tau^\top U^k Q_\tau,\qquad U^k Q_\tau = Q_\tau\widetilde{U}^k.\tag{16}\] (\(\Rightarrow\)) Assume that \(\widetilde{U}\) exhibits PST at time \(k\), that is, \[\widetilde{U}^k x = y, \quad \text{for some } x,y \in \operatorname{Im}(\widetilde{Q}).\] From Equation 16 , we obtain \[U^k Q_\tau x = Q_\tau \widetilde{U}^k x = Q_\tau y.\] Hence, \(U\) exhibits PST from \(Q_\tau x\) to \(Q_\tau y\) at time \(k\).

(\(\Leftarrow\)) Conversely, suppose that \(U\) exhibits PST at time \(k\), that is, \[U^k Q_\tau x = Q_\tau y, \quad \text{for some } x,y \in \operatorname{Im}(\widetilde{Q}).\] Multiplying on the left by \(Q_\tau^{\top}\) and using \(Q_\tau^{\top} Q_\tau = I\), together with 16 , we obtain \[\widetilde{U}^k x = Q_\tau^{\top} U^k Q_\tau x = Q_\tau^{\top} Q_\tau y = y.\] Thus \(\widetilde{U}\) exhibits PST from \(x\) to \(y\) at time \(k\). Therefore, PST in the quotient system is equivalent to PST in the original system restricted to the invariant subspace \(\operatorname{Im}(Q_\tau)\). ◻

Proof. By Theorem 8, we have the isomorphisms \(LD(G)/\tau \;\cong\; G \quad \text{and} \quad LD(G/\pi)/\sigma \;\cong\; G/\pi,\) from which the result follows. ◻

Proof. Since \(A(G) = A(LD(G/\pi))\), the graphs \(G\) and \(L(G/\pi)\) are identical, and in particular have the same vertex set. Therefore \[|V(G)| = |V(L(G/\pi))| = |\mathcal{A}(G/\pi)|,\] which gives \(|\mathcal{A}(G/\pi)| = nd\). Now consider the dimensions of each side of \(Q_\tau = \widetilde{Q}\otimes I_d\). Since \(|\mathcal{A}(G)|=2nd\) and \(\tau\) partitions \(\mathcal{A}(G)\) into \(n\) cells, \(Q_\tau \in \mathbb{R}^{2nd \times 2n}.\) Since \(|\mathcal{A}(G/\pi)|=nd\) and \(\sigma\) partitions \(\mathcal{A}(G/\pi)\) into \(n\) cells, \(\widetilde{Q} \in \mathbb{R}^{nd \times n}, \quad Q_\tau= I_d\otimes \widetilde{Q} \in \mathbb{R}^{nd^2 \times nd}.\) For the two sides to be equal, their column dimensions must agree, thus \(2n = nd \implies d = 2.\) Therefore \(G\) is \(2\)-regular. For the converse, \(G\) being \(2\)-regular and satisfying \(Q_\tau = I_2 \otimes \widetilde{Q}\) does not imply \(A(G)=A(LD(G/\pi))\) in general; a counterexample is provided in Example 13. ◻

Proof. (a). Set \(P = I_d \otimes Q_{\tau}\). Since \(P^{\top}P = I\), we compute \[\begin{align} R_{\tau}\,P &= \Bigl(2\,P\,(I_2 \otimes Q_{\tau}Q_{\tau}^{\top})\,P^{\top} - I\Bigr)P = P\,\Bigl(2\,(I_2 \otimes Q_{\tau}Q_{\tau}^{\top}) - I\Bigr) = P\,\widetilde{R}_{\tau}. \end{align}\] Hence \[R_{\tau}\,(I_d \otimes Q_{\tau}) = (I_d \otimes Q_{\tau})\,\widetilde{R}_{\tau}.\] The second identity follows by the identical argument with \(Q_{\tau}\) replaced by \(\widetilde{Q}\) and \(R_{\tau}\) replaced by \(R_{\sigma}\).

(b). Since \(\tau\) is an equitable arc partition of \(LD(G)\), we have \(A_{LD(G)/\tau} = Q_{\tau}^{\top}\,A_{LD(G)}\,Q_{\tau}.\) Since \(LD(G)/\tau\) and \(LD(G)\) are both \(d\)-regular, by same argument as Lemma 2 and Remark 5, we have \(\widetilde{S}_{\tau} = (I_d \otimes Q_{\tau})^{\top}\,S_{\tau}\,(I_d \otimes Q_{\tau}).\) Therefore, \[\begin{align} \widetilde{U}_{\tau} = \widetilde{S}_{\tau}\,\widetilde{R}_{\tau} &= (I_d \otimes Q_{\tau})^{\top}\,S_{\tau}\,(I_d \otimes Q_{\tau})\, \widetilde{R}_{\tau} \\ &= (I_d \otimes Q_{\tau})^{\top}\,S_{\tau}\,R_{\tau}\, (I_d \otimes Q_{\tau}) \qquad\text{(by part~(a))} \\ &= (I_d \otimes Q_{\tau})^{\top}\,U_{\tau}\,(I_d \otimes Q_{\tau}). \end{align}\] For the second identity, since \(\sigma\) is an equitable arc partition of \(LD(G/\pi)\) and \(LD(G/\pi)/\sigma \cong G/\pi\) by Theorem 8, both \(LD(G/\pi)/\sigma\) and \(LD(G/\pi)\) are \(d\)-regular, by same argument as Lemma 2 and Remark 5, we have \(\widetilde{S} = (I_d \otimes \widetilde{Q})^{\top}\,S_{\sigma}\, (I_d \otimes \widetilde{Q}).\) Therefore, \[\begin{align} \widetilde{U} = \widetilde{S}\,\widetilde{R} &= (I_d \otimes \widetilde{Q})^{\top}\,S_{\sigma}\, (I_d \otimes \widetilde{Q})\,\widetilde{R} \\ &= (I_d \otimes \widetilde{Q})^{\top}\,S_{\sigma}\,R_{\sigma}\, (I_d \otimes \widetilde{Q}) \qquad\text{(by part~(a))} \\ &= (I_d \otimes \widetilde{Q})^{\top}\,U_{\sigma}\, (I_d \otimes \widetilde{Q}). \end{align}\] By Lemma 1, \((I_d \otimes Q_{\tau})(I_d \otimes Q_{\tau})^\top\) commutes with \(U\), and hence \(\operatorname{Im}(I_d \otimes Q_{\tau})\) is invariant under \(U_{\tau}\).This gives \(U_{\tau}\,(I_d \otimes Q_{\tau}) = (I_d \otimes Q_{\tau})\,\widetilde{U}_{\tau}\). Applying this relation inductively yields \[\label{induction} U_{\tau}^{k}(I_d \otimes Q_{\tau}) = (I_d \otimes Q_{\tau})\,\widetilde{U}_{\tau}^{\,k} \quad \forall k \geq 0\tag{17}\]

Multiplying both sides of (17 ) on the left by \((I_d \otimes Q_{\tau})^{\top}\) and using \((I_d \otimes Q_{\tau})^{\top}(I_d \otimes Q_{\tau}) = I\), we obtain \[\widetilde{U}_{\tau}^{\,k} = (I_d \otimes Q_{\tau})^{\top}\,U_{\tau}^{k}\, (I_d \otimes Q_{\tau}) \quad\text{for all } k \geq 0.\] The identity for \(\widetilde{U}^{\,k}\) follows by the identical argument with \(Q_{\tau}\) replaced by \(\widetilde{Q}\) and \(U_{\tau}\) replaced by \(U_{\sigma}\). ◻

Proof. Let \(U_{\tau}\), \(\widetilde{U}_{\tau}\), \(U_{\sigma}\), and \(\widetilde{U}\) denote the unitary evolution operators on \(LD(G)\), \(LD(G)/\tau\), \(LD(G/\pi)\), and \(LD(G/\pi)/\sigma\), respectively. Since \(\tau\) is an equitable arc partition of \(LD(G)\) and \(\sigma\) is an equitable arc partition of \(LD(G/\pi)\), Proposition 14 gives, for every integer \(k \geq 0\), \[\begin{align} U_{\tau}^{k}\,(I_d \otimes Q_{\tau}) &= (I_d \otimes Q_{\tau})\,\widetilde{U}_{\tau}^{\,k}, \tag{18}\\ U_{\sigma}^{k}\,(I_d \otimes \widetilde{Q}) &= (I_d \otimes \widetilde{Q})\,\widetilde{U}^{\,k}. \tag{19} \end{align}\]

(\(\Rightarrow\)). Suppose \(\widetilde{U}\) exhibits PST at time \(k\), so that \[\widetilde{U}^{\,k}\,x = y \qquad \text{for some } x, y \in \operatorname{Im}(I_d \otimes \widetilde{Q}).\] Applying 19 yields \[U_{\sigma}^{k}\,(I_d \otimes \widetilde{Q})\,x = (I_d \otimes \widetilde{Q})\,y.\] Since \(LD(G)/\tau \cong LD(G/\pi)\), we have \(U_{\sigma} = \widetilde{U}_{\tau}\), and 18 then gives \[U_{\tau}^{k}\,(I_d \otimes Q_{\tau})(I_d \otimes \widetilde{Q})\,x = (I_d \otimes Q_{\tau})(I_d \otimes \widetilde{Q})\,y.\] Hence \(U_{\tau}\) exhibits PST between the corresponding lifted states in \(LD(G)\).

(\(\Leftarrow\)). Conversely, suppose \(U_{\tau}\) exhibits PST at time \(k\), so that \[U_{\tau}^{k}\,(I_d \otimes Q_{\tau})(I_d \otimes \widetilde{Q})\,x = (I_d \otimes Q_{\tau})(I_d \otimes \widetilde{Q})\,y.\] Multiplying on the left by \((I_d \otimes Q_{\tau})^{\top}\) and using 18 together with \((I_d \otimes Q_{\tau})^{\top}(I_d \otimes Q_{\tau}) = I\), we obtain \[U_{\sigma}^{k}\,(I_d \otimes \widetilde{Q})\,x = (I_d \otimes \widetilde{Q})\,y.\] Multiplying on the left by \((I_d \otimes \widetilde{Q})^{\top}\) and using 19 together with \((I_d \otimes \widetilde{Q})^{\top}(I_d \otimes \widetilde{Q}) = I\), we obtain \[\widetilde{U}^{\,k}\,x = y.\] Hence \(\widetilde{U}\) exhibits PST from \(x\) to \(y\). Therefore, PST occurs in \(LD(G/\pi)/\sigma\) between states \(x\) and \(y\) if and only if it occurs in \(LD(G)\) between the lifted states \((I_d \otimes Q_{\tau})(I_d \otimes \widetilde{Q})\,x\) and \((I_d \otimes Q_{\tau})(I_d \otimes \widetilde{Q})\,y\). ◻

Proof. Case (i): With \(\widetilde{Q}=\frac{1}{\sqrt{d}}(I_n^{\top}\cdots I_n^{\top})^{\top}\) and \(\widetilde{S}=\mathrm{diag}(\widetilde{P}_1,\dots,\widetilde{P}_d)\), block multiplication gives \[\widetilde{S}\,\widetilde{Q} \;=\; \begin{pmatrix}\widetilde{P}_1&&\\&\ddots&\\&&\widetilde{P}_d\end{pmatrix} \frac{1}{\sqrt{d}} \begin{pmatrix}I_n\\\vdots\\I_n\end{pmatrix} \;=\; \frac{1}{\sqrt{d}} \begin{pmatrix}\widetilde{P}_1\\\vdots\\\widetilde{P}_d\end{pmatrix},\] and therefore \[\widetilde{D} \;=\; \widetilde{Q}^{\!\top}\widetilde{S}\,\widetilde{Q} \;=\; \frac{1}{d} \begin{pmatrix}I_n&\cdots&I_n\end{pmatrix} \begin{pmatrix}\widetilde{P}_1\\\vdots\\\widetilde{P}_d\end{pmatrix} \;=\; \frac{1}{d}(\widetilde{P}_1+\cdots+\widetilde{P}_d) \;=\; \frac{1}{d}\,\widetilde{A}.\]

Case (ii): With \(\widetilde{Q}=\frac{1}{\sqrt{d}}(\widetilde{P}_1^{\top}\cdots \widetilde{P}_d^{\top})^{\top}\) and the same \(\widetilde{S}\), block multiplication gives \[\widetilde{S}\,\widetilde{Q} \;=\; \frac{1}{\sqrt{d}} \begin{pmatrix} \widetilde{P}_1^2\\\vdots\\\widetilde{P}_d^2\end{pmatrix},\]therefore \[\begin{align} \widetilde{D} &\;=\; \widetilde{Q}^{\!\top}\widetilde{S}\,\widetilde{Q} \;=\; \frac{1}{d} \begin{pmatrix}\widetilde{P}_1^{\top}&\cdots&P_d^{\top}\end{pmatrix} \begin{pmatrix} \widetilde{P}_1^2\\\vdots\\\widetilde{P}_d^2 \end{pmatrix} \;=\; \frac{1}{d}\sum_{k=1}^d\widetilde{P}_k^{\top}\widetilde{P}_k^2. \end{align}\] Since each \(\widetilde{P}_k\) is a permutation matrix we have \(\widetilde{P}_k^{\top}\widetilde{P}_k=I_n\), hence \(\widetilde{P}_k^{\top}\widetilde{P}_k^2=P_k\), and so \[\widetilde{D} \;=\; \frac{1}{d}\sum_{k=1}^d \widetilde{P}_k \;=\; \frac{1}{d}\,\widetilde{A}.\]

Since each \(\widetilde{P}\) is a permutation matrix, every row of \(\widetilde{P}_k\) sums to \(1\). Hence every row of \(\widetilde{A}=\sum_{k=1}^d \widetilde{P}_k\) sums to \(d\), and therefore every row of \(\widetilde{D}=\frac{1}{d}\widetilde{A}\) sums to \(1\), confirming that \(\widetilde{D}\) is row-stochastic with non-negative entries. By the Perron–Frobenius theorem [30], the spectral radius of a row-stochastic matrix equals \(1\), so every eigenvalue of \(\widetilde{D}\) satisfies \(|\lambda(\widetilde{D})|\le 1\). ◻

Proof. We first observe that for every \(k \geq 1\): \[\label{eq:discriminant} \widetilde{D}_k = \widetilde{Q}^{\top} \widetilde{U}^k \widetilde{Q} = \widetilde{Q}^{\top} \widetilde{U}^{k-1} \widetilde{S} \widetilde{Q}.\tag{22}\] Indeed, using the shunt-decomposition \(\widetilde{U} = \widetilde{S}(2\widetilde{Q}\widetilde{Q}^{\top} - I)\): \[\begin{align} \widetilde{Q}^{\top} \widetilde{U}^k \widetilde{Q} &= \widetilde{Q}^{\top} \widetilde{U}^{k-1} \bigl[\widetilde{S}(2\widetilde{Q}\widetilde{Q}^{\top} - I)\bigr] \widetilde{Q} \\ &= 2\widetilde{Q}^{\top} \widetilde{U}^{k-1} \widetilde{S} (\widetilde{Q}\widetilde{Q}^{\top}\widetilde{Q}) - \widetilde{Q}^{\top} \widetilde{U}^{k-1} \widetilde{S} \widetilde{Q} \\ &= 2\widetilde{Q}^{\top} \widetilde{U}^{k-1} \widetilde{S} \widetilde{Q} - \widetilde{Q}^{\top} \widetilde{U}^{k-1} \widetilde{S} \widetilde{Q} \qquad (\text{since } \widetilde{Q}^{\top}\widetilde{Q} = I) \\ &= \widetilde{Q}^{\top} \widetilde{U}^{k-1} \widetilde{S} \widetilde{Q}. \end{align}\] We now proceed by induction on \(k\). For the base cases:

• \(k = 0\): \(\widetilde{D}_0 = \widetilde{Q}^{\top} I \widetilde{Q} = I = T_0(\widetilde{D})\).

• \(k = 1\): \(\widetilde{D}_1 = \widetilde{Q}^{\top} \widetilde{S} \widetilde{Q} = \widetilde{D} = T_1(\widetilde{D})\).

Assume the identity holds for \(k-1\) and \(k-2\). Using Eq. 22 and the shunt-decomposition, we have \[\begin{align} \widetilde{D}_k &= \widetilde{Q}^{\top} \widetilde{U}^{k-1} \widetilde{S} \widetilde{Q} }\\ &= \widetilde{Q}^{\top} \bigl[\widetilde{U}^{k-2}\widetilde{S} (2\widetilde{Q}\widetilde{Q}^{\top} - I)\bigr] \widetilde{S}\widetilde{Q} \\ &= 2(\widetilde{Q}^{\top}\widetilde{U}^{k-2}\widetilde{S}\widetilde{Q}) (\widetilde{Q}^{\top}\widetilde{S}\widetilde{Q}) - \widetilde{Q}^{\top}\widetilde{U}^{k-2}\widetilde{Q} \\ &= 2\widetilde{D}_{k-1}\,\widetilde{D} - \widetilde{D}_{k-2}and induction hypothesis}\\ &= T_k(\widetilde{D}). \end{align}\] Since \(T_k(p) = 2p\,T_{k-1}(p) - T_{k-2}(p)\) and the identity holds for all base cases, by induction we conclude \(\widetilde{D}_k = T_k(\widetilde{D})\) for all \(k \in \mathbb{N} \cup \{0\}\). ◻

Proof. The proof is analogous to the vertex-state case in standard Grover walks (see [16]).

Since \(\widetilde{D} = \widetilde{Q}^{\top}\widetilde{S}\widetilde{Q}\) and \(\widetilde{S}\) is a symmetric matrix, \(\widetilde{D}\) is symmetric, and hence all its eigenvalues are real and satisfy \(\mu \in \Sigma_{C_i} \subset [-1,1]\). This guarantees that the spectral decomposition \(\widetilde{D} = \sum_{\mu \in \Sigma_{C_i}.} \mu\, \widetilde{E}_\mu\) holds with orthogonal projectors \(\widetilde{E}_\mu\), and that \(|T_k(\mu)| \leq 1\) for all \(\mu \in \Sigma_{C_i}\). By expressing \(\|T_k(\widetilde{D})\,e_{C_i}\|^2\) through this spectral decomposition, we obtain: \[\|T_k(\widetilde{D})\,e_{C_i}\|^2 = \sum_{\mu \in \Sigma_{C_i}} |T_k(\mu)|^2\,\langle \widetilde{E}_\mu\,e_{C_i},\, e_{C_i}\rangle.\] Since \(|T_k(\mu)| \le 1\) for all \(\mu \in [-1,1]\) and \(\sum_{\mu}\langle \widetilde{E}_\mu\,e_{C_i}, e_{C_i}\rangle = \|e_{C_i}\|^2 = 1\), the norm is bounded by \(1\). Equality is achieved if and only if \(|T_k(\mu)| = 1\), i.e.\(T_k(\mu) = \pm 1\), for all \(\mu\) in the support \(\Sigma_{C_i}\). ◻

Proof. Suppose PST occurs at time \(k\). Following the characterization of PST in  [16], the condition \(|\langle x_{C_j}, \widetilde{U}^\tau x_{C_i} \rangle| = 1\) is equivalent to \(|\langle e_{C_j}, T_k(\widetilde{D}) e_{C_i} \rangle| = 1\) by Lemma 8. Applying the Cauchy–Schwarz inequality: \[1 = |\langle e_{C_j}, T_k(\widetilde{D}) e_{C_i} \rangle| \le \|e_{C_j}\| \cdot \|T_k(\widetilde{D}) e_{C_i}\| \le 1.\] This implies \(\|T_k(\widetilde{D}) e_{C_i}\| = 1\), and the result follows directly from Lemma 9. ◻

Proof. Since the cells \(C_i = \{i, i+n\}\) for \(i = 1, \ldots, n\) are pairwise disjoint and cover \(\{1, \ldots, 2n\}\), the collection \(\pi\) is indeed a partition. For \(n \geq 3\), no two vertices within the same cell are adjacent in \(C_{2n}\), since their difference is \(n \geq 3\), whereas adjacency requires a difference of \(1\) or \(2n-1\). Hence \(G/\pi\) has no self-loops. Now fix \(i \in \{1, \ldots, n\}\) and consider the two vertices \(v = i\) and \(w = i + n\) of \(C_i\). Their neighbours in \(C_{2n}\) are \[N(v) = \{i-1,\; i+1\}, \qquad N(w) = \{i+n-1,\; i+n+1\}.\] Since \(i - 1, \, i+n-1 \in C_{i-1}\) and \(i+1,\, i+n+1 \in C_{i+1}\) (indices modulo \(n\)), each vertex of \(C_i\) has exactly one neighbour in \(C_{i-1 \bmod n}\) and exactly one neighbour in \(C_{i+1 \bmod n}\), and no neighbours in any other cell. As this count is independent of the choice of vertex in \(C_i\), the partition \(\pi\) is equitable. Consequently, in the quotient graph \(C_{2n}/\pi\), each cell \(C_i\) is adjacent only to \(C_{i-1 \bmod n}\) and \(C_{i+1 \bmod n}\), which is precisely the adjacency structure of \(C_n\). Hence \[C_{2n}/\pi \;\cong\; C_n.\] ◻

Proof. By Lemma 10, \(G/\pi \cong C_n\) has \(n\) undirected edges, so \(\mathrm{LD}(G/\pi)\) has exactly \(2n\) directed arcs. Hence the number of arcs of \(\mathrm{LD}(G/\pi)\) equals the number of vertices of \(G = C_{2n}\). The equitable vertex partition \(\pi\) partitions the \(2n\) vertices of \(G\) into \(n\) cells each of size \(2\), giving \[Q \;=\; \frac{1}{\sqrt{2}} \begin{pmatrix} I_n \\ I_n \end{pmatrix} \;\in\; \mathbb{R}^{2n \times n},\] where the upper \(I_n\) corresponds to the elements \(\{1, 2, \ldots, n\}\) and the lower \(I_n\) corresponds to the elements \(\{n+1, n+2, \ldots, 2n\}\) of each cell. The arc partition \(\sigma\) partitions the \(2n\) arcs of \(\mathrm{LD}(G/\pi)\) into \(n\) classes each of size \(2\), namely the two arcs directed into each vertex of \(C_n\). Ordering the arcs as \[\underbrace{(u_1,v_1),\,(u_2,v_2),\,\ldots,\,(u_n,v_n)}_{ \text{first arc of each class}}, \qquad \underbrace{(w_1,v_1),\,(w_2,v_2),\,\ldots,\,(w_n,v_n)}_{ \text{second arc of each class}},\] where \((u_i, v_i)\) and \((w_i, v_i)\) are the two arcs in class \(\sigma_i\), the normalized characteristic matrix takes the form \[\widetilde{Q} \;=\; \frac{1}{\sqrt{2}} \begin{pmatrix} I_n \\ I_n \end{pmatrix} \;\in\; \mathbb{R}^{2n \times n}.\] Hence \(Q = \widetilde{Q}\), and \(\widetilde{Q}\) satisfies the equitable partition condition \[A_{\mathrm{LD}(G/\pi)}\,\widetilde{Q} \;=\; \widetilde{Q}\,\widetilde{A}, \qquad \widetilde{A} = A(C_n),\] confirming that \[\mathrm{LD}(G/\pi)/\sigma \;\cong\; C_n \;\cong\; G/\pi.\] ◻

Proof. Since \(C_n\) has degree \(2\), its adjacency matrix satisfies \(A(C_n) = \widetilde{P}_1 + \widetilde{P}_2\), where \(\widetilde{P}_1\) and \(\widetilde{P}_2\) are the two permutation matrices corresponding to the two arc directions. Since each \(\widetilde{P}_j\) is an involution, i.e.\(\widetilde{P}_j^2 = I\), it follows by Corollary 2 that \(\widetilde{S}^2 = I\). Since \(\widetilde{S}\) is unitary and satisfies \(\widetilde{S}^2 = I\), we have \(\widetilde{S}^{-1} = \widetilde{S}\). Combined with the unitarity condition \(\widetilde{S}^{-1} = \widetilde{S}^{\top}\), this gives \(\widetilde{S} = \widetilde{S}^{\top}\), and hence \(\widetilde{S}\) is symmetric. ◻

Proof. By Lemma 7 and Corollary 20, the quotient graph is \(C_{2n}/\pi \cong C_n\) and the discriminant satisfies \(\widetilde{D} = \tfrac{1}{2}A(C_n)\). The eigenvalues of \(A(C_n)\) are \(2\cos\!\bigl(\tfrac{2\pi t}{n}\bigr)\) for \(t = 0,1,\ldots,n-1\), so the eigenvalues of \(\widetilde{D}\) are \[\label{eq:disc-evals} \mu_t = \cos\!\left(\frac{2\pi t}{n}\right), \qquad t = 0, 1, \ldots, n-1.\tag{23}\]

By Theorem 19, PST from \(\widetilde{Q}e_{C_i}\) to \(\widetilde{Q}e_{C_j}\) at time \(k\) requires \[T_k(\mu_t) = \pm 1 \qquad \text{for all } t = 0, 1, \ldots, n-1 \text{ and } \mu_t \in \Sigma_{C_i}.\] where \(T_k\) is the Chebyshev polynomial of degree \(k\). Using \(T_k(\cos\theta) = \cos(k\theta)\), this condition becomes \[\cos\!\left(k \cdot \frac{2\pi t}{n}\right) = \pm 1 \quad\iff\quad k \cdot \frac{2t}{n} \in \mathbb{Z} \quad \text{for all } t = 0,1,\ldots,n-1.\] To satisfy this for all \(t\), it suffices to consider \(t=1\), which yields \[\frac{2k}{n} \in \mathbb{Z} \quad\Longrightarrow\quad k = m\,\frac{n}{2}, \quad m \in \mathbb{Z}_{>0}.\] The smallest positive value is \(k = \dfrac{n}{2}\), which is a positive integer since \(n\) is even. Let \(E_t\) denote the spectral projector of \(\widetilde{D}\) onto the eigenspace of \(\mu_t\). At \(k = n/2\), the sign pattern is \[T_{n/2}(\mu_t) = \cos\!\left(\frac{n}{2}\cdot\frac{2\pi t}{n}\right) = \cos(\pi t ) = (-1)^t,\] so the transfer operator is \[T_{n/2}(\widetilde{D}) = \sum_{t=0}^{n-1}(-1)^t E_t.\] Since \(n\) is even and \(C_n\) is vertex-transitive, the antipodal symmetry of \(C_n\) (sending cell \(C_i\) to cell \(C_{i+n/2 \bmod n}\)) implies \[T_{n/2}(\widetilde{D})\,e_{C_i} = e_{C_{i+n/2 \bmod n}},\] that is, the transfer operator maps each basis vector to the diametrically opposite basis vector of \(C_n\). Hence \[\bigl\langle \widetilde{U}^{n/2}\,\widetilde{Q}e_{C_i},\; \widetilde{Q}e_{C_j} \bigr\rangle = 1, \qquad j = i + \tfrac{n}{2} \bmod n,\] establishing PST at time \(k = n/2\). ◻

Proof. By Lemma 10, the partition \(\pi\) is equitable with \(n\) cells each of size \(2\), and the quotient satisfies \(C_{2n}/\pi \cong C_n\). By Corollary 20, the vertex and arc characteristic matrices coincide: \[Q \;=\; \widetilde{Q} \;=\; \frac{1}{\sqrt{2}} \begin{pmatrix} I_n \\ I_n \end{pmatrix} \;\in\; M_{2n \times n}(\mathbb{R}), \qquad \widetilde{Q}^\top \widetilde{Q} = I_n.\] The arc characteristic matrix of \(\mathrm{LD}(C_{2n})\) takes the form \[Q_\tau \;=\; I_2\otimes \widetilde{Q} \;=\; \frac{1}{\sqrt{2}} \begin{pmatrix} I_{2n} \\ I_{2n} \end{pmatrix} \;\in\; M_{4n \times 2n}(\mathbb{R}), \qquad Q_\tau^\top Q_\tau = I_{2n}.\] By construction, \(Q_\tau\) satisfies the intertwining identity \[A_{\mathrm{LD}(C_{2n})}\, Q_\tau \;=\; Q_\tau\, A_{C_{2n}},\] where \(A_{\mathrm{LD}(C_{2n})} \in M_{4n \times 4n}(\mathbb{R})\) and \(A_{C_{2n}} \in M_{2n \times 2n}(\mathbb{R})\). By Lemma 11, the quotient \(C_n\) exhibits PST at time \(k = \tfrac{n}{2}\) (a positive integer since \(n\) is even) between the antipodal states \(\widetilde{Q}\,e_{C_i}\) and \(\widetilde{Q}\,e_{C_j}\), that is, \[\left| e_{C_j}^\top\, \widetilde{Q}^\top\, \widetilde{U}^{\,k}\, \widetilde{Q}\, e_{C_i} \right| = 1.\] Applying Theorem 11 with \(Q_\tau = I_2 \otimes \widetilde{Q}\), PST on the quotient lifts to the original graph, giving \[\left| x_{C_j}^\top\, Q_\tau^\top\, U^{k}\, Q_\tau\, x_{C_i} \right| \;=\; \left| e_{C_j}^\top\, \widetilde{Q}^\top\, \widetilde{U}^{\,k}\, \widetilde{Q}\, e_{C_i} \right| \;=\; 1,\] where \(U\) and \(\widetilde{U}\) are the transition operators on \(C_{2n}\) and \(C_n\), respectively. Hence \(C_{2n}\) exhibits PST at time \(k = \tfrac{n}{2}\) from the state \(Q_\tau\, x_{C_i}\) to the state \(Q_\tau\, x_{C_j}\), with \(j \equiv i + \tfrac{n}{2} \pmod{n}\). ◻

Proof. Since \(d = n\), the same root of unity \(\omega = e^{2\pi i/n}\) governs both the cyclic shift \(\widetilde{P}\) on \(\mathbb{C}^n\) and the DFT structure on \(\mathbb{C}^n\). The DFT basis vectors \[f_l = \frac{1}{\sqrt{n}}\bigl[1,\,\omega^{l},\,\omega^{2l},\,\ldots,\, \omega^{(n-1)l}\bigr]^\top, \qquad l \in \mathbb{Z}_n,\] satisfy \(\widetilde{P} f_l = \omega^l f_l\). The subspaces \(V_l = \operatorname{span}\{f_m \otimes f_l : m \in \mathbb{Z}_n\}, \qquad l \in \mathbb{Z}_n,\) are \(\widetilde{U}\)-invariant and \(\mathbb{C}^{n^2} = \bigoplus_{l=0}^{n-1} V_l\). Indeed, since \(d = n\), the action of \(S\) gives \(S(f_m \otimes f_l) = f_{m+l \bmod n} \otimes f_l \in V_l\), and the action of \(R\) gives \(R(f_m \otimes f_l) = d_m^{(l)}(f_m \otimes f_l) \in V_l\), both of which keep \(V_l\) invariant. It therefore suffices to find the eigenvalues of \(\widetilde{U}_l = \widetilde{U}|_{V_l}\) for each \(l \in \mathbb{Z}_n\). In the basis \(\{f_m \otimes f_l\}_{m \in \mathbb{Z}_n}\) one has \[\widetilde{U}_l = \Sigma_l D_l,\] where \(\Sigma_l\) is the cyclic shift by \(l\) on \(\mathbb{C}^n\) (that is\((\Sigma_l)_{m,m'} = \delta_{m,\,m'+l \bmod n}\)), arising from \(S|_{V_l}\), and \(D_l = \operatorname{diag}(d_0^{(l)},\ldots,d_{n-1}^{(l)})\) with \[d_m^{(l)} = \begin{cases} +1 & m = l,\\ -1 & m \neq l,\end{cases}\] arising from \(R|_{V_l}\). Write \(D_l\) as a rank-one update of \(-I_n\), \(D_l = -I_n + 2\,e_l e_l^\top,\) since this matrix has \(+1\) in position \((l,l)\) and \(-1\) elsewhere on the diagonal. Hence \[\widetilde{U}_l = \Sigma_l D_l = \Sigma_l(-I_n + 2\,e_l e_l^\top) = -\Sigma_l + 2\,(\Sigma_l e_l)\,e_l^\top.\] This expresses \(\lambda I - \widetilde{U}_l\) as a rank-one perturbation of \(\lambda I + \Sigma_l\) \[\lambda I - \widetilde{U}_l = \underbrace{(\lambda I + \Sigma_l)}_{=\,A} + \underbrace{(-2\,\Sigma_l e_l)}_{=\,u} \,\underbrace{e_l^\top}_{=\,v^\top}. \label{eq:rankone}\tag{24}\] For an invertible matrix \(A\) and vectors \(u,v\), \[\det(A + uv^\top) = \det(A)\,(1 + v^\top A^{-1} u).\] Applying this to 24 with \(A = \lambda I + \Sigma_l\), \(u = -2\Sigma_l e_l\), \(v = e_l\) \[\begin{align} \det(\lambda I - \widetilde{U}_l) &= \det(\lambda I + \Sigma_l) \Bigl(1 - 2\,e_l^\top(\lambda I + \Sigma_l)^{-1}\Sigma_l e_l\Bigr). \label{eq:MDL} \end{align}\tag{25}\]

The matrix \(\Sigma_l\) is the cyclic permutation \(m \mapsto m + l \bmod n\) on \(\mathbb{C}^n\), whose eigenvalues are \(\{\omega^{lm} : m \in \mathbb{Z}_n\}\) with \(\omega = e^{2\pi i/n}\). Therefore \(\det(\lambda I + \Sigma_l) = \prod_{m=0}^{n-1}(\lambda + \omega^{lm}).\) Now we compute \(e_l^\top(\lambda I + \Sigma_l)^{-1}\Sigma_l e_l\). The shift \(\Sigma_l\) maps the \(k\)-th standard basis vector to \(e_{k+l \bmod n}\), so in particular \(\Sigma_l e_l = e_{2l \bmod n}.\) Hence the resolvent entry becomes \[\label{eq:res} e_l^\top(\lambda I + \Sigma_l)^{-1}\Sigma_l e_l = e_l^\top(\lambda I + \Sigma_l)^{-1} e_{2l \bmod n} = \bigl[(\lambda I + \Sigma_l)^{-1}\bigr]_{l,\,2l \bmod n}.\tag{26}\] Since \(\Sigma_l\) is a circulant matrix on \(\mathbb{C}^n\), so is \((\lambda I + \Sigma_l)^{-1}\). Its \((j,k)\) entry is \[\bigl[(\lambda I + \Sigma_l)^{-1}\bigr]_{j,k} = \frac{1}{n}\sum_{m=0}^{n-1}\frac{\omega^{m(j-k)}}{\lambda + \omega^{lm}}.\] Setting \(j = l\) and \(k = 2l \bmod n\) gives \(j - k \equiv -l \pmod{n}\), so \[\label{eq:entry} \bigl[(\lambda I + \Sigma_l)^{-1}\bigr]_{l,\,2l \bmod n} = \frac{1}{n}\sum_{m=0}^{n-1}\frac{\omega^{-ml}}{\lambda + \omega^{lm}}.\tag{27}\] Substituting 26 and 27 into 25 : \[\det(\lambda I - \widetilde{U}_l) = \prod_{m=0}^{n-1}(\lambda + \omega^{lm}) \left(1 - \frac{2}{n}\sum_{m=0}^{n-1} \frac{\omega^{-ml}}{\lambda + \omega^{lm}}\right).\] Clearing denominators by multiplying through gives \[\label{det} \det(\lambda I - \widetilde{U}_l) = \prod_{m=0}^{n-1}(\lambda + \omega^{lm}) - \frac{2}{n}\sum_{m=0}^{n-1} \omega^{-ml}\prod_{\substack{j=0\\j\neq m}}^{n-1}(\lambda + \omega^{lj}) = p_l(\lambda).\tag{28}\] This is a degree-\(n\) polynomial in \(\lambda\), valid for each \(l \in \mathbb{Z}_n\). Thus the eigenvalues of \(\widetilde{U}\) are \(\bigcup_{l=0}^{n-1}\{\lambda : p_l(\lambda) = 0\}\). ◻

Proof. Proof of part (i). Recall from Lemma 12 that \(\widetilde{U}_l = \Sigma_l D_l\), where \(\Sigma_l\) is the cyclic shift by \(l\) on \(\mathbb{C}^n\) and \(D_l = \operatorname{diag}(d_0^{(l)}, \ldots, d_{n-1}^{(l)})\) with \(d_m^{(l)} = +1\) if \(m = l \bmod n\) and \(d_m^{(l)} = -1\) otherwise. We first establish that for all \(k \geq 1\), \[\label{eq:ind} \widetilde{U}_l^k = \Sigma_{kl \bmod n}\,E_k,\tag{29}\] where \(\Sigma_{kl}\) denotes the cyclic shift by \(kl \bmod n\) on \(\mathbb{C}^n\) and \(E_k\) is the \(n \times n\) diagonal matrix with entries \[\label{eq:Ek} (E_k)_{mm} = \prod_{r=0}^{k-1} d_{m-rl \bmod n}^{(l)}, \qquad m \in \mathbb{Z}_n,\tag{30}\]

Base case \(k = 1\). We have \(\widetilde{U}_l^1 = \Sigma_l D_l = \Sigma_l E_1\) since \((E_1)_{mm} = d_m^{(l)}\).

Inductive step. Assume \(\widetilde{U}_l^k = \Sigma_{kl} E_k\). Then \(\widetilde{U}_l^{k+1} = \Sigma_{kl} E_k \cdot \Sigma_l D_l.\) Since \(E_k\) is diagonal and \(\Sigma_l\) is the shift by \(l\) on \(\mathbb{C}^n\), commuting \(E_k\) past \(\Sigma_l\) relabels the diagonal indices: \[E_k \Sigma_l = \Sigma_l \widehat{E}_k, \qquad (\widehat{E}_k)_{mm} = (E_k)_{m-l \bmod n,\; m-l \bmod n}.\] Hence \[\widetilde{U}_l^{k+1} = \Sigma_{(k+1)l}\,\widehat{E}_k D_l = \Sigma_{(k+1)l}\,E_{k+1},\] where \[(E_{k+1})_{mm} = (\widehat{E}_k)_{mm}\cdot d_m^{(l)} = \prod_{r=0}^{k-1} d_{m-(r+1)l}^{(l)} \cdot d_m^{(l)} = \prod_{r=0}^{k} d_{m-rl}^{(l)}.\] This completes the induction. At \(k = n\) the shift satisfies \(\Sigma_{nl} = \Sigma_0 = I_n\) since \(nl \equiv 0 \pmod{n}\) for every \(l\), so \[\widetilde{U}_l^n = E_n,\] and it remains to determine the diagonal entries of \(E_n\). Fix \(m \in \mathbb{Z}_n\) and consider the sequence of indices \[m,\; m-l,\; m-2l,\; \ldots,\; m-(n-1)l \pmod{n}.\] Let \(g = \gcd(l \bmod n,\,n)\). The map \(r \mapsto m - rl \bmod n\) has period \(n/g\), so as \(r\) runs over \(\{0,1,\ldots,n-1\}\) each element of the orbit \[\mathcal{O}(m,l) = \{m - rl \bmod n : r \in \mathbb{Z}_n\}\] is visited exactly \(g\) times. The factor \(d_{m-rl}^{(l)}\) equals \(+1\) only when \(m - rl \equiv l \pmod{n}\). The number of such \(r \in \{0,\ldots,n-1\}\) is \[N_+(m,l) = \#\{r \in \mathbb{Z}_n : rl \equiv m-l \pmod{n}\} = \begin{cases} g & \text{if } g \mid (m-l),\\ 0 & \text{if } g \nmid (m-l). \end{cases}\] The remaining \(n - N_+(m,l)\) factors each equal \(-1\), so \[\label{eq:Enentry} (E_n)_{mm} = (+1)^{N_+}\cdot(-1)^{n-N_+} = (-1)^{n-N_+}.\tag{31}\]

8.0.0.1 Case 1: \(g \nmid (m-l)\).

Then \(N_+ = 0\), so \((E_n)_{mm} = (-1)^n = +1\) since \(n = 2^s\) is even.

8.0.0.2 Case 2: \(g \mid (m-l)\).

Then \(N_+ = g\), so \((E_n)_{mm} = (-1)^{n-g}\). Write \(g = \gcd(l \bmod n,\,n) = 2^a\) with \(0 \leq a \leq s\), so that \(n - g = 2^s - 2^a = 2^a(2^{s-a}-1)\).

• If \(a \geq 1\) (that is\(l \bmod n\) is even): \(n - g\) is even, so \((-1)^{n-g} = +1\).

• If \(a = 0\) (that is\(l \bmod n\) is odd, \(g = 1\)): \(n - g = 2^s - 1\) is odd for \(s \geq 1\), so \((-1)^{n-g} = -1\).

Combining both cases, for every \(m \in \mathbb{Z}_n\), \[(E_n)_{mm} = \begin{cases} +1 = (-1)^{l \bmod n} & \text{if } l \bmod n \text{ is even},\\ -1 = (-1)^{l \bmod n} & \text{if } l \bmod n \text{ is odd}. \end{cases}\] Hence \(E_n = (-1)^{l \bmod n}\,I_n\) independently of \(m\), and therefore \[\widetilde{U}_l^n = (-1)^{l \bmod n}\,I_n.\] Squaring gives \(\widetilde{U}_l^{2n} = I_n\). To see that the order is exactly \(2n\) when \(l \bmod n\) is odd, note that \(\widetilde{U}_l^n = -I_n \neq I_n\), so no divisor of \(n\) is the order. For \(n < T < 2n\), write \(T = n + q\) with \(1 \leq q < n\); then \[\widetilde{U}_l^T = \widetilde{U}_l^n \cdot \widetilde{U}_l^q = -\widetilde{U}_l^q.\] For \(\widetilde{U}_l^T = I_n\) we would need \(\widetilde{U}_l^q = -I_n\), hence \(\Sigma_{ql \bmod n} = I_n\), that is\(ql \equiv 0 \pmod{n}\). Since \(\gcd(l \bmod n,\,n) = 1\) this forces \(n \mid q\), contradicting \(1 \leq q < n\). Hence the order of \(\widetilde{U}_l\) is exactly \(2n\) for every \(l\) with \(l \bmod n\) odd. This proves part (i).

Proof of part (ii). Since \(d = n\), we verify directly that \(\widetilde{U}^{\,n}\) and \(I_n \otimes \widetilde{P}^{n/2}\) agree on every basis vector \(f_m \otimes f_l\) of \(\mathbb{C}^{n^2}\). From part (i), \[\widetilde{U}^{\,n}(f_m \otimes f_l) = \widetilde{U}_l^n\,(f_m \otimes f_l) = (-1)^{l \bmod n}\,(f_m \otimes f_l) = (-1)^l\,(f_m \otimes f_l),\] where the last equality uses \(l \in \mathbb{Z}_n\) so that \(l \bmod n = l\). Using the mixed-product property and the eigenrelation \(\widetilde{P}\,f_l = \omega^l f_l\) with \(\omega = e^{2\pi i/n}\), we have \[(I_n \otimes \widetilde{P}^{n/2})(f_m \otimes f_l) = f_m \otimes \widetilde{P}^{n/2} f_l = f_m \otimes \omega^{ln/2}\,f_l = e^{i\pi l}\,(f_m \otimes f_l) = (-1)^l\,(f_m \otimes f_l).\] Both sides produce the same scalar \((-1)^l\) on every basis vector \(f_m \otimes f_l\) of \(\mathbb{C}^{n^2}\), so \[\widetilde{U}^{\,n} = I_n \otimes \widetilde{P}^{n/2},\] which is part (ii). ◻

Proof. Let the vertices of \(K_n^{\circlearrowleft}\) be labeled by \(V(K_n^{\circlearrowleft}) = \{v_0,v_1,\ldots,v_{n-1}\}.\) Let \(\widetilde{U}\) be transition matrix of \(K_n^{\circlearrowleft}\) defined by \(\widetilde{U} = \widetilde{S} \widetilde{R}\), where \(S = \bigoplus_{k=0}^{n-1} \widetilde{P}^k\) and \(R = 2\widetilde{Q}\widetilde{Q}^\top - I_{n^2}\), \(\widetilde{Q} = \frac{1}{\sqrt{d}} \begin{bmatrix} I_n \\ \widetilde{P} \\ \widetilde{P}^2 \\ \vdots \\ \widetilde{P}^{d-1} \end{bmatrix}.\) Thus the arc set of \(K_n^{\circlearrowleft}\) is \(\mathcal{A}(K_n^{\circlearrowleft}) = \bigl\{(v_i, v_j) : i, j \in \mathbb{Z}_n\bigr\},\) so the state space of the walk is \(\mathbb{C}^{n^2}\) with orthonormal basis \(\{e_{v_i} \otimes e_{v_j}\}_{(v_i,v_j) \in \mathcal{A}(K_n^{\circlearrowleft})}\in \operatorname{Im}(I_d\otimes \widetilde{Q})\). Since \(d=n\) for \(K_n^{\circlearrowleft}\), we have by Lemma 13, \[\label{eq:Un-thm} \widetilde{U}^{\,n} = I_n\otimes \widetilde{P}^{n/2},\tag{32}\] where \(\widetilde{P}\) is the cyclic shift matrix satisfying \(\widetilde{P} e_{v_j}=e_{v_{j+1\bmod n}}\). The basis vector \(e_{v_i}\otimes e_{v_j}\) represents the walker on the arc \((v_i,v_j)\). Using the mixed-product property, \[(I_n\otimes \widetilde{P}^{n/2})(e_{v_i}\otimes e_{v_j}) = (I_n e_{v_i})\otimes(\widetilde{P}^{n/2}e_{v_j}) = e_{v_i}\otimes e_{v_{j+n/2\bmod n}}.\] Hence, by 32 , \[\widetilde{U}^{\,n}(e_{v_i}\otimes e_{v_j}) = e_{v_i}\otimes e_{v_{j+n/2\bmod n}}.\] Therefore every arc \((v_i,v_j)\) is mapped to its antipodal arc \((v_i,v_j) \longmapsto (v_i,v_{j+n/2\bmod n})\) with amplitude \(\bigl(\widetilde{U}^{\,n}\bigr)_{ (v_i,v_{j+n/2\bmod n}), (v_i,v_j)} = 1.\) Since \(\widetilde{U}^{\,n}\) is unitary, all other entries in the same column are zero, and thus the transfer fidelity is \[\mathcal{F} = \Bigl| \bigl(\widetilde{U}^{\,n}\bigr)_{ (v_i,v_{j+n/2\bmod n}), (v_i,v_j)} \Bigr|^2 = 1.\] This proves (i).

Applying 32 twice gives \[\widetilde{U}^{\,2n} = (\widetilde{U}^{\,n})^2 = (I_n\otimes C^{n/2})^2 = I_n\otimes C^n = I_{n^2}.\] Thus the period divides \(2n\). Since \(n\ge2\), \(\widetilde{P}^{n/2}e_{v_j} = e_{v_{j+n/2}} \neq e_{v_j},\) so \(\widetilde{P}^{n/2}\neq I_n\), and hence \[\widetilde{U}^{\,n} = I_n\otimes \widetilde{P}^{n/2} \neq I_{n^2}.\] Therefore the period does not divide \(n\). Since it divides \(2n\) but not \(n\), the period is exactly \(2n\). This proves (ii). ◻

Proof. Every arc of \(E\) is uniquely of the form \((a_i,b_j)\) or \((b_i,a_j)\) for some \((i,j)\in[n]^2\), so each arc belongs to exactly one cell \(C_{ij}\). The cells are pairwise disjoint and cover \(E\), so \(\tau\) partitions \(E\) into \(n^2\) cells each of size \(2\). For each cell \(C_{ij}\) \[\label{tail32head} \mathrm{tail}(C_{ij})=\{a_i,b_i\},\quad \mathrm{head}(C_{ij})=\{a_j,b_j\}.\tag{33}\]

By definition of the line digraph, \(C_{ij}\to C_{kl}\) in \(LD(K^{\rightleftharpoons}_{n,n})\) if and only if \[\mathrm{head}(C_{ij})\cap\mathrm{tail}(C_{kl})\neq\emptyset,\] that is, \(\{a_j,b_j\}\cap\{a_k,b_k\}\neq\emptyset\), which holds if and only if \(j=k\). Hence out neighbours of \[\label{head32tail} (C_{ij})=\{C_{jl}:1\le l\le n\},\tag{34}\] and every cell has out-degree exactly \(n\). We must show that for every pair of cells \(C_{ij}\) and \(C_{kl}\), every arc \(e\in C_{ij}\) points to the same number of arcs in \(C_{kl}\), and that this number equals \(B_{(i,j),(k,l)}\).

Case 1: \(j\neq k\). By Equation 34 , no arc of \(C_{ij}\) points to any arc of \(C_{kl}\), so the count is \(0\).

Case 2: \(j=k\). Take any arc \(e\in C_{ij}\). From Equation  33 , \(e\) has a unique head vertex \(v\in\mathrm{head}(C_{ij})=\{a_j,b_j\}\), namely: \[v=\begin{cases}b_j & \text{if }e=(a_i,b_j),\\ a_j & \text{if }e=(b_i,a_j).\end{cases}\] Now consider cell \(C_{jl}\) (since \(k=j\)). Its two arcs are \((a_j,b_l)\) and \((b_j,a_l)\), with tails \(a_j\) and \(b_j\) respectively. Exactly one of these tails equals \(v\): \[\begin{cases} (a_j,b_l)\text{ has tail }a_j=v & \text{if }e=(b_i,a_j),\\ (b_j,a_l)\text{ has tail }b_j=v & \text{if }e=(a_i,b_j). \end{cases}\] Hence exactly \(1\) arc in \(C_{jl}=C_{kl}\) follows \(e\), and this count is independent of which arc \(e\in C_{ij}\) we chose and independent of \(i\) and \(l\). Combining both cases, the number of arcs in \(C_{kl}\) that any arc \(e\in C_{ij}\) points to is \[B_{(i,j),(k,l)}=\begin{cases}1 & \text{if }j=k,\\0 & \text{if }j\neq k,\end{cases}\] which depends only on \(j\) and \(k\), not on \(i\), \(l\), or the choice of \(e\in C_{ij}\). Therefore \(\tau\) is an equitable partition with quotient matrix \(B\) as stated. If \(Q_\tau\) is the normalized characteristic matrix of \(\tau\), then \[A_{LD(K^{\rightleftharpoons}_{n,n})}\,Q_\tau=Q_\tau\,B,\] where \(A_{LD(K^{\rightleftharpoons}_{n,n})}\) is the adjacency matrix of \(LD(K^{\rightleftharpoons}_{n,n})\). Under the identification \(C_{ij}\mapsto(i\to j)\), the adjacency rule \[C_{ij}\to C_{kl}\iff j=k\] coincides exactly with the arc-composition rule \((i\to j)\to(j\to l)\) in \(LD(K^{\circlearrowleft}_n)\). Hence \[LD(K^{\rightleftharpoons}_{n,n})/\tau\cong LD(K^{\circlearrowleft}_n).\] ◻

Proof. Fix any two cells \(C_i, C_j \in \pi\). Since \(a_i\) has out-neighbours \(\{b_1,\dots,b_n\}\) and \(b_j\) is the unique member of \(B\cap C_j\), vertex \(a_i\) has exactly one out-neighbour in \(C_j\). Likewise \(b_i\) has out-neighbours \(\{a_1,\dots,a_n\}\) and \(a_j\) is the unique member of \(A\cap C_j\), so \(b_i\) also has exactly one out-neighbour in \(C_j\). This count is \(1\) for every pair \((i,j)\), including \(i=j\), so \(\pi\) is equitable with quotient matrix \[B_{ij} \;=\; 1 \quad\text{for all } i,j, \qquad\text{that is, } B = J_n.\] Each cell \(C_i = \{a_i, b_i\}\) has size \(d = 2\), so the normalized characteristic matrix is \[Q \;=\; \frac{1}{\sqrt{2}} \begin{pmatrix} I_n \\ I_n \end{pmatrix} \;\in\; \mathbb{R}^{2n\times n},\] where the \(i\)-th column has entry \(\tfrac{1}{\sqrt{2}}\) at rows \(a_i\) and \(b_i\), and zero elsewhere. Fix any \(i \in [n]\). The \(i\)-th column of \(A_G Q\) is \[A_{K_{n,n}^{\rightleftharpoons}} Q\, e_i \;=\; \frac{1}{\sqrt{2}}\,A_{K_{n,n}^{\rightleftharpoons}}\,\mathbf{1}_{C_i},\] where \(\mathbf{1}_{C_i} \in \mathbb{R}^{2n}\) denotes the indicator vector of the cell \(C_i\), with entry \(1\) at vertices \(a_i, b_i\) and \(0\) elsewhere. Since \(a_i\) sends an arc to every \(b_j\) and \(b_i\) sends an arc to every \(a_j\), every vertex of \(K_{n,n}^{\rightleftharpoons}\) receives exactly one arc from \(C_i\), so \(A_{K_{n,n}^{\rightleftharpoons}}\,\mathbf{1}_{C_i} \;=\; \mathbf{1}_{V(K_{n,n}^{\rightleftharpoons})}.\) The \(i\)-th column of \(Q J_n\) is \[Q J_n\, e_i \;=\; \frac{1}{\sqrt{2}} \begin{pmatrix} I_n \\ I_n \end{pmatrix} \mathbf{1}_n \;=\; \frac{1}{\sqrt{2}}\,\mathbf{1}_{V(K_{n,n}^{\rightleftharpoons})},\] since \(J_n e_i = \mathbf{1}_n\) and each vertex of \(G\) belongs to exactly one cell, so \(\sum_{j=1}^n \mathbf{1}_{C_j} = \mathbf{1}_{V(K_{n,n}^{\rightleftharpoons})}\). Both columns equal \(\tfrac{1}{\sqrt{2}}\,\mathbf{1}_{V(K_{n,n}^{\rightleftharpoons})}\) for every \(i \in [n]\), hence \(A_{K_{n,n}^{\rightleftharpoons}}\,Q = Q\,J_n\). Thus, the quotient graph \(K_{n,n}^{\rightleftharpoons}/\pi\) has adjacency matrix \(B = J_n\), which has a \(1\) in every position including the diagonal. Hence \(K_{n,n}^{\rightleftharpoons}/\pi\) has an arc from \(C_i\) to \(C_j\) for every \((i,j)\in[n]^2\), including \(i=j\), giving \[K_{n,n}^{\rightleftharpoons}/\pi \cong K_n^{\circlearrowleft}.\] ◻

Proof. Let \(\pi = \{C_1, C_2, \ldots, C_n\}\) be an equitable vertex partition where \(C_i = \{a_i, b_i\}\). By Lemma 15, we have \[K^{\rightleftharpoons}_{n,n}/\pi \;\cong\; K_n^{\circlearrowleft}, \label{eq:quotient95iso}\tag{35}\] the complete graph with a loop at every vertex. Let \(\sigma = \{\sigma_1, \ldots, \sigma_n\}\) be an equitable arc partition of \(\mathrm{LD}(K^{\rightleftharpoons}_{n,n}/\pi)\). Then by Theorem 8, \[\mathrm{LD}(K^{\rightleftharpoons}_{n,n}/\pi)/\sigma \;\cong\; K^{\rightleftharpoons}_{n,n}/\pi \;\cong\; K_n^{\circlearrowleft}.\] Since \(\sigma\) is an equitable arc partition, by Lemma 5 we have \[A_{\mathrm{LD}(K^{\rightleftharpoons}_{n,n}/\pi)}\,\widetilde{Q} \;=\; \widetilde{Q}\,\widetilde{A},\] where \(\widetilde{A}\) is the adjacency matrix of \(K_n^{\circlearrowleft}\). By relabeling the arcs of \(K^{\rightleftharpoons}_{n,n}/\pi\), the normalized characteristic matrix takes the form \[\widetilde{Q} \;=\; \frac{1}{\sqrt{d}} \begin{bmatrix} I_n \\ \widetilde{P} \\ \widetilde{P}^2 \\ \vdots \\ \widetilde{P}^{d-1} \end{bmatrix},\] where \[I_n + \widetilde{P} + \widetilde{P}^2 + \cdots + \widetilde{P}^{d-1} \;=\; A(K_n^{\circlearrowleft}),\] that is, \(\widetilde{P}, \ldots, \widetilde{P}^{d-1}\) are the cyclic shifts (permutation matrices) of the adjacency matrix of \(K_n^{\circlearrowleft}\).

By Theorem 25, \(K_n^{\circlearrowleft}\) exhibits PST at step \(k = n\) and is periodic at step \(2n\). Moreover, by Lemma 14, \[\mathrm{LD}(K^{\rightleftharpoons}_{n,n})/\tau \;\cong\; \mathrm{LD}(K^{\circlearrowleft}_n).\] Therefore, by Theorem 15, the transition matrix \(U_\sigma\) of \(\mathrm{LD}(K^{\rightleftharpoons}_{n,n}/\pi)\) exhibits PST from \((I_d\otimes \widetilde{Q} )\,x\) to \((I_d \otimes \widetilde{Q})\,y\), for all \(x, y \in \mathrm{Im}(I_d\otimes \widetilde{Q} )\), at step \(k = n\) and is periodic at step \(2n\). Furthermore, the transition matrix \(U_\tau\) of \(\mathrm{LD}(K^{\rightleftharpoons}_{n,n})\) exhibits PST from \[(I_d\otimes Q_\tau )(I_d \otimes \widetilde{Q})\,x \quad \text{to} \quad (I_d \otimes Q_\tau )(I_d \otimes \widetilde{Q} )\,y,\] for all \(x, y \in \mathrm{Im}(I_d \otimes \widetilde{Q} )\), at step \(k = n\) and is periodic at step \(2n\). ◻

Proof. Write \(\mathbb{Z}_{2n} = \mathcal{E} \sqcup \mathcal{O}\) where \(\mathcal{E} = \{0,2,\dots,2n-2\}\) and \(\mathcal{O} = \{1,3,\dots,2n-1\}\) are the even and odd elements respectively, each of cardinality \(n\). By hypothesis, each cell \(C_{r'}\) satisfies \(|C_{r'} \cap \mathcal{E}| = |C_{r'} \cap \mathcal{O}| = 1\), so we may write \(C_{r'} = \{e_{r'}, o_{r'}\}\) with \(e_{r'} \in \mathcal{E}\) and \(o_{r'} \in \mathcal{O}\). Fix \(r \in \{1,\dots,n\}\) and let \(v \in C_r\) be arbitrary. Since every \(s \in S = \mathcal{O}\) is odd, \[v + s \equiv v + 1 \pmod{2},\] so all \(n\) neighbours \(N(v) = \{v + s \pmod{2n} : s \in S\}\) lie entirely in \(\mathcal{O}\) if \(v \in \mathcal{E}\), and entirely in \(\mathcal{E}\) if \(v \in \mathcal{O}\). Moreover, since \(0 \notin S\), the map \(s \mapsto v + s \pmod{2n}\) is injective on \(S\), so \(|N(v)| = |S| = n\). Now fix \(r' \in \{1,\dots,n\}\). We count \(|N(v) \cap C_{r'}|\) by considering two cases.

Case 1: \(v \in \mathcal{E}\). Then \(N(v) \subseteq \mathcal{O}\), so \(N(v) \cap C_{r'} = N(v) \cap \{o_{r'}\}\). The element \(o_{r'} \in N(v)\) if and only if \(o_{r'} - v \pmod{2n} \in S\). Since \(v \in \mathcal{E}\) and \(o_{r'} \in \mathcal{O}\), we have \(v \neq o_{r'}\), so \(o_{r'} - v \not\equiv 0 \pmod{2n}\). Furthermore \(o_{r'} - v\) is odd (odd minus even), hence \(o_{r'} - v \pmod{2n} \in \mathcal{O} = S\). Thus \(|N(v) \cap C_{r'}| = 1\).

Case 2: \(v \in \mathcal{O}\). Then \(N(v) \subseteq \mathcal{E}\), so \(N(v) \cap C_{r'} = N(v) \cap \{e_{r'}\}\). Since \(v \in \mathcal{O}\) and \(e_{r'} \in \mathcal{E}\), we have \(v \neq e_{r'}\), so \(e_{r'} - v \not\equiv 0 \pmod{2n}\). Furthermore \(e_{r'} - v\) is odd (even minus odd), hence \(e_{r'} - v \pmod{2n} \in \mathcal{O} = S\). Thus \(|N(v) \cap C_{r'}| = 1\).

In both cases \(|N(v) \cap C_{r'}| = 1\), and this count depends only on \(r\) and \(r'\), not on the particular choice of \(v \in C_r\). Hence by definition \(\pi\) is an equitable partition of \(G\) with \[A(G/\pi)_{r,r'} = 1 \qquad \text{for all } r,r' \in \{1,\dots,n\},\] giving \[A(G/\pi) = J_{n\times n}\]. The diagonal entries \(A(G/\pi)_{r,r} = 1\) correspond to loops at each vertex of \(G/\pi\), so the quotient multigraph is \(K_n^{\circlearrowleft}\). ◻

Proof. Observe that \(o_j - e_i = (2j-1)-(2i-2) = 2(j-i)+1 \in S,\) so \((e_i,o_j)\in\mathcal{A}(G)\), and \(e_j - o_i = (2j-2)-(2i-1) = 2(j-i)-1 \equiv 2(j-i)-1 \pmod{2n},\) which is odd and hence lies in \(S\), so \((o_i,e_j)\in\mathcal{A}(G)\). Thus \(|C_{ij}|=2\) for all \((i,j)\in[n]^2\). Since \[\mathcal{A}(G) = \{(v,w)\in\mathbb{Z}_{2n}^2 : w-v\in S\} = \{(e_i,o_j):1\le i,j\le n\} \cup\{(o_i,e_j):1\le i,j\le n\},\] and the maps \((e_i,o_j)\mapsto (i,j),\quad (o_i,e_j)\mapsto (i,j)\) are both bijections from their respective domains to \([n]^2\), each arc of \(G\) belongs to exactly one cell \(C_{ij}\). Hence \(\bigsqcup_{(i,j)\in[n]^2} C_{ij} = \mathcal{A}(G),\) so \(\tau\) partitions \(\mathcal{A}(G)\) into \(n^2\) cells each of size \(2\). For each cell \(C_{ij}\), \[\label{circ:tailhead} \mathrm{tail}(C_{ij})=\{e_i,o_i\}=m_i,\qquad \mathrm{head}(C_{ij})=\{o_j,e_j\}=m_j.\tag{36}\] By definition of the line digraph, \(C_{ij}\to C_{kl}\) in \(LD(G)\) if and only if \[\mathrm{head}(C_{ij})\cap\mathrm{tail}(C_{kl})\neq\emptyset,\] that is, \(m_j\cap m_k\neq\emptyset\), which holds if and only if \(j=k\). Hence the out-neighbours of \(C_{ij}\) are \[\label{circ:outnbr} \{C_{jl}:1\le l\le n\},\tag{37}\] and every cell has out-degree exactly \(n\). We must show that for every pair of cells \(C_{ij}\) and \(C_{kl}\), every arc \(e\in C_{ij}\) points to the same number of arcs in \(C_{kl}\), and that this number equals \(B_{(i,j),(k,l)}\).

Case 1: \(j\neq k\). By Equation  37 , no arc of \(C_{ij}\) points to any arc of \(C_{kl}\), so the count is \(0\).

Case 2: \(j=k\). Take any arc \(e\in C_{ij}\). From Equation 36 , \(e\) has a unique head vertex \(v\in\mathrm{head}(C_{ij})=m_j\), namely \[v=\begin{cases}o_j & \text{if }e=(e_i,o_j),\\ e_j & \text{if }e=(o_i,e_j).\end{cases}\] Now consider cell \(C_{jl}\) (since \(k=j\)). Its two arcs are \((e_j,o_l)\) and \((o_j,e_l)\), with tails \(e_j\) and \(o_j\) respectively. Exactly one of these tails equals \(v\) \[\begin{cases} (e_j,o_l)\text{ has tail }e_j=v & \text{if }e=(o_i,e_j),\\ (o_j,e_l)\text{ has tail }o_j=v & \text{if }e=(e_i,o_j). \end{cases}\] Hence exactly \(1\) arc in \(C_{jl}=C_{kl}\) follows \(e\), and this count is independent of which arc \(e\in C_{ij}\) we chose and independent of \(i\) and \(l\). Combining both cases, the number of arcs in \(C_{kl}\) that any arc \(e\in C_{ij}\) points to is \[B_{(i,j),(k,l)}=\begin{cases}1 & \text{if }j=k,\\0 & \text{if }j\neq k,\end{cases}\] which depends only on \(j\) and \(k\), not on \(i\), \(l\), or the choice of \(e\in C_{ij}\). Therefore \(\tau\) is an equitable partition with quotient matrix \(B\) as stated. If \(Q_\tau\) is the normalised characteristic matrix of \(\tau\), then \[A_{LD(G)}\,Q_\tau=Q_\tau\,B,\] where \(A_{LD(G)}\) is the adjacency matrix of \(L(\mathrm{Circ}(2n,S))\). Under the identification \(C_{ij}\mapsto(i\to j)\), the adjacency rule \[C_{ij}\to C_{kl}\iff j=k\] coincides exactly with the arc-composition rule \((i\to j)\to(j\to l)\) in \(L(K^{\circlearrowleft}_n)\). Hence \[LD(\mathrm{Circ}(2n,S))/\tau\cong LD(K^{\circlearrowleft}_n).\qquad\square\] ◻

Proof. Let \(\pi = \{C_1, C_2, \ldots, C_n\}\) be an equitable vertex partition of \(G\) where each cell \(C_i\) contains exactly one even and one odd element of \(\mathbb{Z}_{2n}\). By Lemma 16, we have \[G/\pi \;\cong\; K_n^{\circlearrowleft}, \label{eq:circ95quotient95iso}\tag{38}\] the complete graph with a loop at every vertex. Let \(\sigma = \{\sigma_1, \ldots, \sigma_n\}\) be an equitable arc partition of \(\mathrm{LD}(G/\pi)\). Then by Theorem 8, \[\mathrm{LD}(G/\pi)/\sigma \;\cong\; G/\pi \;\cong\; K_n^{\circlearrowleft}.\] Since \(\sigma\) is an equitable arc partition, by Lemma 5 we have \[A_{\mathrm{LD}(G/\pi)}\,\widetilde{Q} \;=\; \widetilde{Q}\,\widetilde{A},\] where \(\widetilde{A}\) is the adjacency matrix of \(K_n^{\circlearrowleft}\). By relabeling the arcs of \(G/\pi\), the normalized characteristic matrix takes the form \[\widetilde{Q} \;=\; \frac{1}{\sqrt{d}} \begin{bmatrix} I_n \\[4pt] \widetilde{P} \\[4pt] \widetilde{P}^2 \\[4pt] \vdots \\[4pt] \widetilde{P}^{d-1} \end{bmatrix},\] where \[I_n + \widetilde{P} + \widetilde{P}^2 + \cdots + \widetilde{P}^{d-1} \;=\; A\!\left(K_n^{\circlearrowleft}\right),\] that is, \(\widetilde{P}, \widetilde{P}^2, \ldots, \widetilde{P}^{d-1}\) are the cyclic shifts (permutation matrices) of the adjacency matrix of \(K_n^{\circlearrowleft}\). By Theorem 25, \(K_n^{\circlearrowleft}\) exhibits PST at step \(k = n\) and is periodic at step \(2n\). Moreover, by Lemma 17, \[\mathrm{LD}(G)/\tau \;\cong\; \mathrm{LD}\!\left(K_n^{\circlearrowleft}\right).\] Therefore, by Theorem 15, the transition matrix \(U_\sigma\) of \(\mathrm{LD}(G/\pi)\) exhibits PST from \((I_d \otimes \widetilde{Q})\,x\) to \((I_d \otimes \widetilde{Q} )\,y\), for all \(x,\, y \in \mathrm{Im}(I_d \otimes \widetilde{Q})\), at step \(k = n\) and is periodic at step \(2n\). Furthermore, the transition matrix \(U_\tau\) of \(\mathrm{LD}(G)\) exhibits PST from \[(I_d \otimes Q_\tau)(I_d \otimes \widetilde{Q} )\,x \quad\text{to}\quad (I_d \otimes Q_\tau )(I_d \otimes \widetilde{Q} )\,y,\] for all \(x,\, y \in \mathrm{Im}(I_d \otimes \widetilde{Q} )\), at step \(k = n\) and is periodic at step \(2n\). ◻