# Find a graph with an adjacency matrix consisting $0$

(okay, I'm not learning math in english, so please don't be harsh with me for not using the correct terminology here, but I hope you can understand my problem. also feel free to correct me)

Find a connected graph for every $n\geq4$ , for which is true, that his adjacency matrix on every power consists at least one(probably will consist 2) $0$. (where $n$ is the quantity of the vertices).

Consider the graph on vertices $\{1,\dots,n\}$ with the edges $(1,2),(2,3),\dots,(n-1,n)$. This is a connected graph whose adjacency matrix is given by $$A_G = \pmatrix{ 0&1&0 & 0&\cdots & 0\\ 1&0&1&0&\cdots &0\\ 0&1&0&1&\cdots &0\\ \,&&\ddots &\ddots& \ddots &\vdots\\ \\ &&&0&1&0 }$$ The powers of this matrix will always contain a zero.

Suppose that $B$ is a matrix of the form $$B = \pmatrix{ 0&b_{12}&0&b_{14}&\cdots\\ b_{12} & 0 & b_{23} & 0 & \cdots\\ 0 & b_{23} & 0 & b_{34} & \cdots\\ b_{14} & 0 & b_{34} & 0 & \cdots\\ &\vdots&&\vdots & \ddots }$$ Then $A_G B$ will be a matrix of the form $$A_G B = C = \pmatrix{ c_{11}&0&c_{13}&0&\cdots\\ 0&c_{22} & 0 & c_{24} & \cdots\\ c_{13} & 0 & c_{33} & 0 &\cdots\\ 0&c_{24} & 0 & c_{34} & \cdots\\ &\vdots&&\vdots & \ddots }$$ Similarly, if $C$ is any matrix of the above form, then $A_G C$ will be a matrix with the form of $B$.

Using induction, you can conclude that ${A_G}^k$ will always have either the form of $B$ or $C$.

• but why? could you explain or prove it? – Wanderer Nov 27 '13 at 21:18
• I've added to my answer. Let me know if what I said is unclear. – Ben Grossmann Nov 27 '13 at 21:59
• I feel quite dumb now, because I can't work out that induction. Could you give me a hint on how to prove the power of a matrix? (especially when you have 2 options to be the result) – Wanderer Nov 28 '13 at 11:19
• You shouldn't feel dumb; my explanation wasn't particularly thorough. If you still haven't figured it out, I'll clarify what I mean with that induction. – Ben Grossmann Nov 28 '13 at 18:27
• That is, I'll add to my answer once I get the chance. Probably later today. – Ben Grossmann Nov 28 '13 at 18:38

Let $G$ be a connected bipartite graph with at least one vertex in each group.

If $u$ is a vertex, any walk from $u$ to $u$ has even length. This shows that tall the diagonal entries in $A^{2n+1}$ are $0$.

If $u,v$ are vertices in the two different group/color, any walk from $u$ to $v$ has odd length. This shows that the corresponding entry in the even powers of $A$ are all $0$.

To make it simple, let $v_1,v_2$ be vertices in the two different groups of the bi-partite graph. Then the $(1,1)$ and $(2,2)$ entries of $A^{2n+1}$ are all $0$, while the $(1,2)$ and $(2,1)$ entries of $A^{2n}$ are all $0$.

P.S. The answer provided by Omno is a tree, thus fit in this class of examples.