Various explicit parametrized formulas are available for constructing orthogonal matrices. To construct a random orthogonal matrix we can take such a formula and assign random values to the parameters. For example, a Householder matrix is orthogonal and symmetric and we can choose the nonzero vector randomly. Such an example is rather special, though, as it is a rank- perturbation of the identity matrix.
What is usually meant by a random orthogonal matrix is a matrix distributed according to the Haar measure over the group of orthogonal matrices. The Haar measure provides a uniform distribution over the orthogonal matrices. Indeed it is invariant under multiplication on the left and the right by orthogonal matrices: if is from the Haar distribution then so is for any orthogonal (possibly non-random) and . A random Householder matrix is not Haar distributed.
A matrix from the Haar distribution can be generated as the orthogonal factor in the QR factorization of a random matrix with elements from the standard normal distribution (mean , variance ). In MATLAB this is done by the code
[Q,R] = qr(randn(n)); Q = Q*diag(sign(diag(R)));
[Q,R] = qr(randn(n)), which returns the orthogonal factor , is not enough on its own to give a Haar distributed matrix, because the QR factorization is not unique. The second line adjusts the signs so that is from the unique factorization in which the triangular factor has nonnegative diagonal elements. This construction requires flops.
A more efficient construction is possible, as suggested by Stewart (1980). Let be an -vector of elements from the standard normal distribution and let be the Householder matrix that reduces to , where is the first unit vector. Then is Haar distributed, where , , and . This construction expresses as the product of Householder matrices of growing effective dimension, and the product can be formed from right to left in flops. The MATLAB statement
Q = gallery('qmult',n) carries out this construction.
A similar construction can be made using Givens rotations (Anderson et al., 1987).
Orthogonal matrices from the Haar distribution can also be formed as , where the elements of are from the standard normal distribution. This is the orthogonal factor in the polar decomposition (where is symmetric positive semidefinite).
Random orthogonal matrices arise in a variety of applications, including Monte Carlo simulation, random matrix theory, machine learning, and the construction of test matrices with known eigenvalues or singular values.
All these ideas extend to random unitary (complex) matrices. In MATLAB, Haar distributed unitary matrices can be constructed by the code
[Q,R] = qr(complex(randn(n),randn(n))); Q = Q*diag(sign(diag(R)));
This code exploits the fact that the factor computed by MATLAB has real diagonal entries. If the diagonal of were complex then this code would need to be modified to use the complex sign function given by .
This is a minimal set of references, which contain further useful references within.
- T. W. Anderson, I. Olkin and L. G. Underhill, Generation of random orthogonal matrices, SIAM J. Sci. Statist. Comput. 8(4), 625–629, 1987.
- Alan Edelman and N. Raj Rao, Random matrix theory, Acta Numerica, 14, 233–297, 2005.
- Nicholas J. Higham, Accuracy and Stability of Numerical Algorithms, second edition, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2002. (Chapter 28.)
- Francesco Mezzadri, How to generate random matrices from the classical compact groups, Notices Amer. Math. Soc. 54(5), 592–604, 2007
- G. W. Stewart, The efficient generation of random orthogonal matrices with an application to condition estimators, SIAM J. Numer. Anal. 17(3), 403–409, 1980.
Related Blog Posts
This article is part of the “What Is” series, available from https://nhigham.com/category/what-is and in PDF form from the GitHub repository https://github.com/higham/what-is.