# Analysis of the Laplacian of a random bipartite graph

My analysis of an engineering problem reduced to analysis of the Laplacian of a (random) bipartite graph. There are a few particular questions I am interested in, but not sure which direction to take at the moment. Below, I am outlining the problem. Would really appreciate any advice.

## The Graph

I have an undirected weighted complete bipartite graph $G = (V_1, V_2, E)$, with $\vert V_1 \vert = n_1$, $\vert V_2 \vert = n_2$, $n_1 + n_2 \equiv n$. Each vertex from $V_1$ is connected with each one from $V_2$. $G$ is obviously connected. Edge weights are positive i.i.d. random variables: $e_{ij} \in (e_\text{min}, e_\text{max})$, where $e_\text{min},e_\text{min} \in \mathbb{R}_+$ and $e_\text{min} \ll e_\text{max}$.

The edge weights of $G$ can be represented by a (random) matrix $S \in \mathbb{R}_+^{n_1 \times n_2}$: each element of this matrix, $s_{ij}$, represents a weight of the edge that connects $v_i \in V_1$ and $v_j \in V_2$. In this case, weighted adjacency matrix, $A \in \mathbb{R}_+^{n \times n}$, and Laplacian matrix, $L = D - A$, will have the following block structures: $$A = \begin{pmatrix} 0 & S\\ S^\top & 0 \end{pmatrix},\quad L = \begin{pmatrix} D_1 & -S\\ -S^\top & D_2 \end{pmatrix},$$ where $D_1 = \text{diag}(\sum_{j=1}^{n_2} s_{1j}, \dots, \sum_{j=1}^{n_2} s_{n_1j})$ and $D_2 = \text{diag}(\sum_{i=1}^{n_1} s_{i1}, \dots, \sum_{i=1}^{n_1} s_{in_2})$.

## Analysis and Questions

Given a graph instance, $G$, I am interested in inferring its edge weights from resistance distances I can "query" for each pair of the vertices. It can be shown that the resistance distance between $v_i$ and $v_j$ can be expressed as follows [1]: $$r_{ij} = L^{\dagger}_{ii} + L^{\dagger}_{jj} - 2L^{\dagger}_{ij},$$ where $L^{\dagger}$ is the Moore-Penrose pseudoinverse of the Laplacian, which can be expressed as $L^{\dagger} = (L + \frac{1}{n}J)^{-1} - \frac{1}{n}J$, where $J$ is an $n \times n$ matrix of all ones [1]. The resistance distance can be also expressed as [2]: $$r_{ij} = \frac{\det L(i,j)}{\det L(i)} = \frac{\det L(i,j)}{\det L(j)},$$ where $L(i)$ is denotes $L$ without the $i$-th row and column, and $L(i,j)$ denotes $L$ without $i$-th and $j$-th both rows and columns.

Given a set $\{r_{ij}\}$ for $G$, I want to resolve the above system of equations for the unknown variables $\{s_{kl}\}$.

Q1: Is it possible to show that there exists a (non-)unique solution?

The problem is that $r_{ij} = \det L(i,j) / \det L(i)$ leads to a system of polynomial equations, and I have never dealt with. Any suggestions how to approach Q1?

Q2: Suppose, the system for $s_{kl}$ is underdetermined (i.e., we don't have enough $r_{ij}$ values). Is there a way to analyze the distribution of the random graphs over the solution space, i.e., $\mathbb{P}(\{s_{kl}\} \vert \{r_{ij}\})$?

Given that determinants, $\det L(i,j)$ and $\det L(i)$, can be represented as products of the corresponding eigenvalues, Laplacian spectral theory and random matrix theory can probably be the right thing to start with. However, I am only slightly familiar with the former and have no idea whether methods of the latter can help answer my question. Do I need to take this path in my analysis, or there are better ways I should consider?

### References

[1] Bapat, R. B. (2010). Graphs and matrices. Chapter 10. New York (NY): Springer.

[2] Bapat, R. B., Gutmana, I., & Xiao, W. (2003). A simple method for computing resistance distance. Zeitschrift für Naturforschung A, 58(9-10), 494-498.