1
$\begingroup$

In a directed graph I'm interested in finding pairs of vertices pointing towards a common vertex. More in detail, from an adjacency matrix I want to derive a matrix where a positive entry denotes that the vertices represented by the entry's row and column both point to a common vertex.

For example, a graph with the following adjacency matrix: $$ \left[\begin{matrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ \end{matrix}\right], $$ would result in the following matrix: $$ \left[\begin{matrix} 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ \end{matrix}\right]. $$ Since vertex 2 and 4 points to vertex 3 and vertex 1 and 3 points to vertex 4. (Or with the diagonal as ones if one does not need unique vertices in the pairs.)

I'm thinking that there must be a simple matrix algebra solution to this, similar to using powers of the adjacency matrix to find walks. My intuition tells me: $$ \mathbf{A}\mathbf{A}^T $$ would do the trick, where $\mathbf{A}$ is the adjacency matrix. (In this case with a single vertex allowed to form a pair). While every example I've tested works out well, I cannot prove it will work in general. So I'm wondering: will it?

$\endgroup$
0
$\begingroup$

Yes, you're correct (nice guess!)

I find it a bit easier to visualize the $(i,j)$-entry of $AA^T$ as the standard inner product of rows $i$ and $j$ of $A$. Since all entries of $A$ are non-negative, you will got a positive value if and only if there is a column $k$ so that both entries in coordinates $(i,k)$ and $(j,k)$ are positive, i.e., there is a $k$ so that $(i,k)$ and $(j,k)$ are directed edges in the graph.

So in your example, this occurs for $i=1$ and $j=3$ (at $k=4$), and also for $i=2$ and $j=4$ (at $k=3$), which of course is what you found.

$\endgroup$

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.