5
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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 $\endgroup$ Aug 6, 2012 at 3:38

1 Answer 1

7
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Aug 6, 2012 at 4:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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