From: Veit Elser <ve10@cornell.edu> Here's a question about orthogonal matrices. Consider orthogonal matrices U of size NxN with the following "energy": E(U) = -sqrt(N) sum_{i j} |U_i j| (the negative sum of the absolute values of all the elements, appropriately scaled). The lowest energy matrices are Hadamard matrices, as these have equal-magnitude elements. We'll consider only N where Hadamard matrices exist.

Let U_0 and U_1 be any two distinct Hadamard matrices, so two ground states of our energy function. Let U(t) be a continuous curve between these two matrices, i.e. U(0)=U_0 and U(1)=U_1. Here's the question: find a good lower bound on the "energy barriers" between ground states: the maximum over t, of E(U(t))-E(U(0)).

For the 2x2matrix 1 0 0 1 we have E = -2*sqrt(2) while for the 2x2 matrix +1 -1 -1 +1 / sqrt(2) we have E = -4, confirming V.E's claim for this one case anyhow. Re barrier, any Hadamard matrix of size N>=4 has size divisible by 4 and any 3 of its rows wlog are of the form 11111111111111111111 1111111111---------- 11111-----11111----- where - stands for -1. If we were to do the Givens rotation on the first two (wlog) of those rows we'd reach at the halfway point 00000000001111111111 11111111110000000000 * sqrt(2) which is a barrier height of (2-sqrt2)*N=0.585786*N above the ground energy -N*N. The four kinds of columns can be thought of as the 4 vertices of the top face of the cube [-1,+1]^3. If we rotate the cube about (say) the y axis (010) by 90 degrees, that is just a Givens rotation with aforementioned barrier=(2-sqrt2)*N=0.585786*N. We could instead rotate it about a 3-fold axis like (111) by 120 degrees, with barrier=(2/3)*N=0.666667*N. Or about a 2-fold axis like (110) by 180 degrees, with barrier=1*N. So this tentatively makes it appear that the Givens plan is best possible.