Neighborhood overlap matrix for a bipartite graph

Question

Let $G$ be an undirected, simple, bipartite graph with parts $V$ (having $n$ vertices) and $W$ (having $m$ vertices). Define the following $n$-by-$n$ matrix: for any $i,j \in V$, $$a_{ij} = |N_i \cap N_j|,$$ the number of vertices in the neighborhoods of both $i$ and $j$. (So the diagonal entry $a_{ii}$ is the degree of vertex $i$.)

Another way of expressing this matrix is to consider a $n$-by-$m$ matrix $C$ such that $c_{ij}=1$ if and only if vertices $i \in V$ and $j \in W$ are adjacent in $G$; then note that $A=CC^T$. From this we see immediately $A$ is positive semidefinite.

The question: Can we find an "explicit" or interpretable expression for the inverse of $A$, when $A$ is invertible?

Answer 1

Your matrix $C$ is one of the off-diagonal blocks of (symmetric) adjacency matrix $B$ of your graph. The diagonal blocks of $B$ are zero. Your matrix $A$ is then one of the diagonal blocks of $B^2$, which would be block diagonal. So, its inverse is then the corresponding diagonal block of $B^{-2}$, since inverses preserve block structure. In fact, the inverse symmetric matrix $B^{-1}$ will have the same block structure as $B$, with some off-diagonal block $D$. Then your $A^2$ is $DD^{T}$.

It remains to compute $D$, or equivalently $B^{-1}$. Now, using Cramer's rule, the formula for the elements $B^{-1}$ is $B^{-1}_{ij} = (\operatorname{adj} B)_{ij}/\det{B}$, where $\operatorname{adj} B$ is the adjugate matrix of $B$, which is the same as the cofactor matrix, being symmetric for symmetric $B$. So $(\operatorname{adj} B)_{ij} = (-1)^{i+j} \det B^{(i,j)}$, where $B^{(i,j)}$ is the same matrix as $B$ except that $B^{(i,j)}_{ij} = 1$ and all other elements in the $i$'th row, as well as the $j$'th column, set to zero.

I think the above formula can be made "interpretable" in graph theoretic terms if we can find such an interpretation for the determinant of the adjacency matrix of a graph. Turns out, there is such an interpretation, which was mentioned in question MO134956: if we interpret $B$ as the adjacency matrix of a directed graph (each edge is double to pass from an undirected graph to a directed one), $\det B$ counts with signs the partitions of the underlying graph into subsets, where each subset must consist of the vertices of a directed graph cycle; if $v$ is the number of vertices in the graph and $s$ is the number of subsets in a given partition, the corresponding sign is $(-1)^{v+s}$.

So, that does it for $\det B$. What about $\det B^{(i,j)}$? Well, $B^{(i,j)}$ is the adjacency matrix of the directed graph obtained from the directed version of $B$ as follows. First, insert a directed edge between from vertex $i$ to vertex $j$, if it is not already there. Then, remove all edges outgoing from $i$ and all edges incoming to $j$. Some of this description may simplify when specialized to bipartite graphs.

I don't know if this cycle-counting interpretation is convenient for the purposes you had in mind, but it least it seems to fit the parameters of the question.