If we have a graph $G$, and $A$ the adjacency matrix that represents $G$, how can we proof the diagonal of $A^3$ having a $1$ implies that there is a triangle in $G$?
I try to use the theorem that $A$ is the adjacency matrix of a graph then $A^k_{ij}=1$ if and only if there is a path of length $k$ from $i$ to $j$, but I how we can link it with the diagonal?
Let $G$ be a graph and $A$ the adjacency matrix for $G$.
If the equation $A^k_{ij} =1$ for any vertices $i$ and $j$ [now $i$ and $j$ may be the same], then there is a walk $W$ from $i$ to $j$ of length precisely $k$, and for the case where $i=j$ then there is a closed walk $W$ of length precisely $k$. Now, a priori, $W$ is not guaranteed to be a path for the case where $i \not = j$, and $W$ is not guaranteed to be a cycle for the case where $i=j$,
For example, if $A$ is the adjacency matrix of a matching on 2 vertices $\{1,2\}$ then $A^{2k}_{ii}$ is positive for $i=1,2$ and all even $k$, but there are clearly no cycles of length $2k$ for $k \ge 2$.
However, for $k=3$ and also a graph with no loops i.e., every diagonal element of $A$ is 0, the following holds: A walk $W$ of length $k=3$ that starts and ends at the same vertex is indeed a 3-cycle which is indeed a triangle. You can see this directly for yourself, try drawing a closed walk of length 3 that is not a triangle and where the same vertex does not appear consecutive times.
However, even for $k=3$, it is crucial that $W$ starts and ends at the same vertex i.e., $W$ be a closed walk. Otherwise, what about if $W$ starts and ends at different vertices? Then you need more information to guarantee that $W$ is indeed a path of length precisely 3. For example, getting back to the instance where $A$ is the adjacency matrix of a matching on 2 vertices $\{1,2\}$ then $A^{k}_{12}$ is positive for all odd $k$, but there are clearly no paths of length precisely $k$ for $k \ge 3$.