# An upper bound for a vector with given norm 1 and norm 2

Suppose $X = (x_1, \ldots , x_n)$ is given and we know that $x_i$'s are nonnegative, $\sum_{i=1}^n x_i = n$ and $\sum_{i=1}^n x_i^2 = m$. Just by this information, is it possible to find a vector that majorizes $X$? the meaning of majorization can be found here: https://en.wikipedia.org/wiki/Majorization.

Certainly, $(n , 0 , \ldots , 0)$ is an answer, but I want a nontrivial vector. In particular,I'm looking for some nontrivial known results .

Thanks.

• If $X = (n,0,\ldots,0)$, then you clearly cannot find a nontrivial vector that majorizes $X$. If $X\neq (n,0,\ldots,0)$, then you $X$ will be majorized by $(n-\epsilon,\epsilon,0,\ldots,0)$ for small enough $\epsilon$. If this is not what you wanted, then you'll have to make your question more precise. – Tobias Fritz Apr 16 '18 at 19:02
• @TobiasFritz What the OP says is $(n,\ldots)$ majorizes any $X$, but the condition $\sum x_i^2=m$ makes other majorizers possible (if $m$ is small enough). – Jean Duchon Apr 17 '18 at 8:28
• For example if $m=n$ the only possible $X$ is $(1,\ldots,1)$, while if $m=n^2$, $(n,0,\ldots,0)$ is the only majorizer of $X$. – Jean Duchon Apr 17 '18 at 9:24
• And to complete the easy cases, for $n=2$, $X_1$ has to be $1\pm\sqrt{2m-4}/2$ – Jean Duchon Apr 17 '18 at 9:49
• @JeanDuchon yes exactly, I want m to be small. – user115608 Apr 17 '18 at 11:37

