Month: March 2012

This short post is devoted to an intriguing random walk on the unitary group. Namely, let us fix an integer \( {d\geq1} \) and pick some \( {d\times d} \) unitary matrix \( {U_0} \) from the unitary group \( {\mathbb{U}} \). From the spectral theorem, there exists a unitary matrix \( {U_1} \) in \( {\mathbb{U}} \) such that \( {U_1U_0U_1^*} \) is diagonal with diagonal elements in the unit circle of \( {\mathbb{C}} \). This unitary diagonalization is not unique, and we may pick \( {U_1} \) at random uniformly among the possibilities. This can be written as \( {U_1=f(U_0,\varepsilon_1)} \) where \( {\varepsilon_1} \) is a random variable. Now, we define the sequence \( {{(U_n)}_{n\geq0}} \) by

\[ U_{n+1}=f(U_n,\varepsilon_{n+1}) \]

where \( {{(\varepsilon_n)}_{n\geq1}} \) is an auxiliary i.i.d. sequence, chosen independent of \( {U_0} \) which may be taken at random. This defines a random walk, or a Markov chain if one prefers, on the unitary group \( {\mathbb{U}} \). What do we know about this chain? I have never met this chain before.

Let us say that \( {Q\in\mathbb{U}} \) is a complex permutation matrix when there exists a permutation \( {\sigma} \) of \( {\{1,\ldots,d\}} \) and phases \( {\varphi_1,\ldots,\varphi_d} \) (i.e. complex numbers of unit module) such that

\[ Q_{i,j}=\varphi_i\mathbf{1}_{j=\sigma(i)} \]

for every \( {1\leq i,j\leq d} \). This is equivalent to say that there exists a diagonal matrix \( {D\in\mathbb{U}} \) and a permutation matrix \( {P} \) such that \( {Q=DP} \). Note that \( {Q=DP=PP^{-1}DP=PD’} \) where \( {D’} \) is like \( {D} \). The set of complex permutation matrices is a sub-group of \( {\mathbb{U}} \). If \( {M} \) is a \( {d\times d} \) matrix and \( {Q} \) is a complex permutation matrix, then \( {QM} \) is obtained from \( {M} \) by permuting the rows and multiplying them by a phase (one for each).

Let us say that two elements \( {U} \) and \( {V} \) of \( {\mathbb{U}} \) are equivalent, and we denote \( {U\equiv V} \), when \( {V=QU} \) for some complex permutation matrix \( {Q} \). Conditional on \( {U_n} \), the law of \( {U_{n+1}} \) is uniform over an equivalent class for \( {\equiv} \). The class of \( {I_d} \) includes the commutative subgroup of \( {\mathbb{U}} \) formed by diagonal elements. This class is an irreducible communication class of the chain. In contrast, if \( {U_0} \) is a permutation matrix not equal to the identity then \( {U_1} \) belongs to the class of a sort of bloc circulant Vandermonde matrix given by the roots of unity associated to the cycles decomposition of the permutation. On the other hand, the Haar probability measure on \( {\mathbb{U}} \) is invariant for the chain. How about the spectral decomposition of the chain and its trend to the equilibrium? The convergence seems to be very fast on simulations.

Note that one may start the chain from the eigenvectors matrix of an arbitrary \( {d\times d} \) random matrix \( {X} \) using the unitary Schur decomposition.