{"id":5018,"date":"2012-07-06T22:50:02","date_gmt":"2012-07-06T20:50:02","guid":{"rendered":"http:\/\/djalil.chafai.net\/blog\/?p=5018"},"modified":"2014-06-15T10:21:05","modified_gmt":"2014-06-15T08:21:05","slug":"an-observation-on-permutation-matrices","status":"publish","type":"post","link":"https:\/\/djalil.chafai.net\/blog\/2012\/07\/06\/an-observation-on-permutation-matrices\/","title":{"rendered":"An observation on permutation matrices"},"content":{"rendered":"

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

This post is devoted to certain properties of random permutation matrices. Let \\( {\\mathfrak{S}_n} \\) be the symmetric group, \\( {n\\geq2} \\), and let \\( {\\mathcal{P}_n} \\) be the group of \\( {n\\times n} \\) permutation matrices, obtained by the isomorphism \\( {\\sigma\\in\\mathfrak{S}_n\\mapsto P_\\sigma={(\\mathbf{1}_{j=\\sigma(i)})}_{1\\leq i,j\\leq n}} \\). We know that \\( {\\mathcal{P}_n} \\) is a subgroup of the orthogonal group \\( {\\mathbb{O}_n} \\). It is also the set of extremal points of the Birkhoff polytope \\( {\\mathcal{B}_n} \\) formed by doubly stochastic matrices (these matrices with entries in \\( {[0,1]} \\) with rows and columns all summing to one). The uniform probability measure on \\( {\\mathcal{P}_n} \\), which gives mass \\( {1\/n!} \\) to every atom, is a Haar measure (left and right translation invariant). We denote by \\( {J} \\) the \\( {n\\times n} \\) matrix with all entries equal to \\( {1} \\). We have \\( {\\frac{1}{n}J\\in\\mathcal{B}_n} \\).<\/p>\n

Theorem 1 (Moments and fixed points)<\/strong> Let \\( {k\\geq1} \\) and \\( {\\psi_n(k):=\\mathrm{Card}\\{1\\leq r\\leq n:r \\vert k\\}} \\). If \\( {P} \\) is a random matrix uniformly distributed on \\( {\\mathcal{P}_n} \\), and \\( {F_k:=\\mathbb{E}(P^k)} \\), then<\/em><\/p>\n

\\[ \\mathrm{diag}(F_k)=\\frac{\\psi_n(k)}{n}I \\quad\\text{and in particular}\\quad \\mathrm{Tr}(F_k)=\\psi_n(k). \\]<\/em><\/p>\n

If \\( {\\sigma} \\) is a random permutation uniformly distributed on \\( {\\mathfrak{S}_n} \\), then<\/em><\/p>\n

\\[ \\mathbb{E}(\\mathrm{Card}\\{1\\leq i\\leq n:\\sigma^k(i)=i\\}) =\\psi_n(k). \\]<\/em><\/p>\n<\/blockquote>\n

Note that \\( {n\\mapsto\\psi_n(k)} \\) grows until \\( {\\psi_k(k)=\\mathrm{Card}\\{1\\leq r\\leq k:r\\vert k\\}} \\).<\/p>\n

Proof:<\/em> The second part follows from the first part since if \\( {P_\\sigma:={(\\mathbf{1}_{j=\\sigma(i)})}_{1\\leq i,j\\leq n}} \\) then \\( {P^k\\overset{d}{=}P_\\sigma^k=P_{\\sigma^k}} \\), and \\( {\\mathrm{Tr}(P_{\\sigma^k})=\\mathrm{Card}\\{1\\leq i\\leq n:\\sigma^k(i)=i\\}} \\), and thus<\/p>\n

\\[ \\mathrm{Tr}(F_k) =\\mathbb{E}(\\mathrm{Tr}(P_{\\sigma^k})) =\\mathbb{E}(\\mathrm{Card}\\{1\\leq i\\leq n:\\sigma^k(i)=i\\}). \\]<\/p>\n

To establish the first part, we write, for all \\( {1\\leq i\\leq n} \\),<\/p>\n

\\[ (F_k)_{i,i} =\\mathbb{E}((P_{\\sigma^k})_{i,i}) =\\mathbb{E}(\\mathbf{1}_{\\sigma^k(i)=i}) =\\mathbb{P}(\\sigma^k(i)=i) =\\frac{1}{n!}\\sum_{\\sigma\\in\\mathfrak{S}_n}\\mathbf{1}_{\\sigma^k(i)=i}. \\]<\/p>\n

Now \\( {i} \\) is a fixed point of \\( {\\sigma^k} \\) iff \\( {i} \\) belongs to a cycle of \\( {\\sigma} \\) of length \\( {r} \\) such that \\( {r\\vert k} \\). There are<\/p>\n

\\[ A_{n-1,r-1}=\\frac{(n-1)!}{(n-1-(r-1))!}=\\frac{(n-1)!}{(n-r)!} \\]<\/p>\n

ways to choose this cycle, and \\( {(n-r)!} \\) ways to permute the elements outside this cycle. Therefore<\/p>\n

\\[ \\frac{1}{n!}\\sum_{\\sigma\\in\\mathfrak{S}_n}\\mathbf{1}_{\\sigma^k(i)=i} =\\frac{1}{n!}\\sum_{\\substack{1\\leq r\\leq k\\\\r\\vert k}}\\frac{(n-1)!}{(n-r)!}(n-r)! =\\frac{\\psi_n(k)}{n}. \\]<\/p>\n

\u2610<\/p>\n

Theorem 2 (Structure of \\( {F_k} \\))<\/strong> With the settings of theorem 1<\/a>, we have<\/em><\/p>\n

\\[ F_k =\\frac{\\psi_n(k)-1}{n-1}I +\\left(1-\\frac{\\psi_n(k)-1}{n-1}\\right)\\frac{1}{n}J. \\]<\/em><\/p>\n<\/blockquote>\n

In particular, the matrix \\( {F_k} \\) belongs to the interval \\( {[I,\\frac{1}{n}J]} \\) in \\( {\\mathcal{B}_n} \\).<\/p>\n

Proof:<\/em> Let \\( {\\sigma} \\) be a random permutation following the uniform distribution on \\( {\\mathfrak{S}_n} \\), as in theorem 1<\/a>. For any fixed \\( {\\tau\\in\\mathfrak{S}_n} \\), we have \\( {\\tau\\sigma\\overset{d}{=}\\sigma\\overset{d}{=}\\sigma\\tau} \\), and thus<\/p>\n

\\[ P_\\tau C_\\tau=F_k=C_\\tau P_\\tau \\]<\/p>\n

where \\( {C_\\tau=\\mathbb{E}(P_\\sigma\\underbrace{P_\\tau P_\\sigma\\cdots P_\\tau P_\\sigma}_{k-1\\text{ times}})} \\). Therefore, for any \\( {\\tau\\in\\mathfrak{S}_n} \\),<\/p>\n

\\[ P_{\\tau^{-1}}F_k=F_kP_{\\tau^{-1}}=C_\\tau \\ \\ \\ \\ \\ (1) \\]<\/p>\n

and thus, for any \\( {\\tau\\in\\mathfrak{S}_n} \\)<\/p>\n

\\[ P_{\\tau^{-1}}F_kP_{\\tau}=F_k. \\]<\/p>\n

In other words, for any \\( {\\tau\\in\\mathfrak{S}_n} \\) and any \\( {1\\leq i,j\\leq n} \\),<\/p>\n

\\[ (F_k)_{\\tau(i),\\tau(j)}=(F_k)_{i,j}. \\]<\/p>\n

Thus \\( {(F_k)_{i,i}=(F_k)_{1,1}} \\) and \\( {(F_k)_{i,j}=(F_k)_{1,2}} \\) for any \\( {1\\leq i\\neq j\\leq n} \\). Since \\( {F_k} \\) is a stochastic matrix, we have \\( {1=F_{1,1}+(n-1)F_{1,2}} \\). Now theorem 1<\/a> gives \\( {F_{1,1}=\\frac{\\psi_n(k)}{n}} \\), and the value of \\( {F_{1,2}}\\) follows. \u2610<\/p>\n

Algebra.<\/strong> For \\( {k=1} \\), the formula (1)<\/a> allows to determine \\( {F_1} \\) without using theorem 1<\/a>. Namely, for \\( {k=1} \\), we have \\( {C_\\tau=\\mathbb{E}(P_\\sigma)=F_1} \\), and thus \\( {P_\\tau F_1=F_1=F_1P_\\tau} \\). Therefore \\( {F_1} \\) has all its rows identical, and all its columns identical, and thus all its entries identical. Since \\( {F_1} \\) is a stochastic matrix, we obtain \\( {F_1=\\frac{1}{n}J} \\) and we recover in particular that \\( {\\mathrm{Tr}(F_1)=1=\\psi_n(1)} \\). For \\( {k>1} \\), the matrix \\( {C_\\tau} \\) depends on \\( {\\tau} \\), and we ignore how to deduce \\( {F_k} \\) by using simply the translation invariance of the law of \\( {\\sigma} \\), without using the combinatorics of the cycles structure of \\( {\\sigma} \\).<\/p>\n

Blocs and cycles.<\/strong> We may play with the cycles decomposition of \\( {\\sigma} \\) using matrices. Namely, we know that \\( {P_\\sigma} \\) is conjugated in \\( {\\mathcal{P}_n} \\) to \\( {\\oplus_{i=1}^\\ell B_i} \\) where \\( {B_1\\in\\mathcal{P}_{n_1},\\ldots,B_\\ell\\in\\mathcal{P}_{n_\\ell}} \\) are the matrices of the \\( {\\ell} \\) cycles of \\( {\\sigma} \\), of lengths \\( {n_1,\\ldots,n_\\ell} \\). Thus \\( {P_\\sigma^k} \\) is conjugated to \\( {\\oplus_{i=1}^\\ell B_i^k} \\). But \\( {\\mathrm{Tr}(B_i^k)=n_i\\mathbf{1}_{n_i\\vert k}} \\) and thus<\/p>\n

\\[ \\mathrm{Tr}(P_\\sigma^k) =\\sum_{i=1}^\\ell\\mathrm{Tr}(B_i^k) =\\sum_{i=1}^\\ell n_i\\mathbf{1}_{n_i\\vert k}. \\]<\/p>\n

Denoting \\( {A_1,\\ldots,A_n} \\) the number of cycles of \\( {\\sigma} \\) of lengths \\( {1,\\ldots,n} \\), we get<\/p>\n

\\[ \\mathrm{Tr}(P_\\sigma^k)=\\sum_{j=1}^n jA_j\\mathbf{1}_{j\\vert k}. \\]<\/p>\n

Therefore, theorem 1<\/a> gives<\/p>\n

\\[ \\sum_{j=1}^n j\\mathbb{E}(A_j)\\mathbf{1}_{j\\vert k} =\\mathbb{E}(\\mathrm{Tr}(P_\\sigma^k)) =\\psi_n(k). \\]<\/p>\n

Not a surprise for the readers knowing that \\( {\\mathbb{E}(A_j)=\\frac{1}{j}} \\) for any \\( {1\\leq j\\leq n} \\).<\/p>\n

Note.<\/strong> This post comes from discussions with Yan Doumerc.<\/p>\n","protected":false},"excerpt":{"rendered":"

This post is devoted to certain properties of random permutation matrices. Let \\( {\\mathfrak{S}_n} \\) be the symmetric group, \\( {n\\geq2} \\), and let \\(…<\/p>\n

Continue readingAn observation on permutation matrices<\/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":243},"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/posts\/5018"}],"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=5018"}],"version-history":[{"count":48,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/posts\/5018\/revisions"}],"predecessor-version":[{"id":7361,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/posts\/5018\/revisions\/7361"}],"wp:attachment":[{"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/media?parent=5018"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/categories?post=5018"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/tags?post=5018"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}