Generators for the solution set of a system of inequalities Given a system of linear equations of the form
\begin{align*}
a_{1,1}x_1+a_{1,2}x_2+&\dots+a_{1,n}x_n = b_1 \\
a_{2,1}x_1+a_{2,2}x_2+&\dots+a_{2,n}x_n = b_2 \\
\vdots \\
a_{n,1}x_1+a_{n,2}x_2+&\dots+a_{n,n}x_n = b_n,
\end{align*}
where all $x_i,a_{i,j},b_i \in \mathbb{R}$, it can be written in terms of the matrix $A:=(a_{i,j})$ and the vectors $\mathbf{x}:=(x_1,\dots,x_n)$ and $\mathbf{b}:=(b_1,\dots,b_n)$ as
$$A\mathbf{x}=\mathbf{b}.$$
However, we could also consider the complement of the solution set for $\mathbf{x}$ through the inequality
$$A\mathbf{x} \neq \mathbf{b}.$$
Is there a way to find generators for the set of solutions of the above inequality? Or even a way to express it algebraically without having to consider all the possible combinations of equalities and inequalities in the system? Furthermore, could the solution (if it exists) be generalized to non-linear systems?
My motivation is to define the union, intersection and complement of the solution sets of systems. The former two are farily straight-forward, but I'm having trouble with the latter. If you have any suggestions of resources that could be helpful, I'd be very grateful.
 A: TLDR; Solutions $A\,x = b$ are a translation of the vector space $\mathrm{ker}(A).$ It suffices to come up with all vectors that lift us away from this affine subspace, and we can use non-zero vectors in $\mathrm{im}(A^\top)$ to do that. It isn't clear it can be generalized, since there is rarely algebraic structure on solutions to nonlinear equations, and we are leveraging some important properties of linear algebra to make this work.
Longer:
Clearly when there does not exist a $p$ so that $A\,p = b,$ then the entire space of solutions to $A\,x\neq b$ is $\mathbb{R}^n.$ Generating that set is straightforward.
Instead, suppose there exists a $p \in \mathbb{R}^n$ so that
$$
A\,p = b.
$$
It is well-understood then that the entire space of solutions to $A\,x  = b$ is the set
$$
\mathscr{S}(A;b) = \{ x \in \mathbb{R}^n \colon x - p \in \mathrm{ker}(A) \}.$$
What you want is $\mathbb{R}^n\setminus \mathscr{S}(A;b),$ i.e. all those vectors that, when multiplied by $A,$ do not equal $b.$ This amounts to expressing all those vectors that "offset" from the affine subspace $\mathscr{S}(A;b).$ This is a straightforward application of,
$$\mathbb{R}^n = \mathrm{ker}(A) \oplus \mathrm{im}(A^\top).$$
Recognizing that $\mathscr{S}(A;b)$ is just a translation of the vector subspace $\mathrm{ker}(A)$ by the vector $p,$ it suffices to take any vector in $\mathscr{S}(A;b)$ and add a non-zero vector in $\mathrm{im}(A^\top).$
Let me do this explicitly. Write a basis for $\mathbb{R}^n$ so that,
$$\begin{aligned}
\mathrm{ker}(A) &= \mathrm{span}\{u_1,\ldots,u_{n-r}\},\\
\mathrm{im}(A^\top) &= \mathrm{span}\{v_{1}, \ldots, v_r\}.
\end{aligned}$$
Let $\alpha = (\alpha_1,\ldots,\alpha_{n-r}) \in \mathbb{R}^{n-r}$ be an arbitrary vector of real numbers, and let $\beta = (\beta_1, \ldots, \beta_r) \in \mathbb{R}^{r} \setminus \{0\}$ be in the punctured real space (removing the origin, so all non-zero vectors).
Then any vector $v \in \mathbb{R}^n$ taking the form,
$$ v = p + \sum_{i = 1}^{n - r} \alpha_i\,u_{i} + \sum_{i = 1}^{r} \beta_i\,v_i,$$
solves the inequality
$$A\,v \neq b.$$
That is easy enough to verify computationally, but the question you may have is  "is this actually all possible solutions?" Suppose that $q$ solves,
$$
A\,q \neq b.
$$
Equivalently,
$$
A\,(q - p + p) \neq b,
$$
or,
$$
A\,(q - p) \neq 0.
$$
Therefore, $q - p \notin \mathrm{ker}(A).$ But, because $q - p \in \mathbb{R}^n = \mathrm{ker}(A)\oplus \mathrm{im}(A^\top)$,
$$q - p = \sum_{i = 1}^{n - r} \alpha_i\,u_{i} + \sum_{i = 1}^{r} \beta_i\,v_i$$
for some $\alpha_i$ and $\beta_i.$ It follows that at least one of the $\beta_i$ is non-zero.
