1
$\begingroup$

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?

  • 2
    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.2012-05-26

4 Answers 4

6

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

3

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.

  • 0
    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?2012-05-26
0

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

  • 0
    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).2012-05-26
0

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.