I Cycles from patterns in a permutation matrix

nomadreid
Gold Member
Messages
1,750
Reaction score
243
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
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.
 
Thanks, fresh_42. So the answer to my question is "no". That seems pretty clear.
 
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.
 
Thread 'Derivation of equations of stress tensor transformation'
Hello ! I derived equations of stress tensor 2D transformation. Some details: I have plane ABCD in two cases (see top on the pic) and I know tensor components for case 1 only. Only plane ABCD rotate in two cases (top of the picture) but not coordinate system. Coordinate system rotates only on the bottom of picture. I want to obtain expression that connects tensor for case 1 and tensor for case 2. My attempt: Are these equations correct? Is there more easier expression for stress tensor...
Back
Top