1
$\begingroup$

I am currently dealing with the following problem. I am given a matrix $A$ of order $n \times n$ where $n \leq 20.$

The principal $(n-1) \times (n-1)$ matrix of $A$ is symmetric and contains only $\{0,1\}$ as its entries. The $n'$th row and column contains a scaled row sum of this principal sub-matrix. In particular $A$ is not symmetric but its eigenvalues are real.

I would like to determine whether the second largest eigenvalue $\lambda_2$ of $A$ is greater than $2.$

Its perfectly ok for me if the procedure says this is not so (while in fact it is) as long as I do not get false positives.

Right now I am simply computing the eigenvalues of $A$ and checking the condition but it takes a lot of time given that $A$ is not symmetric.

Hence my question is

Are there any better (faster) ways to determine if $\lambda_2 > 2?$

I suppose I could evaluate some determinants of the form $A+\epsilon+2I$ and compare signs, but this approach looks really scary to me.

$\endgroup$
  • $\begingroup$ I am not sure what you mean by a lot of time. On my machine, calculating the eigenvalues for 10,000 random matrices of order 20x20 using the numpy SVD takes about 4 seconds. Is that too long for your particular problem? $\endgroup$ – SquaredSum Feb 12 '15 at 19:55
  • $\begingroup$ Yes, that is indeed too long. I need to do that for an extreme amount of matrices. $\endgroup$ – Jernej Feb 12 '15 at 20:24
  • $\begingroup$ How many matrices do you need? $\endgroup$ – nicoguaro Feb 12 '15 at 20:31
  • $\begingroup$ @nicoguaro Lets say about $2^{30}$ as a rough estimate. $\endgroup$ – Jernej Feb 12 '15 at 21:22
  • $\begingroup$ Your arithmetic in the above comment is a bit off. $2^{30}$ is about $1 \times 10^{9}$, so if you could get $\lambda_{2}$ in a billionth of a second you could do this for a billion matrices in about 1 second. At the slow speed of 4 seconds for 10,000 matrices, your $10^{9}$ matrices would take about $4 \times 10^{5}$ seconds or 120 hours. $\endgroup$ – Brian Borchers Feb 12 '15 at 22:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.