Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
(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$.
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.
