# Solving an overdetermined system of inequalities using null-space arguments

The solutions to a linear system of equations:

$$A\cdot x = b$$

(where $x$ is a $(n\times 1)$ column vector, $b$ is a $(m\times 1)$ column vector and $A$ is $(m\times n)$ matrix)

can all be expressed as:

$$x_{1} + \sum_{i=1}^{n-m}c_{i}\vec{\lambda}_{i}$$

where $x_{1}$ is any one solution and $\{\vec{\lambda}_{1}, \cdots, \vec{\lambda}_{n-m}\}$ span the null space of $A$.

Hence as an algorithm to generate the possible solutions, I can think of finiding one possible solution and then using the null-space to enumerate all others.

Here is my question, which concerns a system of linear inequalities:

$$A\cdot x \leq b$$

Moreover, i have an over-determined system of inequalities i.e, more constraints than unknowns. Hence $A$ is a $(m\times n)$ where $m > n$. If I know one solution, Can I imagine to use the null-space of a sub-matrix of $A$ to generate solutions ?

Sorry, I don't know how to think about using the null-space here actually.

Any hints will be helpful. Thanks.

-
What does it mean for a vector to be less than another vector? This is what you're saying when you say $A\cdot x \leq b$. –  noobProgrammer Mar 15 '13 at 3:22
I mean element-vise inequalities. Sorry, I skipped to mention it as I thought it was implicit. –  Pavithran Iyer Mar 15 '13 at 3:33
You have both $m>n$ and the set $\{\vec{\lambda}_{1}, \cdots, \vec{\lambda}_{n-m}\}$. This implies there is no null space... –  adam W Mar 19 '13 at 15:50