(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$.

  • $\begingroup$ but why? could you explain or prove it? $\endgroup$ – Wanderer Nov 27 '13 at 21:18
  • $\begingroup$ I've added to my answer. Let me know if what I said is unclear. $\endgroup$ – Ben Grossmann Nov 27 '13 at 21:59
  • $\begingroup$ 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) $\endgroup$ – Wanderer Nov 28 '13 at 11:19
  • $\begingroup$ 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. $\endgroup$ – Ben Grossmann Nov 28 '13 at 18:27
  • $\begingroup$ That is, I'll add to my answer once I get the chance. Probably later today. $\endgroup$ – 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.


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.