# Intuition for Haar measure of random matrix

What is an intuitive way to understand Haar measure as defined for random matrices, say, $N\times N$ orthogonal or unitary matrices?

My understanding for what Haar measure means for $U(1)$ is that it can be thought of as a measure over a uniform distribution of phases on a circle, i.e. a matrix representing $M \in U(1)$ can be parameterized with an angle $\theta$ so that $$d\mu(M) = \frac {d\theta}{2\pi}$$

What is a correct generalization of this intuition to $N>1$? In particular, are there any explicit parameterizations of Haar measure that resemble writing down angles that are uniformly distributed?

One possibility that came to mind is that eigenvectors, rows and/or columns have (generalized) phases that can be thought of as direction angles that are in some sense uniform over $SO(N)$ or $U(N)$? (Edit: seems like this would not be the case for rows and columns.)

Another possibility I have thought of is using Givens rotations to parameterize an orthogonal matrix using the resulting rotation angles that bring it to the identity matrix. Are there any known results about the distribution of the Givens angles? It would seem plausible that they could be uniformly distributed, but given that the Givens rotations are usually applied in a particular fashion to achieve diagonalization, that could introduce correlations that would result in nonuniformity.

(Caveat: I'm new to all this so I could very well be wrong about even trying to conceptualize such a question.)

• What do you mean by random? The rows of a matrix sampled from the Haar/uniform distribution on SO(N) will not, if I recall correctly, be independent. (Although they might be asymptotically independent in the large $N$ limit, I'm afraid I don't recall.) – Yemon Choi Sep 24 '11 at 23:54
• This question is rather incoherently phrased.... – Igor Rivin Sep 25 '11 at 8:24
• I have rewritten the question to try to make it more precise. Hopefully the second time round it will be more sensible. – Jiahao Chen Sep 25 '11 at 16:49

You want to think of the Haar measure $d\mu(U)$ as a way of measuring uniformity in the group $U(N)$ of unitary $N\times N$ matrices.

To form your intuition, consider $N=1$. You then have $U=e^{i\phi}$, with $0<\phi\leq 2\pi$ and $d\mu(U)=d\phi$ measures the perimeter of the unit circle. This is a uniform measure, because $d(\phi+\phi_0)=d\phi$ for any fixed phase shift $\phi_0$. You could write the requirement of uniformity in the form $d\mu(UU_0)=d\mu(U)$, with $U_0=e^{i\phi_0}$ the unitary matrix corresponding to the phase shift $\phi_0$.

Once your intuition is formed for $N=1$, you simply generalize to $N>1$ using the same definition of uniformity, $d\mu(UU_0)=d\mu(U)$ for any fixed $U_0\in U(N)$. For orthogonal (or symplectic) matrices you use the same definition of uniformity, with $U_0$ now restricted to the orthogonal or symplectic subgroup of $U(N).$

To explicitly write down the Haar measure $d\mu(U)$ in terms of the matrix elements of $U$ is only easily done for a few small values of $N$. (In particular, there is no relationship to random directions of rows or columns, as Yemon Choi pointed out.) You typically do not need such explicit expressions, since integrals with the Haar measure can be evaluated by using only the definition of uniformity.

In response to the follow-up question: If you wish to evaluate Haar-measure integrals of polynomials of matrix elements of $U$, you can use the socalled Weingarten functions.

http://en.wikipedia.org/wiki/Weingarten_function

Here is a Mathematica program to generate these,

http://arxiv.org/abs/1109.4244

If you need an explicit expression for the Haar measure, the steps to take are the following:

1) parameterize your matrix $U$ in terms of a set of real parameters $\{x_i\}$.

2) calculate the metric tensor $m_{ij}$, defined by $\sum_{ij}|dU_{ij}|^2 = \sum_{ij}m_{ij}dx_i dx_j$

3) obtain the Haar measure by equating $d\mu(U) = ($Det $m)^{1/2}\prod_i dx_i$

This is the general recipe. In practice, for many parameterizations the answer is in the literature. In particular, for the Haar measure in Euler angle parameterizations see:

http://arxiv.org/abs/math-ph/0205016

http://www.cft.edu.pl/~karol/pdf/ZK94.pdf

• This was helpful for me to understand the uniform property of Haar measure. In the context of your answer, I better understand my own question as really a question about how one can explicitly parameterize Haar measure. – Jiahao Chen Sep 25 '11 at 17:02
• I agree that integrating wrt Haar measure is usually simple in the sense that explicit expressions are not needed. However, it would be useful for me as a computational scientist to understand what is going on if I had to write it out explicitly. – Jiahao Chen Sep 25 '11 at 17:13

Dear Jiahao Chen, if you're interested in explicit expressions of the Haar measure you might want to look at the paper http://arxiv.org/abs/1103.3408 which contains simple parametrizations of U(N) and SU(N), as well as a formula of the normalized Haar measure for arbitrary N. This paper could be interesting for you as the provided framework can directly be applied to compute group integrals. Knowledge of the Weingarten functions is not required.

