nilpotent adjacency matrix

jtaa
17 ●2 ●4 ●11

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

add a comment

2 Answers

Sort by » oldest newest most voted

answered 12 years ago

Benjamin Young
63 ●2 ●3 ●7

updated 12 years ago

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

link

Comments

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 ( 12 years ago )

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 ( 12 years ago )

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 ( 12 years ago )

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

Benjamin Young ( 12 years ago )

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

jtaa ( 12 years ago )

add a comment

answered 12 years ago

jtaa
17 ●2 ●4 ●11

updated 12 years ago

fidbc

2423 ●4 ●26 ●61

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

link

add a comment

Your Answer

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

Add Answer

nilpotent adjacency matrix

2 Answers

Comments

Your Answer

Question Tools

Stats

Related questions

nilpotent adjacency matrix savecancel

2 Answers

Comments

Your Answer

Question Tools

Stats

Related questions

nilpotent adjacency matrix