9

Let $a_{i},b_{i}\in [p,q](p,q>0),i=1,2,3,...,n$,($n$ is given number,and $p,q$ is given too) and such that $$\sum_{i=1}^{n}a^2_{i}=\sum_{i=1}^{n}b^2_{i}$$ Find the minimum of the $$\dfrac{\displaystyle\sum_{i=1}^{n}a_{i}b_{i}}{\displaystyle\sum_{i=1}^{n}a^2_{i}}$$

Thank you!

When $n=1$,then

$$\dfrac{\displaystyle\sum_{i=1}^{n}a_{i}b_{i}}{\displaystyle\sum_{i=1}^{n}a^2_{i}}=\dfrac{a_{1}b_{1}}{a^2_{1}}=1$$ because $a^2_{1}=b^2_{1}.$

When $n=2$, $$\dfrac{\displaystyle\sum_{i=1}^{n}a_{i}b_{i}}{\displaystyle\sum_{i=1}^{n}a^2_{i}}=\dfrac{a_{1}b_{1}+a_{2}b_{2}}{a^2_{1}+a^2_{2}}$$

After using Polya-szego inequality,we have $$(a^2_{1}+a^2_{2})(b^2_{1}+b^2_{2})\le \dfrac{1}{4}\left(\sqrt{\dfrac{q^2}{p^2}}+\sqrt{\dfrac{p^2}{q^2}}\right)^2(a_{1}b_{1}+a_{2}b_{2})^2$$ so $$\dfrac{a_{1}b_{1}+a_{2}b_{2}}{a^2_{1}+a^2_{2}}\ge \dfrac{2pq}{p^2+q^2}$$

this polya-szego inequality(link) can usefull to solve this problem for $n=2k$

,but for $n=2k+1$ is not usefull,Thank you

math110
  • 93,304
  • 1
    For $n=2$, the minimum seems $\dfrac{2pq}{p^2+q^2}$. – Macavity May 02 '14 at 14:56
  • Have you tried minimizing $\sum a_i b_i$ and maximizing $\sum a_i^2?$ – Sugata Adhya May 02 '14 at 15:03
  • @Macavity, if you alternate between $p$ and $q$ for both sequences, you also get $2 p q / (p^2 + q^2)$, whatever $n$ may be. This looks like the minimum. – vonbrand May 02 '14 at 15:12
  • @vonbrand Yes - for even $n$ that works. The Polya-Szego link math110 gave says the same thing for all $n$. So it should be true that $\dfrac{2pq}{p^2+q^2}$ is the minimum, but we need to prove. – Macavity May 02 '14 at 15:16
  • @vonbrand When $n$ is even, the link shows it is the minimum. It remains to see whether this can be achieved when $n$ is odd, that is, if $n=3$. – Did May 02 '14 at 15:16
  • Who says $n$ has to be even for the Polya-Szegö inequality to hold? – Christian Blatter May 02 '14 at 15:34
  • @Macavity, you are right. That works only for even $n$. – vonbrand May 02 '14 at 15:34
  • 1
    @ChristianBlatter You can't attain equality in the P-S inequality if $n$ is odd (in the context of this problem). And if you can't attain equality, then the minimum we seek is not given by the inequality, it just gives a lower bound. – Macavity May 02 '14 at 15:42
  • 1
    Conjecture: when $n=2k+1$ the minimum is reached by adding one entry $p$ to the $(a_i)$ and the $(b_i)$ that are optimal for $n=2k$. Example: $n=3$, $(a_i)=(p,q,p)$, $(b_i)=(q,p,p)$. – Did May 02 '14 at 15:59
  • @Macavity: Thank you for the clarification. – Christian Blatter May 02 '14 at 16:25
  • Which values are fixed, and which are we free to choose? It's not clear from the question. – user2357112 May 04 '14 at 15:37
  • This question seems to have a simple geometric interpretation as finding two equal-length vectors with endpoints inside a given hypercube and with the greatest possible angle between them. After playing around with a Rubik's cube for a bit, I believe the odd-dimensional case is much less simple than the even-dimensional case. In the even case, the vectors in the hypercube with the greatest angle between them happen to have equal length. In the odd case, this convenient thing does not happen. – user2357112 May 04 '14 at 15:50

