Upper bound for largest eigenvalue of 0-1 matrix 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
 A: 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.
