# Range of inner product of a sequence and its permutation

$a^n :=(a_i)_1^n$ is a finite sequence of real numbers of length $n$, where $\sum\limits_{i=1}^n a_i=0$ and $\sum\limits_{i=1}^n a_i^2=1$. Consider $s_n(a^n,\sigma):=\sum\limits_{i=1}^n a_ia_{\sigma(i)}$ where $\sigma$ runs over $S_n$ the symmetric group of order $n$ (set of permutations of $(1,2,3,...,n)$). Obviously, it is no less than $-1$ by the Cauchy-Schwarz inequality. Is $-1$ always achievable? Is $0$ always achievable? Please give examples when the answers to the previous questions are in the negative. What is the minimum of $s_n(a^n,\sigma)$? What is the minimum of $|s_n(a^n,\sigma)|$?

Below, Steven Taschuk has answered the above questions. Here is a new question. What is $\sup\limits_{a^n}\min\limits_{\sigma\in S_n}\left|s_n(a^n,\sigma)\right|$? What is its asymptotics as $n\rightarrow\infty$?

• If $n=1$, neither are achievable. – T.J. Gaffney Dec 20 '13 at 20:03
• @DavideGiraudo: You misunderstood my question. I am asking for $\sigma$ running over the whole symmetric group (of permutations), not just one permutation. – Hans Dec 20 '13 at 20:07
• @Gaffney: $n$ can not be $1$ because, it does not satisfy the premise. – Hans Dec 20 '13 at 20:08
• @Hansen So what is given is the sequence $(a_i)$ with the two conditions. And you ask whether there is a permutation such that $\sum a_ia_{\sigma(i)}=0$ (resp $-1$), don't you? – Davide Giraudo Dec 20 '13 at 20:16
• @DavideGiraudo: Yes. I have edited the question and added two more sub-questions. Hopefully, it is clearer now. – Hans Dec 20 '13 at 20:18

$a=\frac1{\sqrt6}(1,1,-2)$ is a counterexample for both.

(There are really only two cases to consider, $\langle(1,1,-2),(1,1,-2)\rangle$ and $\langle(1,1,-2),(1,-2,1)\rangle$.)

Edit: More on the case $-1$: By the equality case of the Cauchy-Schwarz inequality, the only way to get $\langle a,a^\sigma\rangle=-1$ is if $a$ and $-a$ are permutations of each other. The only way that can happen is if $a$ is a permutation of $(v,-v)$ (if $n$ even) or of $(v,-v,0)$ (if $n$ odd), where $v\in\mathbb R^{\lfloor n/2\rfloor}$. We automatically get $\sum_i a_i = 0$ in either case, and can get $\|a\|=1$ just by scaling $v$ appropriately. (These cases were described in a now-deleted answer; the point is that these are the only ones.)

Edit: More on the case $0$: For any $n\ge 4$, there are vectors $a$ with $\min |s(\sigma)|=0$, e.g., $a=\frac1{\sqrt2}(1,-1,0,0,\dotsc,0)$. (Just permute so that $a$ and $a^\sigma$ have disjoint supports. Geometrically this corresponds to the fact that the opposite edges of a regular tetrahedron (more generally, disjoint edges of a regular simplex) are perpendicular.) On the other hand, for any $n\ge 3$, there are vectors $a$ with $\min |s(\sigma)|>0$, such as $a=\frac1{\sqrt{n(n-1)}}(1,1,\dotsc,1,-n+1)$, for which $\min |s(\sigma)| = 1/(n-1)$. (Again, there are only two cases to consider.) (Geometrically such $a$ are the vertices of the regular simplex you get by projecting the standard basis vectors on the hyperplane $\sum_i x_i=0$ (and normalizing); permutations of coordinates give the symmetries of this simplex, so you can only get the inner product of a vertex with another vertex this way. So in fact in this case, $s(\sigma) = -1/(n-1)$ for any $\sigma$ other than the identity (correction: for any $\sigma$ that moves the last coordinate)).

Edit: For the question in comments, to determine $\sup_a \min_\sigma |\langle a,a^\sigma\rangle|$, here's a computation to show that it's at most $1/\sqrt{n-1}$. First we compute the average of the squares: \begin{align*} \frac1{n!} \sum_\sigma \langle a,a^\sigma\rangle^2 &= \frac1{n!} \sum_\sigma \sum_i \sum_j a_i a_j a_{\sigma(i)} a_{\sigma(j)} \\ &= \sum_i \sum_j a_i a_j \Big( \frac1{n!} \sum_\sigma a_{\sigma(i)} a_{\sigma(j)} \Big) \\ &= \sum_i a_i^2 \Big( \frac1{n!} \sum_\sigma a_{\sigma(i)}^2 \Big) + \sum_i \sum_{j\ne i} a_i a_j \Big( \frac1{n!} \sum_\sigma a_{\sigma(i)} a_{\sigma(j)} \Big) \\ &= \sum_i a_i^2 \Big( \frac1n \sum_k a_k^2 \Big) + \sum_i \sum_{j\ne i} a_i a_j \Big( \frac1{n(n-1)} \sum_k \sum_{\ell\ne k} a_k a_\ell \Big) \\ &= \frac1n \Big( \sum_i a_i^2 \Big)^2 + \frac1{n(n-1)} \Big( \sum_i \sum_{j\ne i} a_i a_j \Big)^2 \\ &= \frac1n \Big( \sum_i a_i^2 \Big)^2 + \frac1{n(n-1)} \Big( \Big(\sum_i a_i\Big)^2 - \sum_i a_i^2 \Big)^2 \\ &= \frac1n + \frac1{n(n-1)} = \frac1{n-1} \end{align*} Thus $$\min_\sigma |\langle a,a^\sigma\rangle| = \sqrt{\min_\sigma \langle a,a^\sigma\rangle^2} \le \sqrt{\frac1{n!} \sum_\sigma \langle a,a^\sigma\rangle^2} = \frac1{\sqrt{n-1}}$$ I'm not sure whether this is sharp. (Well, you could shave off a tiny bit by excluding the identity from the average; I mean I'm not sure whether it's asymptotically sharp.)

• Very nice! Does the parity of $n$ matter? Does the magnitude of $n$ affect the closeness of the value $s(\sigma)$ to $0$ and $-1$? – Hans Dec 20 '13 at 20:29
• Added a bit on the case -1; for this case evidently the parity doesn't matter. – user21467 Dec 20 '13 at 20:36
• Re magnitude of $n$: I'm not sure what you're asking. The minimum of $s(\sigma)$ depends on $a$; for any $n$, there are $a\in\mathbb R^n$ with $\min s(\sigma)=-1$ and $a$ with $\min s(\sigma)>-1$. – user21467 Dec 20 '13 at 20:39
• I see your point. What can one say about the closeness of $|s(\sigma)|$ to $0$? – Hans Dec 20 '13 at 20:45
• Added an upper bound for that. – user21467 Dec 20 '13 at 22:49