Homework 4 - Solution Sketch

(1)
(a) Since the graph is strongly connected, average consensus is possible in this graph.

(c) The graph is not strongly connected, so average consensus is not possible.


(2)

(a) A doubley stochastic matrix with element Mij non-zero whenever
        directed link (j,i) is present (with other elements being 0)
        will suffice. Note that A bidirection link between 1 and 2 is
        equivalent to a pair of directed links (1,2) and (2,1).
        Also, for the current purpose, each node should be viewed as
        having a link to itsef.  

(b) For this case, use a row stochastic matrix with non-zero elements
    in same positions as part (a), but in this case, the matrix should
    not be column stochastic. 


(3) Consider a complete graph consisting of 3 nodes. This graph does not
    satisfy the necessary condition in  the paper. However, under the weaker
    model, consensus is achieved after just one iteration.

(4) No, it is not possible. If the 4-node graph is not complete, then
    at least one node has only 2 incoming links from the other nodes.
    Suppose that node 1 has only two incoming links, say, from nodes 2 and 3.
    Then choose L = {1}, R = {3,4}, C = {} and F = {2}.
    This partition does not satisfy the necessary condition,
    since node 1 has only 1 link from R+C, and L+C contains only one node,
    so each node in R has only 1 link from L+C.