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