5
$\begingroup$

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

$\endgroup$
  • 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
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ That's a cool technique! $\endgroup$ – Dirk May 30 '16 at 12:51

Your Answer

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

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