Past exam of the random matrix theory course of the University of Oxford / 2025 / 3 / d

Use Haar sampling by Gaussian QR decomposition:

The matrix $G$ is invertible almost surely. Indeed, successively sampled Gaussian columns have probability zero of lying in the proper linear subspace spanned by the previous columns. Thus the diagonal signs used above exist with probability one. Equivalently, apply the Gram-Schmidt process to the columns, always dividing each residual by its positive Euclidean norm; this produces $M$ directly.

To prove uniformity, fix $H\in O(n)$. Each column of $G$ has density proportional to $e^{-\Vert x{\Vert }^2/2}$, so orthogonal transformations preserve its probability distribution. Column independence therefore gives $HG\stackrel{\mathrm{d}}{=}G$.

The QR decomposition with positive diagonal is unique: if $G=Q_1{R}_1=Q_2{R}_2$, then $Q_2^T{Q}_1=R_2{R}_1^{-1}$ is both an orthogonal matrix and an upper triangular matrix, hence diagonal with entries $\pm 1$. Its diagonal entries are positive, so it is the identity. It follows that the orthogonal factor of $HG=HMR$ is $HM$. ThereforeBy uniqueness of normalized Haar measure on the compact group $O(n)$, the returned matrix has exactly the required probability distribution. Reflection invariance gives each determinant sign probability $1/2$, so the algorithm samples both components of the orthogonal group. The positive-diagonal correction is essential when a numerical QR decomposition chooses its own signs.