2
$\begingroup$

Let $T$ be an invertible tree on $n$ vertices. Obtain the tree $T_1$ from $T$ by adding a pendant $v$ at some vertex of $T$. Let $A$ be adjacency matrix of $T_1$. Assume last column of $A$ is indexed by vertex $v$. I noticed that every eigenvector of $A$ has last entry nonzero. How to prove that it can never be zero?

$\endgroup$
2
  • 1
    $\begingroup$ please explain briefly what an invertible tree is and what is a pendant, thanks! $\endgroup$ – orangeskid Apr 22 '20 at 5:27
  • $\begingroup$ Invertible tree is one whose adjacency matrix is nonsingular. A pendant is vertex of degree $1$. $\endgroup$ – Sry Apr 22 '20 at 5:29
2
$\begingroup$

Here's a counterexample:

1 -- 2 -- 3 -- 4 -- 5 -- 6 -- 7 -- 8 
          |
          v

The tree $T$ which is a path on $8$ vertices is invertible (it has a perfect matching). However, adding the vertex $v$ adjacent to vertex $3$ gives us a tree $T_1$ one of whose eigenvectors is $(1, 1, 0, -1, -1, 0, 1, 1, 0)$, with a $0$ in $v$'s entry.

Here's that eigenvector in tree form:

1 -- 1 -- 0 -- -1 -- -1 -- 0 -- 1 -- 1
          |
          0
$\endgroup$
0
$\begingroup$

HINT:

Let $\tilde x = (x,0)$. The equality $A \tilde x = \lambda \tilde x$ is equivalent to $A' x = \lambda x$ and $ x_i=0$, where $A'$ is the matrix of the original tree $T$ and $i$ is the vertex of $T$ connected to the new vertex. So we have to check that no eigenvector of $T$ has any zero component.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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