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

Abstract

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$ Householder transformations, which can be computed in $O(n^2 )$ time. The technique is used in an empirical study of two methods for estimating the condition number of a matrix.