Alan Edelman

Welcome to my new website! (September 16, 2014)

• Professor of Applied Mathematics
• Computer Science and AI Laboratories

Random Eigenvalues etc.

 Beyond Universality in Random Matrix Theory Edelman, A., Guionnet, A., & Péché, S. (2016). The Annals of Applied Probability, 26(3), 1659-1697. PDFarXivAbstract Abstract: In order to have a better understanding of finite random matrices with non-Gaussian entries, we study the 1/N expansion of local eigenvalue statistics in both the bulk and at the hard edge of the spectrum of random matrices. This gives valuable information about the smallest singular value not seen in universality laws. In particular, we show the dependence on the fourth moment (or the kurtosis) of the entries. This work makes use of the so-called complex deformed GUE and Laguerre ensembles. Infinite random matrix theory, tridiagonal bordered Toeplitz matrices, and the moment problem Dubbs, A., & Edelman, A. (2015). Linear Algebra and its Applications, 467, 188-201. PDFAbstract Abstract: The four major asymptotic level density laws of random matrix theory may all be showcased through their Jacobi parameter representation as having a bordered Toeplitz form. We compare and contrast these laws, completing and exploring their representations in one place. Inspired by the bordered Toeplitz form, we propose an algorithm for the finite moment problem by proposing a solution whose density has a bordered Toeplitz form. The singular values of the GUE (less is more) Edelman, A., & La Croix, M. (2015, October). Random Matrices:Theory and Applications, 4(4), Issue 04. PDFarXivAbstract Abstract: Some properties that nominally involve the eigenvalues of Gaussian Unitary Ensemble (GUE) can instead be phrased in terms of singular values. By discarding the signs of the eigenvalues, we gain access to a surprising decomposition: the singular values of the GUE are distributed as the union of the singular values of two independent ensembles of Laguerre type. This independence is remarkable given the well known phenomenon of eigenvalue repulsion. The structure of this decomposition reveals that several existing observations about large n limits of the GUE are in fact manifestations of phenomena that are already present for finite random matrices. We relate the semicircle law to the quarter-circle law by connecting Hermite polynomials to generalized Laguerre polynomials with parameter ±1/2. Similarly, we write the absolute value of the determinant of the n×n GUE as a product n independent random variables to gain new insight into its asymptotic log-normality. The decomposition also provides a description of the distribution of the smallest singular value of the GUE, which in turn permits the study of the leading order behavior of the condition number of GUE matrices. The study is motivated by questions involving the enumeration of orientable maps, and is related to questions involving powers of complex Ginibre matrices. The inescapable conclusion of this work is that the singular values of the GUE play an unpredictably important role that had gone unnoticed for decades even though, in hindsight, so many clues had been around. Random Matrix Theory, Numerical Computation and Applications Edelman, A., Sutton, B. D., & Wang, Y. (2014). Modern Aspects of Random Matrix Theory, 72, 53. PDF The Beta-MANOVA Ensemble with General Covariance Dubbs, A., & Edelman, A. (2014). Random Matrices: Theory and Applications, 3(01), 1450002. PDFarXivAbstract Abstract: We find the joint generalized singular value distribution and largest generalized singular value distributions of the $\beta$-MANOVA ensemble with positive diagonal covariance, which is general. This has been done for the continuous $\beta > 0$ case for identity covariance (in eigenvalue form), and by setting the covariance to $I$ in our model we get another version. For the diagonal covariance case, it has only been done for $\beta = 1,2,4$ cases (real, complex, and quaternion matrix entries). This is in a way the first second-order $\beta$-ensemble, since the sampler for the generalized singular values of the $\beta$-MANOVA with diagonal covariance calls the sampler for the eigenvalues of the $\beta$-Wishart with diagonal covariance of Forrester and Dubbs-Edelman-Koev-Venkataramana. We use a conjecture of MacDonald proven by Baker and Forrester concerning an integral of a hypergeometric function and a theorem of Kaneko concerning an integral of Jack polynomials to derive our generalized singular value distributions. In addition we use many identities from Forrester's {\it Log-Gases and Random Matrices}. We supply numerical evidence that our theorems are correct. Low-temperature random matrix theory at the soft edge Edelman, A., Persson, P. O., & Sutton, B. D. (2014). Journal of Mathematical Physics, 55(6), 063302. PDFAbstract Abstract: "Low temperature" random matrix theory is the study of random eigenvalues as energy is removed. In standard notation, β is identified with inverse temperature, and low temperatures are achieved through the limit β → ∞. In this paper, we derive statistics for low-temperature random matrices at the "soft edge," which describes the extreme eigenvalues for many random matrix distributions. Specifically, new asymptotics are found for the expected value and standard deviation of the general-β Tracy-Widom distribution. The new techniques utilize beta ensembles, stochastic differential operators, and Riccati diffusions. The asymptotics fit known high-temperature statistics curiously well and contribute to the larger program of general-β random matrix theory. Computing with Beta Ensembles and Hypergeometric Functions Drensky, V., Edelman, A., Genoar, K., Kan, R., & Koev, P. (2014). RMTA. PDF Eigenvalue distributions of Beta-Wishart matrices Edelman, A., & Koev, P. (2014). Random Matrices: Theory and Applications, 3(02), 1450009. PDFAbstract Abstract: We derive explicit expressions for the distributions of the extreme eigenvalues of the beta-Wishart random matrices in terms of the hypergeometric function of a matrix argument. These results generalize the classical results for the real (β = 1), complex (β = 2), and quaternion (β = 4) Wishart matrices to any β > 0. Random Matrix Theory and its Innovative Applications Edelman, A., & Wang, Y. (2013). In Advances in Applied Mathematics, Modeling, and Computational Science (pp. 91-116). Springer US. PDFAbstract Abstract: Recently more and more disciplines of science and engineering have found Random Matrix Theory valuable. Some disciplines use the limiting densities to indicate the cutoff between "noise" and "signal." Other disciplines are finding eigenvalue repulsions a compelling model of reality. This survey introduces both the theory behind these applications and MATLAB experiments allowing a reader immediate access to the ideas The beta-Wishart ensemble Dubbs, A., Edelman, A., Koev, P., & Venkataramana, P. (2013). Journal of Mathematical Physics, 54(8), 083507. PDFarXivAbstract Abstract: This paper proves a matrix model for the Wishart Ensemble with general covariance and general dimension parameter beta. In so doing, we introduce a new and elegant definition of Jack polynomials. Isotropic Entanglement Edelman, A., & Movassagh, R. (2010, revised 2012). Isotropic entanglement. arXiv preprint arXiv:1012.5039. PDFarXivAbstract Abstract: The method of "Isotropic Entanglement" (IE), inspired by Free Probability Theory and Random Matrix Theory, predicts the eigenvalue distribution of quantum many-body (spin) systems with generic interactions. At the heart is a "Slider", which interpolates between two extrema by matching fourth moments.The first extreme treats the non-commuting terms classically and the second treats them isotropically. Isotropic means that the eigenvectors are in generic positions. We prove Matching Three Moments and Slider Theorems and further prove that the interpolation is universal, i.e., independent of the choice of local terms. Our examples show that IE provides an accurate picture well beyond what one expects from the first four moments alone. Error Analysis of Free Probability Approximations to the Density of States of Disordered Systems Chen, J., Hontz, E., Moix, J., Welborn, M., Van Voorhis, T., Suárez, A., ... & Edelman, A. (2012). Physical review letters, 109(3), 036403. PDFarXivAbstract Abstract: Theoretical studies of localization, anomalous diffusion and ergodicity breaking require solving the electronic structure of disordered systems. We use free probability to approximate the ensemble- averaged density of states without exact diagonalization. We present an error analysis that quantifies the accuracy using a generalized moment expansion, allowing us to distinguish between different approximations. We identify an approximation that is accurate to the eighth moment across all noise strengths, and contrast this with the perturbation theory and isotropic entanglement theory. Condition Numbers of Indefinite Rank 2 Ghost Wishart Matrices Edelman, A., & Movassagh, R. (2015, October). Linear Algebra and its Applications, 483, 342-351. PDFarXivAbstract Abstract: We define an indefinite Wishart matrix as a matrix of the form $A=W^{T}W\Sigma$, where $\Sigma$ is an indefinite diagonal matrix and $W$ is a matrix of independent standard normals. We focus on the case where $W$ is $L$ by 2 which has engineering applications. We obtain the distribution of the ratio of the eigenvalues of $A$. This distribution can be "folded" to give the distribution of the condition number. We calculate formulas for $W$ real $(\beta=1)$, complex $(\beta=2)$, quaternionic $(\beta=4)$ or any ghost 0<$\beta$<$\infty$. We then corroborate our work by comparing them against numerical experiments. Random Triangle Theory with Geometry and Applications Edelman, A., & Strang, G. (2012). Foundations of Computational Mathematics, 15(3), 681-713.Accompanying Julia Notebook [html] [ipynb] PDFAbstract Abstract: What is the probability that a random triangle is acute? We explore this old question from a modern viewpoint, taking into account linear algebra, shape theory, numerical analysis, random matrix theory, the Hopf fibration, and much much more. One of the best distributions, all six vertex coordinates being independent standard Gaussians, can be reduced to four by translation of the center to (0, 0) or reformulation as a 2x2 random matrix problem.In this note, we develop shape theory in its historical context for a wide audience. We hope to encourage others to look again (and differently) at triangles.We provide a new constructive proof, using the geometry of parallelians, of a key result of shape theory: that triangle shapes naturally fall on a hemisphere. We give several proofs of uniformity when the normal distribution is transferred to the hemisphere, including a new proof related to the distribution of random condition numbers. Generalizing to higher dimensions, we obtain the “square root ellipticity statistic” of random matrix theory. Another proof connects the Hopf map to the SVD of 2 by 2 matrices. A new theorem decribes three similar triangles hidden in the hemisphere. Many triangle properties are reformulated as matrix theorems, providing insight to both. This paper argues for a shift of viewpoint to the modern approaches of random matrix theory.As one example, we propose that the smallest singular value is an effective test for uniformity. New software is developed and applications are proposed. Partial Freeness of Random Matrices Chen, J., Van Voorhis, T., & Edelman, A. (2012). arXiv preprint arXiv:1204.2257. PDFarXivAbstract Abstract: We investigate the implications of free probability for random matrices. From rules for calculating all possible joint moments of two free random matrices, we develop a notion of partial freeness which is quantified by the breakdown of these rules. We provide a combinatorial interpretation for partial freeness as the presence of closed paths in Hilbert space defined by particular joint moments. We also discuss how asymptotic moment expansions provide an error term on the density of states. We present MATLAB code for the calculation of moments and free cumulants of arbitrary random matrices. Density of States of Quantum Spin Systems from Isotropic Entanglement Edelman, A., & Movassagh, R. (2011). Physical review letters, 107(9), 097205. PDFarXivAbstract Abstract: We propose a method which we call "Isotropic Entanglement" (IE), that predicts the eigenvalue distribution of quantum many body (spin) systems (QMBS) with generic interactions. We interpolate between two known approximations by matching fourth moments. Though, such problems can be QMA-complete, our examples show that IE provides an accurate picture of the spectra well beyond what one expects from the first four moments alone. We further show that the interpolation is universal, i.e., independent of the choice of local terms. The Random Matrix Technique of Ghosts and Shadows Edelman, A. (2010). Markov Processes and Related Fields, 16(4), 783-790. PDF Sturm Sequences and Random Eigenvalue distributions Albrecht, J. T., Chan, C. P., & Edelman, A. (2009). Foundations of Computational Mathematics, 9(4), 461-483. PDFAbstract Abstract: This paper proposes that the study of Sturm sequences is invaluable in the numerical computation and theoretical derivation of eigenvalue distributions of random matrix ensembles. We first explore the use of Sturm sequences to efficiently compute histograms of eigenvalues for symmetric tridiagonal matrices and apply these ideas to random matrix ensembles such as the β-Hermite ensemble. Using our techniques, we reduce the time to compute a histogram of the eigenvalues of such a matrix from O(n 2+m) to 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 (m is usually much smaller than n). Second, we derive analytic formulas in terms of iterated multivariate integrals for the eigenvalue distribution and the largest eigenvalue distribution for arbitrary symmetric tridiagonal random matrix models. As an example of the utility of this approach, we give a derivation of both distributions for the β-Hermite random matrix ensemble (for general β). Third, we explore the relationship between the Sturm sequence of a random matrix and its shooting eigenvectors. We show using Sturm sequences that assuming the eigenvector contains no zeros, the number of sign changes in a shooting eigenvector of parameter λ is equal to the number of eigenvalues greater than λ. Finally, we use the techniques presented in the first section to experimentally demonstrate a O(log n) growth relationship between the variance of histogram bin values and the order of the β-Hermite matrix ensemble. Statistical eigen-inference from large Wishart Matrices Rao, N. R., Mingo, J. A., Speicher, R., & Edelman, A. (2008). The Annals of Statistics, 2850-2885. PDFarXivAbstract Abstract: We consider settings where the observations are drawn from a zero-mean multivariate (real or complex) normal distribution with the population covariance matrix having eigenvalues of arbitrary multiplicity. We assume that the eigenvectors of the population covariance matrix are unknown and focus on inferential procedures that are based on the sample eigenvalues alone (i.e., "eigen-inference"). Results found in the literature establish the asymptotic normality of the fluctuation in the trace of powers of the sample covariance matrix. We develop concrete algorithms for analytically computing the limiting quantities and the covariance of the fluctuations. We exploit the asymptotic normality of the trace of powers of the sample covariance matrix to develop eigenvalue-based procedures for testing and estimation. Specifically, we formulate a simple test of hypotheses for the population eigenvalues and a technique for estimating the population eigenvalues in settings where the cumulative distribution function of the (nonrandom) population eigenvalues has a staircase structure. Monte Carlo simulations are used to demonstrate the superiority of the proposed methodologies over classical techniques and the robustness of the proposed techniques in high-dimensional, (relatively) small sample size settings. The improved performance results from the fact that the proposed inference procedures are "global" (in a sense that we describe) and exploit "global" information thereby overcoming the inherent biases that cripple classical inference procedures which are "local" and rely on "local" information. The Polynomial Method for Random Matrices Rao, N. R., & Edelman, A. (2008). Foundations of Computational Mathematics, 8(6), 649-702. PDFarXivAbstract Abstract: We define a class of "algebraic" random matrices. These are random matrices for which the Stieltjes transform of the limiting eigenvalue distribution function is algebraic, i.e., it satisfies a (bivariate) polynomial equation. The Wigner and Wishart matrices whose limiting eigenvalue distributions are given by the semi-circle law and the Marcenko-Pastur law are special cases. Algebraicity of a random matrix sequence is shown to act as a certificate of the computability of the limiting eigenvalue density function. The limiting moments of algebraic random matrix sequences, when they exist, are shown to satisfy a finite depth linear recursion so that they may often be efficiently enumerated in closed form. In this article, we develop the mathematics of the polynomial method which allows us to describe the class of algebraic matrices by its generators and map the constructive approach we employ when proving algebraicity into a software implementation that is available for download in the form of the RMTool random matrix "calculator" package. Our characterization of the closure of algebraic probability distributions under free additive and multiplicative convolution operations allows us to simultaneously establish a framework for computational (non-commutative) "free probability" theory. We hope that the tools developed allow researchers to finally harness the power of the infinite random matrix theory. On Computing Schur Functions and Series Thereof Chan, C., Drensky, V., Edelman, A., Kan, R., & Koev, P. (2008). preprint. PDF The beta-Jacobi matrix model, the CS decomposition, and generalized singular value problems Edelman, A., & Sutton, B. D. (2008). Foundations of Computational Mathematics, 8(2), 259-285. PDF Sample eigenvalue based detection of high-dimensional signals in white noise using relatively few samples Nadakuditi, R. R., & Edelman, A. (2008). Signal Processing, IEEE Transactions on, 56(7), 2625-2638. PDFarXivAbstract Abstract: We present a mathematically justifiable, computationally simple, sample eigenvalue based procedure for estimating the number of high-dimensional signals in white noise using relatively few samples. The main motivation for considering a sample eigenvalue based scheme is the computational simplicity and the robustness to eigenvector modelling errors which are can adversely impact the performance of estimators that exploit information in the sample eigenvectors. There is, however, a price we pay by discarding the information in the sample eigenvectors; we highlight a fundamental asymptotic limit of sample eigenvalue based detection of weak/closely spaced high-dimensional signals from a limited sample size. This motivates our heuristic definition of the effective number of identifiable signals which is equal to the number of "signal" eigenvalues of the population covariance matrix which exceed the noise variance by a factor strictly greater than 1+sqrt(Dimensionality of the system/Sample size). The fundamental asymptotic limit brings into sharp focus why, when there are too few samples available so that the effective number of signals is less than the actual number of signals, underestimation of the model order is unavoidable (in an asymptotic sense) when using any sample eigenvalue based detection scheme, including the one proposed herein. The analysis reveals why adding more sensors can only exacerbate the situation. Numerical simulations are used to demonstrate that the proposed estimator consistently estimates the true number of signals in the dimension fixed, large sample size limit and the effective number of identifiable signals in the large dimension, large sample size limit. Sample Size Cognizant Detection of Signals in White Noise Nadakuditi, R. R., & Edelman, A. (2007, June). In Signal Processing Advances in Wireless Communications, 2007. SPAWC 2007. IEEE 8th Workshop on (pp. 1-5). IEEE. PDFarXivAbstract Abstract: The detection and estimation of signals in noisy, limited data is a problem of interest to many scientific and engineering communities. We present a computationally simple, sample eigenvalue based procedure for estimating the number of high-dimensional signals in white noise when there are relatively few samples. We highlight a fundamental asymptotic limit of sample eigenvalue based detection of weak high-dimensional signals from a limited sample size and discuss its implication for the detection of two closely spaced signals. This motivates our heuristic definition of the 'effective number of identifiable signals.' Numerical simulations are used to demonstrate the consistency of the algorithm with respect to the effective number of signals and the superior performance of the algorithm with respect to Wax and Kailath's "asymptotically consistent" MDL based estimator. From Random Matrices to Stochastic Operators Edelman, A., & Sutton, B. D. (2007). Journal of Statistical Physics, 127(6), 1121-1165. PDFarXivAbstract Abstract: We propose that classical random matrix models are properly viewed as finite difference schemes for stochastic differential operators. Three particular stochastic operators commonly arise, each associated with a familiar class of local eigenvalue behavior. The stochastic Airy operator displays soft edge behavior, associated with the Airy kernel. The stochastic Bessel operator displays hard edge behavior, associated with the Bessel kernel. The article concludes with suggestions for a stochastic sine operator, which would display bulk behavior, associated with the sine kernel. MOPS: Multivariate Orthogonal Polynomials (symbolically) Dumitriu, I., Edelman, A., & Shuman, G. (2007). Journal of symbolic computation, 42(6), 587-620. PDFarXivAbstract Abstract: In this paper we present a Maple library (MOPs) for computing Jack, Hermite, Laguerre, and Jacobi multivariate polynomials, as well as eigenvalue statistics for the Hermite, Laguerre, and Jacobi ensembles of Random Matrix theory. We also compute multivariate hypergeometric functions, and offer both symbolic and numerical evaluations for all these quantities. We prove that all algorithms are well-defined, analyze their complexity, and illustrate their performance in practice. Finally, we also present a few of the possible applications of this library. On the Largest Principal Angle between Random Subspaces Absil, P. A., Edelman, A., & Koev, P. (2006). Linear Algebra and its applications, 414(1), 288-294. PDFAbstract Abstract: Formulas are derived for the probability density function and the probability distribution function of the largest canonical angle between two p -dimensional subspaces of Rn chosen from the uniform distribution on the Grassmann manifold (which is the unique distribution invariant by orthogonal transformations of Rn). The formulas involve the gamma function and the hypergeometric function of a matrix argument. Global Spectrum Fluctuations for the beta-Hermite and beta-Laguerre ensembles via matrix models Dumitriu, I., & Edelman, A. (2006). Journal of Mathematical Physics, 47(6), 063302. PDFarXivAbstract Abstract: We study the global spectrum fluctuations for beta-Hermite and beta-Laguerre ensembles via the tridiagonal matrix models introduced in [11], and prove that the fluctuations describe a Gaussian process on monomials. We extend our results to slightly larger classes of random matrices. On the Efficient Evaluation of the Hypergeometric Function of a Matrix Argument Koev, P., & Edelman, A. (2006). Mathematics of Computation, 75(254), 833-846. PDFarXivAbstract Abstract: We present new algorithms that efficiently approximate the hypergeometric function of a matrix argument through its expansion as a series of Jack functions. Our algorithms exploit the combinatorial properties of the Jack function, and have complexity that is only linear in the size of the matrix. On the Probability Distribution of the Outputs of the Diagonally Loaded Capon-MVDR Processor Nadakuditi, R. R., & Edelman, A. (2005, October). In Signals, Systems and Computers, 2005. Conference Record of the Thirty-Ninth Asilomar Conference on (pp. 1717-1723). IEEE. Numerical Methods for Eigenvalue Distributions of Random Matrices Edelman, A., & Persson, P. O. (2005). arXiv preprint math-ph/0501068. PDFarXivAbstract Abstract: We present efficient numerical techniques for calculation of eigenvalue distributions of random matrices in the beta-ensembles. We compute histograms using direct simulations on very large matrices, by using tridiagonal matrices with appropriate simplifications. The distributions are also obtained by numerical solution of the Painleve II and V equations with high accuracy. For the spacings we show a technique based on the Prolate matrix and Richardson extrapolation, and we compare the distributions with the zeros of the Riemann zeta function. Tails of Condition Number Distributions Edelman, A., & Sutton, B. D. (2005). SIAM journal on matrix analysis and applications, 27(2), 547-560. PDFAbstract Abstract: Let $\kappa$ be the condition number of an m-by-n matrix with independent standard Gaussian entries, either real ($\beta = 1$) or complex ($\beta = 2$). The major result is the existence of a constant C (depending on m, n, and $\beta$) such that $P[\kappa > x] < C \, x^{-\beta}$ for all x. As $x \rightarrow \infty$, the bound is asymptotically tight. An analytic expression is given for the constant C, and simple estimates are given, one involving a Tracy--Widom largest eigenvalue distribution. All of the results extend beyond real and complex entries to general $\beta$. Eigenvalues of Hermite and Laguerre ensembles: Large Beta Asymptotics Dumitriu, I., & Edelman, A. (2005). In Annales de l'IHP Probabilités et statistiques, 41(6), 1083-1099. PDFarXivAbstract Abstract: In this paper we examine the zero and first order eigenvalue fluctuations for the $\beta$-Hermite and $\beta$-Laguerre ensembles, using the matrix models we described in [5], in the limit as $\beta \to \infty$. We find that the fluctuations are described by Gaussians of variance $O(1/\beta)$, centered at the roots of a corresponding Hermite (Laguerre) polynomial. We also show that the approximation is very good, even for small values of $\beta$, by plotting exact level densities versus sum of Gaussians approximations. Matrix Models for Beta Ensembles Dumitriu, I., & Edelman E. (2002). Journal of Mathematical Physics, 43, 5830--5847. PDFarXivAbstract Abstract: This paper constructs tridiagonal random matrix models for general ($\beta>0$) $\beta$-Hermite (Gaussian) and $\beta$-Laguerre (Wishart) ensembles. These generalize the well-known Gaussian and Wishart models for $\beta = 1,2,4$. Furthermore, in the cases of the $\beta$-Laguerre ensembles, we eliminate the exponent quantization present in the previously known models. We further discuss applications for the new matrix models, and present some open problems. How many zeros of a random polynomial are real? Edelman, A., & Kostlan, E. (1995). Bulletin of the American Mathematical Society, 32(1), 1-37. PDFarXivAbstract Abstract: We give an elementary derivation of the Kac integral formula for the expected number of real roots of a random polynomial with independent standard normally distributed coefficients. We show that the expected number of real roots is the length of the moment curve $(1,t,\ldots,t^n)$ projected onto the surface of the unit sphere, divided by $\pi$. The density of the root is proportional to how fast this curve is traced out. We generalize the Kac formula to polynomials with coefficients that have an arbitrary multivariate normal distribution. We show, for example, that for a particularly nice definition of random polynomial, the expected number of real roots is exactly the square root of the degree.When the random polynomials have an arbitrary density function, we express the expected number of roots as a weighted length of the curve. We also calculate the the distribution of the real zeros of random power series and Fourier series, random sums of orthogonal polynomials, and random Dirichlet series. On the determinant of a uniformly distributed complex matrix Edelman, A. (1995). Journal of Complexity, 11(3), 352-357. PDF How many eigenvalues of a random matrix are real? Edelman, A., Kostlan, E., & Shub, M. (1994). Journal of the American Mathematical Society, 7(1), 247-267. PDFAbstract Abstract: Let $A$ be an $n \times n$ matrix whose elements are independent random variables with standard normal distributions. As $n \to \infty$, the expected number of real eigenvalues is asymptotic to $\sqrt {2n/\pi }$. We obtain a closed form expression for the expected number of real eigenvalues for finite $n$, and a formula for the density of a real eigenvalue for finite $n$. Asymptotically, a real normalized eigenvalue $\lambda /\sqrt n$ of such a random matrix is uniformly distributed on the interval [-1, 1]. Analogous, but strikingly different, results are presented for the real generalized eigenvalues. We report on numerical experiments confirming these results and suggesting that the assumption of normality is not important for the asymptotic results. The road from Kac's matrix to Kac's random polynomials Edelman, A. & Kostlan, E. (1994). Proceedings of the 1994 SIAM Applied Linear Algebra Conference J.G. Lewis, ed., SIAM, Philadelphia, 503--507 PDF Eigenvalue Roulette and Random Test Matrices Edelman, A. (1993). In Linear Algebra for Large Scale and Real-Time Applications (pp. 365-368). Springer Netherlands. PDFAbstract Abstract: Random matrices may not be mentioned in research abstracts, but second only to Matlab, the most widely used tool of numerical linear algebraists is the “random test matrix.” Algorithmic developers in need of guinea pigs nearly always take random matrices with standard normal entries or perhaps close cousins, such as the uniform distribution on [-1,1]. The choice is highly reasonable: these matrices are generated effortlessly and might very well catch programming errors. What is a mistake is to psychologically link a random matrix with the intuitive notion of a "typical" matrix or the vague concept of "any old matrix." The Circular Law and the Probability that a Random Matrix Has $k$ Real Eigenvalues Edelman, A. (1993). preprint. PDFAbstract Abstract: Let $A$ be an $n$ by $n$ matrix whose elements are independent random variables with standard normal distributions. Girko's controversial circular law states that the distribution of appropriately normalized eigenvalues is asymptotically uniform in the unit disk in the complex plane. We derive the exact distribution of the complex eigenvalues for finite $n$, from which convergence in distribution to the circular law for normally distributed matrices may be derived. Similar methodology allows us to derive a joint distribution formula for the real Schur decomposition of $A$. Integration of this distribution yields the probability that $A$ has exactly $k$ real eigenvalues. For example, we show that the probability that $A$ has all real eigenvalues is exactly $2^{-n(n-1)/4}$. On the distribution of a scaled condition number Edelman, A. (1992). Mathematics of Computation, 58(197), 185-190. PDF The distribution and moments of the smallest eigenvalue of a random matrix of Wishart type Edelman, A. (1991). Linear algebra and its applications, 159, 55-80. Abstract Abstract: Given a random rectangular m × n matrix with elements from a normal distribution, what is the distribution of the smallest singular value? To pose an equivalent question in the language of multivariate statistics, what is the distribution of the smallest eigenvalue of a matrix from the central Wishart distribution in the null case? We give new results giving the distribution as a simple recursion. This includes the more difficult case when n – m is an even integer, without resorting to zonal polynomials and hypergeometric functions of matrix arguments. With the recursion, one can obtain exact expressions for the density and the moments of the distribution in terms of functions usually no more complicated than polynomials, exponentials, and at worst ordinary hypergeometric functions. We further elaborate on the special cases when n – m = 0, 1, 2, and 3 and give a numerical table of the expected values for 2 ⩽ m ⩽ 25 and 0 ⩽ n – m ⩽ 25. Eigenvalues and Condition Numbers of Random Matrices Edelman, A. (1989). MIT PhD Dissertation(4).(As of 2002, the figures are now included in this file. They were all recomputed!) PDF Eigenvalues and condition numbers of random matrices Edelman, A. (1988). SIAM Journal on Matrix Analysis and Applications, 9(4), 543-560. PDFAbstract Abstract: Given a random matrix, what condition number should be expected? This paper presents a proof that for real or complex $n \times n$ matrices with elements from a standard normal distribution, the expected value of the log of the 2-norm condition number is asymptotic to $\log n$ as $n \to \infty$. In fact, it is roughly $\log n + 1.537$ for real matrices and $\log n + 0.982$ for complex matrices as $n \to \infty$. The paper discusses how the distributions of the condition numbers behave for large n for real or complex and square or rectangular matrices. The exact distributions of the condition numbers of $2 \times n$ matrices are also given.Intimately related to this problem is the distribution of the eigenvalues of Wishart matrices. This paper studies in depth the largest and smallest eigenvalues, giving exact distributions in some cases. It also describes the behavior of all the eigenvalues, giving an exact formula for the expected characteristic polynomial. A linear-time algorithm for evaluating series of Schur functions Chan, C., Drensky, V., Edelman, A., & Koev, P. preprint PDF

