## returns the positive support as an integral matrix
def posSupInt(A):            #input: matrix, return: postive support
   rows = A.nrows()
   cols = A.ncols() 
   B = Matrix(ZZ,rows,cols)
   for i in range(rows):
      for j in range(cols):  
         if A[i,j] >0:
            B[i,j] = 1  
         else:
            B[i,j] = 0
   return B

#input: regular graph, output: transition matrix of quantum walk, scalar factor of deg
def quantumWalk(G):
	D = DiGraph(G)
	arcs = D.edges()
	deg = G.degree()[0]
	U = Matrix(len(arcs), len(arcs))
	for i in range(len(arcs)):
		for j in range(len(arcs)):
			if arcs[j][1]== arcs[i][0]:
				U[i,j] = 2
				if arcs[j][0] == arcs[i][1]:
					U[i,j] = 2 - deg
	return U

def SUMtx(G):
	U = quantumWalk(G)
	return posSupInt(U^3)