Conditions when a permutation matrix is symmetric












1












$begingroup$


I am now playing with permutation matrices, http://mathworld.wolfram.com/PermutationMatrix.html.



Also, there is a similar discussion: Symmetric Permutation Matrix.
I want to ask more details than this one.



As we know, a permutation matrix is orthogonal, i.e., $E^T=E^{-1}$. I am interested in when it is symmetric, i.e., $E^T=E^{-1} = E$



Suppose




  1. Start from an identity matrix $I_n$.


  2. $n$ can be even or odd number.

  3. Pick $(i,j)$, where $0<i,jleq n$ and $i, j$ are integer. Exchange $i$-th and $j$-th columns of $I_n$ (identity matrix) and get $E$. Then $E$ is symmetric. This is because $E_{ii}=E_{jj}=0$ and $E_{ij}=E_{ji}=1$.

  4. Based on 3., if I pick a number of sets $(i,j)$, $(k,l)$, $(q,r), ldots$, without repeated index in each $(cdot,cdot)$, and permute columns of $I_n$ according to these sets, then the resulting permutation matrix $E$ is symmetric.


One key thing here is "without repeated index in each $(cdot,cdot)$". This is because if I do $(1,2)$ and $(2,3)$ for $I_3$ for example, I get



$$begin{bmatrix}0 & 0 & 1 \ 1 & 0 & 0 \ 0 & 1 & 0 end{bmatrix},$$



which is not symmetric. In this case, I repeat $2$ in each suit.



Is the above correct? Or I miss some key assumptions?










share|cite|improve this question









$endgroup$








  • 1




    $begingroup$
    Yes, in general the permutation is idempotent when is a disjoint product of fix points and cycles of length $2.$
    $endgroup$
    – Phicar
    4 hours ago






  • 1




    $begingroup$
    Yes, it's correct. A permutation matrix describes a permutation $pi$. You want $E^2 = I$, so $picircpi = id$.
    $endgroup$
    – amsmath
    4 hours ago
















1












$begingroup$


I am now playing with permutation matrices, http://mathworld.wolfram.com/PermutationMatrix.html.



Also, there is a similar discussion: Symmetric Permutation Matrix.
I want to ask more details than this one.



As we know, a permutation matrix is orthogonal, i.e., $E^T=E^{-1}$. I am interested in when it is symmetric, i.e., $E^T=E^{-1} = E$



Suppose




  1. Start from an identity matrix $I_n$.


  2. $n$ can be even or odd number.

  3. Pick $(i,j)$, where $0<i,jleq n$ and $i, j$ are integer. Exchange $i$-th and $j$-th columns of $I_n$ (identity matrix) and get $E$. Then $E$ is symmetric. This is because $E_{ii}=E_{jj}=0$ and $E_{ij}=E_{ji}=1$.

  4. Based on 3., if I pick a number of sets $(i,j)$, $(k,l)$, $(q,r), ldots$, without repeated index in each $(cdot,cdot)$, and permute columns of $I_n$ according to these sets, then the resulting permutation matrix $E$ is symmetric.


One key thing here is "without repeated index in each $(cdot,cdot)$". This is because if I do $(1,2)$ and $(2,3)$ for $I_3$ for example, I get



$$begin{bmatrix}0 & 0 & 1 \ 1 & 0 & 0 \ 0 & 1 & 0 end{bmatrix},$$



which is not symmetric. In this case, I repeat $2$ in each suit.



Is the above correct? Or I miss some key assumptions?










share|cite|improve this question









$endgroup$








  • 1




    $begingroup$
    Yes, in general the permutation is idempotent when is a disjoint product of fix points and cycles of length $2.$
    $endgroup$
    – Phicar
    4 hours ago






  • 1




    $begingroup$
    Yes, it's correct. A permutation matrix describes a permutation $pi$. You want $E^2 = I$, so $picircpi = id$.
    $endgroup$
    – amsmath
    4 hours ago














1












1








1





$begingroup$


I am now playing with permutation matrices, http://mathworld.wolfram.com/PermutationMatrix.html.



Also, there is a similar discussion: Symmetric Permutation Matrix.
I want to ask more details than this one.



As we know, a permutation matrix is orthogonal, i.e., $E^T=E^{-1}$. I am interested in when it is symmetric, i.e., $E^T=E^{-1} = E$



Suppose




  1. Start from an identity matrix $I_n$.


  2. $n$ can be even or odd number.

  3. Pick $(i,j)$, where $0<i,jleq n$ and $i, j$ are integer. Exchange $i$-th and $j$-th columns of $I_n$ (identity matrix) and get $E$. Then $E$ is symmetric. This is because $E_{ii}=E_{jj}=0$ and $E_{ij}=E_{ji}=1$.

  4. Based on 3., if I pick a number of sets $(i,j)$, $(k,l)$, $(q,r), ldots$, without repeated index in each $(cdot,cdot)$, and permute columns of $I_n$ according to these sets, then the resulting permutation matrix $E$ is symmetric.


