0

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.

  • 2
    $A(\lambda x + (1-\lambda )y) = \lambda A x + (1-\lambda ) A y = \lambda b + (1-\lambda) b = b$ – ned grekerzberg Oct 29 '18 at 16:16
  • How about closeness? –  Oct 29 '18 at 16:26
  • 1
    The inverse image of a closed set, here ${b}$, under a continuous function is also closed. Is $x\rightarrow Ax$ continuous? What is the inverse image? – Flowrian Oct 29 '18 at 16:31
  • We cannot find the inverse image, because i) $A$ is not square ii) if it was, we had no assumption on the invertibility of it. –  Oct 29 '18 at 16:37
  • The inverse image is not the same as applying a possible inverse function. Consider $A^{-1}({b})={x\in\mathbb{R}^m : Ax=b}$. – Flowrian Oct 29 '18 at 16:46
  • @Saeed what does supp(x) have to do with all this? Also, if you row reduce the augmented matrix, the solution will be a affine subspace of $\mathbb{R}^n$. That is to say, the solution space will look like v + S, where v satisfies the equation and S is the Null(A). Since Null(A) is closed, the set will remain closed upon translation by v. – Joel Pereira Oct 29 '18 at 18:27
  • Do you want the solution set to be closed and convex, or the support to be closed and convex? – LinAlg Oct 30 '18 at 00:03
  • @LinAlg: as the question asks, the solution set should be closed. –  Oct 30 '18 at 01:22
  • 1
    @Saeed so the title of the question should be changed then. Why even introduce the definition of support? – LinAlg Oct 30 '18 at 01:30

1 Answers1

1

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.

jjjjjj
  • 2,671