Condition on ratio related to bipartite graph

102 Views Asked by At

I know that for a bipartite graph, the adjacency matrix can be written as \begin{align} A = \begin{pmatrix} 0_{rr} & B \\ B^T & 0_{ss} \end{pmatrix}. \end{align} Let $M_{-}$ be the signed incidence matrix and let $C$ be the matrix defined as \begin{align} C = \begin{pmatrix} 0_{rr} & B \\ 0_{rs} & 0_{ss} \end{pmatrix}. \end{align} I'm interested to find, under which conditions on the graph, the ratio \begin{align} \kappa = \frac{\sigma_{\max}(C)}{\tilde{\sigma}_{\min}(M_{-})} \end{align} is very small, (i.e. almost zero)? where $\sigma_{\max}(C)$ is the maximum singular value of the matrix $C$ and $\tilde{\sigma}_{\min}(M_{-})$ is is the minimum non-zero singular value of $M_{-}$.