# How many inequalities do I need to ensure a unique solution?

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.

$$\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 $$$$\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}$$$$ imply the equalities $$$$\v g_1\cdot\v x=\dots=\v g_{k-1}\cdot\v x=0. \tag{1}$$$$ 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 $$$$\v1\cdot\v x=1 \tag{2}$$$$ 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 $$$$\v g_1\cdot\v x\ge0,\dots,\v g_{k-1}\cdot\v x\ge0 \tag{0a}$$$$ 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
$$$$\v b:=\frac{\v a+\v h}{\v1\cdot(\v a+\v h)}\in(0,\infty)^k. \tag{3}$$$$ 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.