Ask Your Question

Obtaining directed graphs associated to matrices

asked 2021-03-30 17:51:14 +0200

klaaa gravatar image

updated 2021-03-30 19:42:14 +0200

Let $M$ be an $n \times n$-matrix with entries only 0 or 1 and all diagonal entries equal to 1. (usually $M$ is upper triangular) Let $R$ be the same matrix as $M$ but with all diagonal entries set to zero. Let $U=(u_{i,j})$ be the matrix with 1 as an entry if $R^2$ (the matrix product of $R$ with itself) has a non-zero entry in the same position and let $U$ have 0 in this entry if $R^2$ has 0 as an entry in this position. Let $C=(c_{i,j})$ be the matrix $R-U$. Let $G_M$ be the directed graph with $n$ vertices and there is an arrow from $i$ to $j$ if and only if $c_{i,j}$ is 1.

For example when $M$ is the matrix with rows $[1,1,1],[0,1,1],[0,0,1]$ then the graph $G_M$ has 3 vertices with an arrow from 1 to 2 and an arrow from 2 to 3.

My question is whether there is a quick method to obtain all such 0-1 matrices with Sage for a given $n$ and the associated graph $G_M$ displayed as a picture (and as a graph in sage).

edit retag flag offensive close merge delete


In your example, R^2 will have a single nonzero entry, in entry (1, 3). So why does $G_M$ have two arrows?

John Palmieri gravatar imageJohn Palmieri ( 2021-03-30 18:18:29 +0200 )edit

Thank you for your comment. I forgot that the graph is defined via the matrix $R-U$ instead of $U$. I hope it it correct now.

klaaa gravatar imageklaaa ( 2021-03-30 19:41:51 +0200 )edit

3 Answers

Sort by » oldest newest most voted

answered 2021-03-30 18:23:57 +0200

updated 2021-03-30 18:25:05 +0200

You can have Sage perform each step of your computation:

sage: M = matrix([[1,1,1], [0,1,1], [0,0,1]])
sage: R = M - identity_matrix(3)
sage: T = R^2
sage: [1 if a != 0 else 0 for a in T.list()] # list of elements, converting any nonzero entry to 1
[0, 0, 1, 0, 0, 0, 0, 0, 0]
sage: U = matrix(3, 3, [1 if a != 0 else 0 for a in T.list()]) # form a matrix out of those entries
sage: G = DiGraph(U)  # now get a directed graph
edit flag offensive delete link more

answered 2021-03-30 18:22:12 +0200

FrédéricC gravatar image

Like this maybe

sage: M = matrix([[1,1,1],[0,1,1],[0,0,1]])                                       
sage: U = (M-1)**2                                                                
sage: DiGraph(U,multiedges=False,loops=False).plot()
edit flag offensive delete link more

answered 2021-04-01 19:44:18 +0200

If I understand well your construction in terms of graphs, each time you have arcs (u, v), (v, w) and (u, w), so a transitive tournament on 3 vertices, you remove arc (u, w). This can be done as follows:

def toto(M): 
    D = DiGraph(M - identity_matrix(M.ncols())) 
    A = [] 
    for u, v in D.edges(labels=False): 
        for w in D.neighbor_out_iterator(u): 
            if D.has_edge(v, w): 
                A.append((u, w)) 
    return D
edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2021-03-30 17:51:14 +0200

Seen: 67 times

Last updated: Apr 01