# On sum of elements in products of matrices for a simple graph

Let $$G$$ be a simple graph with vertex set $$\{v_1,v_2,\ldots,v_n\}$$. The adjacency matrix of $$G$$ is the 0-1 matrix $$A$$, where $$A_{i,j}=1$$ when $$v_i$$ is adjacent with $$v_j$$. The degree matrix is the diagonal matrix $$D$$ where $$D_{i,i}$$ is the degree of $$v_i$$.

It seems that for any graph $$G$$, the sum of elements in any product of any $$A$$'s and any $$D$$'s (in any order) is always even. Can any one give a proof for this observation? Is it a known result? Note that the sum of elements in any power of $$A$$ (or $$D$$ ) is even, giving the first evidence to the above observation.

For example, consider $$A= \left( \begin{matrix} 0&0&1&1\\ 0&0&1&0\\ 1&1&0&1\\ 1&0&1&0\\ \end{matrix} \right), D=\left( \begin{matrix} 2&0&0&0\\ 0&1&0&0\\ 0&0&3&0\\ 0&0&0&2\\ \end{matrix} \right).$$ One can verifies that $$e^TAe=8,e^TDe=8,\ldots,e^TADAAADe=422,\ldots$$ are all even, where $$e=(1,1,1,1)^T$$.

I think this is false.

Here is a graph and some code in Sage to compute the sum of elements of $$AADAAD$$ which appears to be odd.

I tried to prove it for a while, failed, so then decided to try some randomised searching on smallish graphs.

x = Graph('G?B@dW')

• The entries of such products are counting homomorphisms from a graph $H$ determined by the string to the fixed graph $G$. So if the number of homomorphisms from $H$ to $G$ is even independent of $G$ (e.g., if $H$ is just an edge), then the sum of the entries will be even. To determine $H$, let $K_2$ be a complete graph on the two vertices $a$ and $b$. Then $A_{uv}$ is the number of homomorphisms from $K_2$ to $G$ where $a,b$ get mapped to $u,v$ respectively, and $D_{uv}$ is the number of homomorphisms where $a,a$ gets mapped to $u,v$ respectively (thus the zeros off the diagonal). Aug 24, 2019 at 15:43