Suppose I have a real symmetric matrix. I would like to tell wether it has at least $k$ strictly positive eigenvalues, but using only additions (no multiplications). Is there a method that I could use? I thought that maybe Gershgorin theorem could be useful, since I need only to add row (or column) elements, but it doesn't guarantee that eigenvalues are different from zero: for example, $$ M = \begin{pmatrix} 1 & -1 & 0 & 0\\ -1 & 3 & -1 & -1\\ 0 & -1 & 2 & -1\\ 0 & -1 & -1 & 2 \end{pmatrix} $$ has eigenvalues $0,1,2,4$, but Gershgorin's theorem would give me estimates $$ \begin{align*} 1 \pm 1 &= [0,2]\\ 3 \pm 3 &= [0,6]\\ 2 \pm 2 &= [0,4]\\ 2 \pm 2 &= [0,4] \end{align*} $$ and I wouldn't know, looking at the estimates only, wethere there is any eigenvalue $>0$.
-
6$\begingroup$ Why no multiplies? $\endgroup$ – Bill Barth May 28 '16 at 1:21
-
1$\begingroup$ I fixed a sentence which has almost correct, but wrong enough to warrent an edit. I would also like to know why you are limited to using additions! Is it a matter of doing a quick sanity check of the input to a routine which is only sure to run to completion if the input is symmetric positive definite? $\endgroup$ – Carl Christian May 30 '16 at 11:56
Conclusions are indeed possible, but Gershgorin's circle theorem must be supplemented with other results. Let \begin{equation} \lambda_1 \leq \lambda_2 \leq \lambda_3 \leq \lambda_4 \end{equation} denote the eigenvalues of $M$. Let $N$ denote the lower 3 by 3 corner of $M$, i.e, \begin{equation} N = \begin{bmatrix} 3 &-1 & -1 \\ -1 & 2 & -1 \\ -1 & -1 & 2 \end{bmatrix} \end{equation} and let \begin{equation} \mu_1 \leq \mu_2 \leq \mu_3 \end{equation} denote the eigenvalues of $N$. Then by Cauchy's interlacing theorem \begin{equation} \lambda_1 \leq \mu_1 \leq \lambda_2 \leq \mu_2 \leq \lambda_3 \leq \mu_3 \leq \lambda_4. \end{equation} The eigenvalues "interlace" much like the teeth of a zipper. Unfortunately, no conclusion's can be drawn from studying Gershgorin's intervals for $N$. However, conclusions are possible by passing to $K$, the upper two by two corner of $N$, i.e. \begin{equation} K = \begin{bmatrix} 3 & -1 \\ -1 & 2 \end{bmatrix}. \end{equation} Let $\nu_1 \leq \nu_2$ denote the eigenvalues of $K$. By Gershorin's theorem, they are both positive. By Cauchy's theorem we have \begin{equation} \mu_1 \leq \nu_1 \leq \mu_2 \leq \nu_2 \leq \mu_3 \end{equation} Since $\nu_1$ is positive, we can conclude $\mu_2$ and $\mu_3$ are positive. It follows that $\lambda_3$ and $\lambda_4$ are both positive.
We can push further using only additions. By inspection, we see that $N$ is irreducibly diagonally dominant, because it is weakly diagonally dominant in rows 2 and 3, and strictly diagonally dominant in row 1. It follows that $N$ is non-singular. Since Gershgorin's theorem implies that $0 \leq \mu_1$, we now know that $0<\mu_1$. It follows immediately, that $0 < \lambda_2$.
As for the remaining eigenvalue of $M$, i.e. $\lambda_1$, we observe that the row sums of $M$ are all $0$. Therefore, $\lambda_1 = 0$, and $v_1 = (1,1,1,1)^T$ is a corresponding eigenvalue.
This procedure generalizes as follows:
Using comparisons we establish that a matrix $M$ is symmetric and has positive diagonal entries. Using additions we can determine that it is also weakly diagonally dominant. By Gershgorin's theorem it follows that it is semi-definite. If there is a single row which is stricly diagonally dominant, then the matrix is irreducibly diagonally dominant, hence non-singular, hence positive definite.
Otherwise, we obtain a new matrix $N$ by deleting, a weakly diagonally dominant row and the corresponding column from $M$. The new matrix will be strictly diagonally dominant in at least one row, because we did remove at least one nontrivial off diagonal element when we created $N$. As before we conclude that $N$ is positive definite. By Cauchy's theorem it follows that $M$ has at least $n-1$ positive eigenvalues.
I do not know if it is possible to determine if zero is an eigenvalue of $M$ using additions only.
