[math-fun] Decomposing Rotation into set of sub-rotations - how many orderings?
This combinatorics question may now have some interest: HOW MANY orderings of the (N-1)*N/2 entries in the lower triangle in an NxN matrix, are there, such that each one may be zeroed via an adjacent-coordinate 2x2 rotation, successively, without destroying the previously-created zeros? The going-up-columns raster scan (starting at leftmost column) and the diagonal raster (going southeast, on longer and long diagonals) ordering are two answers, but there evidently are many more possible orderings. (Here I am just considering multiplying by the 2x2 rotation from the left. I we also allow multiplications by 2x2s on the right, that'd be more.) The question is equivalent to the following. How many ways can you fill in that triangle with the integers 1,2,3,...,(N-1)*N/2 in such a way that: if some cell contains integer K, then each cell on the same row containing an integer<K, must be accompanied by a "mate" -- the cell immediately above it -- also with contents <K. ? A crude rough "probabilistic" heuristic estimate is as follows. Consider choosing one of the [(N-1)*N/2]! orderings at random. The chance it satisfies the "mate conditions" seems to be about C^(-N*N) for some constant C>1, perhaps C is about 2. So therefore I estimate the number of allowable orderings is about [(N-1)*N/2]! * C^(-N*N) for some constant C>1. Note this grows to infinity with N rather rapidly regardless of the value of C. But one might be able to get an exact not approximate formula. I would suggest determining the #orderings as a function of N for small N by computer enumeration. By hand: N #ord 1 1 2 1 3 1 4 ? -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
The question is equivalent to the following. How many ways can you fill in that triangle with the integers 1,2,3,...,(N-1)*N/2 in such a way that: if some cell contains integer K, then each cell on the same row containing an integer<K, must be accompanied by a "mate" -- the cell immediately above it -- also with contents <K. ?
--Sorry, it occurs to me there is another demand: the ordering must be such that the integers increase going upward within each column. ("vertical monotonicity.") This has a very major effect on the count of orderings and may totally destroy my heuristic estimate. Then we manually find the only two allowed orderings when N=4 are 4 2 5 1 3 6 3 2 5 1 4 6 OEIS finds 11820 sequences containing 1,1,1,2... (Perhaps for some reason horizontal monotonicity is also required? And/or monotonicity along the NW-SE diagonals? If so, the arguments for why will be indirect. The conditions on the orderings I have mentioned so far, are direct and presumably imply these further conditions if they are valid.) -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
So the allowable orderings of the (N-1)*N/2 entries in the strict lower triangle of an NxN matrix (strict lower triangle only) according to my two criteria 1. if some cell contains integer K, then each cell on the same row containing an integer<K, must be accompanied by a "mate" -- the cell immediately above it -- also with contents <K. 2. the ordering must be such that the integers increase going upward within each column. ("vertical monotonicity.") They are as follows: N=2: 1 N=3: 2 1 3 N=4: 4 2 5 1 3 6 3 2 5 1 4 6 N=5: 7 4 8 2 5 9 1 3 6 10 6 4 8 2 5 9 1 3 7 10 6 4 7 2 5 9 1 3 8 10 5 4 8 2 6 9 1 3 7 10 5 4 7 2 6 9 1 3 8 10 7 3 8 2 5 9 1 4 6 10 6 3 8 2 5 9 1 4 7 10 6 3 7 2 5 9 1 4 8 10 5 3 8 2 6 9 1 4 7 10 5 3 7 2 6 9 1 4 8 10 4 3 8 2 6 9 1 5 7 10 4 3 7 2 6 9 1 5 8 10 And the sequence giving the numbers of allowable orderings begins (for N=1,2,3,4,5,6,7): 1, 1, 1, 2, 12, 286, 33592 which agrees with OEIS https://oeis.org/A003121 "strict ballot numbers". Formula known and stated there, and indeed grows SuperExponentially(N^2) as I had originally conjectured. Well, isn't that nifty. So for any NxN orthogonal matrix, there are at least F(N) ways to write it as a product of N*(N-1)/2 terms, each a 2x2 rotation for adjacent coordinates, where F(N) is the sequence above... Indeed more strongly, if the matrix is generic there are exactly F(N) ways to multiply the orthog by 2x2s on the left, N*(N-1)/2 of them in all, each involving adjacent coordinates, such that the strict lower triangle gets zeroed one entry at a time, never unzeroing. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
participants (1)
-
Warren D Smith