1 Answers1

5

Let $a_i, b_i\in[p,q]$, $0<p<q$, $i=1,2,3,\dots n$ and $\sum_{i=1}^{n}a_i^2 = \sum_{i=1}^{n}b_i^2$. The following statement is valid:

The minimum of the expression

\begin{equation*} C_{a,b}:=\frac{\sum_{i=1}^{n}a_ib_i}{\sum_{i=1}^{n}a_i^2} = \begin{cases} \frac{2pq}{p^2+q^2} & \text{if }n=2k,\\ &\\ \frac{(2k+1)pq}{(k+1)p^2+kq^2} & \text{if } n=2k+1. \end{cases} \end{equation*}

Note: The following answer is an elementary approach based on $\mathbb{R^n}$ as Euclidean vector space. One argument is heuristic, so it's not a complete proof. But I do hope to present the main ideas in a proper way, so that a complete proof should be derivable. The answer is done in four steps:

Step 1: Geometrical interpretation using scalar products in Euclidian Space $\mathbb{R}^n$ to observe, that minimizing the expression is the same as maximizing the angle between the position vectors $a=(a_i)_{i=1}^{n}$ and $b=(b_i)_{i=1}^{n}$.

Step 2: Heuristic argument that the angle is maximized iff specific vertices of the Hypercube $H=[p,q]^n$ are attained.

Step 3: Not all vertices are proper. If $a$ and $b$ have equal length, they have the same number of $p$'s and the same number of $q$'s. Let's say $k$ $p$'s and $n-k$ $q$'s. Here we show that the expression $C_{a,b}$ is minimal among those pairs, which have as few as possible coordinates of $a$ and $b$ with equal values. So, e.g. $C_{(p,p,p,q,q),(q,q,p,p,p)} \leq C_{(p,p,p,q,q),(p,q,p,p,q)}$

Step 4: We show, that the expression $C_{a,b}$ of vertices $a$ and $b$ is minimal, iff the number of $p$'s is equal to the number of $q$'s in $a,b$ in case $n$ is even and the number of $p$'s is $1$ more than the number of $q$'s in $a,b$ in case $n$ is odd.

Result: $C_{a,b}$ attains the minimum at $\binom{2k}{k}$ vertices $a,b$ with the number of $p$'s equal to the number of $q$'s and at $\binom{2k+1}{k}$ vertices with $a,b$ with the number of $p$'s $1$ more than the number of $q$'s in case $n=2k+1$, with the minimum $C_{a,b}$ as stated above.

And now the gory details:

Step 1: Geometrical interpretation using scalar products in Euclidian Space $\mathbb{R}^n$

Let's consider $a=(a_i)_{i=1}^{n}$, $b=(b_i)_{i=1}^{n}$ being vectors in the Euclidian space $\mathbb{R}^n$, with $\sum_{1\leq i \leq n}a_i^2=\sum_{1\leq i \leq n}b_i^2$, i.e. $a$ and $b$ having the same length $\Vert a \Vert=\Vert b \Vert$.

Let $0<p<q$ and $a,b \in [p,q]^n$

Task: Find $a,b$, so that $$C_{a,b}=\frac{\sum_{i=1}^{n}a_{i}b_{i}}{\sum_{i=1}^{n}a_i^2}\rightarrow\text{min}$$

Observe that $$C_{a,b}=\frac{<a,b>}{\Vert a\Vert^2}=\frac{\Vert b \Vert}{\Vert a \Vert}\cos (a,b)$$ So, $C_{a,b}$ is the scaling factor of the vector $a$ when $b$ is orthogonally projected to $a$. This implies: $$b-C_{a,b}a=b-\frac{<a,b>}{\Vert a\Vert^2}a \perp a$$ Therefore we have to find $a,b$ so that the scaling factor becomes a minimum. Since the $\cos$ is monotonically decreasing in $[0,\frac{\pi}{2}]$, this holds, iff the angle between $a$ and $b$ becomes a maximum.

Step 2: $C_{a,b}$ reaches a minimum if $a,b$ are specific vertices of the hypercube $H=[p,q]^n$.

The following argument is only heuristic, not a strict proof.

Let's consider $a,b$ being inside the hypercube $H=[p,q]^n$. In this case we can consider a line going through $a$ and $b$ and use the intersection points with faces of $H$ to get $a^{\prime}$ and $b^{\prime}$. Since the angle $\measuredangle(a^{\prime},0,b^{\prime})$ is greater than $\measuredangle(a,0,b)$ we can without loss of generality assume, that $a,b$ are points on the faces of $H$.

Next we consider a plane going through $a^{\prime},0$ and $b^{\prime}$. This plane intersects certain edges of $H$ where we can find $a^{\prime\prime}$ and $b^{\prime\prime}$, so that $\measuredangle(a^{\prime\prime},0,b^{\prime\prime})$ is greater than $\measuredangle(a^{\prime},0,b^{\prime})$.

Argumenting the same way we now walk along the edges of $H$ till we reach proper vertices $a^{\prime\prime\prime}$ and $b^{\prime\prime\prime}$, so that $\measuredangle(a^{\prime\prime\prime},0,b^{\prime\prime\prime})$ is greater than $\measuredangle(a^{\prime\prime},0,b^{\prime\prime})$.

So, we can without loss of generality assume that the points $a,b$ have to be vertices of the hypercube $H$ in order that $C_{a,b}$ attains a minimum.

$$$$

Step 3: Let's assume $a,b$ are vertices of $H$ with the same length $\Vert a\Vert=\Vert b\Vert$. So, they have an equal number of $p$'s and an equal number of $q$'s as coordinates. For the $i$-th coordinate the $a_i$ and $b_i$ are either equal ($a_i=b_i=p$ or $a_i=b_i=q$) or they may be different. We show, that $C_{a,b}$ attains a minimum iff as few as possible coordinates of $a$ and $b$ have equal coordinate values.

So, let's consider for $1\leq i\leq j\leq n$, two pairs $a_1,b_1$ and $a_2,b_2$ which are coordinate-wise equal except at the $i$-th and $j$-th position. We have $a_1=(\dots,p,\dots,q,\dots), b_1=(\dots,q,\dots,p,\dots)$ with different coordinates at the $i$-th and $j$-th position and $a_2=(\dots,p,\dots,q,\dots), b_2=(\dots,p,\dots,q,\dots)$ of vertices with equal coordinates at the $i$-th and $j$-th position.

Now $C_{(a_1,b_1)} < C_{(a_2,b_2)}$ is valid, because this inequality simplifies to

\begin{align*} C_{((\dots,p,\dots,q,\dots),(\dots,q,\dots,p,\dots))}&<C_{((\dots,p,\dots,q,\dots),(\dots,p,\dots,q,\dots))}\\ \frac{A+2pq}{B+p^2+q^2}&<\frac{A+p^2+q^2}{B+p^2+q^2}\\ 0&<(p-q)^2 \end{align*}

with $A,B$ taken accordingly. So, the minimum $C_{(a,b)}$ is attained if $a,b$ have as few as possible equal coordinates. In the following we may therefore without loss of generality assume, that $a,b$ are chosen this way.

Step 4: Let $a,$b be vertices of the hypercube $H=[p,q]^n$ with equal length. So, the number of $p$'s in $a$ is equal to the number of $p$'s in $b$. Now, $C_{a,b}$ becomes minimal, iff the number of components of $a,b$ attaining $p$ is equal to the number of components attaining $q$ in case $n$ is even. In case $n$ is odd, $a,b$ have to contain one $p$ more than the number of $q$'s.

