I would be grateful for pointing me out a reference to some general bound on the $\ell_{\infty}$ norm of a solution of a linear system. To be specific, suppose that we have an underdetermined linear system $Ax = b$. What I want to know, is some general upper bound on the minimum $\ell_{\infty}$ norm of the solution.
In other words: I want to know that I can find a solution of the system with a norm not greater than…
Bound should be in terms of: the number of variables, the number of equations (we can assume that this number is much smaller if it helps) and of course of $A$ and $b$.
For example, if we have $n$ variables and one equation: $a_1x_1 + a_2x_2 + \ldots + a_nx_n = b$, then the minimal norm is given by $\frac{|b|}{|a_1|+|a_2| + \ldots + |a_n|}$. I suspect that for an arbitrary number of equations, smaller than $n$, there should exist some nice estimation of the norm. I have searched in the web for such a result on my own, but have only managed to find a papers concerning the problem of finding such solution algoritmically and no explicit bounds were mentioned.
Best Answer
I believe you cannot give any general bound, but if the coefficients are integers, this is Siegel's Lemma: a system of $M$ equations in $N$ variables with integer coefficients $b_{ij}$ has an integer solution $X$ with $\|X\|_\infty \le (NB)^{M/(N-M)}$, where $B=\|b_{ij}\|_\infty$.