1
$\begingroup$

Given a permutation matrix that is not full rank, is there a linear algebraic and corresponding algebraic criterion to tell if matrix contains more than one disjoint non-trivial cycle or exactly one non-trivial cycle?

Is there a criteria to tell $X,Y$ have unique cycles of length $d_x,d_y$ respectively by looking at $X\otimes Y$?

Example: Consider $$\begin{pmatrix} 0& 0& 0& 0& 1& 0& 0& 0\\ 1& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 1\\ 0& 1& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 1& 0& 0 \end{pmatrix}$$

This matrix embeds 1st row->2nd row->6th row->8th row->5th row->1st row cycle (essentially a 5-cycle in $8\times 8$ matrix). Hence we have a non-trivial $5$-cycle.

In above matrix, if (3,3),(4,4),(7,7) entry is 1, we still get a 5 cycle with 3 fixed points.

On other hand if (4,3),(3,4) entry is 1 and (7,7) entry is 0, we obtain disjoint 2 and 5 cycles with no fixed points (turning (7,7) to 1 gets you a fixed point).

When previous example acts on left on \begin{pmatrix} a1& a2& a3& a4& a5& a6& a7& a8\\ b1& b2& b3& b4& b5& b6& b7& b8\\ c1& c2& c3& c4& c5& c6& c7& c8\\ d1& d2& d3& d4& d5& d6& d7& d8\\ e1& e2& e3& e4& e5& e6& e7& e8\\ f1& f2& f3& f4& f5& f6& f7& f8\\ g1& g2& g3& g4& g5& g6& g7& g8\\ h1& h2& h3& h4& h5& h6& h7& h8 \end{pmatrix}

we get \begin{pmatrix} e1& e2& e3& e4& e5& e6& e7& e8\\ a1& a2& a3& a4& a5& a6& a7& a8\\ 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0\\ h1& h2& h3& h4& h5& h6& h7& h8\\ b1& b2& b3& b4& b5& b6& b7& b8\\ 0& 0& 0& 0& 0& 0& 0& 0\\ f1& f2& f3& f4& f5& f6& f7& f8 \end{pmatrix}

Acting on left $5$ times gives\begin{pmatrix} a1& a2& a3& a4& a5& a6& a7& a8\\ b1& b2& b3& b4& b5& b6& b7& b8\\ 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0\\ e1& e2& e3& e4& e5& e6& e7& e8\\ f1& f2& f3& f4& f5& f6& f7& f8\\ 0& 0& 0& 0& 0& 0& 0& 0\\ h1& h2& h3& h4& h5& h6& h7& h8 \end{pmatrix}

cross posted: https://math.stackexchange.com/questions/1149588/classifying-1-cycle-permutation-matrices

$\endgroup$
  • $\begingroup$ You can just see if the characteristic polynomial is of the form $x^r(x^s - 1)$, where $r + s = n$. I think this criterion should be necessary and sufficient. $\endgroup$ – John Binder Feb 16 '15 at 1:45
  • $\begingroup$ so we cannot say anything linear algebraically? $\endgroup$ – Brout Feb 16 '15 at 1:52
  • 1
    $\begingroup$ @JohnBinder your first condition on the characteristic polynomial is not "if and only if", since it allows to have nontrivial blocks with the zero eigenvalue in the Jordan normal form... $\endgroup$ – Vladimir Dotsenko Feb 16 '15 at 8:18
  • 3
    $\begingroup$ IMHO such matrices are not even called permutational, to begin with. $\endgroup$ – Dima Pasechnik Feb 16 '15 at 10:52
  • 1
    $\begingroup$ @VladimirDotsenko I was operating under the assumption that all such permutation matrices were semisimple, from the statement of the problem, that the matrices in question were semisimple. I should have stated this to begin with, but if this assumption is relaxed then you are correct. $\endgroup$ – John Binder Feb 16 '15 at 13:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.