# A State of the Art Review of Systems of Linear Inequalities and Related Observability Problems
## 3 Systems of Linear Inequalities
### Complete Systems of Linear Inequalities  
Consider now the following complete linear system of inequalities ([[https://www.uclm.es/Conocimiento/Cursos/Algebra-2-En/Bloque-3/Item-97](https://www.uclm.es/Conocimiento/Cursos/Algebra-2-En/Bloque-3/Item-97) id_peticn=]([https://www.uclm.es/Conocimiento/Cursos/Algebra-2-En/Bloque-3/Item-97](https://www.uclm.es/Conocimiento/Cursos/Algebra-2-En/Bloque-3/Item-97) id_peticn=)[A827E15C-65 EF-4 CFA-8671-BB2F12122D25], accessed on 12 July 2023):  
\[ \begin{array}{cccccccc}a_{11}x_{1}&+a_{12}x_{2}&+&\cdots&+a_{1n}x_{n}&\leq&b _{1}\\ a_{21}x_{1}&+a_{22}x_{2}&+&\cdots&+a_{2n}x_{n}&\leq&b_{2}\\ \cdots&\cdots&\cdots&\cdots&\cdots&\cdots\\ a_{m1}x_{1}&+a_{m2}x_{2}&+&\cdots&+a_{mn}x_{n}&\leq&b_{m}x_{n+1}\end{array}  \tag{24}\]  
where the \(b\) coefficients are not all zeros. Since we want to use the point of view of duality, we try to identify one dual cone to work with, but unfortunately, it is not easy with the system written in this form. For the dual cone to appear in some place, we need to write this system in another equivalent form. To this end, first, we multiply the right-hand side terms, \(b_{1},b_{2},\ldots,b_{m}\) by a virtual unknown \(x_{n+1}\), which we make equal to \(1\) in order not to alter the system. Thus, we add the last constraint \(x_{n+1}=1\). \[ \begin{array}{cccccccc}a_{11}x_{1}&+a_{12}x_{2}&+&\cdots&+a_{1n}x_{n}&\leq& b_{1}x_{n+1}\\ a_{21}x_{1}&+a_{22}x_{2}&+&\cdots&+a_{2n}x_{n}&\leq&b_{2}x_{n+1}\\ \cdots&\cdots&\cdots&\cdots&\cdots&\cdots\\ a_{m1}x_{1}&+a_{m2}x_{2}&+&\cdots&+a_{mn}x_{n}&\leq&b_{m}x_{n+1}\\ &&x_{n+1}&=&1\end{array}  \tag{25}\]  
Next, we move the right-hand side terms to the left-hand sides and we obtain:  
\[ \begin{array}{cccccccc}a_{11}x_{1}&+a_{12}x_{2}&+&\cdots&+a_{1n}x_{n}&-b_{1 }x_{n+1}&\leq&0\\ a_{21}x_{1}&+a_{22}x_{2}&+&\cdots&+a_{2n}x_{n}&-b_{2}x_{n+1}&\leq&0\\ \cdots&\cdots&\cdots&\cdots&\cdots\\ a_{m1}x_{1}&+a_{m2}x_{2}&+&\cdots&+a_{mn}x_{n}&-b_{m}x_{n+1}&\leq&0\\ x_{n+1}&=&1.\end{array}  \tag{26}\]  
Finally, for convenience, we also incorporate the constraint \(-x_{n+1}\leq 0\), which is redundant, because since \(x_{n+1}=1\) we have \(x_{n+1}\geq 0\), which is equivalent to \(-x_{n+1}\leq 0\):  
\[ \begin{array}{cccccccc}&-x_{n+1}&\leq&0\\ a_{11}x_{1}&+a_{12}x_{2}&+&\cdots&+a_{1n}x_{n}&-b_{1}x_{n+1}&\leq&0\\ a_{21}x_{1}&+a_{22}x_{2}&+&\cdots&+a_{2n}x_{n}&-b_{2}x_{n+1}&\leq&0\\ \cdots&\cdots&\cdots&\cdots&\cdots\\ a_{m1}x_{1}&+a_{m2}x_{2}&+&\cdots&+a_{mn}x_{n}&-b_{m}x_{n+1}&\leq&0\\ x_{n+1}&=&1.\end{array}  \tag{27}\]Thus, the initial system of Equation (24) and the system (27) are equivalent. This immediately suggests solving first the homogeneous system in (27) and imposing later its last constraint. As shown, in the following example, this shows that the general solution of a system of linear inequalities is a polyhedron, that is, the sum of a linear subspace plus a cone plus a polytope:  
\[\mathbf{x}=\mathbf{V}\boldsymbol{\rho}+\mathbf{W}\boldsymbol{\pi}+\mathbf{P} \boldsymbol{\lambda} \tag{28}\]  
where the columns of matrices \(\mathbf{V}\), \(\mathbf{W}\), and \(\mathbf{P}\) contain the basis of the linear subspace, the set of edges of the cone, and the set of vertices of the polytope, and some of them could not exist. Thus, it is convenient to have algorithms, such as the \(\Gamma\) algorithm, that directly supply a basis, a set of edges, and a set of vertices, respectively, as their minimal representations. The most frequent case in practice occurs when the system of inequalities is bounded, then, the final result is a polytope (to learn about polytopes, see [3; 22]). The problem of obtaining the set of vertices of a polytope was dealt with in [2; 4; 20; 23; 24]. A comparison of several methods can be seen in [23]. A very well-known case is the case of systems of linear equations, that lead to affine spaces, that is, the sum of a linear subspace and a degenerated polytope, generated by a unique vector. An algorithm to solve this special case is given in [6].