# smallest eigenspace dimension symmetric

Hi would you help me with the following:

Let $A = (a_{ij}) R^{n \times n}$ be a symmetric matrix satisfying: $a_{1i} \neq 0$; Sum of each row equals $0$ and each diagonal element is the sum of absolute values of other entries in the row.

Determine the dimension of eigenspace corresponding to the smallest eigenvalue of $A$.

Thanks a lot!!

-
Just a clarification, what do you mean by small? In terms of absolute value, or relative? I.e. would you consider 0 the smallest eigenvalue? –  Calvin Lin Jan 8 '13 at 4:23
the eigenvalues are nonnegative anyway by Gershgorin. –  Salih Ucan Jan 8 '13 at 4:25
Interesting I didn't know that theorem. Well, it's clear that 0 is an eigenvalue, so you could phrase it as asking for the dimension of the kernel. –  Calvin Lin Jan 8 '13 at 4:30

First, let's write down something that everyone knows. By the properties of $A$, all diagonal entries of $A$ are positive and all off-diagonal entries of $A$ are nonpositive. Hence by Gersgorin disc theorem and the symmetry of $A$, all eigenvalues of $A$ are nonnegative. In particular, $0$ is the smallest of $A$ and $(1,1,\ldots,1)^T$ is a corresponding eigenvector.

Now let $e^T$ be the $(n-1)$-vector containing all ones. Write $A=\begin{pmatrix}a&b^T\\b&C\end{pmatrix}$ where $a$ is the $(1,1)$-th entry of $A$. By the properties of $A$, we have $$\begin{pmatrix}1&e^T\\0&I_{n-1}\end{pmatrix} A\begin{pmatrix}1&0\\e&I_{n-1}\end{pmatrix} =\begin{pmatrix}1&e^T\\0&I_{n-1}\end{pmatrix} \begin{pmatrix}0&b^T\\0&C\end{pmatrix} =\begin{pmatrix}0&0\\0&C\end{pmatrix}=:B \ \text{ (say)}.$$ Since all off-diagonal entries in the first row/column of $A$ are strictly negative, $C$ is strictly diagonally dominant. Hence all eigenvalues of $C$ are positive, i.e. $0$ is a simple eigenvalue of $B$. Therefore, by Sylvester's law of inertia, $0$ is also a simple eigenvalue of $A$. Hence the dimension of eigenspace corresponding to the smallest eigenvalue of $A$ is $1$.

-
+1 I think yours is much better, and deals with it cleanly. I wasn't aware of Greshgorin initially, didn't think of Sylvester to determine the signage (though on hindsight that should have been the approach). –  Calvin Lin Jan 8 '13 at 16:38
@CalvinLin I'm not flattering you, but I really like your eigenvector idea. And based on your communications to the OP, I doubt if the OP could understand my solution (no offence to him/her). In contrast, yours is very easy to understand, and that's why I think your solution is nice (at least the idea is nice; the presentation, after all those edits, is getting a bit messy, though). –  user1551 Jan 8 '13 at 17:00
Haha, well, there's always 'the way to approach linear algebra', and 'the way students do brute force matrix manipulation'. I'm strongly in favor of the former, as it indicates an understanding of the subject. Am slowly remembering all my Linear Algebra Theorems. I never saw Greshgorin before, and it's really cool, esp about the disjoint discs. –  Calvin Lin Jan 8 '13 at 17:03

Since the matrix is symmetric, all eigenvalues are real. By Greshgorin circle theorem, each of these eigenvalues lies in the disc centered $a_{ii}$ with radius $a_{ii}$, hence are non-negative. The eigenvalues are thus non-negative. The smallest eigenvalue is clearly $0$, since the all 1 vector is an eigenvector with eigenvalue 0.

Since each diagonal element is the sum of absolute values in each row, and each row has a sum of 0, thus the only positive entries are on the diagonal, and the rest of the entries are nonpositive. In particular, all the $a_{1i}, i\neq 1$ are negative.

(Added explanation: If any of the non-diagonal elements are positive, then by considering the sum of that row, we will get a positive value, hence the row doesn't have a sum of 0. The mathematical proof is:

$a_{kk} = \sum_{k \neq i} |a_{ki}|$, so $0 = |a_{kk} + \sum_{k\neq i} a_{ki}| \geq a_{kk} - \sum_{k \neq i} |a_{ki}| = 0$ by the triangle inequality. Since equality holds, this implies that $a_{ki}$ must have the opposite sign (or could be 0), as compared to $a_{kk}$.)

Edit: Since a real symmetric matrix has a complete (orthogonal) eigenbasis, to calculate the dimension of the generalized eigenspace, it is sufficient to consider just eigenvectors.

Now, consider any other eigenvector $v$ that isn't a multiple of the all 1 vector. If it isn't a multiple of a vector with $\pm 1$ entries, let $v_k$ be (one of) the entry with the largest absolute value, and there exists $j$ such that $|v_j| < |v_k|$ Consider expansion along row $k$, we get $$\sum_{i\neq k} |a_{k i} v_i| \leq \sum_{i \neq k} |a_{ki}| \cdot |v_k| \leq |a_{k k} v_k|.$$ However, we cannot have equality hold throughout, since we have $|v_j| < |v_k|$. Hence, the kth entry in $A v_k$ is not 0, so the eigenvalue is not 0.

If $v$ is a multiple of a vector with $\pm1$ entries, consider expansion along the first row. We now use the condition that $a_{1i} < 0$, which shows that in order for this eigenvector to have eigenvalue 0, then this eigenvector must be a multiple of $(1, 1, 1, \ldots, 1)$, which we already considered.

Hence, there is no other possible eigenvector with eigenvalue 0, so the dimension of this eigenspace is 1.

You should read user1551's solution, as that has a better way of dealing with the eigenvalues, then such a crude brute force computation.

-
@AdamW Agreed. I've now edited it to account for $\pm 1$, and actually used the condition that $a_{1i} \neq 0$. Otherwise, the conclusion need not be true, like if we had 2 by 2 symmetric blocks. –  Calvin Lin Jan 8 '13 at 14:17
@Calvin i dont understand why the off diagonal elements must be nonpositive?? –  Salih Ucan Jan 8 '13 at 15:10
@Yobo This follows directly from the condition that "Sum of each row equals 0 and each diagonal element is the sum of absolute values of other entries in the row." Let me add an explanation. –  Calvin Lin Jan 8 '13 at 15:12
@Yobo, the rest of the entries are nonpositive. I do not know what you edited that. For example, consider $\begin{pmatrix} 2 &-1 &-1\\ -1 & 2 & -1 \\ -1 & -1 & 2 \\ \end{pmatrix}$ –  Calvin Lin Jan 8 '13 at 15:20
@thanks calvin i got that nonpositivity now, i am continuing reading your solution.. –  Salih Ucan Jan 8 '13 at 15:22