Cycles from patterns in a permutation matrix

In summary, the conversation discusses the complexity of finding cycles in a permutation matrix and whether there is a quicker way to detect them. It is mentioned that spotting fixed points and transpositions is easy, but finding cycles would require reading all entries in a row. The question is posed if there is a faster way to detect cycles, and it is suggested that the complexity would depend on the counting method used. It is concluded that the complexity of detecting cycles is likely similar to that of a sorting algorithm, which can be ##O(n\log n)## on average and ##O(n^2)## in the worst case.
  • #1
nomadreid
Gold Member
1,677
210
TL;DR Summary
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?
 
Physics news on Phys.org
  • #2
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.
 
  • Like
Likes nomadreid
  • #3
Thanks, fresh_42. So the answer to my question is "no". That seems pretty clear.
 
  • #4
nomadreid said:
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.
 
  • Like
Likes nomadreid

Similar threads

  • Linear and Abstract Algebra
Replies
12
Views
1K
  • Linear and Abstract Algebra
Replies
1
Views
1K
  • Precalculus Mathematics Homework Help
Replies
32
Views
949
  • Linear and Abstract Algebra
Replies
3
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
1K
  • Linear and Abstract Algebra
Replies
1
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
11
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
1K
  • Linear and Abstract Algebra
Replies
1
Views
4K
  • Calculus and Beyond Homework Help
Replies
5
Views
10K
Back
Top