2
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ Even if you fix $M$, but not $b$ you can't say anything. If $M$ is not onto, there exist arbitrary large vectors arbitrary close to the range of $M$. $\endgroup$
    – Oleg Eroshkin
    Commented Jul 5, 2023 at 16:02
  • $\begingroup$ Consider for example the case $m = 2, n = 1$ and assume that the statement is not true. Then if $M = (m_1 m_2)$ and $b = (b_1 b_2)$, we have that: $$ |m_1x' - b_1| < \epsilon \\ |m_2x' - b_2| < \epsilon. $$ Combining the two, we get: $$ |\frac{b_2}{m_2} - \frac{b_1}{m_1}| < \frac{\epsilon}{m_1} + \frac{\epsilon}{m_2}. $$ If the left hand side is 0, then we can find a solution. If it is non-zero, then it is bounded away from $0$ by $\frac{1}{m_1*m_2}$, so $\epsilon$ can't be arbitrarily small. Similar considerations work for other small pairs of $(m,n)$. $\endgroup$
    – Leon Staresinic
    Commented Jul 5, 2023 at 16:17
  • 1
    $\begingroup$ Ok, if $b$ has integer coordinates, then the distance from the range (if non-zero) is bounded from below. An elementary bound is $\mathrm{dist}(b, \mathrm{Ran} M)\geq 1/\mathrm{det}(M')$, where $\mathrm{det}(M')$ is a nonzero minor of the full rank. $\endgroup$
    – Oleg Eroshkin
    Commented Jul 5, 2023 at 17:56

1 Answer 1

Reset to default
1
$\begingroup$

Considering $M$ as a linear operator from $\mathbb R^n$ to $\mathbb R^m$, its range $\text{Ran}(M)$ is a linear subspace. Linear subspaces in finite-dimensional spaces are closed. Thus if $b \notin \text{Ran}(M)$, its distance to $\text{Ran}(M)$ is nonzero, i.e. there is $\epsilon > 0$ such that $\|M x' - b\| > \epsilon$ for all $x' \in \mathbb R^n$.

We can be a little bit more quantitative, perhaps. We can use $M$ to construct an orthogonal projection $P$ on $\text{Ker}(M^{T}) = (\text{Ran}(M))^\perp$. If $b \notin \text{Ran}(M)$, then $0 < \|Pb\| \le \|b - M x'\|$ for all $x' \in \mathbb R^n$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I was perhaps unclear, here $M$ and $b$ are not fixed, the only thing known is that $b$ has much bigger coefficients and that there is this $x'$ which is almost a solution. For example, it the case when $n = 1$, it can be easily seen that the statement is true if $b$ is big enough and the $x'$ very close to a solution. It is also true for several small combinations of $n$ and $m$. $\endgroup$
    – Leon Staresinic
    Commented Jul 5, 2023 at 15:40
  • $\begingroup$ In these terms my question can be rephrased as: If $\| Pb \|$ is non-zero, is it uniformly bounded? Note again that $b$ has non-negative integers for coefficients. $\endgroup$
    – Leon Staresinic
    Commented Jul 5, 2023 at 16:37
  • $\begingroup$ "here $M$ and $b$ are not fixed...." But the very first phrase in the question is, "Let $M$ be a fixed $m\times n$ rectangular matrix...." $\endgroup$
    – Gerry Myerson
    Commented Aug 4, 2023 at 21:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .