{"id":4550,"date":"2012-03-11T12:52:14","date_gmt":"2012-03-11T11:52:14","guid":{"rendered":"http:\/\/djalil.chafai.net\/blog\/?p=4550"},"modified":"2012-03-13T00:53:24","modified_gmt":"2012-03-12T23:53:24","slug":"a-random-walk-on-the-unitary-group","status":"publish","type":"post","link":"https:\/\/djalil.chafai.net\/blog\/2012\/03\/11\/a-random-walk-on-the-unitary-group\/","title":{"rendered":"A random walk on the unitary group"},"content":{"rendered":"

\"Modules<\/a><\/p>\n

This short post is devoted to an intriguing random walk on the unitary group<\/a>. 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<\/a>, 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<\/p>\n

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

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.<\/p>\n

Let us say that \\( {Q\\in\\mathbb{U}} \\) is a complex permutation matrix<\/em> 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<\/p>\n

\\[ Q_{i,j}=\\varphi_i\\mathbf{1}_{j=\\sigma(i)} \\]<\/p>\n

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<\/a> \\( {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).<\/p>\n

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<\/a> 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<\/a> given by the roots of unity associated to the cycles decomposition of the permutation. On the other hand, the Haar<\/a> 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.<\/p>\n

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<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"

This short post is devoted to an intriguing random walk on the unitary group. Namely, let us fix an integer \\( {d\\geq1} \\) and pick…<\/p>\n

Continue readingA random walk on the unitary group<\/span><\/a><\/div>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"iawp_total_views":239},"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/posts\/4550"}],"collection":[{"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/comments?post=4550"}],"version-history":[{"count":52,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/posts\/4550\/revisions"}],"predecessor-version":[{"id":4605,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/posts\/4550\/revisions\/4605"}],"wp:attachment":[{"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/media?parent=4550"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/categories?post=4550"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/tags?post=4550"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}