= Solution
Use <Haar sampling by Gaussian QR decomposition>:
* Generate an $n$-by-$n$ real <matrix> $G$ with <independent> entries having the <standard normal distribution>.
* Compute a <QR decomposition> $G=Q_0R_0$ with $Q_0$ an <orthogonal matrix> and $R_0$ an <upper triangular matrix>.
* Put $S=\operatorname{diag}(\operatorname{sgn}(R_{0,11}),\ldots,\operatorname{sgn}(R_{0,nn}))$ and return $\boxed{M=Q_0S}$. Then $G=MR$ with $R=SR_0$ having strictly positive diagonal.
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^{-\lVert x\rVert^2/2}$, so <orthogonal transformations> preserve its <probability distribution>. Column <independence> therefore gives $HG\overset{\mathrm d}=G$.
The <QR decomposition> with positive diagonal is unique: if $G=Q_1R_1=Q_2R_2$, then $Q_2^TQ_1=R_2R_1^{-1}$ is both an <orthogonal matrix> and an <upper triangular matrix>, hence diagonal with entries $\pm1$. Its diagonal entries are positive, so it is the identity. It follows that the orthogonal factor of $HG=HMR$ is $HM$. Therefore
$$
\boxed{HM\overset{\mathrm d}=M\quad\text{for every }H\in O(n).}
$$
By 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.
Back to article page
