In [13]:
m = Matrix([[2,2,2],[2,3,4],[2,4,7]])
m
Sage knows how to compute a few things.
In [23]:
m.dimensions()
In [15]:
m.determinant()
In [16]:
m.eigenvalues()
In [59]:
m.matrix_from_rows_and_columns([0,2],[1,2]) # rows and columns start at 0
In [22]:
m.minors(2) # all minors 2x2
In [49]:
def is_TP(m):
"""
Returns True if m is TP and false otherwise
"""
n = min(m.dimensions())
for i in range(1,n+1): # from 1 to n
for v in m.minors(i):
if v <= 0:
return False
return True
In [51]:
# another (shorter) way to write this
def is_TP(m):
n = min(m.dimensions())
return all(v > 0 for k in range(1,n+1) for v in m.minors(k))
In [31]:
is_TP(m)
In [34]:
m2 = Matrix([[2,2,2],[3,3,4],[2,4,4]])
is_TP(m2)
In [52]:
m3 = Matrix([[2,2,2],[2,3,3],[2,4,5]])
is_TP(m3)
Exercise: complete the following function that test if a matrix is TNN (all minors are non negatives)
In [56]:
def is_TNN(m):
"""
Return True if m is TNN
"""
# edit here
In [53]:
m = Matrix([[2,2,2],[2,3,4],[2,4,7]])
is_TNN(m) # should return True
In [54]:
m2 = Matrix([[2,2,2],[3,3,4],[2,4,4]])
is_TNN(m2) # should return False
In [57]:
m3 = Matrix([[2,2,2],[2,3,3],[2,4,5]])
is_TNN(m3) # should return True
We have seen in the class that we didn't actually need to compute all minors. For each entry, we can compute the minors obtained by the biggest square going up and left. Complete the follwing function which compute this minor for a given entry.
You can use the method matrix_from_rows_and_columns to get the sub matrix.
In [68]:
def up_left_minor(m, i,j):
"""
Return the minor computed by taking the determinant of the biggest submatrix which is a square going up
and left from the entry (i,j)
"""
# edit here
In [69]:
m = Matrix([[2,2,2],[2,3,4],[2,4,7]])
m
In [70]:
up_left_minor(m,0,0) # = 2
In [71]:
up_left_minor(m,0,1) # = 2
In [72]:
up_left_minor(m,1,1) # = 2
In [73]:
up_left_minor(m,1,2) # = 2
In [75]:
up_left_minor(m,2,2) # determinent of the matrix = 2
Rewrite the is_TP function using your up_left_minor function
In [78]:
def is_TP(m):
"""
Returns True if m is TP and false otherwise
"""
# edit here
In [79]:
m = Matrix([[2,2,2],[2,3,4],[2,4,7]])
is_TP(m) # should return True
In [80]:
m2 = Matrix([[2,2,2],[3,3,4],[2,4,4]])
is_TP(m2) # should return False
In [81]:
m3 = Matrix([[2,2,2],[2,3,3],[2,4,5]])
is_TP(m3) # should return False
In [89]:
K.<a,b,c,d,e,f,g,h> = QQ[] # the polynomials in variable a,b,c,d,e,f,g,h
In [92]:
G = DiGraph()
G.add_vertices([1,2,3]) # starting points
G.add_vertices([4,5,6]) # ending points (we shift the numbers to have unique labels)
G.add_vertices(["v" + str(i) for i in range(8)]) # all the other points
G.add_edges([(3,"v0",1), ("v0","v1",f), ("v1",6,1)])
G.add_edges([(3,"v2",a),("v0","v3",c),("v4","v1",g),("v5",6,1)])
G.add_edges([(2,"v2",1), ("v2","v3",1),("v3","v4",e), ("v4","v5",1), ("v5",5,1)])
G.add_edges([("v2","v6",b),("v7","v5",h)])
G.add_edges([(1,"v6",1), ("v6","v7",d), ("v7",4,1)])
# for nice plot
pos = {1:(0,-2),2:(0,-1),3:(0,0),"v0":(1,0),"v1":(4,0),"v2":(1,-1),"v3":(2,-1),"v4":(3,-1),"v5":(4,-1),"v6":(2,-2), "v7":(3,-2),4:(5,-2),5:(5,-1),6:(5,0)}
G.plot(edge_labels = True, pos = pos)
We can find all paths between chosen points.
In [94]:
list(G.all_paths(2,5))
The following function computes the product associated to a certain path.
In [98]:
def path_product(G,P):
"""
Computes the product of edges on the path P on G
"""
p = 1
for i in range(len(P)-1):
u,v = P[i],P[i+1]
p*= G.edge_label(u,v)
return p
In [99]:
path_product(G,[2, 'v2', 'v3', 'v4', 'v5', 5])
In [100]:
path_product(G,[2, 'v2', 'v6', 'v7', 'v5', 5])
Exercise : use the functions path_product and G.all_paths to compute the $3 \times 3$ matrix associated with the network.
Exercise (more difficult) : construct the network for any n
In [ ]: