$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$?

  • $\begingroup$ If $n=1$, neither are achievable. $\endgroup$ – T.J. Gaffney Dec 20 '13 at 20:03
  • $\begingroup$ @DavideGiraudo: You misunderstood my question. I am asking for $\sigma$ running over the whole symmetric group (of permutations), not just one permutation. $\endgroup$ – Hans Dec 20 '13 at 20:07
  • $\begingroup$ @Gaffney: $n$ can not be $1$ because, it does not satisfy the premise. $\endgroup$ – Hans Dec 20 '13 at 20:08
  • $\begingroup$ @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? $\endgroup$ – Davide Giraudo Dec 20 '13 at 20:16
  • $\begingroup$ @DavideGiraudo: Yes. I have edited the question and added two more sub-questions. Hopefully, it is clearer now. $\endgroup$ – 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.)

  • $\begingroup$ 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$? $\endgroup$ – Hans Dec 20 '13 at 20:29
  • $\begingroup$ Added a bit on the case -1; for this case evidently the parity doesn't matter. $\endgroup$ – user21467 Dec 20 '13 at 20:36
  • $\begingroup$ 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$. $\endgroup$ – user21467 Dec 20 '13 at 20:39
  • $\begingroup$ I see your point. What can one say about the closeness of $|s(\sigma)|$ to $0$? $\endgroup$ – Hans Dec 20 '13 at 20:45
  • 1
    $\begingroup$ Added an upper bound for that. $\endgroup$ – user21467 Dec 20 '13 at 22:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.