Return to Question

Let $M$ be a fixed $m \times n$ rectangular matrix ($m > n$) with non-negative integer coefficients.

Does there exist a pair $(R, \epsilon)$ with the following properties:

If $b$ is a $m \times 1$ vector with non-negative integer coefficients such that $\| b \| > R$ and $x'$ a $n \times 1$ vector in $\mathbb{R}^n$ such that:

$$ \|Mx' - b\| < \epsilon, $$ i.e. $x'$ is almost a solution to $My = b$, then there exists a vector $x \in \mathbb{R}^n$ which is an actual solution, i.e $Mx = b$.

Let $M$ be a fixed $m \times n$ rectangular matrix ($m > n$) with non-negative integer coefficients.

Does there exist a pair $(R, \epsilon)$ with the following properties:

If $b$ is a $m \times 1$ vector with non-negative integer coefficients such that $\| b \| > R$ and $x'$ a $n \times 1$ vector in $\mathbb{R}^n$ such that:

$$ \|Mx' - b\| < \epsilon, $$ i.e. $x'$ is almost a solution to $My = b$, then there exists a vector $x \in \mathbb{R}^n$ which is an actual solution, i.e $Mx = b$.

EDIT: I've changed the original formulation to make it more transparent.

Consider a linear equation $Mx = b$, where the $M$ is an $m \times n$ rectangular matrix ($m > n$) with integer coefficients and $b$ is a $m \times 1$ vector with integer coefficients. The norm of $b$ is much bigger than that of $M$.

I am looking for a solution over the reals of this equation, i.e. $x \in \mathbb{R}^n$. I know that there exists a vector $x'$ which is almost a solution, i.e. all coefficients of $Mx' - b$ are very small.

Does this mean that there exists an actual solution? Is there a quantitative version of this result?

EDIT: $M$ and $b$ are not fixed here, what is known is that $M$ is bounded, $b$ can be arbitrarily big and $Mx' - b$ arbitrarily small.

Let $M$ be a fixed $m \times n$ rectangular matrix ($m > n$) with non-negative integer coefficients.

Does there exist a pair $(R, \epsilon)$ with the following properties:

If $b$ is a $m \times 1$ vector with non-negative integer coefficients such that $\| b \| > R$ and $x'$ a $n \times 1$ vector in $\mathbb{R}^n$ such that:

$$ \|Mx' - b\| < \epsilon, $$ i.e. $x'$ is almost a solution to $My = b$, then there exists a vector $x \in \mathbb{R}^n$ which is an actual solution, i.e $Mx = b$.

Consider a linear equation $Mx = b$, where the $M$ is an $m \times n$ rectangular matrix ($m > n$) with integer coefficients and $b$ is a $m \times 1$ vector with integer coefficients. The norm of $b$ is much bigger than that of $M$.

I am looking for a solution over the reals of this equation, i.e. $x \in \mathbb{R}^n$. I know that there exists a vector $x'$ which is almost a solution, i.e. all coefficients of $Mx' - b$ are very small.

Does this mean that there exists an actual solution? Is there a quantitative version of this result?

Consider a linear equation $Mx = b$, where the $M$ is an $m \times n$ rectangular matrix ($m > n$) with integer coefficients and $b$ is a $m \times 1$ vector with integer coefficients. The norm of $b$ is much bigger than that of $M$.

I am looking for a solution over the reals of this equation, i.e. $x \in \mathbb{R}^n$. I know that there exists a vector $x'$ which is almost a solution, i.e. all coefficients of $Mx' - b$ are very small.

Does this mean that there exists an actual solution? Is there a quantitative version of this result?

EDIT: $M$ and $b$ are not fixed here, what is known is that $M$ is bounded, $b$ can be arbitrarily big and $Mx' - b$ arbitrarily small.