# 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

• 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] that any binary matrix $\|A\|$ is bounded above by $n\sqrt{n}$ where $n$ is the dimension of $A$. : math.uconn.edu/~kconrad/blurbs/linmultialg/matrixnorm.pdf Aug 6 '12 at 3:38

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.