Let's define for every pair of vectors $u,v\in\mathbb{R}^n$, a quantity as follows: $$f(u,v) = \sum_{1\leq i,j\leq n}|u_iu_j-v_iv_j|.$$

I want to find: $$M(n)= \max \{f(u,v): u,v\in \mathbb{R}^n, |u|=|v|=1, u\perp v\}.$$

An easy estimate using the triangle inequality gives $M(n) <2n$, but it seems there should be better upper bounds.

Remark. 1) Let $a = \cos(\pi/8), b = \sin(\pi/8)$, then if for even numbers $n$ we define the vectors $u = \sqrt{\frac{2}{n}}(a,b,a,b,\dots)$ and $ v = \sqrt{\frac{2}{n}}(b,-a,b,-a,\dots)$, we have $f(u,v)=\sqrt{2}n\leq M(n)$. 2)A similar construction shows that for every positive integers $n,k$, $\frac{M(n)}{n}\leq \frac{M(nk)}{nk}.$


2 Answers 2


Just use Cauchy-Schwarz and the identity $$ \sum_{i,j}(u_iu_j-v_iv_j)^2=\left[\sum_i u_i^2\right]^2+\left[\sum_i v_i^2\right]^2-2\left[\sum_i u_iv_i\right]^2=2 $$ to get $f(u,v)\le \sqrt2 n$ for all $n$. As you have observed yourself, this is sharp for even $n$. For odd $n$ you can, probably, do a bit better but the estimates get messy and it is not clear (to me) what the sharp bound really is.

  • $\begingroup$ How does one apply Cauchy-Schwarz to the problem? $\endgroup$ Nov 3, 2018 at 11:51
  • 1
    $\begingroup$ @ClaudeChaunier The sum of absolute values of $n^2$ real numbers does not exceed $n$ times the square root of the sum of their squares. $\endgroup$
    – fedja
    Nov 3, 2018 at 17:59

Numerical approximations suggest $M(n)=\sqrt{2n^2-1}$ when $n$ is odd, with the max reached for some $u=(a,b,a,b,\dots,a)$, $v=(c,d,c,d,\dots,c)$. Solving exactly for such $u,v$ is easy and only implies a quadratic equation in one variable, $x=b^2$ for instance. Assuming $b>d>0$ without loss of generality, one finds $b^2 = \frac{1}{n-1}(1+\frac{n}{\sqrt{2n^2-1}})$ and deduce $a,c,d$ from the constraints $|u|=|v|=1$ and $u\cdot v=0$, yielding $M(n)\ge \sqrt{2n^2-1}$ when $n$ is odd. Now we still must show that more $a$ in $u$ or more than two distinct components in $u$ cannot improve the bound.

EDIT: Here are elementary details on an analysis for $u$ and $v$ restricted to
$$u=(a,a,\dots,a,b,b,\dots,b)\in\{a\}^{k}\times\{b\}^{\ell}$$ $$v=(c,c,\dots,c,d,d,\dots,d)\in\{c\}^{k}\times\{d\}^{\ell}$$ with $k+\ell=n$ odd or even and $0\lt d\le b$ and $0\lt a\le -c$.

$\langle u|u\rangle = \langle v|v\rangle = 1$ and $\langle u|v\rangle = 0$ translate into $$ka^2+\ell b^2 = 1$$ $$kc^2+\ell d^2 = 1$$ $$kac+\ell bd = 0$$ hence $$(kac)^2 = (\ell bd)^2 = (\ell b^2)(\ell d^2) = (1-ka^2)(1-kc^2)$$ simplifies into $$ka^2+kc^2 = 1$$ and likewise $$\ell b^2+\ell d^2 = 1$$ Furthermore $$\begin{matrix} k\ell(ab)^2 &=& (ka^2)(\ell b^2) &=& (1-\ell b^2)(\ell b^2) & &\\ k\ell(cd)^2 &=& (kc^2)(\ell d^2) &=& (1-\ell d^2)(\ell d^2) &=& (\ell b^2)(1-\ell b^2)\\ \end{matrix}$$ hence $0\lt 1-\ell b^2$ and $$ab = -cd = \sqrt{\frac{b^2-\ell b^4}{k}}$$

