Show that the support of a solution of $Ax=b$ is closed and convex

588 Views Asked by At

For a vector $x \in \mathbb{R}^n$, the index set $\text{supp}(x):=\{i \mid x_i \neq 0\}$ is called the support of $x$. Suppose a nonzero matrix $A \in \mathbb{R}^{m \times n}$ and a nonzero vector $b \in \mathbb{R}^m$ are such that the equation $Ax=b$, $x \geq 0$ has a solution, where $x \geq 0$ means that each component of $x$ is nonnegative.

Show that the solution set of the equation is closed and convex.

1

There are 1 best solutions below

0
On

Ignoring the support part of the question...


For a vector $x \in \mathbb{R}^n$, a nonzero matrix $A \in \mathbb{R}^{m \times n}$, and a nonzero vector $b \in \mathbb{R}^m$, consider the set $S=\{x:Ax=b,x \geq 0\}$. Suppose that $S \neq \emptyset$ has a solution, where $x \geq 0$ means that each component of $x$ is nonnegative. Show that the solution set of the equation is closed and convex.


First observe that the set $H=\{x:Ax=b\}$ is closed. To see this, let $H_i=\{x:a_i^\top x-b = 0\}$ for each $i=1,2,\ldots,m$. Then $H_i$ is the inverse image of the set $\{0\}$ for some affine function $f$. Since $\{0\}$ is closed and $f$ is affine (hence continuous), then $H_i$ is closed. But $H$ is the intersection of closed sets $H_i$, so $H$ is closed. Finally, the set $P = \{x:x\geq0\}$ is also closed, so $H\cap P$ is closed.

A comment shows that $H$ is convex; since $P$ is convex, then the intersection of two convex sets is convex so $H\cap P$ is convex, too.