×
×

# Solved: A graph having n vertices such that every vertex is connected to every other

ISBN: 9781118474228 398

## Solution for problem T1 Chapter 10.5

Elementary Linear Algebra, Binder Ready Version: Applications Version | 11th Edition

• Textbook Solutions
• 2901 Step-by-step solutions solved by professors and subject experts
• Get 24/7 help from StudySoup virtual teaching assistants

Elementary Linear Algebra, Binder Ready Version: Applications Version | 11th Edition

4 5 1 251 Reviews
23
5
Problem T1

A graph having n vertices such that every vertex is connected to every other vertex has a vertex matrix given by Mn = 01111 1 10111 1 11011 1 11101 1 11110 1 . . . . . . . . . . . . . . . ... . . . 11111 0 In this problem we develop a formula for Mk n whose (i, j )-th entry equals the number of k-step connections from Pi to Pj . (a) Use a computer to compute the eight matrices Mk n for n = 2, 3 and for k = 2, 3, 4, 5. (b) Use the results in part (a) and symmetry arguments to show that Mk n can be written as Mk n = 01111 1 10111 1 11011 1 11101 1 11110 1 . . . . . . . . . . . . . . . ... . . . 11111 0 k = k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k . . . . . . . . . . . . . . . ... . . . k k k k k k (c) Using the fact that Mk n = MnMk1 n , show that k k = 0 n 1 1 n 2 k1 k1 with 1 1 = 0 1 (d) Using part (c), show that k k = 0 n 1 1 n 2 k1 0 1 (e) Use the methods of Section 5.2 to compute 0 n 1 1 n 2 k1 and thereby obtain expressions for k and k , and eventually show that Mk n = (n 1)k (1)k n ! Un + (1) k In where Un is the n n matrix all of whose entries are ones and In is the n n identity matrix. (f ) Show that for n > 2, all vertices for these directed graphs belong to cliques.

Step-by-Step Solution:
Step 1 of 3

L. Sec:rr4.7 GeowrH AND DBcan FORMULA: If Arows ordecays exponentiallthenitsatisftheequation A- Pn o* o ,4rows 'n 0 K7 o ,decays if KLA (t) , Yor* th,eple L.P{t):800e0'02'.tehowamanydayswilli,papulati,onaysobeys...

Step 2 of 3

Step 3 of 3

##### ISBN: 9781118474228

This textbook survival guide was created for the textbook: Elementary Linear Algebra, Binder Ready Version: Applications Version, edition: 11. This full solution covers the following key subjects: . This expansive textbook survival guide covers 80 chapters, and 2108 solutions. The full step-by-step solution to problem: T1 from chapter: 10.5 was answered by , our top Math solution expert on 03/14/18, 04:26PM. Since the solution to T1 from 10.5 chapter was answered, more than 211 students have viewed the full step-by-step answer. Elementary Linear Algebra, Binder Ready Version: Applications Version was written by and is associated to the ISBN: 9781118474228. The answer to “A graph having n vertices such that every vertex is connected to every other vertex has a vertex matrix given by Mn = 01111 1 10111 1 11011 1 11101 1 11110 1 . . . . . . . . . . . . . . . ... . . . 11111 0 In this problem we develop a formula for Mk n whose (i, j )-th entry equals the number of k-step connections from Pi to Pj . (a) Use a computer to compute the eight matrices Mk n for n = 2, 3 and for k = 2, 3, 4, 5. (b) Use the results in part (a) and symmetry arguments to show that Mk n can be written as Mk n = 01111 1 10111 1 11011 1 11101 1 11110 1 . . . . . . . . . . . . . . . ... . . . 11111 0 k = k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k . . . . . . . . . . . . . . . ... . . . k k k k k k (c) Using the fact that Mk n = MnMk1 n , show that k k = 0 n 1 1 n 2 k1 k1 with 1 1 = 0 1 (d) Using part (c), show that k k = 0 n 1 1 n 2 k1 0 1 (e) Use the methods of Section 5.2 to compute 0 n 1 1 n 2 k1 and thereby obtain expressions for k and k , and eventually show that Mk n = (n 1)k (1)k n ! Un + (1) k In where Un is the n n matrix all of whose entries are ones and In is the n n identity matrix. (f ) Show that for n > 2, all vertices for these directed graphs belong to cliques.” is broken down into a number of easy to follow steps, and 342 words.

#### Related chapters

Unlock Textbook Solution