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

edit retag close merge delete

Sort by » oldest newest most voted

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

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

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

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

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

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

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

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

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

more