Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Here is the full question.

  • Only the last row and the last column can contain non-zero entries.

  • The matrix entries can take values only from $\{0,1\}$. It is a kind of binary matrix.

I am interested in the eigenvalues of this matrix. What can we say about them? In particular, when are all of them positive?

share|improve this question
    
Most ot them are zero, so you mean maybe nonnegative? –  Alex Mar 27 '13 at 16:24
    
If $M$ is your matrix, you should try to develop the determinant of $(M - \lambda I)$ using cofactors –  Vincent Nivoliers Mar 27 '13 at 16:32

4 Answers 4

up vote 1 down vote accepted

$$\pmatrix{Q & 0 \\ 0 & 1}\pmatrix{\mathbf{0} & u \\ v^\top & a}\pmatrix{Q^{-1} & 0 \\ 0 & 1}=\pmatrix{\mathbf{0} & Qu \\ v^\top Q^{-1} & a}$$

This similarity operation preserves the value of the product of the vectors: $$v^\top u \leftarrow v^\top Q^{-1} Q u = v^\top u $$ Say that the $Q$ is Gaussian elimination on the column $u$ so that you are left with a zero column except the one element, giving the $2 \times 2$ sub-matrix $$\pmatrix{0 & 1 \\ v^\top u & a}$$

This represents the only two non-trivial eigenvalues (the rest are zero). It may be transformed with the similarity parameterized with some $k$: \begin{align} \pmatrix{1 & 0 \\ k & 1}\pmatrix{0 & 1 \\ v^\top u & a}\pmatrix{1 & 0 \\ -k & 1} \\ = \pmatrix{0 & 1 \\ v^\top u & k+a}\pmatrix{1 & 0 \\ -k & 1} \\ = \pmatrix{-k & 1 \\ v^\top u - k^2 - ka & k+a} \\ \end{align} and of course you want to solve $$v^\top u - k^2 - ka = 0$$ giving the two eigenvalues of $$\lambda_0=-k$$ and $$\lambda_1 = k+a$$ $$ k^2 + ka - v^\top u = 0 \Rightarrow k=\frac{-a \pm \sqrt{a^2 + 4 v^\top u}}{2}$$ $$\lambda = \frac{a \pm \sqrt{a^2 + 4 v^\top u}}{2}$$ Since your elements are $0$ or $1$ you have that $v^\top u\ge 0$, and you have eigenvalues both positive and negative when $v^\top u \gt 0$, and another zero eigenvalue ($\lambda_0 = 0$ and $\lambda_1 = a$) when $v^\top u = 0$.

Not all of them are positive since there are zero eigenvalues, and they are only non-negative when $$v^\top u = 0$$

share|improve this answer

At first I thought I understood your question, but after reading those comments and answers here, it seems that people here have very different interpretations. So I'm not sure if I understand it correctly now.

To my understanding, you want to find the eigenvalues of $$ A=\begin{pmatrix}0_{(n-1)\times(n-1)}&u\\ v^T&a\end{pmatrix}, $$ where $a$ is a scalar, $u,v$ are vectors and all entries in $a,u,v$ are either $0$ or $1$. The rank of this matrix is at most $2$. So, when $n\ge3$, $A$ must have some zero eigenvalues. In general, the eignevalues of $A$ include (at least) $(n-2)$ zeros and $$\frac{a \pm \sqrt{a^2 + 4v^Tu}}{2}.$$ Since $u,v$ are $0-1$ vectors, $A$ has exactly one positive eigenvalue and one negative eigenvalue if $v^Tu>0$, and the eigenvalues of $A$ are $\{a,0,0,\ldots,0\}$ if $v^Tu=0$.

share|improve this answer
    
Hello user1551, Do you remember this question math.stackexchange.com/questions/262385/… –  dineshdileep Mar 28 '13 at 4:33
    
I was trying to prove it on my own. The idea was to use induction. For a $n+1 \times n+1$ matrix $B_{n+1}=[[B_{n},0];[0,0]]+A$, $B_{n}$ is a binary matrix with all eigenvalues as 1, $A$ is as you defined in the answer. Now, we have to prove only that $B_{n+1}$ will also have all eigenvalues as 1. –  dineshdileep Mar 28 '13 at 4:36
    
Thanks for the answer btw. –  dineshdileep Mar 28 '13 at 4:48
    
@dineshdileep I remember that question. Did you find a solution? –  user1551 Mar 28 '13 at 11:36
    
No, I try it once in a while. It is tagged in my favorites. Today, I was again at it. That is how this question came out. Please, check the previous comment. –  dineshdileep Mar 28 '13 at 15:24

Such a matrix, of size $3 \times 3$ or larger, will never have all non-zero eigenvalues. This is because the first two columns of the matrix are linearly independent, hence the determinant is zero, hence zero is an eigenvalue.

share|improve this answer
    
What if the first columns are zero? –  dineshdileep Mar 28 '13 at 4:38
    
If there's a row of zeros then the determinant is zero. –  Jim Mar 28 '13 at 5:39

I'm not sure whether this is the kind of thing you are looking for but...

Let $n_r$ be the number of ones on the last row and $n_c$ that on the last column. Then, by Gershgorin circle theorem then the eigenvalues all lie in

$B(0,1)\cup B(a,min\{n_c,n_r\}-a)$

where $a$ is bottom right corner entry of the matrix and $B(x,y)$ is the closed ball of radius $y$, centred around $x$.

Also - adding to Jim's answer - the rank of such a matrix will be at most two, thus the matrix will have at most two non-zero eigenvalues.

share|improve this answer
    
that is one way to look at it I guess. Thanks –  dineshdileep Mar 28 '13 at 4:38

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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