Point isolation through linear constraints

Question

I consider a set of $n$ points in $\mathbb R^d$: $X=${$x_i$}$_{i=1}^n$. I would like to know for each point $\tilde x\in X$ if there exists a dimension $j\in${$1, ..., d$} and $k$ linear constraints (with $k$ a given integer) such that, among all points of $X$ which satisfy the $k$ linear constraints, $\tilde x$ is the only one which has value $\tilde x_j$ on dimension $j$.

Moreover, I do not consider any linear constraints but only the ones which have exactly one non-zero coefficient (i.e., $a^Tx\leq b$ such that $||a||_0= 1$).

Note that the non-zero coefficient of a constraint is not necessarily the one in dimension $j$.

An obvious sufficient condition is that $\tilde x_j$ is the only point in $X$ which has value $\tilde x_j$ for a dimension $j\in${$1, ..., d$}. In that case, the answer is yes and I can just take any $k$ linear constraints satisfied by $\tilde x$.

Ideally, I would like to find necessary and sufficient conditions but any suggestion is welcome.

Context: if anyone is interested, I am facing this problem while trying to determine the dimension of the convex hull of the solutions of a mixed integer linear program.

Answer 1

You have a set of points in $\mathbb{R}^d$: $X = \{x_1, x_2, \ldots, x_n\}$.

For each point $\tilde x \in X$, you want to know if there exist $k$ linear constraints, each with only one non-zero coefficient, such that $\tilde x$ is the only point in $X$ that satisfies these $k$ constraints for the $j$-th dimension.

The $k$ linear constraints can be represented as $a^T x \leq b$ with the constraint $a$ having only one non-zero coefficient.

To find necessary and sufficient conditions for this, you can think of it as a combinatorial problem. First, let's define some terms:

• $X_j = \{x_i \in X \mid x_{ij} = \tilde x_j\}$: The set of points in $X$ that have the same value as $\tilde x$ in dimension $j$.
• $L_j = \{a_i \in \mathbb{R}^d \mid a_i \text{ has only one non-zero coefficient in dimension } j\}$: The set of possible linear constraints for dimension $j$.

Now, the question is whether you can pick $k$ constraints from $L_j$ in such a way that they uniquely identify $\tilde x$ in dimension $j$. This can be thought of as a combinatorial problem, and there may not always be a unique solution.

Necessary conditions:

For $\tilde x$ to have a unique position in dimension $j$, $X_j$ should contain exactly one point, i.e., $|X_j| = 1$.

Sufficient conditions:

If $|X_j| = 1$, you can trivially pick any $k$ constraints from $L_j$, and $\tilde x$ will be the only point in $X$ that satisfies these constraints for dimension $j.

So, necessary and sufficient conditions for $\tilde x$ having a unique position in dimension $j$ are:

Necessary: $|X_j| = 1$

Sufficient: $|X_j| = 1$ If $|X_j| > 1$, you may not always be able to find $k$ linear constraints with one non-zero coefficient for dimension $j$ that uniquely identify $\tilde x$. This may depend on the specific points in $X$ and their positions in dimension $j$. In general, this problem can be quite complex, and finding necessary and sufficient conditions for all cases may not be straightforward. It might be necessary to consider additional properties or constraints on the points in $X$.