# Nonlinear eigenvalue problem - sorta

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?

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

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

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

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

-