jtaa's profile - activity

i wish to define a nilpotent adjacency matrix.

example vertex adjacency matrix of a graph ($K_4$ minus an edge) is
A=
[0 1 1 0]
[1 0 1 1]
[1 1 0 1]
[0 1 1 0]

where N=4 vertices

so for all entries $A_{ij}$ i wish to define a function to replace the 1's by $b_j$ so for the example above i get a nilpotent matrix
B=
[0 $b_2$ $b_3$ 0]
[$b_1$ 0 $b_3$ $b_4$]
[$b_1$ $b_2$ 0 1]
[0 $b_2$ $b_3$ 0]

where the $b_j$ where $i,j\in${1,2,3,4} obey the following rules of multiplication:

$b_jb_i=b_ib_j$ and $b_j^2=0$ (so i also need to define a function for these rules)

so for the nilpotent adjacency matrix i can define matrix multiplication using the above rules for its entries i.e. $B^N$

i'd like the function to be something like nil(B,k) and for it to print the trace of $B^k$

e.g. $nil(B,2)=2b_1b_2+2b_1b_3+2b_2b_3+2b_2b_4+2b_3b_4$

i'll try to work on this myself too in the meantime, but this is probably the most complicated function i've had to do.. mainly due to redefining the adjacency matrix

I'VE COMPLETELY REVISED MY QUESTION

I wish to take a simple undirected graph (i.e. the complete graph K_4) Arbitrarily direct said graph, and then create a line graph from the directed version of the graph.

However, in Sage it appears to create a line graph that shows a connection between two edges (that are just inverses of each other), so what I really want is a line graph that doesn't give an edge connected to its own inverse.

That's why I asked if we could remove cycles of length 2, but that doesn't seem to solve the problem.

Here's what I am trying to work out:

G = graphs.RandomGNP(4,1)  
GD = G.to_directed()     #orients G  
m = GD.size()            #number of edges of digraph GD  
LG = GD.line_graph()     #the line graph of the digraph  
IM = identity_matrix(QQ,GD.size())  
T = LG.adjacency_matrix()#returns the adjacency matrix of the line graph   
var('u')                 #defines u as a variable  
X=IM-u*T                 #defines a new matrix X  
Z=X.det()                #defines polynomial in u  aka inverse of the Ihara zeta function
Z                        #computes determinant of X  
Z.coefficients(u)        #extracts coefficients

considering my graph is a complete graph on 4 vertices - the coefficients should be as such:
[coeff,degree of u]
[1,0], [0,1], [0,2],[-8,3],[-2,4]

NOTE:
im only interested in coefficients up to the order of n=#of nodes in the graph, so here for K_4 obviously n=4.
where the coefficient of u^3 corresponds to the negative of twice the number of triangles in K_4
where the coefficient u^4 corresponds to the negative of twice the number of squares in K_4

Here is an image of a K_4 graph minus an edge and the line graph construction of K_4 that i want

(x=nodes, y=cycles)

the following 3 sets of data points on the same graph:

IZF (color=red): [(0,0),(1,0),(2,0),(3,35),(4,105),(5,252),(6,1260),(7,2910)]
vs
Actual (color=black): [(0,0),(1,0),(2,0),(3,35),(4,105),(5,252),(6,420),(7,360)]
vs
c_adj (color=blue): [(0,0),(1,0),(2,42),(3,210),(4,1302),(5,7770),(6,46662),(7,279930)]

i'm not even sure what type graph would be appropriate, whereby you can see reasonably where each point y is, because my current plots (due to y going up to 279,930) shows the different data points coinciding, i.e. you cant differentiate between the initial datapoints.

awesome thanks

Here is a sample of what you can do in Sage.

var('a,n')
model(x) = a*x^n
N = [16,28,59,120] 
T = [0.135,0.523,7.36,248]
data = zip(N,T)
@interact
def _(n=[1..5]):
    L = find_fit(data,model.subs(n=n))
    show(plot(model.subs(a=L[0].rhs(),n=n),(x,0,120))+points(data,pointsize=20,color='black'))

See it live and in action here. Note that with four data points, of course the fifth-degree one is perfect! My guess is that here you may have (yuck) exponential growth, but without more data it's hard to be sure - definitely could also be $O(x^3)$ or $O(x^4)$ or something.

what if i wanted a new formula for s_k=[c_1s_{k-1}+...+c_{k-1}s_1-kc_k] ?

Time = [0.135, 0.523, 2.72, 7.36, 23.2, 45.1, 96.3, 248]   Edges = [16.0, 28.0, 47.0, 59.0, 77.0, 84.0, 98.0, 120.0] -- seems like it's more like O(N^5) growth with these additional points?

well, i just want to know the order of growth. i.e. as the edges increase what is the order of growth in terms of time taken to compute my function.

I wish to make a plot of N vs Time where $N=$ # of edges in a graph. i.e. i want to make an empirical estimate of the time complexity it takes to compute certain things about a graph based on its number of edges.

so i guess i'm wanting to know how i can plot these data points in sage and find a polynomial that best fits?

i.e.
N = [(16,28,59,120)]
T = [(0.135,0.523,7.36,248)] --where time is measured in seconds

i'm a beginner so any help will be much appreciated.

