Suppose you have a directed tree with root $v$ and let $A$ be its adjacency matrix. Assume that the number of vertices is $N$. Compute $A^{2N}$.
I know that the $n-$th power of an adjacency matrix gives the number of of length n between two nodes. Now, since we are talking about a tree, we can’t allow cycles. Is it possible to build a tree with a $2N$ long path? I tried, but I couldn't find it, thus all $A^{2N}$ matrices I could compute were formed of all zero entries.
What I am asking is: why is the exercise asking for $A^{2N}$ and not simply for $A^{N}$, which is already formed of all zero entries? What does $2$ mean here?
Let $A$ be the adjacency matrix of a digraph $T$. Note that for any integer $\ell$, the matrix $A^{\ell}$ gives the number of directed walks between any two vertices; i.e., for any two vertices $u$ and $v$, the integer $A^{\ell}_{uv}$ is the number of directed walks between $u$ and $v$. If $T$ is acyclic [by acyclic we also require having no cycles of length 1 or 2--i.e., no arcs that are loops and no pair of vertices $u$ and $v$ s.t. both $(u,v)$ and $(v,u)$ are arcs in $T$] then this implies that any directed walk between two vertices must be a directed path or dipath for short.
Thus, Let $\ell$ be the length [by length I mean number of edges], of a longest dipath in any acyclic graph $T$ [which includes any tree where every edge is directed in exactly one direction--it can be but does not have to be rooted] and let $A$ be the adjacency matrix of $T$. Then $A^{\ell+1}_{uv}$ is 0 for each vertex $u$ and $v$ in $T$ and thus $A^{\ell+1}$ is the 0-matrix, and similarly, so is $A^k$ for each $k \ge \ell+1$. The length of the longest dipath in a tree on $N$ vertices--indeed any graph on $N$ or fewer vertices--is no more than $N-1$. So $A^k$ is 0 for all $k \ge \ell$ for such a graph $T$.