2
$\begingroup$

I have the following 6 inequalities:

$$ x_1 + x_2 + x_4 \le K \\ x_3 + x_4 + x_5 \le K \\ x_1 + x_5 + x_6 \le K \\ x_1 + x_2 + x_6 \le K \\ x_2 + x_3 + x_4 \le K \\ x_3 + x_5 + x_6 \le K $$

where $x_1$, $x_2$, $x_3$, $x_4$, $x_5$, $x_6$ and $K$ are positive

This gives the following matrix

$$ A = \begin{bmatrix} 1 & 1 & 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 1 & 1 & 0\\ 1 & 0 & 0 & 0 & 1 & 1\\ 1 & 1 & 0 & 0 & 0 & 1\\ 0 & 1 & 1 & 1 & 0 & 0\\ 0 & 0 & 1 & 0 & 1 & 1\\ \end{bmatrix} $$

The rank of $A$, I found to equal 4. Therefore, I expected that these 6 inequalities reduced to only 4. Wolfram alpha was not able to reduce them to the 4 inequalites.

My questions are:

  1. Can these system on inequalities be reduced to only 4 inequalities
    • If not, why doesn't the logic of the rank of a matrix in linear algebra extend to inequalities
    • If it does, what are these 4 inequalities
$\endgroup$
1
  • 2
    $\begingroup$ It's highly unlikely that four inequalities will suffice for this system. You can certainly verify that each inequality in the original six inequalities are necessary. For example, if $K = 2$ (which, it might as well be, given you can always sub $y_i = Kx_i/2$), you could look at $(1, 1, 0, 1, 0, 0)$, which satisfies every inequality but the first. If we were dealing with equalities, then we could reduce the six equations down to four, but here we cannot lose a single inequality. That should at least convince you that the intuition from equations does not carry over here. $\endgroup$ Mar 21 at 4:12

1 Answer 1

2
$\begingroup$

Short answer: no, the solution set cannot be expressed with four inequalities. In fact, any system of linear inequalities that express this solution set, must contain these six inequalities, or positive multiples of them.

The longer answer is long, so here is the structure:

  1. Analysis of illustrative examples in lower dimensions. By looking at some toy examples that we can plot, we can build intuition.
  2. Establishing a result that can help us in general. This section is basically just a proof.
  3. We apply the section 2 results to the example in your question, to get the result in the short answer.

${}$1. Intuition

Let's examine a system of three inequalities in $x$ and $y$. Consider the system $$\left\{\begin{aligned} -x + 0y &\le 0 \\ 0x - y &\le 0 \\ x + y &\le 1\end{aligned}\right.$$ If we plot these three inequalities we get:

Triangle

It may be a little tricky to see, but everything to the right of the $y$-axis is shaded red, everything above the $x$-axis is shaded orange, and everything below the line $x + y = 1$ is shaded green. Respectively, these are the points $(x, y)$ such that $-x \le 0$, $-y \le 0$, and $x + y \le 1$. The intersection of these inequalities is shaded purple, being the set of points that satisfy our system of linear inequalities.

Now, the matrix of coefficients, $\pmatrix{-1 & 0 \\ 0 & -1 \\ 1 & 1}$ has rank $2$. Does this mean that we can reduce these down to a system of two inequalities?

Think about what a system of two inequalities could look like. Essentially, you need to pick two lines through $\Bbb{R}^2$, shade everything on one side of them, and hope you get that purple triangle. But, it's not possible. No matter which two lines you choose, you will not even get a bounded figure! You may get an unbounded wedge, if the lines are not parallel, or if they are parallel, you might get an unbounded strip, or possibly a line, or possibly no intersection at all. There's no way to get a three-sided figure.

There's something more to notice here as well. Each of the three inequalities was responsible for a side of the triangle. Indeed, simply by identifying the lines that make up the sides of the triangles, we can identify the linear inequalities necessary carve out the solution. While we could add superfluous inequalities, such as $y \le 2$, at some point, we are going to need to specify $x \ge 0$, and $y \ge 0$, and $x + y \le 1$. Of course, we could dress it up, and say $-2x \le 0$, $-12y \le 0$, and $3x + 3y \le 3$, but ultimately, we will need those same lines to carve out precisely this triangle.

