Suppose it is given that there exists a ‘strictly positive’ vector $\vec x \in (0,1)^k$, which lies on the probability simplex $\sum\_i x\_i = 1$. What is the least number of inequalities of the form $\vec g\_i^T \vec x \geq 0$ required to ensure that the solution set is a singleton vector? Note that there is no restriction on $\{\vec g\_i \}$ so one can pick the ‘best’ possible vectors (it should be consistent in the sense that there must exist one solution on the simplex with positive components).


I believe the answer would be $2(k-1)$ — I know it definitely is sufficient but can't seem to be able to show that it is necessary as well. Construction for sufficiency — take pairs of $\vec g\_i, - \vec g\_i$ so essentially you would have $k-1$ equations of form $\vec x^T \vec g\_i = 0$ and $\sum\_i x\_i = 1$. We have $k$ equations so this has a unique solution and it's not hard to see that by suitable choice of $\vec g\_i$, we can make the solution have positive components.



How many inequalities do I need to ensure a unique solution?
$\newcommand\v\vec\newcommand\R{\mathbb R}$For any natural $k\ge2$, $k$ inequalities (but not fewer than $k$) will suffice.


Indeed, take any vector $\v a\in(0,\infty)^k$ such that $\v1\cdot\v a=1$, where $\v1:=(1,\dots,1)\in\R^k$ and $\cdot$ denotes the dot product. Take any linearly independent vectors $\v g\_1,\dots,\v g\_{k-1}$ in $\R^k$ that are orthogonal to $\v a$, and then let $\v g\_k:=-\v g\_1-\dots-\v g\_{k-1}$. Then, for each $\v x\in\R^k$, the inequalities
\begin{equation}
 \v g\_1\cdot\v x\ge0,\ \dots,\ \v g\_{k-1}\cdot\v x\ge0,\ \v g\_k\cdot\v x\ge0 \tag{0} 
\end{equation}
imply the equalities
\begin{equation}
 \v g\_1\cdot\v x=\dots=\v g\_{k-1}\cdot\v x=0. \tag{1}
\end{equation}
Also, the vector $\v1$ is linearly independent of $\v g\_1,\dots,\v g\_{k-1}$ -- otherwise, we would have $1=\v1\cdot\v a=0$, since (1) holds for $\v x=\v a$. So, the system of equalities (1) together with the equality
\begin{equation}
 \v1\cdot\v x=1 \tag{2}
\end{equation}
has a unique solution.


Moreover, equalities (1) and (2) do hold for $\v x=\v a$.


Thus, $\v x=\v a$ is the unique solution of the system of inequalities (0) and equality (2),  

as desired.




---


Also, for any natural $k\ge2$, any $k-1$ inequalities of the form
\begin{equation}
 \v g\_1\cdot\v x\ge0,\dots,\v g\_{k-1}\cdot\v x\ge0 \tag{0a} 
\end{equation}
will not suffice to identify $\v a$, even together with the equality (2).


Indeed, suppose the contrary, so that $\v a$ is the only solution in $(0,\infty)^k$ of the system (0a)--(2).


Consider first the case when $\v a$ is not orthogonal to
\begin{equation\*}
 V:=\text{span}(\v g\_1,\dots,\v g\_{k-1}). 
\end{equation\*}
Take any nonzero vector $\v h\in\R^k$ orthogonal to $V$ and such that $\v1\cdot\v h\ge0$, so that $\v1\cdot(\v a+\v h)\ge1>0$, and also short enough so that $\v a+\v h\in(0,\infty)^k$. Let  

\begin{equation}
 \v b:=\frac{\v a+\v h}{\v1\cdot(\v a+\v h)}\in(0,\infty)^k. \tag{3}
\end{equation}
Then $\v b\ne \v a$, while (0a) and (2) hold with $\v x=\v b$. This contradicts $\v a$ being the only solution in $(0,\infty)^k$ of the system (0a)--(2).


Next, consider the case when $\v a$ is orthogonal to $V$ and $\v g\_1,\dots,\v g\_{k-1}$ are linearly dependent, so that there is a nonzero vector $\v h\in\R^k$ orthogonal to $V$ and to $\v a$ and such that $\v1\cdot\v h\ge0$, which also is short enough so that $\v a+\v h\in(0,\infty)^k$. Then again, for $\v b$ as in (3), we have $\v b\ne \v a$, while (0a) and (2) hold with $\v x=\v b$. This contradicts $\v a$ being the only solution in $(0,\infty)^k$ of the system (0a)--(2). Again, a contradiction.


Finally, consider the case when $\v a$ is orthogonal to $V$ and $\v g\_1,\dots,\v g\_{k-1}$ are linearly independent. Then there is a vector $\v h\_1\in V$ such that $\v g\_1\cdot\v h\_1=1$ and $\v g\_j\cdot\v h\_1=0$ for $j=2,\dots,k-1$. Letting now $\v h:=t\,\v h\_1$ for a small enough $t>0$ so that $\v1\cdot\v h\ge-1/2$ and $\v a+\v h\in(0,\infty)^k$, we get $\v1\cdot(\v a+\v h)\ge1/2>0$.
So, again for $\v b$ as in (3), we have $\v b\ne \v a$, while (0a) and (2) hold with $\v x=\v b$. This contradicts $\v a$ being the only solution in $(0,\infty)^k$ of the system (0a)--(2). Once again, a contradiction.


Thus, $k$ is the smallest number of inequalities of the form $\v g\_j\cdot\v x\ge0$ that will suffice.


