[Math] Sum of elements of square of adjacency matrix of a graph

Question

Let $G$ be a simple graph (no loop and undirected) with $p$ vertices. $A$ is Adjacency Matrix of Graph $G$ and $A^2$ is the square of adjacency matrix of graph $G$. How to prove that sum of all the elements of $A^2$ equals to $\sum_{i=1}^p v_{i}^2$ where $v_{i}$ is the degree of every vertex. I know the element on the main diameter equals to degree of that vertex and also element of row i and column j equals to number of common neighbours of vertices i and j. But I can't prove that sum of all elements of this matrix equals to $\sum_{i=1}^p v_{i}^2$

Answer 1

So you know that each entry of $A^2$ on the main diagonal equals to degree of that vertex, i.e. $(A^2)_{i,i}=v_i$ so $\sum_{1 \le i \le p}(A^2)_{i,i}=\sum_{i=1}^pv_i$.

You also know that $(A^2)_{i,j}=(A^2)_{j,i}$, both equal to number of common neighbours of vertices $i$ and $j$. Let $a_{ij,k}=1$ if vertices $i,j$ are adjacent to $k$. Hence, $(A^2)_{i,j}=\sum_{k=1}^pa_{ij,k}$. This follows $$\sum_{i \ne j}(A^2)_{i,j}=2 \sum_{i<j}(A^2)_{i,j}=2 \sum_{i<j} \sum_{k=1}^p a_{ij,k}=2\sum_{k=1}^p \left( \sum_{i<j} a_{ij,k} \right).$$ Note that $\sum_{i<j}a_{ij,k}$ is essentially number of unordered pairs of vertices $(i,j)$ so they are both adjacent to $k$, which equals $\binom{v_k}{2}$. Hence, $$\sum_{i \ne j} (A^2)_{i,j} = 2 \sum_{k=1}^p \binom{v_k}{2}=\sum_{i=1}^p v_i^2 - \sum_{j=1}^p v_j.$$ Thus, $$\sum_{1 \le i,j \le p} (A^2)_{i,j}= \sum_{i=1}^p v_i^2.$$