On Spectral Portraits of Incidence Matrices of Nearest Neighbor Graphs

Application of Godunov’s method for constructing the spectral portrait of a matrix for estimating the rank of matrices of a special form that arise in a number of applications, such as analyzing the structures of nearest neighbor graphs, the theory of finite state machines, and estimating the spectrum of sparse matrices is studied. A computational algorithm for generating an ensemble of random distance matrices and associated nearest neighbor graphs is described. On the basis of a computational experiment, parameters of the distribution of degrees of vertices of random nearest neighbor graphs are estimated. Estimates can be obtained due to the fact that the specified distribution is independent of the distribution function of random distances and is a multidimensional normal distribution. It is proved that the rank of the incidence matrix of the nearest neighbor graph is equal to the total number of vertices with in-degrees zero and one, and the distribution of the rank of such a matrix is obtained. It is shown that in this problem of determining the rank of a matrix, a method based on the analysis of the distribution of vertex degrees is also very effective.