ON SPECTRAL PORTRAITS OF NEAREST NEIGHBOR GRAPH INCIDENCE MATRICES

This paper explores the possibility of applying S.K. Godunov’s method of constructing spectral portraits of matrices to estimate the rank of special types of matrices that appear in various applications, such as nearest neighbor graph structure analysis, finite automata theory, and sparse matrix spectrum estimation. A computational algorithm for generating an ensemble of random distance matrices and the associated nearest neighbor graphs is described. Based on computational experiments, parameters of the vertex degree distribution of random nearest neighbor graphs are evaluated. These estimates are feasible because the distribution is independent of the random distance function and follows a multivariate normal distribution. It is proven that the rank of the incidence matrix of a nearest neighbor graph equals the total number of vertices with in-degree 0 and 1, and the rank distribution of such a matrix is derived. It is also shown that, in this context, a method based on analyzing the vertex degree distribution is highly effective for determining the matrix rank.

nearest neighbor graph, vertex degree distribution, spectral portrait, matrix rank distribution