# A State of the Art Review of Systems of Linear Inequalities and Related Observability Problems
## 3 Systems of Linear Inequalities
### Homogeneous Systems of Linear Inequalities  
Consider the following system of linear inequalities ([[https://www.uclm.es/Conocimiento/Cursos/Algebra-2-En/Bloque-3/Item-87](https://www.uclm.es/Conocimiento/Cursos/Algebra-2-En/Bloque-3/Item-87) id_peticion=]([https://www.uclm.es/Conocimiento/Cursos/Algebra-2-En/Bloque-3/Item-87](https://www.uclm.es/Conocimiento/Cursos/Algebra-2-En/Bloque-3/Item-87) id_peticion=)[A827E15C-65 EF-4 CFA-8671-BB 2F12122D25], accessed on 12 July 2023):  
\[a_{11}x_{1}+a_{12}x_{2}+\cdots+a_{1n}x_{n} \leq 0\] \[a_{21}x_{1}+a_{22}x_{2}+\cdots+a_{2n}x_{n} \leq 0\] \[\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\] \[a_{m1}x_{1}+a_{m2}x_{2}+\cdots+a_{mn}x_{n} \leq 0, \tag{17}\]  
which can be written in equivalent form as:  
\[(a_{11},a_{12},\cdots,a_{1n})\cdot(x_{1},x_{2},\cdots,x_{n}) \leq 0\] \[(a_{21},a_{22},\cdots,a_{2n})\cdot(x_{1},x_{2},\cdots,x_{n}) \leq 0\] \[\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\] \[(a_{m1},a_{m2},\cdots,a_{mn})\cdot(x_{1},x_{2},\cdots,x_{n}) \leq 0. \tag{18}\]  
Since the definition of the dual cone of a cone is the set of vectors such that their dot product by the vectors of the dual cone are non-positive, this new representation of the above system proves that its solution is the dual cone of the cone generated by the vectors whose components are the equation coefficients. It is great that we identify the structure of the set of solutions of homogeneous systems of linear inequalities just based on the definition of a dual cone and its properties. Since it is well known (see [18]) that any cone is the sum of a linear subspace and an acute cone, an immediate conclusion is that it is of interest to obtain its linear subspace part, as its basis, and the acute part of the cone, if it exists, as the set of edges of the acute cone. In this way, we can have minimal representations of the corresponding sets of solutions. The reader can see how to deal with these matters with general methods in [19; 20]. Thus, if we have an algorithm able to obtain the dual cone of a given cone, we also have an algorithm for solving linear systems of inequalities. Some of these algorithm are described in some detail in [6; 18; 20; 21]. Example of a Homogeneous System of Linear Inequalities  
Consider the linear system of inequalities:  
\[ \begin{array}{rrrrr}&x_{2}&-x_{3}&+2x_{4}&\leq&0\\ x_{1}&+x_{2}&+x_{3}&\leq&0\\ x_{1}&+2x_{2}&+x_{4}&\leq&0\\ x_{1}&+x_{2}&+x_{3}&+x_{4}&\leq&0.\end{array}  \tag{19}\]  
which can be written as:  
\[(0,1,-1,2)\cdot(x_{1},x_{2},x_{3},x_{4}) \leq 0\] \[(1,1,1,0)\cdot(x_{1},x_{2},x_{3},x_{4}) \leq 0\] \[(1,2,0,1)\cdot(x_{1},x_{2},x_{3},x_{4}) \leq 0\] \[(1,1,1,1)\cdot(x_{1},x_{2},x_{3},x_{4}) \leq 0. \tag{20}\]  
The solution is the dual of the cone generated by the vectors of the equation coefficients, that is, the dual of the cone:  
\[\left( \begin{array}{c}x_{1}\\ x_{2}\\ x_{3}\\ x_{4}\end{array} \right)=\left( \begin{array}{rrrr}0&1&1&1\\ 1&1&2&1\\ -1&1&0&1\\ 2&0&1&1\end{array} \right)_{\pi}. \tag{21}\]Note that we represent linear subspaces and cones as matrices containing as columns their generator vectors and a subindex \(\rho\) or \(\pi\) to refer to real and non-negative real coefficients, respectively. Using the \(\Gamma\) algorithm, we can obtain the dual cone, which, written as a linear subspace plus an acute cone, provides the general solution of the homogeneous system (19) as:  
\[\left( \begin{array}{c}x_{1}\\ x_{2}\\ x_{3}\\ x_{4}\end{array} \right)=\left( \begin{array}{c}-2\\ 1\\ 1\\ 0\end{array} \right)_{\rho}+\left( \begin{array}{rrrr}-3&-1&1&1\\ 2&1&-2&-1\\ 0&0&0&0\\ -1&-1&1&0\end{array} \right)_{\pi}=\left( \begin{array}{c}-2\rho-3\pi_{1}-\pi_ {2}+\pi_{3}+\pi_{4}\\ \rho+2\pi_{1}+\pi_{2}-2\pi_{3}-\pi_{4}\\ \rho\\ -\pi_{1}-\pi_{2}+\pi_{3}\end{array} \right) \tag{22}\]  
where the Greek letter \(\rho\) refers to linear combinations using real numbers and the \(\pi\) to non-negative real number combinations, respectively. If the solution (22) is replaced in the system of equations (19), we obtain:  
\[\left(