One key thing here is "without repeated index in each $(cdot,cdot)$". This is because if I do $(1,2)$ and $(2,3)$ for $I_3$ for example, I get



$$begin{bmatrix}0 & 0 & 1 \ 1 & 0 & 0 \ 0 & 1 & 0 end{bmatrix},$$



which is not symmetric. In this case, I repeat $2$ in each suit.



Is the above correct? Or I miss some key assumptions?










share|cite|improve this question









$endgroup$




I am now playing with permutation matrices, http://mathworld.wolfram.com/PermutationMatrix.html.



Also, there is a similar discussion: Symmetric Permutation Matrix.
I want to ask more details than this one.



As we know, a permutation matrix is orthogonal, i.e., $E^T=E^{-1}$. I am interested in when it is symmetric, i.e., $E^T=E^{-1} = E$



Suppose




  1. Start from an identity matrix $I_n$.


  2. $n$ can be even or odd number.

  3. Pick $(i,j)$, where $0<i,jleq n$ and $i, j$ are integer. Exchange $i$-th and $j$-th columns of $I_n$ (identity matrix) and get $E$. Then $E$ is symmetric. This is because $E_{ii}=E_{jj}=0$ and $E_{ij}=E_{ji}=1$.

  4. Based on 3., if I pick a number of sets $(i,j)$, $(k,l)$, $(q,r), ldots$, without repeated index in each $(cdot,cdot)$, and permute columns of $I_n$ according to these sets, then the resulting permutation matrix $E$ is symmetric.


One key thing here is "without repeated index in each $(cdot,cdot)$". This is because if I do $(1,2)$ and $(2,3)$ for $I_3$ for example, I get



$$begin{bmatrix}0 & 0 & 1 \ 1 & 0 & 0 \ 0 & 1 & 0 end{bmatrix},$$



which is not symmetric. In this case, I repeat $2$ in each suit.



Is the above correct? Or I miss some key assumptions?







linear-algebra matrices permutations






share|cite|improve this question













share|cite|improve this question











share|cite|improve this question




share|cite|improve this question










asked 4 hours ago









sleeve chensleeve chen

3,20042256




3,20042256








  • 1




    $begingroup$
    Yes, in general the permutation is idempotent when is a disjoint product of fix points and cycles of length $2.$
    $endgroup$
    – Phicar
    4 hours ago






  • 1




    $begingroup$
    Yes, it's correct. A permutation matrix describes a permutation $pi$. You want $E^2 = I$, so $picircpi = id$.
    $endgroup$
    – amsmath
    4 hours ago














  • 1




    $begingroup$
    Yes, in general the permutation is idempotent when is a disjoint product of fix points and cycles of length $2.$
    $endgroup$
    – Phicar
    4 hours ago






  • 1




    $begingroup$
    Yes, it's correct. A permutation matrix describes a permutation $pi$. You want $E^2 = I$, so $picircpi = id$.
    $endgroup$
    – amsmath
    4 hours ago








1




1




$begingroup$
Yes, in general the permutation is idempotent when is a disjoint product of fix points and cycles of length $2.$
$endgroup$
– Phicar
4 hours ago




$begingroup$
Yes, in general the permutation is idempotent when is a disjoint product of fix points and cycles of length $2.$
$endgroup$
– Phicar
4 hours ago




1




1




$begingroup$
Yes, it's correct. A permutation matrix describes a permutation $pi$. You want $E^2 = I$, so $picircpi = id$.
$endgroup$
– amsmath
4 hours ago




$begingroup$
Yes, it's correct. A permutation matrix describes a permutation $pi$. You want $E^2 = I$, so $picircpi = id$.
$endgroup$
– amsmath
4 hours ago










2 Answers
2






active

oldest

votes


















2












$begingroup$

You’re correct!



We can think of the action of $E$ on the set of $n$ standard basis vectors as a permutation $sigma$ on ${1,dots,n}$ and vice versa.



Let $E$ be symmetric, and let $i$ be the only nonzero entry in the first row. This means that $e_{1i}=e_{i1}$ by symmetry. Thus $E$ swaps the first and the $i^{th}$ standard basis vectors, so $(1~i)$ is a cycle in the cycle decomposition of $sigma$. This argument applies to the rest of the rows to show that $sigma$ is a product of disjoint transpositions.






share|cite|improve this answer









