= Haar sampling by Gaussian QR decomposition
{c}
{title2=$Q(G)\sim\operatorname{Haar}(O(n))$}
Generate a real $n$-by-$n$ <matrix> $G$ with <independent> entries having the <standard normal distribution>. Take its <QR decomposition> with positive diagonal in the <upper triangular matrix> factor, $G=QR$. The <orthogonal matrix> $Q$ has normalized <Haar measure> on the full <orthogonal group> $O(n)$. If a numerical factorization returns $Q_0R_0$, set $S=\operatorname{diag}(\operatorname{sgn}R_{0,ii})$ and return $Q_0S$. The signs are nonzero <almost surely>: successively drawn <Gaussian> columns have <probability> zero of lying in the proper <linear subspace> spanned by earlier columns.
For correctness, every fixed <orthogonal matrix> $U$ preserves the standard <Gaussian> column density and column <independence>, so $UG$ and $G$ have the same <probability distribution>. The positive-diagonal <QR decomposition> is unique: two decompositions would give an <orthogonal matrix> that is also an <upper triangular matrix> with positive diagonal, hence the identity. Therefore $Q(UG)=UQ(G)$ and $Q(G)$ has a left-invariant probability law. Uniqueness of normalized <Haar measure> on the <compact group> $O(n)$ identifies that law. Each <determinant> sign has <probability> $1/2$ by reflection invariance.
Back to article page