Similarly, if our solution had more sides, we'd need more inequalities. We could carve out, say, an octagon, and we would always need $8$ linear inequalities to do it. And, the specific inequalities we'd need could be determined by the sides of the octagon.

Hopefully, you have a bit of a better grasp on linear inequalities. With linear equations, we are essentially intersecting hyperplanes of the form $a_1 x_1 + \ldots + a_n x_n = b$. Each time we add a new hyperplane into the intersection, we carve off a dimension from the intersection (provided the new hyperplane adds new information, and doesn't make the system inconsistent). We can usually make the same solution with many different sets of hyperplanes, so we have a lot of power to replace hyperplanes with other hyperplanes (e.g. through elementary row operations).

With linear inequalities, we are not intersecting hyperplanes, we are intersecting half-spaces. We now have much less wiggle room in terms of creating new inequalities out of old ones. If you sum the inequalities $x \ge 0$ and $y \ge 0$, you get $x + y \ge 0$, which contains the intersection of $x \ge 0$ and $y \ge 0$, but contains more points again. So, while $x = 0$ and $y = 0$ is equivalent to, say, $x = 0$ and $x + y = 0$, with inequalities, $x \ge 0$ and $x + y \ge 0$ is very different to $x \ge 0$ and $y \ge 0$.

What we will show in the next section is this idea of the "sides" (or "facets" more generally) determining the inequalities.

${}$2. Result

Let us assume we have a system of linear inequalities $Ax \le b$, where $A$ is $m \times n$. We will concentrate primarily on when the solution set has a non-empty interior, i.e. the solution set $S = \{x : Ax \le b\}$ contains some non-trivial ball.

Speaking of balls, we will denote by $B[x; r]$ the closed ball of radius $r$, centred at $x$.

Let us prove the following:

Suppose we have $x_0 \in S$, $u \in \Bbb{R}^n \setminus \{0\}$, and $r > 0$ such that $$S \cap B[x_0; r] = \{x \in \Bbb{R} : u^\top x \le u^\top x_0\} \cap B[x_0; r]. \tag{$\star$}$$ Then, the inequality $u^\top x \le u^\top x_0$ is a positive scalar multiple of one of the inequalities in the system $Ax \le b$. That is, for some $i$, $$A_{i1} x_1 + \ldots + A_{in} x_n \le b_j$$ is a positive scalar multiple of $$u_1 x_1 + \ldots + u_n x_n \le u^\top x_0.$$

The condition $(\star)$ basically says that $S$ looks identical to the half-space $H = \{x \in \Bbb{R} : u^\top x \le u^\top x_0\}$ locally around $x_0$. Note that $H$ contains $x_0$ on its boundary hyperplane.

Proof. For each $k \in \Bbb{N}$, let $x_k = x_0 + \frac{1}{k} u$. Note that $$u^\top x_k = u^\top x_0 + \frac{1}{k} u^\top u > u^\top x_0.$$ Thus, $x_k \notin H$ for any $k$, while we do have $x_k \to x_0 \in H \cap S$. Due to this convergence to $x_0$, we know that, for some $N$, we have $$k \ge N \implies x_k \in B[x_0; r].$$ But, because $x_k \notin S$, we have $$k \ge N \implies x_k \notin B[x_0; r] \cap H = B[x_0; r] \cap S,$$ which implies $x_k \notin S$, for $k \ge N$.

This implies that each such $x_k \notin S$ must be excluded by at least one of the inequalities in $Ax \le b$. Since there are infinitely many $x_k$ and only finitely many inequalities, one inequality must exclude infinitely many points in the $x_k$ sequence. That is, there is the $i$th row vector $a_i$ from $A$, for some $i$, and there is some subsequence $x_{k_l}$ such that $a_i^\top x_{k_l} > b_i$ for all $l$.

Suppose that $v$ is perpendicular to $u$, and has unit length. Then $$x_0 + rv \in H \cap B[x_0; r] = S \cap B[x_0; r] \subseteq S.$$ We therefore have \begin{align} &a_i^\top (x_0 + rv) \le b_i < a_i^\top x_{k_l} \\ \implies \, &a_i^\top(x_{k_l} - x_0 - rv) > 0 \\ \implies \, &a_i^\top\left(\frac{1}{k_l} u - rv\right) > 0. \end{align} This holds as $l \to \infty$, hence as $k_l \to \infty$, so taking the limit, we get $$a_i^\top (0 - rv) \ge 0 \implies a_i^\top v \le 0.$$ This holds true for any unit length $v$ perpendicular to $u$. In particular, we may substitute $-v$ for $v$, to get $a_i^\top v \ge 0$ as well, hence $a_i^\top v = 0$ for all such $v$. Thus, $a_i$ is perpendicular to any vector perpendicular to $u$, which implies $a_i$ is parallel to $u$. That is $a_i = \lambda u$ for some $\lambda \in \Bbb{R}$.

Since $a_i^\top x \le b_i$ accepts $x_0$, but rejects $x_{k_l}$, we see that $$\lambda u^\top x_0 \le b_i < \lambda u^\top \left(x_0 + \frac{1}{k_l}u\right) = \lambda u^\top x_0 + \lambda \frac{\|u\|^2}{k_l},$$ hence $$0 < \lambda \frac{\|u\|^2}{k_l} \implies \lambda > 0.$$ We also have, as $k_l \to \infty$, $$\lambda u^\top x_0 \le b_i \le \lambda u^\top \left(x_0 + 0u\right) \implies b_i = \lambda u^\top x_0.$$ All of this goes to show that the inequality defining $H$, i.e. $u^\top x \le u^\top x_0$ is a positive multiple of the $i$th inequality from our original system $Ax \le b$, i.e. $a_i^\top x \le b_i$. This completes the proof.

${}$3. The system at hand

I will show that the first inequality is absolutely necessary in the sense of our result from part 2. Let: $$x_0 = \left(\frac{K}{3}, \frac{K}{3}, 0, \frac{K}{3}, 0, 0\right)^\top$$ and $$u = (1, 1, 0, 1, 0, 0)^\top.$$ Also let $r = \frac{K}{9}$. As in the result, we define $S$ to be the solution set, and \begin{align} H &= \{x \in \Bbb{R}^6 : u^\top x \le u^\top x_0\} \\ &= \{x \in \Bbb{R}^6 : x_1 + x_2 + x_4 \le K\}. \end{align} I claim that the condition from the result holds, i.e. $$S \cap B[x_0; r] = H \cap B[x_0; r].$$ Clearly, the $\subseteq$ condition holds, as $S \subseteq H$, so we begin by supposing that $x \in H \cap B[x_0; r]$. We wish to show that $x \in S$, in particular, that $x$ satisfies all the other five inequalities.

Note that, since $\|x - x_0\| \le r = \frac{K}{9}$, we know that $|x_i| \le K/9 \implies x_i \le K/9$ for $i = 3, 5, 6$, and $|x_i - K/3| \le K/9 \implies x_i \le 4K/9$ for $i = 1, 2, 4$. Suppose that we sum any three coordinates of $x$, except $i = 1, 2, 4$. Then, depending on whether we have zero, one, or two of $x_1, x_2, x_4$, the upper bound on the sum must be either $3K/9 = K/3$, $2K/9 + 4K/9 = 2K/3$, or $K/9 + 2(4K/9) = K$. So, each of the other inequalities, each of which involves summing three coordinates, must all be satisfied. Hence, $x \in S$.

Thus, the result applies. There is no way to produce the solution set $S$ without $x_1 + x_2 + x_4 \le K$, or some positive multiple thereof, being one of the inequalities.

A similar argument shows that all of the other inequalities are necessary in this sense too. So, any system of linear inequalities that have the same solution set must have at least six inequalities. In particular, it must have at least these six inequalities, despite the rank of $A$ being four.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .