1
$\begingroup$

Let $A\in\mathbb{R}^{n\times n}$ be the adjacency matrix of an undirected network with n nodes and let 1 $\in R^n$ be a column vector whose elements are all 1. What does the formula $1^T \cdot A \cdot 1$ equal?

Two times the number of edges of a graph or The square of the number of nodes of a graph?

and why?

thanks in advance

$\endgroup$
3
  • $\begingroup$ Shouldn't it be $A\in\mathbb{R}^{n\times n}$ and $1^T \cdot A \cdot 1$? $\endgroup$
    – fabian
    Commented Apr 7, 2016 at 19:52
  • $\begingroup$ Have you played around with some toy examples, like $3\times 3$ or $4\times 4$? $\endgroup$
    – roman
    Commented Apr 8, 2016 at 8:16
  • $\begingroup$ Is this homework? Have you tried anything at all? I'm sure you can work it out if you actually try. :-) $\endgroup$
    – Josse van Dobben de Bruyn
    Commented Apr 8, 2016 at 17:26

1 Answer 1

Reset to default
0
$\begingroup$

$1^T \cdot A \cdot 1$ is the sum of all the entries in the matrix $A$. These entries are, in position $ij$, 1 if there is an edge from vertex $i$ to vertex $j$, and 0 otherwise. (Or, in a multigraph, the number of edges from vertex $i$ to vertex $j$.) Since your graph is undirected, each edge shows up twice: once in position $ij$ and once in position $ji$ (except for any loops, which just show up in position $ii$.)

So, adding all these up gives you twice the number of edges in the graph, at least if there are no loops.

(With loops, it is still true, if you adopt an appropriate convention, e.g. put a 1 in entry $ii$ and count loops as half an edge, or else put a 2 in entry $ii$ (because the loop is incident to vertex $i$ twice.))

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .