Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am thinking of the maximal value and minimal value of two vectors in some special case.

Following is my problem statement.

$\max\sum_{i=1}^Nx_iy_i$ and $\min\sum_{i=1}^Nx_iy_i$ subject to the conditions:

  • $x_i \geq 0$,
  • $y_i \geq 0$,
  • $x_1 \geq x_2 \geq \cdots \geq x_N$,
  • $y_1 \geq y_2 \geq \cdots \geq y_N$
  • $\lVert x\rVert_2=1$
  • $\lVert y\rVert_2=1$

I find the "descending order" constrains is quite annoying and I don't know how to handle it.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

The maximum is always $1$, which happens whenever $\vec{x}=\vec{y}$, e.g. for $x_i=y_i=\frac1{\sqrt n}$ for all $i$ or for $\vec{x}=\vec{y}=(1,0,\dots,0)$. Let $a_n$ be the desired minimum in $n$ dimensions. It measures how far apart the vectors can get, since the dot product of unit vectors is the cosine of the angle between them, and the cosine function decreases for $\theta\in[0,\frac{\pi}2]$. The constraint space is a sector of the $(n-1)$-sphere, the positive quadrant/octant/portion, reduced by the symmetry of permuting the ordinates. For example, for $n=2$, our space is half of the unit circle in the first quadrant, which spans an angle $\frac\pi4$, so that $a_2=\frac1{\sqrt 2}$. In $n$ dimensions, the minimum is $\frac1{\sqrt n}$, which is obtained, for example, when $x_i=\frac1{\sqrt n},y_i=\delta_i$ (i.e. $y_1=1$ and $y_i=0$ for $i>1$). You should be able to prove this with induction, for which you can without loss of generality assume ascending rather than descending order if it is more convenient.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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