Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

While thinking about this question I managed to convince myself that the identity is the only symmetric $0$-$1$ matrix with all eigenvalues positive. However, the argument is rather low-level. It does not give much insight into why, out of all symmetric matrices, $0$-$1$ matrices, and matrices with all eigenvalues positive, the identity is the only matrix that simultaneously has all three properties.

So my question is

Can someone give an intuitive explanation for why the identity is the only symmetric $0$-$1$ matrix with all eigenvalues positive?

Such an explanation might entail a bigger-picture argument than the one I came up with.

For reference, here's my argument. Let $A$ be a symmetric $0$-$1$ matrix with all eigenvalues positive.

  1. Symmetric and all eigenvalues positive implies $A$ is positive definite.
  2. $A$ must have all $1$'s on its diagonal. This is because $a_{jj} = 0 \implies {\bf e}_j^T A {\bf e}_j = 0$, which contradicts positive definite.
  3. $A$ must have all $0$'s for its off-diagonal elements. This is because $A$ is symmetric implies $a_{ij} = a_{ji}$, and $a_{ij} = a_{ji} = 1 \implies ({\bf e}_i - {\bf e}_j)^T A ({\bf e}_i - {\bf e}_j) = 0$, which contradicts positive definite.
  4. Thus $A$ is the identity.

For clarification: I am looking for an answer along these lines: "A symmetric matrix implies or is equivalent to $X$ about the underlying linear transformation. A $0$-$1$ matrix implies or is equivalent to $Y$ about the underlying linear transformation. All eigenvalues positive implies or is equivalent to $Z$ about the underlying linear transformation. ($X$, $Y$, and $Z$ are all big-picture properties.) [Insert argument here.] Thus the only matrix that simultaneously satisfies $X$, $Y$, and $Z$ is the identity."

Robert Israel's answer, while nice, is not the kind of thing I'm hoping for. I view it as a more elegant version of my own low-level argument about what form the entries of the matrix have to take, not what kind of linear transformation has these three properties.

share|improve this question
The more interesting objects have all 2's on the main diagonal, then $0,1,-1$ elsewhere. These include the root lattices for lie algebras. math.rwth-aachen.de/~Gabriele.Nebe/LATTICES and math.rwth-aachen.de/~Gabriele.Nebe/LATTICES/index.html#root –  Will Jagy Dec 23 '12 at 4:49
While attempting to answer that question, I remember convincing myself this using some kind of perron-frobenius argument, but now I can't recall it and I even suspect if it was true. –  dineshdileep Dec 23 '12 at 6:39
add comment

2 Answers

Another way of putting it: if $A$ is positive definite, then so is the $2 \times 2$ submatrix consisting of rows and columns $i$ and $j$ (for any $i \ne j$). The determinant of this submatrix is $a_{ii} a_{jj} - a_{ij}^2$, and if the entries are in $\{0,1\}$ the only way to have $a_{ii} a_{jj} - a_{ij}^2 > 0$ is $a_{ii} = a_{jj} = 1$ and $a_{ij} = 0$.

share|improve this answer
That's a nice argument! I was hoping for something even more intuitive than this, though. –  Mike Spivey Dec 23 '12 at 4:48
add comment
up vote 0 down vote accepted

Here are two "bigger-picture" arguments that I found that I consider sufficient.

Let $A$ be a symmetric, $0$-$1$ matrix with all eigenvalues positive.

Proof 1: Correlation matrices.

Let $B$ be the diagonal matrix consisting of $1$'s where $A$ has $0$'s and $0$'s where $A$ has $1$'s. Then $A+B$ is a correlation matrix. Since adding nonnegative values to $A$'s diagonal can't decrease any of $A$'s eigenvalues (see, for example, Weyl's inequality), $A+B$ has all eigenvalues positive and is thus invertible. But the only invertible $0$-$1$ correlation matrix is the identity. (*) Since $A+B$ is the identity, $A$ must be a diagonal matrix. But the only invertible $0$-$1$ diagonal matrix is the identity. Therefore, $A$ is the identity matrix.

Proof 2: Linear transformations.

Since $A$ is a real symmetric matrix it is orthogonally diagonalizable, which means that it represents a linear transformation with scaling in mutually perpendicular directions. Since the eigenvalues are the scaling factors for the different directions, the scaling factors are all positive. This implies that for ${\bf x} \neq {\bf 0}$, $A$ cannot map ${\bf x}$ to a vector that is perpendicular to ${\bf x}$. (This follows geometrically, but you can also see this by remembering that positive definite implies something even stronger: $A {\bf x}$ must make an acute angle with ${\bf x}$.)

This non-orthogonality restriction between $A {\bf x}$ and ${\bf x}$ rules out any diagonal elements of $A$ being $0$, as otherwise $a_{ii} = 0$ would imply ${\bf e}_i$ and $A {\bf e}_i$ are orthogonal.

Since $A$ has all $1$'s along its diagonal, the non-orthogonality restriction now rules out any off-diagonal elements being $1$. Suppose otherwise; i.e., that $a_{ij} = a_{ji} = 1$ with $a_{ii} = a_{jj} = 1$. Then $A$ maps both ${\bf e}_i$ and ${\bf e}_j$ to the vector $(1,1)$ when the range of $A$ is restricted to the 2D subspace given by span$\{ {\bf e}_i, {\bf e}_j\}$. But this means that $A$ maps ${\bf e}_i - {\bf e}_j$ to the vector $(0,0)$ when the range of $A$ is restricted to span$\{ {\bf e}_i, {\bf e}_j\}$. Since ${\bf e}_i - {\bf e}_j$ is itself in span$\{ {\bf e}_i, {\bf e}_j\}$, this implies that ${\bf e}_i - {\bf e}_j$ and $A ({\bf e}_i - {\bf e}_j)$ are orthogonal, and we have our contradiction with the non-orthogonality restriction.

The only option left is that $A$ is the identity matrix.

(This second proof is mostly just a translation of my original proof into linear transformation terms.)

(*) Added: Marvis asked on my blog for an explanation of why the only invertible $0$-$1$ correlation matrix is the identity. Here is such a one. First, every correlation matrix has $1$'s on its diagonal. Second, a $0$-$1$ correlation matrix means that any of the underlying random variables are either uncorrelated or perfectly correlated. Distinct but perfectly correlated random variables (which means you have a $1$ off-diagonal) are scalar multiples of each other. This linear dependence carries over to the correlation matrix, which therefore can’t be invertible.

share|improve this answer
add comment

Your Answer


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.