Ask Your Question

nilpotent adjacency matrix

asked 2013-03-03 08:59:48 +0200

jtaa gravatar image

i wish to define a nilpotent adjacency matrix.

example vertex adjacency matrix of a graph ($K_4$ minus an edge) is
[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
[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

edit retag flag offensive close merge delete

2 Answers

Sort by ยป oldest newest most voted

answered 2013-03-03 13:11:44 +0200

Benjamin Young gravatar image

updated 2013-03-04 00:25:02 +0200

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


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

edit flag offensive delete link more


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()?

jtaa gravatar imagejtaa ( 2013-03-03 13:42:41 +0200 )edit

OK, now it starts from b_1 - I just used n+1 variables and made the diagonal matrix from the last n of them with a python list slice. As for the sum of the scalar coefficients, the answer is doubtless "yes" but the obvious things I tried haven't worked yet - I haven't worked with quotient rings a whole lot.

Benjamin Young gravatar imageBenjamin Young ( 2013-03-03 15:49:40 +0200 )edit

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.

jtaa gravatar imagejtaa ( 2013-03-03 16:07:35 +0200 )edit

Got it. Fixed in the edit. What a great problem for learning all this stuff!

Benjamin Young gravatar imageBenjamin Young ( 2013-03-03 16:16:51 +0200 )edit

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

jtaa gravatar imagejtaa ( 2013-03-03 17:48:29 +0200 )edit

answered 2013-03-03 18:12:31 +0200

jtaa gravatar image

updated 2013-03-03 21:51:09 +0200

fidbc gravatar image

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

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2013-03-03 08:59:48 +0200

Seen: 886 times

Last updated: Mar 04 '13