# How close are solutions of systems of homogeneous linear inequalities with close coefficients?

Suppose I have two systems of $n$ homogeneous inequalities of $k$ variables: $$Ax \geq 0$$ and $$Bz \geq 0,$$ where both $A$ and $B$ are $n \times k$ matrices such that for any $i=1, \ldots, n$, and $j=1, \ldots, k$, we have $|a_{ij}-b_{ij}|\leq \epsilon$, where $\epsilon>0$ is very small.

Can I conclude from here that there is some distance $\phi(\epsilon)$ (such that $\phi(\epsilon) \rightarrow 0$ as $\epsilon \rightarrow 0$) with the following property: for any solution $x_0$ to the first system with $\|x_0\|=1$ there is a solution $z_0$ to the second system such that $$\|x_0-z_0\|\leq \phi(\epsilon)$$ for some norm $\|\cdot\|$ in $\mathbb{R}^k$? I am interested in the form (or approximation) of such $\phi(\epsilon)$.

EDIT. I am interested in situations when both systems have non-trivial (non-zero) solutions. I would be even willing to assume that both solution sets have non-empty interiors if this would help.

• No; you must take $x_0$ s.t. $||x_0||=1$. – loup blanc Nov 11 '17 at 16:05
• @loupblanc Yes, I agree with your comment and will make edits to the question accordingly. – Neznajka Nov 11 '17 at 18:05

Look at the case where $A$ has a large condition-number.

EDIT 1. For example $A=\begin{pmatrix}0&1\\u&-1\end{pmatrix},B=\begin{pmatrix}-2u&1\\u&-1\end{pmatrix}$ where $u$ is a small $>0$ number; take $x_0=(1,0)$. Then $||x_0-z_0||\ge 1$.

EDIT 2. Answer to Neznajka . The above example shows that $\phi$ does not exist.

Indeed, let $\epsilon >0$. If $u=\epsilon/2$, then $|a_{i,j}-b_{i,j}|\leq \epsilon$. One has $Ax_0\geq 0,||x_0||=1$; $Bz\geq 0$ where $z=[x,y]^T$ is equivalent to $ux\geq y\geq 2ux$, that implies $x\leq 0,y\leq 0$. Thus, if $Bz_0\geq 0$, then $||x_0-z_0||\geq 1$ and finally $\phi(\epsilon)\geq 1$.

EDIT 3. I think that a correct formulation of your problem is as follows.

Let $A\in M_{n,k}$ where $\text{rank}(A)=n\leq k$. Show that there are $a>0$ and a function $\phi:t\in (0,a)\rightarrow (0,+\infty)$ that tends to $0$ with $t$, s.t. for every $B\in M_{n,k},x_0\in\mathbb{R}^k$ satisfying $||A-B||<a,Ax_0\geq 0,||x_0||=1$, there is $z_0\in\mathbb{R}^k$ s.t. $Az_0\geq 0,||x_0-z_0||\leq \phi(||A-B||)$.

• I see it now. Thank you. – Neznajka Nov 14 '17 at 16:46