Laplace spectra of orgraphs and their applications

The Laplace matrix is the matrix $L=(\ell_{ij})\in\mathbb{R}^n\times n$ with nonpositive off-diagonal elements and zero row sums. A weighted orgraph corresponds to each Laplace matrix, its properties being closely related to the algebraic properties of the Laplace matrix. The normalized Laplace matrix $\widetilde{L}$ is the Laplace matrix where $-\dfrac{1}{n}\leqslant\ell_{ij}\leqslant 0$ for all $i\ne j$. The paper was devoted to the spectrum of the Laplace matrices and to the relationship between the spectra of the Laplace and stochastic matrices. The normalized Laplace matrices were proved to be semiconvergent. It was established that the multiplicity of the eigenvalue 0 of the matrix $\widetilde{L}$ is equal to the in-forest dimension of the corresponding orgraph, and the multiplicity of the eigenvalue $1$ is one less than the in-forest dimension of the complementary orgraph. The spectra of the matrices $\widetilde{L}$ belong to the intersection of two circles of radius $1-1/n$ centered at the points $1/n$ and $1-1/n$, respectively. Additionally, the domain that comprises them is included in the intersection of two angles (defined in the paper) with vertices $0$ and $1$ and the band $|{\rm Im}\,(z)|\leqslant\frac{1}{2n}{\mathrm{ctg}}\frac{\pi}{2n}$ (at the limit $|{\rm Im}(z)|< \frac{1}{\pi}$). A polygon with all points being the eigenvalues of the normalized $n$-order Laplace matrices was constructed.

Presented by the member of Editorial Board: B. T. Polyak