Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.