Find vertices pointing to common vertex 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.