This all enables to write $$f(u,v) = k^2(c^2-a^2)+\ell^2(b^2-d^2)+2k\ell(ab-cd)$$ $$= k(1-2ka^2)+\ell(2\ell b^2-1)+4k\ell ab$$ $$= k(2\ell b^2-1)+\ell(2\ell b^2-1)+4k\ell ab$$ and finally $$f(u,v) = g(x) := 2n\ell x -n + 4\ell\sqrt{k}\sqrt{x-\ell x^2}$$ where $0\lt x=b^2\lt \frac{1}{\ell}$. Actually $b^2$ cannot be arbitrarily close to $0$ because from our assumptions $$1 = \ell b^2+\ell d^2 \le 2\ell b^2$$ thus $$\frac{1}{2\ell}\le x=b^2\lt \frac{1}{\ell}$$

Now $$g'(x)=2n\ell + 2\ell\sqrt{k}\frac{1-2\ell x}{\sqrt{x-\ell x^2}}$$ starts positive and goes toward $-\infty$ on the mentioned interval for $x$, therefore $g(x)$ and $f(u,v)$ will be maximal when $g'(x)=0$, which happens when $$ 2\ell x-1 = \frac{2n\ell}{2\ell\sqrt{k}}\sqrt{x-\ell x^2}$$ or equivalently on the prescribed interval $$ (2\ell x-1)^2 = \frac{n^2}{k}(x-\ell x^2)$$ which is the quadratic equation $$x^2-\frac{1}{\ell}x+\frac{k}{\ell(4k\ell+n^2)} = 0$$ whose solutions are $$x_\pm = \frac{1}{2\ell} \pm \frac{1}{2}\sqrt{\frac{1}{\ell^2}-\frac{4k}{\ell(4k\ell+n^2)}}$$ $$= \frac{1}{2\ell} \pm \frac{1}{2}\sqrt{\frac{4k\ell+n^2-4k\ell}{\ell^2(4k\ell+n^2)}}$$ $$= \frac{1}{2\ell} \left(1 \pm \frac{n}{\sqrt{4k\ell+n^2}}\right)$$ where only $x_+$ is in $[\frac{1}{2\ell},\frac{1}{\ell})$. The maximum is then $$g(x_+) = \frac{n^2}{\sqrt{4k\ell+n^2}} + 4\ell\sqrt{k}\sqrt{x_+-\ell x_+^2}$$ The constant coefficient in the quadratic equation is also $x_+x_-$ thus $$x_+-\ell x_+^2=x_+(1-\ell x_+)=x_+(\ell x_-)=\ell x_+x_- = \frac{k}{4k\ell+n^2}$$ yields $$g(x_+) = \frac{n^2+4\ell k}{\sqrt{4k\ell+n^2}} = \sqrt{4k\ell+n^2}$$

In the end, when $u$ and $v$ are restricted to the shapes above, $f(u,v)$ is maximal for $$a = +\sqrt{\frac{1}{2k} \left(1 - \frac{n}{\sqrt{4k\ell+n^2}}\right)}\;, \quad b = \sqrt{\frac{1}{2\ell} \left(1 + \frac{n}{\sqrt{4k\ell+n^2}}\right)}\\ c = -\sqrt{\frac{1}{2k} \left(1 + \frac{n}{\sqrt{4k\ell+n^2}}\right)}\;, \quad d = \sqrt{\frac{1}{2\ell} \left(1 - \frac{n}{\sqrt{4k\ell+n^2}}\right)}\\ $$ and the maximum is $$f(u,v)=\sqrt{4k\ell+n^2}$$ Now allowing $k$ and $\ell=n-k$ to vary for $n$ fixed, one gets that $f(u,v)=\sqrt{4k\ell+n^2}$ is maximum over $k$ for $k=n/2$ when $n$ is even, in which case $f(u,v)=\sqrt{2n^2}$, and $k=(n\pm1)/2$ when $n$ is odd, in which case $f(u,v)=\sqrt{2n^2-1}$. We still have to show that other shapes for $u$ and $v$ cannot improve $f(u,v)$.


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.