Лапласовские спектры орграфов и их приложения

Лапласовская матрица – это матрица $L=(\ell_{ij})\in\mathbb{R}^n\times n$, в которой все недиагональные элементы неположительны, а строчные суммы равны нулю. Каждой лапласовской матрице соответствует взвешенный орграф, и его свойства тесно связаны с алгебраическими свойствами лапласовской матрицы. Нормированная лапласовская матрица $\widetilde{L}$ – это лапласовская матрица, в которой $-\dfrac{1}{n}\leqslant\ell_{ij}\leqslant0$ при всех $i\ne j$. Работа посвящена спектру лапласовских матриц, а также соотношению спектров лапласовских и стохастических матриц. Доказано, что нормированные лапласовские матрицы являются полусходящимися. Установлено, что кратность собственного значения $0$ матрицы $\widetilde{L}$ равна лесной размерности соответствующего орграфа, а кратность собственного значения 1 на единицу меньше лесной размерности дополнительного орграфа. Спектры матриц $\widetilde{L}$ принадлежат пересечению двух кругов с центрами в точках $1/n$ и $1-1/n$ и радиусом $1-1/n$. Кроме того, область, их содержащая, входит в пересечение двух определенных в статье углов с вершинами $0$ и $1$ и полосы $|{\rm Im}\,(z)|\leqslant \frac{1}{2n}{\mathrm{ctg}}\frac{\pi}{2n}$ (в пределе $|{\rm Im}(z)|<\frac{1}{\pi}$). Построен многоугольник, все точки которого являются собственными значениями нормированных лапласовских матриц порядка $n$.

Статья представлена к публикации членом редколлегии: Б. Т. Поляк