I like the following characterisation. Consider a continuous function $f:G\to\mathbb{R}$ (for any compact Lie group $G$) and the set $T=\{t_g(f): g\in G\}$ of translates of $f$, where $t_g(f)(x)=f(gx)$. Let $C$ be the closure of the convex hull of $T$. It can be shown that $C$ contains a unique constant function, and the value of that function is the inegral of $f$ with respect to Haar measure.

• Closure - in what topology ? If I take $G=S^1$ $f=sin(x)$, shifts are $sin(x+a)$... how to see what is convex hull ? – Alexander Chervov Jan 16 '12 at 19:53
• @AlexanderChervov, note that you don't need to see the convex hull of $T = \{\sin(x + a) \colon a \in S^1\}$; you just need to find the unique constant function that can be written as a limit of elements of $T$. From the definition of the Riemann integral, I think you should be able to prove that $F(x) = \tfrac{1}{2\pi} \int_0^{2\pi} \sin(x + a)\;da$ is a limit of convex combinations of elements of $T$ in the uniform topology. As expected, $F(x) = 0$. – Vectornaut Nov 15 '15 at 10:45

see the appendix of this paper for understanding Haar measure: Determinantal point processes in the plane from products of random matrices

intuition for Haar random orthogonal matrix: choose a vector randomly from the unit sphere in ${\mathbb R}^n$ (uniform distribution on the unit sphere). That's the first column. Now for the second column, choose a vector randomly from the unit sphere in the $n-1$ dimensional subspace orthogonal to the first column. Similarly for the third column, choose a vector randomly from the unit sphere in the $n-2$ dimensional subspace orthogonal to the first two columns...and so on....

• Could you please write in a less sloppy style, and use correct grammar and spelling? – Stefan Kohl Oct 6 '15 at 9:15

In MatLab I generate Haar distributed matrices like this:

m = randn(m,m)% all elements are normally distributed

u= qr(m) % make qr decomposition and what you get is Haar measure on "u"

So the math. statement is that if "m" is normally distributed, then "u" is Haar.

The reason is quite trivial - normal distribution is preserved by unitary transformations.

However righting this I begin to doubt myself about tiny details - depending how they implement qr algorithm the matrix u is not unique, it can be multiplied diag(+-1 ). Neverthelss most probably everything should be correct.

• This is not correct! Matlab's QR decomposition does not give you the Haar measure. See link to this related stackoverflow answer QR – g g Apr 28 at 11:26

Carlos Beenacker's answer is to the point, but there are more concrete constructions for $O(N)$ and related groups.

Haar on $O(N)$

Take a $N\times N$ matrix of i.i.d. standard Gaussian random variables. Think of the columns of this matrix as vector $X_1,\dots,X_N$. These vectors a.s. form a basis of $R^N$, and one can apply Gram-Schmidt to them to obtain an orthonormal basis $Y_1,\dots,Y_N$. I claim that the matrix U with columns given by the $Y$'s is distributed according to Haar measure over $O (N)$.

Proof sketch: One can check that the law of $U$ is left-invariant, meaning that, for any $R\in O (N)$, $U$ and $RU$ have the same distribution. Now let $V$ be an independent copy of $U^T$. One can see that the law of $V$ is right invariant and that $VU$ has the same law as both $V$ and $U$. Thus the laws of $U$ and $U^T$ coincide, and the law of $U$ is both left and right invariant. A similar argument shows that there can be onlyour one left-invariant (or right-invariant) distribution over $O (N)$.

Haar over $SO (N)$

Condition on the determinant of $U$ being one.

Haar over $U (N)$

Going back to the $O (N)$ we see that the same proof works if the $X_i$ are i.i.d., spherically symmetric vectors in $R^N$ with $X_1\neq 0$ a.s. . If one replaces $R^N$ with $C^N$ in the preceding sentence, and then does the same Gram-Schmidt procedure, one obtains a Haar distributed element of $U (N)$.

Remark

The basic idea in each case is that the the law of $Y_i$ should be uniform over the unit sphere of the orthogonal complement of the subspace generated by the $i-1$ previous vectors. But this is harder to implement directly.

We can understand Haar measure on orthogonal group more clearly if we treat it as a probability measure on orthogonal group and have a way to generate Haar distributed orthogonal random matrix. We can generate a $n \times n$ Haar distributed random orthogonal matrix in the following way:
we generate $n$ unit vectors one by one, as below, and arrange them as columns in the same order into a matrix to get a orthogonal matrix.
First column:- Generate a unit vector from uniform distribution on unit sphere in $\mathcal{R}^n$. Second column:- Generate a unit vector from uniform distribution on unit sphere in $n-1$ dimensional subspace orthogonal to first column. Third column :- Generate a unit vector from uniform distribution on unit sphere in $n-2$ dimensional subspace orthogonal to first and second columns. .......
$n$-th column:- Generate a unit vector from uniform distribution on unit sphere in $1$ dimensional subspace(let us say, generated by $u$) orthogonal to first $n-1$ columns. In fact, this last step in the algorithm amounts to choosing $u$ or $-u$ with equal probabilities.
algorithm will stop after we choose $n$-th column.