# Sampling the eigenvalues of random orthogonal and unitary matrices

@article{Fasi2021SamplingTE, title={Sampling the eigenvalues of random orthogonal and unitary matrices}, author={Massimiliano Fasi and Leonardo Robol}, journal={ArXiv}, year={2021}, volume={abs/2009.11515} }

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… Expand

#### References

SHOWING 1-10 OF 55 REFERENCES

The Efficient Generation of Random Orthogonal Matrices with an Application to Condition Estimators

- Mathematics
- 1980

This paper presents a method for generating pseudo-random orthogonal matrices from the Haar distribution for the group of orthogonal matrices. The random matrices are expressed as products of $n - 1$… Expand

Eigenvalue distributions of large Hermitian matrices; Wigner's semi-circle law and a theorem of Kac, Murdock, and Szegö

- Mathematics
- 1984

Abstract Wigner's semi-circle law describes the eigenvalue distribution of certain large random Hermitian matrices. A new proof is given for the case of Gaussian matrices, that involves reducing a… Expand

A divide and conquer method for unitary and orthogonal eigenproblems

- Mathematics
- 1990

SummaryLetH∈ℂn xn be a unitary upper Hessenberg matrix whose eigenvalues, and possibly also eigenvectors, are to be determined. We describe how this eigenproblem can be solved by a divide and conquer… Expand

How to generate random matrices from the classical compact groups

- Mathematics, Physics
- 2006

We discuss how to generate random unitary matrices from the classical compact groups U(N), O(N) and USp(N) with probability distributions given by the respective invariant measures. The algorithm is… Expand

Compression of unitary rank-structured matrices to CMV-like shape with an application to polynomial rootfinding

- Computer Science, Mathematics
- J. Comput. Appl. Math.
- 2015

A Lanczos-type algorithm is presented which carries out the reduction of a unitary matrix U to CMV-like shape by computing the block tridiagonal form of the Hermitian part of U, i.e., of the matrix U + U H . Expand

Five-diagonal matrices and zeros of orthogonal polynomials on the unit circle

- Mathematics
- 2002

It is shown that monic orthogonal polynomials on the unit circle are the characteristic polynomials of certain five-diagonal matrices depending on the Schur parameters. This result is achieved… Expand

The QR algorithm for unitary Hessenberg matrices

- Mathematics
- 1986

Abstract Let H be an n × n unitary right Hessenberg matrix with positive subdiagonal elements. Using what we call the Schur parameterization of H , we show how one step of the shifted QR algorithm… Expand

A Matrix Eigenvalue Problem

- Mathematics
- 1979

Find scalars λ and vectors x = 0 for which Ax = λx The form of the matrix affects the way in which we solve this problem, and we also have variety as to what is to be found. • A symmetric and real… Expand

A unitary Hessenberg QR-based algorithm via semiseparable matrices

- Mathematics
- 2005

In this paper, we present a novel method for solving the unitary Hessenberg eigenvalue problem. In the first phase, an algorithm is designed to transform the unitary matrix into a… Expand

A CMV-Based Eigensolver for Companion Matrices

- Mathematics, Computer Science
- SIAM J. Matrix Anal. Appl.
- 2015

A fast and computationally simple structured QR iteration which computes the eigenvalues of a companion matrix of size $n$ in lower staircase form using O(n^2) flops and $O(n) memory storage. Expand