Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I have large $(0-1)$-matrices with the additional property that the first row and the first column are almost all $1$'s. My question is

Is there a (good) algorithm to obtain an upper bound for the largest eigenvalue of such a matrix ?

This question actually didn't come up in my own research but some collaborator of mine asked this question at dinner these days. I thus don't know more about the background of the question, but my impression would be that if anything is known, this is the right place to ask.

Thanks, Christian

share|improve this question
    
The largest Eigenvalue is bounded by the Matrix norm: given your matrix $A$, the norm $\|A\|$ is defined as the supremum of $\frac{\|Av\|}{\|v\|}$ where $v$ ranges over unit vectors. You can see in the second section of [this paper][1] that any binary matrix $\|A\|$ is bounded above by $n\sqrt{n}$ where $n$ is the dimension of $A$. [1]: math.uconn.edu/~kconrad/blurbs/linmultialg/matrixnorm.pdf –  Vidit Nanda Aug 6 '12 at 3:38
add comment

1 Answer

EDIT: this answer was originally written in response to an older version of the question, which merely asked for upper bounds on the largest eigenvalue rather than an algorithm.


Take your matrix to have all entries equal to $1$ to get a matrix which has $n$ as an eigenvalue.

Let $A$ be an $n\times n$ matrix with $0$-$1$ entries. Let $x=(x_1,\dots, x_n)^\top$ and calculate

$$ \begin{aligned} \sum_{i=1}^n \left\vert \sum_{j=1}^n A_{ij} x_j\right\vert^2 & \leq n \left( \sum_{j=1}^n \vert x_j\vert \right)^2 \quad\hbox{(triangle inequality)} \\ & \leq n^2 \sum_{j=1}^n \vert x_j\vert^2 \quad\hbox{(Cauchy-Schwarz)} \\ \end{aligned} $$ to see that $\Vert Ax \Vert^2 \leq n^2 \Vert x\Vert^2$. So the norm (= largest singular value), and hence the largest eigenvalue, of $A$ is at most $n$. The example I gave at the start shows this is sharp.

The moral is that unless we have more information about this 0-1 matrix, very little informative can be said regarding upper bounds on the largest eigenvalue.

share|improve this answer
    
Thanks for your answer -- I guess we do not have more information about the structure of the matrices. My question goes more in the direction of an algorithm to obtain an upper bound for the largest eigenvalue of a particular given matrix. I gonna clarify this in the question as well. –  Christian Stump Aug 6 '12 at 4:53
add comment

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.