Let $G$ be a simple graph, and $A$ be its adjacency matrix. Prove that the entries on the main diagonal of $A^2$ (matrix multiplication $A×A =A^2$) give the degrees of the vertices of $G$. Does this remain true if we drop the "simple" condition?
Please help me in constructing the proof. I don't know what to start. Thank you.
Let's think about what $(A^2)_{i,i}$, the $i$-th term on the diagonal is. We have $$ \textstyle (A^2)_{i,i} = (A \times A)_{i,i} = \sum_j A_{i,j} A_{j,i}. $$ But $A_{i,j} = A_{j,i}$, assuming that the graph is undirected, and $A_{i,j} = 1(i \sim j)$, ie is $1$ if $i$ and $j$ are adjacent and $0$ otherwise. Thus $A_{i,j} A_{j,i} = A_{i,j}^2 = A_{i,j} = 1(i \sim j)$. So the sum is just the number of $j$ such that $i \sim j$, which is precisely the degree.
This works if vertices in your graph may have a single self-loop, provided you count that as $1$ (not $2$) for the degree. Indeed, the term in the sum when $j = i$ is just $A_{i,i}^2$, but you need this to be equal to $A_{i,i}$. Thus it needs to be $0$ or $1$.
It does not work more generally, however, as $A_{i,j}^2 \ne A_{i,j}$ if $A_{i,j} > 1$.
Incidentally, if you look at $A^T A$---which, in some sense, is actually a more natural sense of 'squaring' a matrix---then you immediately get $$ \textstyle (A^T A)_{i,i} = \sum_j A_{i,j}^2 = \deg_\mathrm{out}(i), $$ even for an undirected graph, provided the graph is simple.