3
$\begingroup$

Are there any known issues (such as precision issues) with $\mathsf{MATLAB}$ eig and charpoly functions for large enough $\{-1,0,+1\}$ matrices?

Even if I change $1$ or $2$ entries between matrices would it be able to find the accurate eigenvalues and characteristic polynomials? I am using size less $40\times40$.

My matrices are full rank and symmetric. The condition number of the matrices seems in mid $100$s to $10^{15}$ while absolute value of sum of rows/columns is same.

If I can get char poly that is good enough for me.

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ It depends a lot on the properties of the matrix itself, not just matlab's eig. For example, X = horzcat(-ones(10, 1), vertcat(eye(9), (1:9)==9)); disp(X); eig(X) has all zero eigenvalues, but eig would give them on order of $10^{-3}$. I believe you can expect eig to be accurate when the matrix of eigenvectors $X$ has a low condition number, and error in eigenvalues would be on order of $\epsilon_{\mathrm{mach}} \kappa(X)$. $\endgroup$
    – Kirill
    Dec 25, 2015 at 3:18
  • 2
    $\begingroup$ Can you add any extra information about your matrices, anything at all? Knowing elements are in $\{0,\pm1\}$ isn't so much — it depends more on how sensitive they are to perturbations, and there are matrices in matlab's gallery that have sensitive eigenvalues but consist of $\{0,\pm1\}$. There is also a related question here: scicomp.stackexchange.com/questions/17517/… $\endgroup$
    – Kirill
    Dec 25, 2015 at 3:20
  • 1
    $\begingroup$ Condition number of the matrix itself or the matrix of eigenvectors? If the matrix is symmetric (or, in general, normal), the condition number of $X$ would be precisely 1, in which case eig should be accurate. $\endgroup$
    – Kirill
    Dec 25, 2015 at 3:39
  • 2
    $\begingroup$ Please put all the relevant information you have into the question itself (not the comments), so that the question is clear, direct, and self-contained. That way the question would be helpful also to other people that have the a similar question. [Side note: krill → Kirill] $\endgroup$
    – Kirill
    Dec 25, 2015 at 3:58

2 Answers 2

Reset to default
2
$\begingroup$

If, as you say, you only really need the characteristic polynomial of your matrices, and not the eigenvalues (solving for the roots of the characteristic polynomial doesn't in general give accurate eigenvalues), and since your matrices are really quite small ($40\times40$) and have only integers, it might be sufficient to just use matlab's symbolic manipulation to calculate the characteristic polynomial exactly, like so:

>> charpoly(sym(gallery('grcar', 10)))
ans =
[ 1, -10, 54, -200, 553, -1176, 1935, -2424, 2211, -1328, 401]

which sidesteps any issues with numerical accuracy of eig. Obviously the (integer) coefficients of the characteristic polynomial can be quite large.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I use syms x; polyA = charpoly(A, x); where A is the matrix of interest (is this good enough)? coefficients are very large $\endgroup$
    – Turbo
    Dec 26, 2015 at 5:56
  • $\begingroup$ @Turbo I'm sorry, I don't understand. Did it work? $\endgroup$
    – Kirill
    Dec 27, 2015 at 1:30
  • $\begingroup$ I use command $\mathsf{syms}\text{ }x$ to say $x$ is variable. I define matrix $A$ and then use $\mathsf{polyA} = \mathsf{charpoly}(A, x)$ to compute characteristic polynomial of $A$. Is this good enough? I do not know how to check for large matrices. $\endgroup$
    – Turbo
    Dec 27, 2015 at 1:39
2
$\begingroup$

Kirill's suggestion to use symbolic linear algebra is on-point. Another approach is to work out the characteristic polynomial over a number of finite fields, then use the Chinese remainder theorem to reconstruct the characteristic polynomial over $\mathbb{Z}$. Finite field linear algebra does not suffer from the same kinds of numerical problems as you'll run into with eig.

Improve this answer
$\endgroup$
2
  • $\begingroup$ @tmykledu how do you use finite field stuff in matlab? $\endgroup$
    – Turbo
    Dec 26, 2015 at 5:54
  • $\begingroup$ Good question. I've never done that successfully. $\endgroup$
    – tmyklebu
    Dec 26, 2015 at 5:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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