# Deducing linear combinations of column matrices

I've a $m \times n$ column matrix $A$ that can contain values {0,0.5,1}. i.e $\Omega = \{0,0.5,1\}$

$A$ = $\begin{bmatrix} 0 & 0.5 & 0.5 & 1 & 1 & \cdots & 0 \\ 0.5 & 0 & 1 & 1 & 0 & \cdots & 1 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ 0 & 0 & 0.5 & 0.5 & 1 & \cdots & 0 \end{bmatrix}$

let the column matrix $x$ be equal to $\mathbb{R_0^{+ n \times 1}}$ (non-negative real numbers including 0)

$x$ = $\begin{bmatrix} 1 \\ 2 \\ 0 \\ 0.5 \\ 3 \\ \vdots \\ 0.3 \end{bmatrix}$

We know that $Ax = b$. So given $b$ we can find $x$ by $x = A \backslash b$ (performing matrix left division). 99.9% the matrix A is full rank (because it can contain only 3 values and $m$ is very large) but if not I could always use $x$ = pseudo-inverse$(A) \times b$.

My question is now if we are given $b$ and a matrix $A^{\prime}$ such that $A^{\prime} \supseteq A$ where $A^{\prime} \in \mathbb{R^{m \times \textbf{N}}}$ and $\textbf{N} \supseteq n$ and belong to the same domain as $A$ (pardon my math explanation. $A$ and $A^{\prime}$ has same rows but the columns of $A$ are $\subseteq$ of $A^{\prime}$ ), is it possible to find $x$ ? (Note that we do not need $A$, if a column in $A^{\prime}$ is involved in the linear combination it gets a value or else it can just be $0$).

-
I wonder why is the down vote ? Does anybody think this is not a valid problem ? It would be helpful for learners if the down voters give a reason for their action so they can avoid repeating it. –  Sunil Feb 24 '11 at 0:56
Use linear programming. –  Yuval Filmus Feb 24 '11 at 20:22