Sum(Permutation*Inverse)
Leroy Quet
Let {c(k)} be the inverse-permutation of {b(k)}.
(ie. b(c(j)) =j, for every j.)
Which {b(k)},{c(k)}('s), for any particular m,
MINIMIZE the sum:
sum{k=1 to m} b(k) * c(k) ?
For example, if b is:
[1,2,3],
[2,1,3],
[3,2,1],
each give a sum of 14.
but
[2,3,1],
[3,1,2],
(which are inverses of each other)
both give a sum of 11.
I highly suspect that the generalized solution-pair is
[m,1,m-2,3,m-4,5, ....,m-5,4,m-3,2,m-1]
and
[2,m-1,4,m-3,6,m-5, ....,m-4,5,m-2,3,m,1],
where there is an extra odd term in the center if m= odd integer.
(Either sequence represents {b(k)}, the other{c(k)}, of course.)
Can this conjecture be rigorously proved??
thanks,
Leroy
Quet
Rob Johnson
I think it is clearer if we apply b to the index set of the sum and try
to minimize
m
---
> k b(b(k)) [1]
---
k=1
instead. Of course, to minimize the sum
m
---
> k c(k) [2]
---
k=1
c should switch k and m-k+1. Consider instead a permutation d where
d(m) = k and d(j) = 1. This cannot be minimal since just switching
these assignments gives a smaller sum:
d(m) = k and d(j) = 1: j*d(j) + m*d(m) = j + mk
d(m) = 1 and d(j) = k: j*d(j) + m*d(m) = jk + m
where the difference is (k-1)(m-j) in favor of d(m) = 1. A similar
argument shows that d(m-1) = 2, etc.
The question now is how close to a square root of that permutation can
we come?
If m = 0 or 1 mod 4, we can find an exact square root. If m = 2 or 3
mod 4, we can find b whose square gives a sum 1 greater than c does.
Note that when m = 2 or 3 mod 4, c is odd, so it is impossible to find
an exact square root.
If m <> 3 mod 4, let b be a product of disjoint 4-cycles
[m/4]
---
b = | | (2k-1,2k,m-2k+2,m-2k+1) [3a]
k=1
if m = 3 mod 4, throw a 3-cycle in the middle; let n = (m+1)/2
[m/4]
---
b = (n-1,n,n+1) | | (2k-1,2k,m-2k+2,m-2k+1) [3b]
k=1
In either of these cases, the square of b is c except for the middle 2
or 3 terms when m = 2 or 3 mod 4. When m = 2 mod 4, the middle 2 terms
are left alone by b^2. When m = 3 mod 4, the middle 3 terms are cycled
by b^2. Let us compute the difference of the sum in these cases.
For m = 2 mod 4, let n = m/2
b^2(n) = n and b^2(n+1) = n+1
n*b^2(n) + (n+1)*b^2(n+1) = 2n^2 + 2n + 1
whereas
c(n) = n+1 and c(n+1) = n
n*c(n) + (n+1)*c(n) = 2n^2 + 2n
For m = 3 mod 4, let n = (m+1)/2
b^2(n-1) = n+1 and b^2(n) = n-1 and b^2(n+1) = n
(n-1)*b^2(n-1) + n*b^2(n) + (n+1)*b^2(n+1) = 3n^2 - 1
whereas
c(n-1) = n+1 and c(n) = n and c(n+1) = n-1
(n-1)*c(n-1) + n*c(n) + (n+1)*c(n+1) = 3n^2 - 2
Thus, when m = 2 or 3 mod 4, the b defined in [3] makes [1] only 1
greater than [2].
Therefore, the b defined in [3] minimizes [1].
Rob Johnson <r...@trash.whim.org>
take out the trash before replying
Rob Johnson
The proof above is fine, but I did not notice that in the case when
m = 3 mod 4 that b^2(n-1) = c(n-1). Thus, b^2 and c differ only at
terms n and n+1; that is, 2 terms instead of 3. Since c is odd in
this case, it makes sense that b^2 and c differ by a single 2-cycle
and not a 3-cycle.