Simple graphs and adjacency matrices

Let G G be a simple graph with n n vertices and m m edges: that is, G G is undirected, unweighted, and has no loops (edges from a vertex to itself).

Let A A be the adjacency matrix of G G and let u = ( 1 1 1 ) {\bf u} = \begin{pmatrix} 1&1&\ldots&1 \end{pmatrix} be the 1 × n 1 \times n matrix whose entries are all equal to 1. 1. Then u A u T {\bf u} A {\bf u}^T is a 1 × 1 1 \times 1 matrix ( b ) \begin{pmatrix} b \end{pmatrix} . What is b b ?

Notation : if B B is a matrix, B T B^T denotes its transpose .

m m 2 n 2n 2 m 2m None of these n n

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.

1 solution

Patrick Corn
Nov 22, 2016

For any n × n n\times n matrix A , A, u A u T {\bf u} A {\bf u}^T is the sum of the entries of A . 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 2 to the sum (because an edge from vertex i i to vertex j j corresponds to a i j = a j i = 1 a_{ij} = a_{ji} = 1 ). So the answer is 2 m . 2m.

I don't understand anything about this subject. Matrix and graph is connected?

Saya Suka - 4 years, 6 months ago

Very nice! Saya, you might want to follow the wiki link on Adjacency Matrix (just click the blue link in the problem),

Jason Dyer Staff - 4 years, 6 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...