2
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ 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. $\endgroup$ Apr 16, 2018 at 19:02
  • $\begingroup$ @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). $\endgroup$ Apr 17, 2018 at 8:28
  • $\begingroup$ 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$. $\endgroup$ Apr 17, 2018 at 9:24
  • $\begingroup$ And to complete the easy cases, for $n=2$, $X_1$ has to be $1\pm\sqrt{2m-4}/2$ $\endgroup$ Apr 17, 2018 at 9:49
  • $\begingroup$ @JeanDuchon yes exactly, I want m to be small. $\endgroup$
    – user115608
    Apr 17, 2018 at 11:37

1 Answer 1

2
$\begingroup$

$\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}[1]{\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$.

$\endgroup$
3
  • $\begingroup$ @losif Pinelis thanks,but a point! The norm 2 of the vector Y must be \sqrt (m),but it is not. $\endgroup$
    – user115608
    Apr 18, 2018 at 6:53
  • $\begingroup$ 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. $\endgroup$ Apr 18, 2018 at 7:56
  • 1
    $\begingroup$ @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$. $\endgroup$ Apr 18, 2018 at 15:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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