Ask Your Question

jtaa's profile - activity

2019-03-06 03:58:16 -0500 received badge  Popular Question (source)
2017-07-09 09:58:18 -0500 received badge  Popular Question (source)
2017-04-20 11:31:20 -0500 received badge  Notable Question (source)
2017-04-20 11:31:20 -0500 received badge  Popular Question (source)
2016-06-01 08:52:19 -0500 received badge  Notable Question (source)
2015-09-16 15:00:17 -0500 received badge  Popular Question (source)
2014-10-01 08:31:38 -0500 received badge  Student (source)
2014-06-28 20:15:34 -0500 marked best answer How to get an arbitrary orientation of a graph.

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 Here is an image of a K_4 graph minus an edge and the line graph construction of K_4 that i am after

2014-06-28 20:13:06 -0500 marked best answer How would you plot these data points?

(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.

2013-03-17 17:14:09 -0500 commented answer Empirical Data Plot

awesome thanks

2013-03-17 17:13:57 -0500 marked best answer Empirical Data Plot

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.

2013-03-17 15:54:19 -0500 commented answer Newton's identities in Sage

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

2013-03-15 12:36:18 -0500 commented answer Empirical Data Plot

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?

2013-03-15 04:28:19 -0500 commented question Empirical Data Plot

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.

2013-03-15 02:07:41 -0500 asked a question Empirical Data Plot

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.

2013-03-14 16:36:00 -0500 marked best answer Newton's identities in Sage

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
2013-03-14 11:57:05 -0500 edited question Newton's identities in Sage

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.

2013-03-14 06:51:12 -0500 commented question IndexError: list index out of range

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):

2013-03-14 06:16:57 -0500 asked a question IndexError: list index out of range

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
2013-03-03 11:12:31 -0500 answered a question nilpotent adjacency matrix

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$.

2013-03-03 10:48:59 -0500 marked best answer nilpotent adjacency matrix

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... :)

2013-03-03 10:48:29 -0500 received badge  Commentator
2013-03-03 10:48:29 -0500 commented answer nilpotent adjacency matrix

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

2013-03-03 09:07:35 -0500 commented answer nilpotent adjacency matrix

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.

2013-03-03 06:42:41 -0500 commented answer nilpotent adjacency matrix

I apologise -i t works perfectly. Two things though: is it possible to start from b_1, rather than b_0? Also is there some way to return the sum of all the scalar coefficients of (B**k).trace()?

2013-03-03 01:59:48 -0500 asked a question nilpotent adjacency matrix

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

2013-03-03 01:09:02 -0500 marked best answer How would you plot these data points?

Use list_plot and logarithmic scale on the y-axis.