$endgroup$





















    2












    $begingroup$

    As you have noted condition for a permutation matrix $E$ to be symmetric
    is that $E^{-1}=E$, and this condition can be expressed as $E^2=I$.



    Interpreting the last condition as repeating the permutation is identity. So this represents a permutation that is its own inverse. That is if $E$ sends a basis vector $v$ to $W$ $E^2=I$ implies $Ew=v$. (possible that $v=w$)



    So this corresponds to a permutation where an element is fixed, or if it sends $x$ to $y$ then it has to send $y$ to $x$. Thus this consists of many disjoint swaps (and possibly some fixed points).



    In group theory it is a permutation of cycle type corresponding to the partition of $n$ into $2$'s and $1$'s. For example $9=2+2+2+ 1^6 $ (that is 1 repeated six times).






    share|cite|improve this answer









    $endgroup$














      Your Answer








      StackExchange.ready(function() {
      var channelOptions = {
      tags: "".split(" "),
      id: "69"
      };
      initTagRenderer("".split(" "), "".split(" "), channelOptions);

      StackExchange.using("externalEditor", function() {
      // Have to fire editor after snippets, if snippets enabled
      if (StackExchange.settings.snippets.snippetsEnabled) {
      StackExchange.using("snippets", function() {
      createEditor();
      });
      }
      else {
      createEditor();
      }
      });

      function createEditor() {
      StackExchange.prepareEditor({
      heartbeatType: 'answer',
      autoActivateHeartbeat: false,
      convertImagesToLinks: true,
      noModals: true,
      showLowRepImageUploadWarning: true,
      reputationToPostImages: 10,
      bindNavPrevention: true,
      postfix: "",
      imageUploader: {
      brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
      contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
      allowUrls: true
      },
      noCode: true, onDemand: true,
      discardSelector: ".discard-answer"
      ,immediatelyShowMarkdownHelp:true
      });


      }
      });














      draft saved

      draft discarded


















      StackExchange.ready(
      function () {
      StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3194162%2fconditions-when-a-permutation-matrix-is-symmetric%23new-answer', 'question_page');
      }
      );

      Post as a guest















      Required, but never shown

























      2 Answers
      2






      active

      oldest

      votes








      2 Answers
      2






      active

      oldest

      votes









      active

      oldest

      votes






      active

      oldest

      votes









      2












      $begingroup$

      You’re correct!



      We can think of the action of $E$ on the set of $n$ standard basis vectors as a permutation $sigma$ on ${1,dots,n}$ and vice versa.



      Let $E$ be symmetric, and let $i$ be the only nonzero entry in the first row. This means that $e_{1i}=e_{i1}$ by symmetry. Thus $E$ swaps the first and the $i^{th}$ standard basis vectors, so $(1~i)$ is a cycle in the cycle decomposition of $sigma$. This argument applies to the rest of the rows to show that $sigma$ is a product of disjoint transpositions.






      share|cite|improve this answer









      $endgroup$


















        2












        $begingroup$

        You’re correct!



        We can think of the action of $E$ on the set of $n$ standard basis vectors as a permutation $sigma$ on ${1,dots,n}$ and vice versa.



        Let $E$ be symmetric, and let $i$ be the only nonzero entry in the first row. This means that $e_{1i}=e_{i1}$ by symmetry. Thus $E$ swaps the first and the $i^{th}$ standard basis vectors, so $(1~i)$ is a cycle in the cycle decomposition of $sigma$. This argument applies to the rest of the rows to show that $sigma$ is a product of disjoint transpositions.






        share|cite|improve this answer









        $endgroup$
















          2












          2








          2





          $begingroup$

          You’re correct!



          We can think of the action of $E$ on the set of $n$ standard basis vectors as a permutation $sigma$ on ${1,dots,n}$ and vice versa.



          Let $E$ be symmetric, and let $i$ be the only nonzero entry in the first row. This means that $e_{1i}=e_{i1}$ by symmetry. Thus $E$ swaps the first and the $i^{th}$ standard basis vectors, so $(1~i)$ is a cycle in the cycle decomposition of $sigma$. This argument applies to the rest of the rows to show that $sigma$ is a product of disjoint transpositions.






          share|cite|improve this answer









          $endgroup$



          You’re correct!



          We can think of the action of $E$ on the set of $n$ standard basis vectors as a permutation $sigma$ on ${1,dots,n}$ and vice versa.



          Let $E$ be symmetric, and let $i$ be the only nonzero entry in the first row. This means that $e_{1i}=e_{i1}$ by symmetry. Thus $E$ swaps the first and the $i^{th}$ standard basis vectors, so $(1~i)$ is a cycle in the cycle decomposition of $sigma$. This argument applies to the rest of the rows to show that $sigma$ is a product of disjoint transpositions.







          share|cite|improve this answer












          share|cite|improve this answer



          share|cite|improve this answer










          answered 2 hours ago









          Santana AftonSantana Afton

          3,1922730




          3,1922730























              2












              $begingroup$

              As you have noted condition for a permutation matrix $E$ to be symmetric
              is that $E^{-1}=E$, and this condition can be expressed as $E^2=I$.



              Interpreting the last condition as repeating the permutation is identity. So this represents a permutation that is its own inverse. That is if $E$ sends a basis vector $v$ to $W$ $E^2=I$ implies $Ew=v$. (possible that $v=w$)



              So this corresponds to a permutation where an element is fixed, or if it sends $x$ to $y$ then it has to send $y$ to $x$. Thus this consists of many disjoint swaps (and possibly some fixed points).



              In group theory it is a permutation of cycle type corresponding to the partition of $n$ into $2$'s and $1$'s. For example $9=2+2+2+ 1^6 $ (that is 1 repeated six times).






              share|cite|improve this answer









              $endgroup$


















                2












                $begingroup$

                As you have noted condition for a permutation matrix $E$ to be symmetric
                is that $E^{-1}=E$, and this condition can be expressed as $E^2=I$.



                Interpreting the last condition as repeating the permutation is identity. So this represents a permutation that is its own inverse. That is if $E$ sends a basis vector $v$ to $W$ $E^2=I$ implies $Ew=v$. (possible that $v=w$)



                So this corresponds to a permutation where an element is fixed, or if it sends $x$ to $y$ then it has to send $y$ to $x$. Thus this consists of many disjoint swaps (and possibly some fixed points).



                In group theory it is a permutation of cycle type corresponding to the partition of $n$ into $2$'s and $1$'s. For example $9=2+2+2+ 1^6 $ (that is 1 repeated six times).






                share|cite|improve this answer









                $endgroup$
















                  2












                  2








                  2





                  $begingroup$

                  As you have noted condition for a permutation matrix $E$ to be symmetric
                  is that $E^{-1}=E$, and this condition can be expressed as $E^2=I$.



                  Interpreting the last condition as repeating the permutation is identity. So this represents a permutation that is its own inverse. That is if $E$ sends a basis vector $v$ to $W$ $E^2=I$ implies $Ew=v$. (possible that $v=w$)



                  So this corresponds to a permutation where an element is fixed, or if it sends $x$ to $y$ then it has to send $y$ to $x$. Thus this consists of many disjoint swaps (and possibly some fixed points).



                  In group theory it is a permutation of cycle type corresponding to the partition of $n$ into $2$'s and $1$'s. For example $9=2+2+2+ 1^6 $ (that is 1 repeated six times).






                  share|cite|improve this answer









                  $endgroup$



                  As you have noted condition for a permutation matrix $E$ to be symmetric
                  is that $E^{-1}=E$, and this condition can be expressed as $E^2=I$.



                  Interpreting the last condition as repeating the permutation is identity. So this represents a permutation that is its own inverse. That is if $E$ sends a basis vector $v$ to $W$ $E^2=I$ implies $Ew=v$. (possible that $v=w$)



                  So this corresponds to a permutation where an element is fixed, or if it sends $x$ to $y$ then it has to send $y$ to $x$. Thus this consists of many disjoint swaps (and possibly some fixed points).



                  In group theory it is a permutation of cycle type corresponding to the partition of $n$ into $2$'s and $1$'s. For example $9=2+2+2+ 1^6 $ (that is 1 repeated six times).







                  share|cite|improve this answer












                  share|cite|improve this answer



                  share|cite|improve this answer










                  answered 1 hour ago









                  P VanchinathanP Vanchinathan

                  15.7k12236




                  15.7k12236






























                      draft saved

                      draft discarded




















































                      Thanks for contributing an answer to Mathematics Stack Exchange!


                      • Please be sure to answer the question. Provide details and share your research!

                      But avoid



                      • Asking for help, clarification, or responding to other answers.

                      • Making statements based on opinion; back them up with references or personal experience.


                      Use MathJax to format equations. MathJax reference.


                      To learn more, see our tips on writing great answers.




                      draft saved


                      draft discarded














                      StackExchange.ready(
                      function () {
                      StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3194162%2fconditions-when-a-permutation-matrix-is-symmetric%23new-answer', 'question_page');
                      }
                      );

                      Post as a guest















                      Required, but never shown





















































                      Required, but never shown














                      Required, but never shown












                      Required, but never shown







                      Required, but never shown

































                      Required, but never shown














                      Required, but never shown












                      Required, but never shown







                      Required, but never shown







                      Popular posts from this blog

                      How to label and detect the document text images

                      Vallis Paradisi

                      Tabula Rosettana