An recursive algorithm would be quite inefficient for this problem as yout would have to recalculate all c_k coefficients in each step.

The following few lines should work for your problem (if I hopefully didn't make any mistakes with the formulas):

def c(k,A):
    c_arr=[-A.trace()]
    for j in range(k-1):
        c_arr=c_incr(c_arr,A)
        print c_arr
    return c_arr[k-1]

def c_incr(c_arr, A):
    k=len(c_arr)+1
    c_new=(A^k).trace()
    for c_k in c_arr:
        k-=1
        c_new+=c_k*(A^k).trace()
    c_new=-1/(len(c_arr)+1)*c_new
    c_arr.append(c_new)
    return c_arr

EDIT
I actually need: $s_k=[c_1s_{k-1}+...+c_{k-1}s_1-kc_k]$ ? could somebody help me to change tobias welch's answer so that it computes $s_k$ instead of $c_k$?
END EDIT

I'm combining netwon's identities with le verrier's algorithm

I need some help coding the following on python.

$c_k=\frac{-1}{k}(s_k+c_1s_{k-1}+c_2s_{k-2}+\dots+c_{k-1}s_1)$
where $s_k=Tr(A^k)$, for some square matrix A, $\forall k=1,2,3,\dots,n$

So, i'd like to type in $c(k)$ and python spits out the value for $c_k$ as defined above.

I think I may have pasted the defined functions incorrectly in to sage, i.e. it now seems to be working correctly. return c_arr[k-1] should have been in line with for j in range(k-1):

i'm not sure why i'm getting an error saying list index out of range, as this defined function c(k,A) worked previously for a complete graph on 7 vertices. could anyone help me? (i've printed the code below with the error message - i need to be able to compute c(k,A) where k ranges from 1 to N and N is equal to L.order() )

see previous sage question here for further info on the c(k,A)

sage: G =graphs.RandomNewmanWattsStrogatz(100,3,0.5)  
sage: D = G.to_directed()  
sage: L = D.line_graph()  
sage: L.delete_edges([((x,y,None), (y,x,None)) for x,y in G.edges( labels=None ) ])  
sage: L.delete_edges([((x,y,None), (y,x,None)) for y,x in G.edges( labels=None ) ])  
sage: A = L.adjacency_matrix()  
sage: def c(k,A):  
    c_arr=[-A.trace()]  
    for j in range(k-1):  
        c_arr=c_incr(c_arr,A)  
        print c_arr  
        return c_arr[k-1]  
sage: def c_incr(c_arr, A):  
    k=len(c_arr)+1  
    c_new=(A^k).trace()  
    for c_k in c_arr:  
        k-=1  
        c_new+=c_k*(A^k).trace()  
        c_new=-1/(len(c_arr)+1)*c_new  
        c_arr.append(c_new)  
        return c_arr  
sage: c(2,A)  
[0, 0]  
0  
sage: c(3,A)  
[0, 0]  
---------------------------------------------------------------------------  
IndexError                                Traceback (most recent call last)   
<ipython-input-88-facbb2b4a562> in <module>()  
----> 1 c(Integer(3),A)  

<ipython-input-72-964ce5dcb8d9> in c(k, A)  
      4         c_arr=c_incr(c_arr,A)  
      5         print c_arr  
----> 6         return c_arr[k-Integer(1)]  

IndexError: list index out of range

I've added another bit on:

def c(k):  
     if k<3:  
         return 0  
     if k>2:  
         return sum_of_coeffs(nil(A,k))/(2*k)

where $c(k)$ returns the number of simple cycles in G of length $k$.

Here's a naive answer, as I am somewhat naive (I just posted a question and, while waiting breathlessly for someone to answer it, I thought I'd just have a look at what other people are asking). No idea how efficient it is, but maybe it's a start.

You can construct the ring that you want to work in as a quotient ring of a multivariate polynomial ring. You can then construct the matrix B that you want by multiplying by a diagonal matrix whose entries are the variables you want.

n = 4
R = PolynomialRing(QQ, n+1, 'a')
squared_vars = [t**2 for t in R.gens()]
I = R.ideal(squared_vars)
S = R.quotient_ring(I, 'b')

def nil(A,k):
    B = A * diagonal_matrix(S, n, list(R.gens())[1:])
    return (B**k).trace()

Edit: It turns out that OP also wants to compute the sum of the coefficients. I found it kind of tricky to compute this, largely because the quotient ring classes seem not to have a lot of the methods you'd expect. However it's possible to lift an element of the quotient ring to the obvious preimage in the original ring, and since the original ring is a plain old multivariate polynomial ring, you can do all the things you'd normally do in it, like "subs". Naturally substituting 1 for all the variables computes the sum of the coefficients:

def sum_of_coeffs(x):
    return x.lift().subs({t:1 for t in R.gens()})

so, for instance, you could do

sum_of_coeffs(nil(A,2))

which hopefully should produce the answer 10 when you run it with OP's example, for instance. This was a great question - at least, I feel like I learned a lot... :)

I also learnt a lot - thanks! i tried it on a complete graph on 7 vertices and it worked perfectly :)

Ok, thanks. i also tried extracting the coefficients, but i'm guessing there is a special way when dealing with quotient rings, as i keep getting errors pertaining to it being a quotient ring.