# Adacency matrix of a line digraph

Let $$G$$ be directed graph with adjacency matrix $$A$$ and let us assume that $$A$$ is primitive, i.e. there exists $$N\in\mathbb{N}$$ such that $$(A^N)_{i,j}>0$$ for all $$i,j$$.

Let now $$L(G)$$ be the line digraph of $$G$$ and denote by $$B$$ its adjacency matrix. (Two vertices representing directed edges from $$u$$ to $$v$$ and from $$w$$ to $$x$$ in $$G$$ are connected by an edge from $$uv$$ to $$wx$$ in the line digraph when $$v = w$$).

My guess is that the matrix $$B$$ is again primitive and this seems to fit with some examples I calculated. However, I am not sure how to prove it rigorously. Can anybody share some good ideas?

I have tried to look for ways of expressing $$B$$ in terms of $$A$$, but for digraph I have found no connection...

Thank you very much for your help!

• Just to be sure I understand: the vertices of $L(G)$ are the edges of $G$ and $ee' \in L(G)$ if $e$ ends where $e'$ starts? Aug 5, 2019 at 21:13
• Funny, I just thought about that. My graphs in question are undirected and regular, but I think this could also work for you: There is an entry in $B$, if an edge $(a,b)$ is connected to an edge $(b,c)$, so I ended at $$B=\sum_a \sum_b \langle b|Aa\rangle \sum_{|c\rangle\in A|b\rangle} E_{a,b}\otimes E_{b,c}$$, where $E_{i,j}$ is a matrix with a $1$ at the $i$th row and $j$ column. What do you think? Aug 6, 2019 at 20:07

I think you're looking for what is close to what is defined here as $$W_1$$:
We define the 0,1 edge matrix $$W_1$$ by orienting the $$m$$ edges of $$G$$ and labeling them as in formula (2.1). Then $$W_1$$ is the $$2m×2m$$ matrix with $$ij$$ entry $$1$$ if edge $$e_i$$ feeds into $$e_j$$ provided that $$e_j\neq e^{−1}_i$$, and $$ij$$ entry $$0$$ otherwise. By “$$e_i$$ feeds into $$e_j$$,” we mean that the terminal vertex of edge $$e_i$$ is the same as the initial vertex of edge $$e_j$$.
Let $$u,w,x$$ be labels of vertices of $$G$$ and not caring about the no-backtracking thing for now, the following should give an $$n^2$$ dimensional representation of $$B$$: $$B=\sum_u \sum_w \langle w|Au\rangle \sum_{|x\rangle\in A|w\rangle} E_{u,w}\otimes E_{w,x}$$
Setting $$E_{u,w}\otimes E_{w,u}=0$$ we can remove the backtrackers, to get a $$n^2$$ dimensional representation of $$W_1$$...