Sturm sequences and random eigenvalue distributions (Q839658)

In the paper, the use of Sturm sequences as a computational tool to efficiently compute histograms of eigenvalues for symmetric tridiagonal matrices is explored. By this method it is possible to compute a histogram of the eigenvalues of a tridiagonal matrix in \(O(mn)\) time where \(n\) is the dimension of the matrix and \(m\) is the number of bins (with arbitrary bin centers and widths) desired in the histogram. By the standard way of computing the eigenvalues and their histogramming the \(O(n^2 + m)\) time can be achieved. The developed algorithm represents a significant improvement because \(m\) is usually much smaller than \(n\). This algorithm allows to compute histograms that were earlier computationally infeasible such as those for \(n\) equal to 1 billion. In the first part of the paper, a theoretical use of Sturm sequences, giving both the eigenvalue distribution (level density) and the largest eigenvalue distribution of \(\beta\)-Hermite random matrix ensembles for arbitrary values of \(\beta\), is described. When normalized properly, the eigenvalue distribution converges to the well known Wigner semicircle. Analytic formulas in terms of multivariate integrals for any \(n\) and \(\beta\) are derived by analyzing the Sturm sequences of the tridiagonal matrix model. Then, the relationship between the Sturm sequence of a tridiagonal random matrix \(A\) and its shooting eigenvectors is explored. Shooting eigenvectors are those that result from fixing one value (e. g. \(x_1\)) of a vector \(x=(x_1, x_2, \dots, x_n)\) and solving for the rest of its values under the equation \((A - \lambda I)x = 0\). It is shown, while using Sturm sequences and assuming that the eigenvector contains no zeros, that the number of sign changes in the shooting eigenvector is equal to the number of eigenvalues of \(A\) greater than \(\lambda\). Finally, the presented histogramming technique is used to examine the variance of histogram bin values for eigenvalues of the \(\beta\)-Hermite random matrix ensemble. Plots of the mean variance as \(n\) increases are constructed to illustrate an \(O(\text{log}~ n)\) growth relationship.