2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

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