Bounding the minimal maximum norm of a solution of a linear system.

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.

-
You say overdetermined in the first paragraph, but your example is underdetermined. Which one is it you are looking for? – Igor Rivin Oct 15 '12 at 17:26
I've meant an undetermined system. Thank you. – user3645 Oct 15 '12 at 17:55

2 Answers

The question is easier with $L^2$ norm instead of $L^\infty$ norm -- obviously the former upper bounds the latter. Now, you are trying to minimize the norm of $x$ subject to the constraints that $x \cdot v_i = b_i.$ Using Lagrange multipliers, we see that we need $x = \sum \lambda_j v_j.$ Plugging into the original equation, we get $\mathbf{\lambda} V^t V = b.$ Since $V^t V$ is symmetric, it can be (orthogonally) diagonalized) to the matrix of the squares of singular values of $V.$ Let $\sigma_0$ be the smallest such singular value. This upper bounds all $\lambda$s by $b_{\max}/\sigma_0^2,$ and then we get an upper bound on the $L^2$ norm of $x$ in the obvious way.

-

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$.

-
The OP is not asking for an integer solution, as far as I can tell, so his question is a lot easier... – Igor Rivin Oct 15 '12 at 18:22
@Igor: you may well be right. It is not quite clear exactly what the OP is asking for: ensuring that there is a "small-height" solution, or showing that any solution has "large height". It would be good to have him clarified the matter... – Seva Oct 15 '12 at 19:34
I am asking about the existence of "small-height" solution. I have clarified it. As Igor has already said, I don't know that the coefficients are integers but I also do not seek for an integer solution. Thank you anyway for the reference to Siegel Lemma, what I need is something like a real version of it. – user3645 Oct 15 '12 at 19:49