In [1]:
m = Matrix([[2,2,2],[2,3,4],[2,4,7]])
m
Out[1]:
Sage es capaz de calcular algunas propiedades de matrices.
In [2]:
m.dimensions()
Out[2]:
In [3]:
m.determinant()
Out[3]:
In [4]:
m.eigenvalues()
Out[4]:
In [5]:
m.matrix_from_rows_and_columns([0,2],[1,2]) # el etiquetado de filas y columnas empieza en 0
Out[5]:
In [6]:
m.minors(2) # todas las menores 2x2
Out[6]:
In [49]:
def is_TP(m):
"""
Retorna True si m es TP y False de lo contrario
"""
n = min(m.dimensions())
for i in range(1,n+1): # numeros de 1 a n
for v in m.minors(i):
if v <= 0:
return False
return True
In [51]:
# otra forma (mas corta) de escribir esto
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)
Ejercicio: complete la siguiente funcion que verifica si una matriz es TNN (todas sus menores son no-negativas)
In [56]:
def is_TNN(m):
"""
Retorna True si m es TNN
"""
# edit here
In [53]:
m = Matrix([[2,2,2],[2,3,4],[2,4,7]])
is_TNN(m) # deberia retornar True
In [54]:
m2 = Matrix([[2,2,2],[3,3,4],[2,4,4]])
is_TNN(m2) # deberia retornar False
In [57]:
m3 = Matrix([[2,2,2],[2,3,3],[2,4,5]])
is_TNN(m3) # deberia retornar True
En la clase vimos que en realidad no es necesario calcular todas las menores. Para cada entrada de la matriz, basta con calcular la menor de la submatriz solida mas grande cuya esquina sureste es la entrada en cuestion. Complete la siguiente funcion para calcular esta menor dada una entrada de la matriz.
Para obtener una submatriz se puede usar el metodo matrix_from_rows_and_columns.
In [68]:
def up_left_minor(m, i,j):
"""
Retorna la menor de la submatriz solida obtenida a partir de la entrada (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) # determinante de la matriz = 2
Reescriba la funcion is_TP usando su funcion up_left_minor
In [78]:
def is_TP(m):
"""
Retorna True si m es TP y False de lo contrario
"""
# edit here
In [79]:
m = Matrix([[2,2,2],[2,3,4],[2,4,7]])
is_TP(m) # deberia retornar True
In [80]:
m2 = Matrix([[2,2,2],[3,3,4],[2,4,4]])
is_TP(m2) # deberia retornar False
In [81]:
m3 = Matrix([[2,2,2],[2,3,3],[2,4,5]])
is_TP(m3) # deberia retornar False
In [89]:
K.<a,b,c,d,e,f,g,h> = QQ[] # anillo polinomial sobre los racionales en las variables a,b,c,d,e,f,g,h
In [92]:
G = DiGraph()
G.add_vertices([1,2,3]) # vertices fuente (sources)
G.add_vertices([4,5,6]) # vertices sumidero (sink -- desplazamos las etiquetas para no repetir)
G.add_vertices(["v" + str(i) for i in range(8)]) # los demas vertices
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)
Podemos encontrar todos los caminos entre cualesquiera dos vertices.
In [94]:
list(G.all_paths(2,5))
La siguiente funcion computa el producto asociado a un camino dado.
In [98]:
def path_product(G,P):
"""
Computa el producto de las aristas del camino P en 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])
Ejercicio : use las funciones path_product y G.all_paths para computar la matriz $3 \times 3$ asociada a la red.
Ejercicio (mas dificil) : construya la red para cualquier n
In [0]: