Symmetric 0-1 Matrices with All Eigenvalues Positive

Recently I was surprised to learn that the only n \times n symmetric 0-1 matrix with all eigenvalues positive is the n \times n identity matrix.  Here’s a very nice proof of this fact given in this answer of Robert Israel’s:

Let A be an n \times n symmetric 0-1 matrix with all eigenvalues positive.  Since A is symmetric with all eigenvalues positive, A is positive definite.  The positive definiteness of A implies that any 2 \times 2 submatrix consisting of rows and columns i and j (for i \neq j) is also positive definite.  Thus the determinant of this submatrix is positive.  Therefore, a_{ii} a_{jj} - a_{ij} a_{ji} > 0.  The only way this is possible for a symmetric 0-1 matrix is to have a_{ii} = a_{jj} = 1 and a_{ij} = a_{ji} = 0.  Thus A has all 1’s for its diagonal elements and all o’s for its off-diagonal elements.

I feel like there should be a more high-level explanation of this fact, though – a bigger-picture answer than one that operates on the level of the individual elements in the matrix.  For instance, if a matrix being symmetric implies X about the underlying linear transformation,  a matrix being 0-1 implies Y about the underlying linear transformation, and a matrix having all eigenvalues positive implies Z about the underlying linear transformation, then there ought to be some intuitive argument as to why the only linear transformation that has properties XY, and Z simultaneously is the identity transformation.  I asked this question on math.SE (in fact, Robert Israel’s argument above comes from there), but I haven’t yet received such a big-picture answer.


Added (January 25, 2013): I wrote a follow-up post where I give two bigger-picture proofs.

Advertisements
This entry was posted in linear algebra, matrices. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s