# Affine and Linear programming

Can someone give a simple explanation as to why the feasible region of a set of linear program/equations is affine?

You can transform the feasible set of any LP into the form $Ax = b$. The solutions of this equation can be written as $x = A^{\dagger} b + y$ where $y$ solves $Ay = 0$ (i.e. $y$ is from a subspace) and $A^\dagger$ is the pseudoinverse of $A$. Thus the feasible set is given by $$S = A^\dagger b + \ker A$$ wich is obviously affine.
• The kernel of a linear mapping ($x\mapsto Ax$) is a subspace. An affine space is a translated subspace, i.e. of the form $x = c + y$ where $c$ is a vector and $y$ is from an arbitrary subspace. Aug 22, 2014 at 11:12
• one last question i had, I understand your argument for A,b being a matrix and row vector. What if we had a hyperplane of the form $a_i^Tx <=b$? I believe that this should also define an affine subspace, but using the same argument i cant multiply by any pseudoinverse right? So whats the argument there? Aug 22, 2014 at 12:35
• Here you have a form of $Ax \le b$ wich can be converted to $(A\quad I) \begin{pmatrix}x\\s\end{pmatrix} = b, s_i \ge 0$ This is an intersection of an affine subspace with a half-space ($s\ge 0$) and thus is a polytope (not necessarily an affine subspace) Aug 22, 2014 at 12:39