Cycles from patterns in a permutation matrix

[nomadreid]

TL;DR

Beyond fixed points and transpositions, is there an easy way to spot the subset of rows in a permutation matrix that indicate a cycle ?

In a permutation matrix (the identity matrix with rows possibly rearranged), it is easy to spot those rows which will indicate a fixed point -- the one on the diagonal -- and to spot the pairs of rows that will indicate a transposition: a pair of ones on a backward diagonal, i.e., where the row+column subscripts are a constant -- and of course one can find cycles by multiplying a vector and tracing around what goes to what. But is there some quicker way to spot the collections of rows that will correspond to a cycle?

 

[fresh_42]

The cycle decomposition of a permutation should be $O(n)$. How could you hope to find something faster? You still have to read those $n$ entries.

 

[nomadreid]

Thanks, fresh_42. So the answer to my question is "no". That seems pretty clear.

 

[fresh_42]

Thanks, fresh_42. So the answer to my question is "no". That seems pretty clear.

Maybe I made a mistake. It could be $O(n^2)$ if we have to read all entries of a row to find the next column: if $(i,j)$ read $k$ until $k=j$. So it depends a bit on what we are counting. Your question then could be phrased as: can we detect a cycle before closing the cycle? The answer is likely the complexity of a sorting algorithm which are in general $O(n\log n)$ average and $O(n^2)$ worst case.