How to generate random matrices from the classical compact groups

1 Introduction

• Random Matrix Theory supports applications across many fields because large-dimensional spectral correlations depend on ensemble invariants and its techniques enable analytical computations.The paper lists applications from number theory and physics to statistics and engineering.Source: §1 · p. 1
• The article offers a method requiring only a few lines of code and explains the fairly general ideas behind it.Numerical simulation is sometimes needed even when analytical calculations are possible.Source: §1 · pp. 1–2
• The method covers U(N), O(N), and USp(2N) with their invariant measures, and also considers the COE and CSE circular ensembles.The appropriate ensemble is usually determined by the symmetries of the modeled problem.Source: §1 · p. 2
• Generating random unitary matrices correctly and stably is difficult because their entries are correlated, while technical accounts may be inaccessible to readers without specialist backgrounds.An explicit Euler-angle parameterization is discussed but is not considered equally efficient or convenient.Source: §1 · p. 2

2 Some examples and motivations

• When complicated dynamics resist explicit description, a finite but large random unitary matrix can serve as a model, with matrix space and probability distribution chosen to fit the system.Unitary evolution preserves the norm of a quantum state, as required by the probabilistic interpretation of quantum mechanics.Source: §2 · p. 3
• For a system invariant under time reversal and without other symmetries, the section identifies unitary symmetric matrices as the appropriate matrix space.The unitary symmetric matrices admit a factorization involving a unitary matrix and its transpose.Source: §2 · p. 3
• The COE is obtained from a unitary factorization that induces a uniform measure on the space of unitary symmetric matrices.The resulting measure is described as the unique probability distribution induced there by Haar measure.Source: §2 · pp. 3–4
• For a time-reversal-invariant system with half-integer spin, the section identifies the CSE with a subset of U(2N) and gives its measure by induction from Haar measure.The subset is isomorphic to a coset space involving USp(2N).Source: §2 · p. 4
• A Haar-unitary generator supplies the matrices needed for CUE, COE, and CSE, and Haar-random characteristic polynomials of matrices can model the Riemann zeta function and other L-functions.The paper notes that this modeling approach has contributed to progress in analytic number theory.Source: §2 · pp. 4–5

3 Haar measure and invariance

• The Ginibre ensemble consists of invertible complex matrices with independent, identically distributed standard normal complex entries.Its matrix density is normalized as a probability density, and its entries are statistically independent.Source: §3 · p. 5
• The Ginibre measure is invariant under left and right multiplication by arbitrary unitary matrices.The section introduces invariance because the later algorithm relies on Haar-measure invariance.Source: §3 · pp. 5–6
• Every compact Lie group has a unique left- and right-invariant measure, Haar measure; generating from it requires knowing its invariance and uniqueness, not an explicit coordinate formula.The section describes Haar measure as a natural probability measure after normalization.Source: §3 · p. 6
• A non-compact manifold does not admit an unbiased probability measure in the sense discussed here.A constant density can define a probability measure on a finite interval, but not on the whole real line.Source: §3 · p. 7

4 The QR decomposition and a numerical experiment

• Although Gram–Schmidt orthonormalization yields a unitary matrix from a full-rank input, its implementation is numerically unstable.The input entries are i.i.d. standard complex normal random variables.Source: §4 · p. 7
• Standard QR routines commonly use numerically stable Householder reflections rather than Gram–Schmidt orthonormalization.QR is widely available in standard linear algebra packages.Source: §4 · pp. 7–8
• Haar measure gives a uniform normalized eigenvalue density, but that does not imply that eigenvalues are statistically uncorrelated.The spacing distribution is also used to assess spectral correlations.Source: §4 · p. 8
• The eigenvalue-density and spacing histograms from 10,000 matrices generated by wrong_distribution(n) both deviate from the theoretical CUE predictions.Each matrix is 50×50.Source: §4 · p. 8

5 A correct and efficient algorithm

• QR factorization is not unique, so the choice of how its factors are selected determines whether the induced unitary distribution is Haar.The construction seeks a map compatible with left multiplication by unitary matrices.Source: §5 · pp. 8–10
• Choosing QR factors with positive real diagonal entries in R makes the factorization map obey the required left-unitary equivariance.The chosen representatives are obtained by fixing the phases of R’s diagonal entries.Source: §5 · p. 10
• The resulting factorization decomposes the Ginibre measure into Haar measure on the unitary factor and a measure on the right coset space.The factorization argument uses invariance and uniqueness of Haar measure.Source: §5 · pp. 10–11
• Standard QR routines do not satisfy the required equivariance, so their unitary factors are not Haar distributed.The recipe corrects this by adjusting the diagonal phases of R and applying the corresponding phases to Q.Source: §5 · p. 11
• The corrected routine’s eigenvalue-density and spacing histograms are consistent with theoretical CUE predictions.Figure 2 reports results from 10,000 50×50 unitary matrices produced by haar.Source: §5 · p. 11, Figure 2 · p. 12

6 The unitary symplectic group USp(2N)

• The quaternion symplectic group Sp(N) is isomorphic to the complex matrix group USp(2N).The paper establishes this using a complex representation of quaternion matrices.Source: §6 · p. 13
• The section transfers the unitary-group factorization argument to quaternion matrices, using the isomorphism to connect Sp(N) and USp(2N) Haar measures.The paper leaves proving the stated generalizations as an exercise.Source: §6 · pp. 13, 15
• Quaternion QR factorization yields a symplectic factor and an invertible upper-triangular quaternion factor.The paper constructs a one-to-one map from the factorization and states that it factorizes the quaternion Ginibre measure.Source: §6 · p. 15

7 Householder reflections

• Householder reflections build an orthogonal QR factorization by successively transforming a matrix into upper-triangular form.The method applies reflections to the first column and then to progressively smaller trailing vectors.Source: §7 · pp. 16–17
• Choosing the reflection sign to avoid cancellation reduces round-off risk and makes the diagonal entries of R positive.The implementation includes a factor of sgn(x1) in the reflection definition.Source: §7 · p. 18
• Computing Qw with Householder reflections takes O(N^2), compared with O(N^3) for Gram–Schmidt; explicitly computing Q still takes O(N^3).Generating all the reflections and successively applying them to w each require O(N^2) operations.Source: §7 · p. 19
• The reflection construction generalizes to U(N) and Sp(N) by changing the reflection definitions.The paper gives suitable forms for the unitary and quaternion cases.Source: §7 · p. 19

• The group-theoretic viewpoint addresses the QR approach's use of N^2 random numbers for O(N), whose dimension is N(N−1)/2.Source: §8 · p. 20
• The subgroup algorithm recursively combines uniform coset representatives with uniform elements of smaller subgroups to generate a uniform group element.Source: §8 · p. 20
• For O(N), independent uniform directions on S_{m−1} yield a product of Householder reflections distributed according to Haar measure.Source: §8 · p. 21
• Each normalized Gaussian vector is uniform on its sphere and independent of the other directions, supplying the inputs for the construction.Source: §8 · p. 21
• For O(N), the coset space O(N)/O(N−1) is isomorphic to S_{N−1}, whose points provide representatives for the recursive factorization.Source: §8 · p. 22
• The chosen Householder representatives are discontinuous at e1, although a randomly generated vector hits αe1 with probability zero.Source: §8 · p. 22