Sampling the eigenvalues of random orthogonal and unitary matrices

DOI10.1016/J.LAA.2021.02.031MaRDI QIDQ2020693zbMATH OpenOpenAlexFDO

Authors Massimiliano Fasi, Leonardo Robol

Publication date 24 April 2021

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2009.11515

zbMATH Keywords

eigenvalue samplingHaar distributionorthogonal matrixrandom matrixunitary matrix

Mathematics Subject Classification ID

Eigenvalues, singular values, and eigenvectors (15A18) Factorization of matrices (15A23) Orthogonal matrices (15B10) Random matrices (algebraic aspects) (15B52) Numerical computation of eigenvalues and eigenvectors of matrices (65F15)

Abstract: We develop an efficient algorithm for sampling the eigenvalues of random matrices distributed according to the Haar measure over the orthogonal or unitary group. Our technique samples directly a factorization of the Hessenberg form of such matrices, and then computes their eigenvalues with a tailored core-chasing algorithm. This approach requires a number of floating-point operations that is quadratic in the order of the matrix being sampled, and can be adapted to other matrix groups. In particular, we explain how it can be used to sample the Haar measure over the special orthogonal and unitary groups and the conditional probability distribution obtained by requiring the determinant of the sampled matrix be a given complex number on the complex unit circle.

Review text

The authors develop an efficient algorithm for sampling the eigenvalues of random matrices distributed according to the Haar measure over the orthogonal or unitary group. Their approach uses a technique of \textit{G. W. Stewart} [SIAM J. Numer. Anal. 17, 403--409 (1980; Zbl 0443.65027)] for sampling the upper Hessenberg form of Haar-distributed matrices, and an algorithm for computing the eigenvalues of an \(n\times n\) upper Hesenberg unitary or orthogonal matrix in \(O(n^2)\) flops. Using the unitary QR algorithm (a special case of a rootfinding algorithm of the second author and others [\textit{J. L. Aurentz} et al., SIAM J. Matrix Anal. Appl. 39, No. 3, 1245--1269 (2018; Zbl 1398.65056)]), their technique samples a factorization of the Hessenberg form and computes the eigenvalues with a core-chasing algorithm. The number of floating point operations required is quadratic in the order of the sampled matrix.

Recommendations

• Sampling unitary ensembles
• Algorithm and software for defining the distribution of eigenvalues of random symmetric matrices via simulation
• Generation of Random Orthogonal Matrices
• Distribution of eigenvalues and eigenvectors of orthogonal random matrices
• On the Eigenvalues of Random Matrices

Cites work

• A CMV-Based Eigensolver for Companion Matrices
• A divide and conquer method for unitary and orthogonal eigenproblems
• A unitary Hessenberg \(QR\)-based algorithm via semiseparable matrices
• An implementation of a divide and conquer algorithm for the unitary eigen problem
• Compression of unitary rank-structured matrices to CMV-like shape with an application to polynomial rootfinding
• Core-Chasing Algorithms for the Eigenvalue Problem
• Determinantal random point fields
• Developments in random matrix theory
• Eigenvalue distributions of large Hermitian matrices; Wigner's semi- circle law and a theorem of Kac, Murdock, and Szegö
• Fast and backward stable computation of roots of polynomials. II: Backward error analysis; companion matrix and companion pencil
• Fast and stable unitary QR algorithm
• Fast Hessenberg reduction of some rank structured matrices
• Five-diagonal matrices and zeros of orthogonal polynomials on the unit circle
• How to generate random matrices from the classical compact groups
• scientific article; zbMATH DE number 2187386 (Why is no real title available?)
• scientific article; zbMATH DE number 1012640 (Why is no real title available?)
• scientific article; zbMATH DE number 2003146 (Why is no real title available?)
• scientific article; zbMATH DE number 2174437 (Why is no real title available?)
• scientific article; zbMATH DE number 6159604 (Why is no real title available?)
• scientific article; zbMATH DE number 3060775 (Why is no real title available?)
• scientific article; zbMATH DE number 3069216 (Why is no real title available?)
• Isotropic distributions of test matrices
• Lie Groups, Lie Algebras, and Representations
• Log-gases and random matrices.
• Numerical inverting of matrices of high order
• On the Eigenvalues of Random Matrices
• Random matrix methods for wireless communications.
• Random matrix theory
• Random matrix theory, numerical computation and applications
• The Efficient Generation of Random Orthogonal Matrices with an Application to Condition Estimators
• The eigenvalues of random symmetric matrices
• The Matrix Eigenvalue Problem
• The QR algorithm for unitary Hessenberg matrices
• The Subgroup Algorithm for Generating Uniform Random Variables

Cited in

(10)

• Factorization, invariant measure, and random selection of matrices in SU(n) and other groups
• On spectral and numerical properties of random butterfly matrices
• How long does it take to compute the eigenvalues of a random symmetric matrix?
• Algorithm and software for defining the distribution of eigenvalues of random symmetric matrices via simulation
• scientific article; zbMATH DE number 1390107 (Why is no real title available?)
• Sampling unitary ensembles
• Random orthogonal matrix simulation
• A simple, randomized algorithm for diagonalizing normal matrices
• The eigenvalue decomposition of normal matrices by the skew-symmetric part
• Sturm sequences and random eigenvalue distributions

Describes a project that uses

Uses Software

• UDC

This page was built for publication: Sampling the eigenvalues of random orthogonal and unitary matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2020693)