A plausible argument for this statement: The number of vertices with $k$ $p\text{'s}$ and $n-k$ $q\text{'s}$ is $\binom{n}{k}$ and since the binomial coefficients are a unimodal sequence attaining it's maximum at $n/2$, we get the largest number of vertices of the hypercube with equal length if the number of $p\text{'s}$ is half of $n$. In this case we have the greatest spreading and so the best chance to maximize the angle $\measuredangle(a,b)$. In case of $n=2k+1$ odd, we have additionally to analyse if we reach the maximal angle with $k+1$ $p\text{'s}$ and $k\ q\text{'s}$ or with $k\ p\text{'s}$ and $k+1\ q\text{'s}$

To motivate the following calculations we first consider examples $n=5$ and $n=6$, for odd and even $n$.

$n=5$: Here we consider following variants of $a$ and $b$ and use $t:=\frac{p}{q}$ with $0 < t < 1$.

\begin{align*} C_{a,b}&=C_{(p,p,p,p,q),(q,p,p,p,p)}=\frac{3p^2+2pq}{4p^2+q^2}=\frac{3t^2+2t}{4t^2+1}\qquad&4\ p\text{'s}\\ C_{a,b}&=C_{(p,p,p,q,q),(q,q,p,p,p)}=\frac{p^2+4pq}{3p^2+2q^2}=\frac{t^2+4t}{3t^2+2}\qquad&3\ p\text{'s}\\ C_{a,b}&=C_{(p,p,q,q,q),(q,q,q,p,p)}=\frac{4pq+q^2}{2p^2+3q^2}=\frac{4t+1}{2t^2+3}\qquad&2\ p\text{'s}\\ C_{a,b}&=C_{(p,q,q,q,q),(q,q,q,q,p)}=\frac{2pq+3q^2}{p^2+4q^2}=\frac{2t+3}{t^2+4}\qquad&1\ p\\ \end{align*}

$n=6$:

\begin{align*} C_{a,b}&=C_{(p,p,p,p,p,q),(q,p,p,p,p,p)}=\frac{4p^2+2pq}{5p^2+q^2}=\frac{4t^2+2t}{5t^2+1}\qquad&5\ p\text{'s}\\ C_{a,b}&=C_{(p,p,p,p,q,q),(q,q,p,p,p,p)}=\frac{2p^2+4pq}{4p^2+2q^2}=\frac{2t^2+4t}{4t^2+2}\qquad&4\ p\text{'s}\\ C_{a,b}&=C_{(p,p,p,q,q,q),(q,q,q,p,p,p)}=\frac{6pq}{3p^2+3q^2}=\frac{6t}{3t^2+3}\qquad&3\ p\text{'s}\\ C_{a,b}&=C_{(p,p,q,q,q,q),(q,q,q,q,p,p)}=\frac{4pq+2q^2}{2p^2+4q^2}=\frac{4t+2}{2t^2+4}\qquad&2 p\text{'s}\\ C_{a,b}&=C_{(p,q,q,q,q,q),(q,q,q,q,q,p)}=\frac{2pq+4q^2}{p^2+5q^2}=\frac{2t+4}{t^2+5}\qquad&1 p\\ \end{align*}

You may observe, that we use not all possible variants, but only those, where $a_i$ and $b_i$ do attain different values on the same index-position whenever possible, according to the result of Step 3.

Now we have to split the even and odd case again in a left half (of the negative unimodal sequence $C_{a,b}$) and a right half. So we can show, that the minimum is in the middle of the sequence under consideration.

Now, when looking at the examples above, the following formulas should be reasonable:

Let $n=2k$. We consider the sequences

\begin{align*} A_k(l)&:=\frac{(2k-2l)t^2+2lt}{(2k-l)t^2+l}\qquad&1\leq l \leq k\\ B_k(l)&:=\frac{(2k-2l)+2lt}{(2k-l)+lt^2}\qquad&1\leq l \leq k \end{align*}

Please note, that $A_k(l)$ corresponds to the left half of the example $n=6$ above and that $B_k(l)$ corresponds to the right half. Furthermore you may observe that $A_k(k)=B_k(k)$.

The following statement is valid: \begin{align*} A_k(l+1)<A_k(l)\\ \end{align*} because the corresponding inequality \begin{align*} \frac{(k-l-1)t^2+(l+1)t}{(2k-l-1)t^2+(l+1)}< \frac{(k-l)t^2+lt}{(2k-l)t^2+l}\qquad\qquad1\leq l \leq k\\ \end{align*} simplifies to $0<(t-1)^2$.

Similarly we can show, that for $1\leq l \leq k$ \begin{align*} B_k(l+1)&<B_k(l)\\ \end{align*} because the inequality \begin{align*} \frac{(k-l-1)+(l+1)t}{(2k-l-1)+(l+1)t^2} &< \frac{(k-l)+lt}{(2k-l)+lt^2}\qquad\qquad1\leq l \leq k\\ \end{align*} also simplifies to $0<(t-1)^2$.

The case for $n=2k+1$ can be done analogously. It can be shown, that for

\begin{align*} C_k(l)&:=\frac{(2k-2l+1)t^2+2lt}{(2k-l+1)t^2+l}\qquad&1\leq l \leq k\\ D_k(l)&:=\frac{(2k-2l+1)+2lt}{(2k-l+1)+lt^2}\qquad&1\leq l \leq k\\ \\ C_k(l+1) &< C_k(l)\qquad\text{and}\qquad D_k(l+1) < D_k(l)& \end{align*}

One notable difference to the case $n$ even is, that

$$C_k(k) = \frac{t^2+2kt}{(k+1)t^2+k} \ne \frac{1+2kt}{(k+1)+kt^2} = D_k(k)$$

This corresponds to the fact that in case of $C_k(k)$ $a$ and $b$ contain $k+1$ $p'$s and $k$ $q$'s, while $D_k(k)$ implies that $a$ and $b$ contain $k$ $p$'s and $k+1$ $q$'s.

Now, it can be easily shown, that $C_k(k) < D_k(k)$ again by simplifying the corresponding inequality $\frac{t^2+2kt}{(k+1)t^2+k} < \frac{1+2kt}{(k+1)+kt^2}$ to $0<(t-1)^2$.

Finally, the conclusion is:

The minimum of $C_{a,b}$ is attained in case of even $n=2k$ for $\binom{2k}{k}$ vertices of $H$, with $k$ coordinates equal to $p$ and $k$ coordinates equal to $q$, whereby $a$ and $b$ have different coordinate values $p$ and $q$ at each index position. In case of odd $n=2k+1$ the minimum of $C_{a,b}$ is attained for $\binom{2k+1}{k}$ vertices of $H$, with $k+1$ coordinates equal to $p$ and $k$ coordinates equal to $q$, again $a$ and $b$ having different coordinate values at the same index position whenever possible. For these vertices $C_{a,b}$ attains the values:

\begin{equation*} C_{a,b}=\frac{\sum_{i=1}^{n}a_ib_i}{\sum_{i=1}^{n}a_i^2} = \begin{cases} \frac{2pq}{p^2+q^2} & \text{if }n=2k,\\ &\\ \frac{(2k+1)pq}{(k+1)p^2+kq^2} & \text{if } n=2k+1. \end{cases} \end{equation*}

Markus Scheuer
  • 108,315
  • Cool! Though if I'm not mistaken $C_k(k) \lt D_k(k)$ and thus following your argumentation the minimum should be attained with $k+1$ $p$'s and $k$ $q$'s.

    This would be in line with the reasoning that $$p \lt q \implies \frac{\mathit{min}+p^2}{\mathit{max}+p^2} \lt \frac{\mathit{min}+q^2}{\mathit{max}+q^2}.$$

    – vuur May 08 '14 at 23:20
  • @vuur: Thanks a lot! Of course you're right and so I corrected my answer accordingly. Best regards. – Markus Scheuer May 09 '14 at 08:46
  • oh,Nice solution! Thank you +1 – math110 May 09 '14 at 08:51
  • @math110: Thanks! You're welcome! Best regards. – Markus Scheuer May 09 '14 at 09:06