MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose you have an equation of the form $Ax=f(x)$, where $A$ is a $n \times n$ matrix, $x$ is a vector of length $n$ and $f(\cdot)$ is some function. Is there a name for this sort of problem?

share|cite|improve this question
In other words, you have an equation of the form $g(x) = 0$ where $g$ is some function. – Qiaochu Yuan Sep 7 '12 at 2:27
You can reduce almost all of mathematics to your equation. Hardly a helpful concept, I'm afraid. – Felix Goldberg Sep 7 '12 at 10:09
@Felix: I don't understand. Your equation and my equation are equivalent. Take $g(x) = f(x) - Ax$. – Qiaochu Yuan Sep 8 '12 at 20:16
@Qiaochu: Well, yes. But I thought you were over-generalizing the question to a point of absurdity. Perhaps I over-reacted, so I offer my apologies. I wrote below that my actual interest is in $Mx=\frac{1}{x}$ where I wish to bound the solution from below componentwise - perhaps you'll have some pointers for that. Thanks! – Felix Goldberg Sep 8 '12 at 22:55
@Felix: no, I was pointing out that the question itself was already overgeneralized to the point of absurdity (if you place no conditions on $f$). Your actual interest seems much more tractable. – Qiaochu Yuan Sep 9 '12 at 1:06

If $f$ is assumed to be small in some sense, a common choice is semilinear equation.

share|cite|improve this answer
Thanks a mil!!! – Felix Goldberg Sep 7 '12 at 10:10

and to be sure: the notion of "nonlinear eigenvalue problem" is usually used for equations of the form $A(u)=\lambda u$, where $A$ is a nonlinear operator (or a nonlinear mapping from $R^n$ to $R^n$, if you wish).

share|cite|improve this answer
I know, that's why I added sorta to the title. :) – Felix Goldberg Sep 7 '12 at 10:10

Do you have any examples in mind? As it stands it is essentially a system of $n$ simultaneous equations in $n$ variables. That term would (as commented above) usually suggest a system $$g_i(x)=0 \text{ for } 1 \le i \le n.$$ But that is easily obtained by setting $A$ to be the zero matrix.

If that is too degenerate then we can use your formulation with $A$ your favorite matrix and $f(x)$ returning the vector whose $i$th component is $g_i(x)+(Ax)_i.$

So some restriction is needed to get an interesting question.

share|cite|improve this answer
I was thinking about $f(x)=\frac{1}{x}$ and am interested in bounding the minimum component of a solution. – Felix Goldberg Sep 8 '12 at 10:35
Is $1/x$ a pointwise inverse? – Igor Rivin Sep 9 '12 at 0:32
If $1/x$ is pointwise inverse then the $n=2$ case with diagonal entries $0$ would give $bx_2=1/x_1,\ cx_1=1/x_2$ with either no solutions (if $bc\ne 1$ ) or else $x_1=1/x_2$ – Aaron Meyerowitz Sep 9 '12 at 8:58
@Aaron: In the case that $M$ is, say, symmetric positive definite, there is a unique positive solution. (A result of Marshall & Olkin). – Felix Goldberg Sep 9 '12 at 13:00

This does not answer the question as stated, but your specific question (assuming the inverse is coordinate-wise) can be stated as

$\min_i \min x_i,$ subject to the system of constraints

$x_i <A_i, x> = 1.$

If you remove one level of $\min,$ you are trying to minimize the function (wlog) $x_1$ over the set defined by the constraints, which reduces to a lagrange multiplier problem:

$1 = \lambda_1 \langle A_1, x\rangle + \sum_{j=2}^n \lambda_j A_{j1} x_j.$

and for $k=2, \dotsc, n$

$0 = \lambda_1 x_1 A_{1k} + \lambda_k \langle A_k, x\rangle + \sum_{j=2, j \neq k}^n A_{jk} x_1.$

Unless there is some trick to reduce this system (quite possible, I don't really want to think too hard about it), this is a general system of quadratic equations, which is ETR hard (that is, about as hard as any computational problem), so in that sense, @Quiochu's comment is very a propos.

share|cite|improve this answer

Your Answer


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.