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!

  • $\begingroup$ 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? $\endgroup$
    – qualcuno
    Aug 5, 2019 at 21:13
  • $\begingroup$ 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? $\endgroup$
    – draks ...
    Aug 6, 2019 at 20:07

1 Answer 1


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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