Parallel Computing

 Pascal Matrices Edelman, A., & Strang, G. (2004). American Mathematical Monthly, 189-197. PDF Staircase failures explained by orthogonal versal forms Edelman, A., & Ma, Y. (2000). SIAM Journal on Matrix Analysis and Applications, 21(3), 1004-1025. PDFAbstract Abstract: Treating matrices as points in n2 -dimensional space, we apply geometry to study and explain algorithms for the numerical determination of the Jordan structure of a matrix. Traditional notions such as sensitivity of subspaces are replaced with angles between tangent spaces of manifolds in n2 -dimensional space. We show that the subspace sensitivity is associated with a small angle between complementary subspaces of a tangent space on a manifold in n2 -dimensional space. We further show that staircase algorithm failure is related to a small angle between what we call staircase invariant space and this tangent space. The matrix notions in n2 -dimensional space are generalized to pencils in 2mn-dimensional space. We apply our theory to special examples studied by Boley, Demmel, and Kågström. A Geometric Approach to Perturbation Theory of Matrices and Matrix Pencils. Part II: A Stratification Enhanced Staircase Algorithm Edelman, A., Elmroth, E., & Kågström, B. (1999). SIAM Journal on Matrix Analysis and Applications, 20(3), 667-699. PDFAbstract Abstract: Computing the Jordan form of a matrix or the Kronecker structure of a pencil is a well-known ill-posed problem. We propose that knowledge of the closure relations, i.e., the stratification, of the orbits and bundles of the various forms may be applied in the staircase algorithm. Here we discuss and complete the mathematical theory of these relationships and show how they may be applied to the staircase algorithm. This paper is a continuation of our Part I paper on versal deformations, but it may also be read independently. The Computation and Sensitivity of Double Eigenvalues Lippert, R. A., & Edelman, A. (1999). Advances in Computational Mathematics, Lecture Notes in Pure and Appl. Math, 202, 353-393. PDF A Counterexample to a Hadamard Matrix Pivot Conjecture Edelman, A., & Friendman, D. (1998). Linear and Multilinear Algebra, 44(1), 53-56. Abstract Abstract: In the study of the growth factor of completely pivoted Hadamard matrices, it becomes natural to study the possible pivots. Very little is known or provable about these pivots other than a few cases at the beginning and end. For example it is known that the first four pivots must be 1,2,2 and 4 and the last three pivots in backwards order must be n/2, and n/2. Based on computational experiments, it was conjectured by Day and Peterson, that the n—3rd pivot must always be n/4. This conjecture would have suggested a kind of symmetry with the first four pivots. In this note we demonstrate a matrix whose n–3rd pivot is n/2 showing that the conjecture is false. Non-generic eigenvalue perturbations of Jordan blocks Ma, Y., & Edelman, A. (1998). Linear algebra and its applications, 273(1), 45-63. PDFAbstract Abstract: We show that if an n × n Jordan block is perturbed by an O(ε) upper k-Hessenberg matrix (k subdiagonals including the main diagonal), then generically the eigenvalues split into p rings of size k and one of size r (if r ≠ 0), where n = pk + r. This generalizes the familiar result (k = n, p = 1, r = 0) that generically the eigenvalues split into a ring of size n. We compute the radii of the rings to first order and generalize the result in a number of directions involving multiple Jordan blocks of the same size. A Geometric Approach to Perturbation Theory of Matrices and Matrix Pencils. Part I: Versal Deformation Edelman, A., Elmroth, E., & Kågström, B. (1997). SIAM Journal on Matrix Analysis and Applications, 18(3), 653-692. Abstract Abstract: Computing the Jordan form of a matrix or the Kronecker structure of a pencil is a well-known ill-posed problem. We propose that knowledge of the closure relations, i.e., the stratification, of the orbits and bundles of the various forms may be applied in the staircase algorithm. Here we discuss and complete the mathematical theory of these relationships and show how they may be applied to the staircase algorithm. This paper is a continuation of our Part I paper on versal deformations, but may also be read independently. Polynomial roots from companion matrix eigenvalues Edelman, A., & Murakami, H. (1995). Mathematics of Computation, 64(210), 763-776. PDFAbstract Abstract: In classical linear algebra, the eigenvalues of a matrix are sometimes defined as the roots of the characteristic polynomial. An algorithm to compute the roots of a polynomial by computing the eigenvalues of the corresponding companion matrix turns the tables on the usual definition. We derive a first-order error analysis of this algorithm that sheds light on both the underlying geometry of the problem as well as the numerical error of the algorithm. Our error analysis expands on work by Van Dooren and Dewilde in that it states that the algorithm is backward normwise stable in a sense that must be defined carefully. Regarding the stronger concept of a small componentwise backward error, our analysis predicts a small such error on a test suite of eight random polynomials suggested by Toh and Trefethen. However, we construct examples for which a small componentwise relative backward error is neither predicted nor obtained in practice. We extend our results to polynomial matrices, where the result is essentially the same, but the geometry becomes more complicated. On the complete pivoting conjecture for a Hadamard matrix of order 12 Edelman, A., & Mascarenhas, W. (1995). Linear and Multilinear Algebra, 38(3), 181-187. PDFAbstract Abstract: This paper settles a conjecture by Day and Peterson that if Gaussian elimination with complete pivoting is performed on a 12 by 12 Hadamard matrix, then (1,2,2,4,3,10/3,18/5,4,3,6,6,12) must be the (absolute) pivots. Our proof uses the idea of symmetric block designs to reduce the complexity that would be found in enumerating cases.In contrast, at least 30 patterns for the absolute values of the pivots have been observed for 16 by 16 Hadamard matrices. This problem is non-trivial because row and column permutations do not preserve pivots. A naive computer search would require (12!)2 trials. The dimension of matrices (matrix pencils) with given Jordan (Kronecker) canonical forms Demmel, J. W., & Edelman, A. (1995). Linear algebra and its applications, 230, 61-87. PDFAbstract Abstract: The set of $n$ by $n$ matrices with a given Jordan canonical form defines a subset of matrices in complex $n^2$ dimensional space. We analyze one classical approach and one new approach to count the dimension of this set. The new approach is based upon and meant to give insight into the staircase algorithm for the computation of the Jordan Canonical Form as well as the occasional failures of this algorithm. We extend both techniques to count the dimension of the more complicated set defined by the Kronecker canonical form of an arbitrary rectangular matrix pencil $A-\lambda B$. On Parlett's matrix norm inequality for the Cholesky decomposition Edelman, A., & Mascarenhas, W. F. (1995). Numerical linear algebra with applications, 2(3), 243-250. PDFAbstract Abstract: We show that a certain matrix norm ratio studied by Parlett has a supermum that is O(equation image) when the chosen norm is the Frobenius norm, while it is O(log n) for the 2-norm. This ratio arises in Parlett's analysis of the Cholesky decomposition of an n by n matrix. A simple estimate of the condition number of a linear system Guggenheimer, H. W., Edelman, A. S., & Johnson, C. R. (1995). College Mathematics Journal, 2-5. Scaling for orthogonality Edelman, A., & Stewart, G. W. (1993). Signal Processing, IEEE Transactions on, 41(4), 1676-1677. PDFAbstract Abstract: In updating algorithms where orthogonal transformations are accumulated, it is important to preserve the orthogonality of the product in the presence of rounding error. Moonen et al. (ibid., vol.39, p.1911-13, 1991) have pointed out that simply normalizing the columns of the product tends to preserve orthogonality-though not, as DeGroat (ibid., vol.39, p.1913-14, 1991) points out, to working precision. The authors discuss the previous work and give an analysis of the phenomenon. The complete pivoting conjecture for Gaussian Elimination is false Edelman, A. (1992). Mathematica Journal, 2(2), 58-61. PDF Snapshots of Mobile Jacobi Edelman, A. (1991). In Numerical Linear Algebra, Digital Signal Processing and Parallel Algorithms (pp. 485-488). Springer Berlin Heidelberg.(What a shame that I do not have the pictures available. Even better would be to put the original video on line. Maybe some day!) PDF