46
$\begingroup$

Here's a cute problem that was frequently given by the late Herbert Wilf during his talks.

Problem: Let $A$ be an $n \times n$ matrix with entries from $\{0,1\}$ having all positive eigenvalues. Prove that all of the eigenvalues of $A$ are $1$.

Proof:

Use the AM-GM inequality to relate the trace and determinant.

Is there any other proof?

  • 3
    Huh. Anybody got a different proof? ($\mathbb{F}_2$-representation? Adjacency matrix of a graph?)2012-12-20
  • 0
    @AlexanderGruber I would love to hear one!2012-12-20
  • 2
    Hmmm...What makes a problem "cute"? I don't mean that sarcastically, I've just heard a handful of references lately to "cute" problems, and am curious about what makes a problem "cute"?2012-12-20
  • 1
    @amWhy Short, elegant, and usually elementary.2012-12-20
  • 0
    Are you looking for a proof that uses the hint? Or a different proof?2012-12-20
  • 1
    @MikeSpivey Well, I know how to do it with the hint, so ideally an alternate proof.2012-12-20
  • 0
    can we assume $A$ to be symmetric? because all eigenvalues are real and positive.2012-12-20
  • 1
    @dineshdileep: The only symmetric 0-1 matrix with all eigenvalues real and positive is the identity, so that assumption makes the problem easy. :)2012-12-20
  • 0
    that's what I thought!!, if he agreed, I would have jumped in with that :):)2012-12-20
  • 2
    According to [this paper](https://cs.uwaterloo.ca/journals/JIS/VOL7/Sloane/sloane15.pdf), every $n\times n$ binary matrix with positive eigenvalues is permutation similar to an upper triangular binary matrix with ones on the diagonal.2012-12-20
  • 0
    Does it mean, it is an irreducible matrix?2012-12-20
  • 0
    @user1551 The question OP asked is stated as section 2 corollary (i) in that paper. But I believe, they used the same method OP wanted to avoide2012-12-20
  • 0
    I know. I just want to say that the symmetric case is way too special. BTW, every triangular matrix *is* reducible by definition.2012-12-20
  • 0
    oh,,,I don't know much about it...2012-12-20
  • 0
    Eigenvalues are, in general, complex. "having all positive eigenvalues" means "real and positive" or "positive real part"?2013-02-08
  • 1
    @leonbloy The adjectives 'positive' and 'negative' can refer only to real numbers. I mean real and positive.2013-02-08

3 Answers 3