$\newcommand{\de}{\delta} \newcommand{\De}{\Delta} \newcommand{\ep}{\varepsilon} \newcommand{\ga}{\gamma} \newcommand{\Ga}{\Gamma} \newcommand{\la}{\lambda} \newcommand{\Si}{\Sigma} \newcommand{\thh}{\theta} \newcommand{\R}{\mathbb{R}} \newcommand{\X}{\mathcal{X}} \newcommand{\E}{\operatorname{\mathsf E}} \newcommand{\PP}{\operatorname{\mathsf P}} \newcommand{\ii}{\operatorname{\mathsf I}\{#1\}}$

Let us be guided by the OP's comment: "I suggest to consider a majorizer "good" if it majorizes for $\sum x_i^2 = m$ but not for $\sum x_i^2 = m'$ for $m'>m$."

Let $\X_{n,m}$ be the set of all $X = (x_1, \ldots , x_n)$ such that $x_i$'s are nonnegative, $\sum_{i=1}^n x_i = n$, and $\sum_{i=1}^n x_i^2 = m$. Note that for $X\in\X_{n,m}$ \begin{equation*} \sum x_i^2\le \Big(\sum x_i\Big)^2\le n\sum x_i^2, \end{equation*} so that \begin{equation*} n\le m\le m^2. \end{equation*} To avoid trivialities, suppose that $n\ge2$. Let \begin{equation*} a_{n,m}:=\max\{x_1\colon X\in\X_{n,m}\}. \tag{1} \end{equation*} We shall see that \begin{equation*} a_{n,m}=1+\sqrt{(m-n)(1-1/n)}\in[1,n]. \end{equation*} Let \begin{equation*} q:=\lfloor n/a_{n,m}\rfloor,\quad r:=n-qa_{n,m}\in[0,a_{n,m}), \end{equation*} \begin{equation*} y_1=\cdots=y_q=a_{n,m},\quad y_{q+1}:=r,\quad y_i:=0\ \text{for }i=q+2,q+3,\dots. \end{equation*} Then clearly the vector $Y:=(y_1,\dots,y_n)$ majorizes all vectors in $\X_{n,m}$ -- but, for any $m'>m$, not all vectors in $\X_{n,m'}$ -- since $a_{n,m}$ is strictly increasing in $m$.

It remains to verify (1). The vector $X\in\X_{n,m}$ with the largest $x_1$ satisfies the Lagrange equations \begin{equation} 1=\la+2\mu x_1,\quad 0=\la+2\mu x_i \end{equation} for some real $\la$ and $\mu$ and all $i\in J:=\{j\colon x_j>0\}$. If $\mu=0$, then $0=\la+2\mu x_i$ implies $\la=0$, which contradicts $1=\la+2\mu x_1$. So, $\mu\ne0$ and hence $x_1=a$ and $x_i=b$ for some positive real $a,b$ and all $i\in J$. So, letting $k$ stand for the cardinality of $J$, we have the system of equations \begin{equation} a+kb=n,\quad a^2+kb^2=m. \end{equation} Solving this system, we get \begin{equation} a=\frac{n+\sqrt{k[(k+1) m-n^2]}}{k+1} \end{equation} if $(k+1)m\ge n^2$; otherwise, there is no solution. It is not hard to see that this expression for $a$ is increasing in $k\in[n^2/m-1,n-1]$, so that the maximum of this expression occurs at $k=n-1$. Thus, (1) is verified.

Added in response to a comment by the OP: Take any $X = (x_1, \ldots , x_n)\in\X_{n,m}$.

If the $x_i$'s are all the same, then they are all equal $1$, and hence $m=n$. So, in this case $\X_{n,m}$ is the singleton set $\{(1,\dots,1)\}$.

Consider now the nontrivial case when $n<m\le m^2$. Then the set $\X_{n,m}$ is a subset of the intersection of the $(n-1)$-dimensional sphere of radius $\sqrt m$ centered at the origin of $\R^n$ with the hyperplane in $\R^n$ given by equation $\sum_{i=1}^n x_i = n$, and this intersection is a $(n-2)$-dimensional sphere (say $S_{n,m}$) of radius $\sqrt{m-n}>0$. Suppose now a vector $Z=(z_1,\dots,z_n)\in\X_{n,m}$ majorizes a vector $X=(x_1,\dots,x_n)\in\X_{n,m}$. Then, by Rado's theorem, Theorem R, page 3266, $X$ is a convex combination of vectors obtained by permuting the coordinates $z_1,\dots,z_n$ of $Z$. If at least two coefficients of that convex combination are nonzero, then $X$ cannot belong to $S_{n,m}$, because all the points of a sphere are extreme points of the ball bounded by the sphere.

So, in any case, the only vectors in $\X_{n,m}$ that are majorized by a given vector $Z\in\X_{n,m}$ are the vectors obtained by permuting the coordinates $z_1,\dots,z_n$ of $Z$.

Thus, in the nontrivial case $n<m<m^2$, there is no vector in $\X_{n,m}$ that majorizes all vectors in $\X_{n,m}$ -- because in this case for any vector $Y\in\X_{n,m}$ there is another vector in $\X_{n,m}$ which cannot be obtained by permuting the coordinates of $Y$.

• @losif Pinelis thanks,but a point! The norm 2 of the vector Y must be \sqrt (m),but it is not. – user115608 Apr 18 '18 at 6:53
• The 2-norm of a majorizer of $\cal X_{n,m}$ cannot be $\sqrt m$ in general! Except in the trivial cases $m=n$ and $m=n^2$. Another choice for a "good" majorizer could be the one that minimizes the 2-norm, I think. – Jean Duchon Apr 18 '18 at 7:56
• @user115608 : You never said that the majorizer must be of norm $\sqrt m$. To the contrary, you said "Certainly, $(n,0,\ldots,0)$ is an answer", whereas this vector is of norm $\sqrt m$ only in the trivial case when $m=n^2$. More importantly, as Jean Duchon noted, the 2-norm of a majorizer of $\X_{n,m}$ cannot be $\sqrt m$ -- except in the trivial cases $m=n$ and $m=n^2$. Moreover, as is now shown in the addition at the end of my answer, the only vectors in $\X_{n,m}$ that are majorized by a given vector $Z\in\X_{n,m}$ are the vectors obtained by permuting the coordinates of $Z$. – Iosif Pinelis Apr 18 '18 at 15:27