I wrote:
<<<
For even-length convolutions, this trick fails, since we can only flip
an even number of signs this way, and a length-n acyclic has precisely
n*(n-1)/2 minuses, which is always an odd number.
>>>
Whoops, I'm afraid I let my typng get ahead of my brain there. That
should read "n*(n-1)/2 minuses, which *may* be an odd number, e.g.
for n=2 and n=6." The reason we always have a chance to flip all the
minus signs when n is odd (in which case the number of minuses may
again be odd or even) is this: if we write the individual multiplies
of an acyclic convolution together with their signs as discrete
entries in an n x n table, then each element of the A-vector appears
precisely n times, and multiplies each elemnt of B. Flipping the sign
of a single element of A or B induces n sign changes in the table.
Of course flipping the sign of more than one input element may cause
certain signs to get flipped multiple times, but the parity is not
changed, i.e. k sign flips on the input elements results in a net
number of sign changes which == k*n modulo 2. If n is odd, we can
effect an even or odd number of sign flips this way, but if n is
even, we can only effect an even number. Of course even if n*(n-1)/2
is even, this is no guarantee that we can convert the acyclic into
a cyclic this way.
Consider n=4: the outputs of the acyclic convolution are
x^0: a0.b0-a1.b3-a2.b2-a3.b1
x^1: a0.b1+a1.b0-a2.b3-a3.b2
x^2: a0.b2+a1.b1+a2.b0-a3.b3
x^3: a0.b3+a1.b2+a2.b1+a3.b0
Can anyone find a pattern of sign flips on the aj and bk which
makes all the signs above positive?
-Ernst
