# How to solve $Ax = \lambda x + b$ efficiently?

Let $A$ be a real symmetric invertible matrix and $b$ a real non-zero vector. Consider the problem of finding a real number non-zero $\lambda$ and a real valued vector $x$ such that $$Ax=\lambda x + b.$$

How can I numerically and efficiently solve this problem?

-
There are couple of trivial (silly?) solutions with $\lambda = 0, 1.$ If $\lambda = 0,$ then $Ax = b,$ or $x = A^{-1} b.$ If $\lambda = 1,$ then $Ax = x + b,$ or $x = (A - I)^{-1} b.$ – user2468 May 26 '12 at 16:38
I understand my question may sound silly. There is only a finite number of eigenvalues and I am looking at finding numerically a non-eigenvalue (λ=1 can be an eigenvalue, for exemple take A=I). – Peter Lewis May 26 '12 at 17:04
One thing to note is that you get a (unique) solution for every choice of $\lambda$ that isn't an eigenvalue. (and maybe even some solutions where $\lambda$ is an eigenvalue) If it's okay to diagonalize, that makes it easy to find many solutions. – Hurkyl May 26 '12 at 17:40

If $\lambda$ is not an eigenvalue, then $A-\lambda I$ is invertible, so that you can solve the system $(A-\lambda I)x=b$ by finding the inverse of $A-\lambda I$.

If $\lambda$ is an eigenvalue then the system may not have solutions. Consider

$A=\begin{pmatrix} 1 &0\\ 1 & 1 \end{pmatrix}$ and $\lambda=1$ and $b=\begin{pmatrix} 1\\ 0 \end{pmatrix}$. The system $(A-I)x=b$ is impossible to solve since $b$ is not in the columnspace of $(A-I)=\begin{pmatrix} 0 &0\\ 1 & 0 \end{pmatrix}$.

-

What about looking at the linear system $$(A-\lambda I)x=b\,\,?$$ You can solve this numerically by reducing the LHS matrix, since if this is what I think it is, $\,\lambda\,$ is an eigenvalue of $\,A\,$ and thus the system may not have a unique solution (or even not solution at all), unless $\,b=0\,$ , so using the inverse of the coefficients matrix wouldn't be an option here. If $\,\lambda\,$ is not an eignevalue of A then it may be you can use the inverse matrix.

-
As stated in the question, $b$ is non-zero. So $\lambda$ is not an eigenvalue. – user2468 May 26 '12 at 16:31
Either I missed that info or was added later in edit, yet $\,\lambda\,$ could still be an eigenvalue...why not? – DonAntonio May 26 '12 at 16:35
@J.D. There is no reason that $b$ nonzero should mean $\lambda$ is not an eigenvalue as far as I can see... If $\lambda$ is an eigenvalue then the kernel is nonzero, but that doesn't mean it is the zero map. – rschwieb May 26 '12 at 16:44
@rschwieb you're right. My comment was inaccurate. – user2468 May 26 '12 at 16:45
I believe my problem can be reduced to finding a non-eigenvalue λ, that is (by definition) a real-number λ such that A−λI is invertible. What is the most efficient way to do that? Should I randomly generate a real number λ and test if A−λI is invertible? – Peter Lewis May 26 '12 at 17:06

Too long for a comment.

This is not the most numerically stable algorithm, but I think you can find $\lambda$'s using the characteristic polynomial of $A.$

For your problem, you're looking at $(A - \lambda I)$ being invertible. Let the characteristic polynomial of $A$ be $f(y) = {\rm det}(A - yI) \in \mathbb{R}[y].$ The characteristic polynomial of $(A - \lambda I)$ is then $$g(x) = {\rm det}((A - \lambda I) - xI) = {\rm det}(A - (\lambda+x) I) = f(\lambda + x).$$ The matrix $(A - \lambda I)$ is invertible if the constant coefficient of $g(x)$ is non-zero.

So

1. Find $f(y),$ the characteristic polynomial of $A$.

2. Substitute $y \mapsto \lambda + x$ in $f(y)$ to get $g(x).$

3. Expand $g(x) = g_0(\lambda) + g_1(\lambda) x + \ldots + x^d.$

4. Let $\Lambda \subset R$ be the set of all solution of $g_0(\lambda) = 0.$ The values of $\lambda$ for which $(A - \lambda I)$ is invertible are $\mathbb{R} - \Lambda.$

-
I work with huge matrices, so finding the characteristic polynomial may not be doable in practice. I have made some tests in Matlab and I found that computing the characteristic polynomial takes way more time than computing the determinant (which is done iteratively I think). – Peter Lewis May 26 '12 at 17:34

Unless you're unlucky, and $\lambda$ is an eigenvalue, this is just straightforward solving of a system of linear equations. There is lots of good software for doing this efficiently. Matlab can do it, and there is software in the "Numerical Recipes" book, or elsewhere. Don't try to write the code yourself, and don't try to find the inverse of the matrix.

If you're interested in finding eigenvalues, then there's lots of good software for that, too. Again, "Numerical Recipes" is a good place to start. Again, don't try to write the software yourself. Also, don't try to find the roots of the characteristic polynomial -- that's much more difficult than computing eigenvalues.

-