# How can I generate a random walk on $U(n)$?

I asked this question here on math.SE: https://math.stackexchange.com/q/2250448/78169

I'm asking in the physics forum in order to get a different perspective, and also as I suspect it's likely that many physicists have encountered this topic in the past for modeling purposes.

I'm interested in generating a random walk on $U(n)$ using a computer: any references on this topic or related / requisite topics would be helpful. Specific suggestions that discuss the problem technically are welcome as well. Thank you!

I'm not looking for trivial random walks. For example, randomly alternating between $U$ and $−U$ would technically be a discrete random walk. I'd like to be able to generate a random walk that can access a dense subset of the group elements; and/or I'd like an analytical description of a continuous random walk (like a diffusion process / Brownian motion), and/or a way to simulate / approximate such a continuous process.

I also asked this related question on math.SE: https://math.stackexchange.com/q/2250455/78169

$\rightarrow$ Is there a relationship or connection between compact groups like $U(n)$ and manifolds like $S^{n−1}$ (unit sphere)? If so, what is it?

I am interested in simulating a random walk on unitary groups using a computer and am wondering if it bears any similarity to a random walk on a recognizable manifold like the unit sphere in some number of dimensions. More generally, I'm wondering if the group is isomorphic or in some way similar / analogous / related to such a manifold or geometric object.

• This might be completely naive, but couldn't you just use a generator for a random walk on a non-compact manifold, subdivide the manifold into copies representing your compact manifold, shift all copies until then overlap the central one and sum the probability distribution? Like if your (continuous) distribution looked like: 000011112223343322211110000, you could map copies like: 000|011|112|223|343|322|211|110|000, and sum them up? |11, 12, 11|
– Base
Apr 25 '17 at 22:59
• The most obvious strategy to me is to use the Lie algebra of U(n). For any nxn hermitian matrix X and a unitary $U$, $U' = e^{iX}U$ is again a unitary matrix, and if $X$ is small (measured by operator norm, I think), then $U'$ is topologically close to $U$. Generating a random walk is then a problem of generating random sequences of small hermitian matrices, and also computing $e^{iX}$. Apr 26 '17 at 2:45
• @LukePritchett you could also simply design a random walk in the space of hermitian matrices (should be easy), and exponentiate it at all points -- the "closeness" of the points on the two paths should be preserved. Apr 26 '17 at 10:12
• @GrahamReid, I have to admit I'm having trouble following your suggestion. Which non-compact manifold would it be easier to simulate a random walk on, and how would it be subdivided into copies of a compact manifold like U(n)? Apr 26 '17 at 19:07

The answer for this problem is given by Francesco Mezzadri for all classical compact groups. (I have mentioned that in my answer to a similar question on Mathoverflow)

For $U(N)$ and $O(N)$, the answer is very simple based on the QR decomposition with a little extra care due to the non-uniqueness of the QR decomposition.

The algorithm for $U(N)$ is given in the article is quite simple

1. Start from a GL(N) matrix with random independent Gaussian identically distributed entries (i.e., disqualify cases where the determinant happens to be zero).

2. Perform a QR decomposition.

3. For all $j$, multiply the $j$-th row of Q by the sign of the diagonal element $R_{jj}$

4. The matrices $Q$ become Haar measure distributed unitary matrices.

• Ah, I had not seen your answer! Always the same story: start editing, go start something else… I would dare to say that the method I referenced is way more efficient, even though they are based on the same basic theorem!
– user154997
Sep 7 '17 at 11:22
• @Luc J. Bourhis I don't have a copy from your first reference; according to its abstract it is based on a concatenation of Householder transformations. But this is the standard method of implementing the QR algorithm. So I think that the two methods are equivalent. Sep 7 '17 at 11:40
• Your method draws $N^2$ random coefficients whereas Stewart method draws $N$ for the 1st column, then $N-1$ for the 2nd one, etc, as the Householder transformations only needs to be applied to "what is left down".
– user154997
Sep 7 '17 at 11:51

The efficient way to generate random matrix in $O(n)$, distributed according to the Haar measure, is adapted from theorem 3.3 in [1] (*). See section 9.1 in [2] for an efficient implementation working for the both of $U(n)$ and $O(n)$. This is only one step of a random walk implementation. The method would then be something along the lines of:

generate random matrix Q in U(n)
for k=1:n
generate random matrix Q' in U(n)
Q := QQ'


The sequence of Q's would then be your random walk. Of course, you would probably need to restrict the size of the step introduced by Q', i.e. keeping Q' in a neighbourhood of the identity matrix. I think I remember the LAPACK algorithm in [2] can be modified to do that but I need to refresh my memory. I'll update my answer if I manage.

[1] G.W. Stewart. The efficient generation of random orthogonal matrices with an application to con- dition estimators. SIAM Journal on Numerical Analysis, 17(3):403–409, 1980.

[2] LAPACK Working Note 9. A Test Matrix Generation Suite. http://www.netlib.org/lapack/lawnspdf/lawn09.pdf

(*) This is the same idea as the one in David Bar Moshe's answer but this is a more efficient implementation, which would matter a lot for the application to random walk as the hot spot will be random matrix generation.