Let be a simple graph with vertices and edges: that is, is undirected, unweighted, and has no loops (edges from a vertex to itself).
Let be the adjacency matrix of and let be the matrix whose entries are all equal to Then is a matrix . What is ?
Notation : if is a matrix, denotes its transpose .
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
For any n × n matrix A , u A u T is the sum of the entries of A . For the adjacency matrix of a simple undirected graph, the sum of the entries equals twice the number of edges, because each edge contributes 2 to the sum (because an edge from vertex i to vertex j corresponds to a i j = a j i = 1 ). So the answer is 2 m .