ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sun, 03 Mar 2013 11:12:31 -0600nilpotent adjacency matrixhttp://ask.sagemath.org/question/9870/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 matrixSun, 03 Mar 2013 01:59:48 -0600http://ask.sagemath.org/question/9870/nilpotent-adjacency-matrix/Answer by Benjamin Young for <p>i wish to define a nilpotent adjacency matrix.</p>
<p>example vertex adjacency matrix of a graph ($K_4$ minus an edge) is <br/>
A= <br/>
[0 1 1 0] <br/>
[1 0 1 1] <br/>
[1 1 0 1] <br/>
[0 1 1 0] </p>
<p>where N=4 vertices</p>
<p>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 <br/>
B= <br/>
[0 $b_2$ $b_3$ 0] <br/>
[$b_1$ 0 $b_3$ $b_4$] <br/>
[$b_1$ $b_2$ 0 1] <br/>
[0 $b_2$ $b_3$ 0] </p>
<p>where the $b_j$ where $i,j\in${1,2,3,4} obey the following rules of multiplication:</p>
<p>$b_jb_i=b_ib_j$ and $b_j^2=0$ (so i also need to define a function for these rules)</p>
<p>so for the nilpotent adjacency matrix i can define matrix multiplication using the above rules for its entries i.e. $B^N$</p>
<p>i'd like the function to be something like nil(B,k)
and for it to print the trace of $B^k$ </p>
<p>e.g. $nil(B,2)=2b_1b_2+2b_1b_3+2b_2b_3+2b_2b_4+2b_3b_4$ </p>
<p>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</p>
http://ask.sagemath.org/question/9870/nilpotent-adjacency-matrix/?answer=14621#post-id-14621Here'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... :)Sun, 03 Mar 2013 06:11:44 -0600http://ask.sagemath.org/question/9870/nilpotent-adjacency-matrix/?answer=14621#post-id-14621Comment by jtaa for <p>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. </p>
<p>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. </p>
<pre><code>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()
</code></pre>
<p>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:</p>
<pre><code>def sum_of_coeffs(x):
return x.lift().subs({t:1 for t in R.gens()})
</code></pre>
<p>so, for instance, you could do</p>
<pre><code>sum_of_coeffs(nil(A,2))
</code></pre>
<p>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... :)</p>
http://ask.sagemath.org/question/9870/nilpotent-adjacency-matrix/?comment=18113#post-id-18113Ok, 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.Sun, 03 Mar 2013 09:07:35 -0600http://ask.sagemath.org/question/9870/nilpotent-adjacency-matrix/?comment=18113#post-id-18113Comment by Benjamin Young for <p>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. </p>
<p>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. </p>
<pre><code>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()
</code></pre>
<p>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:</p>
<pre><code>def sum_of_coeffs(x):
return x.lift().subs({t:1 for t in R.gens()})
</code></pre>
<p>so, for instance, you could do</p>
<pre><code>sum_of_coeffs(nil(A,2))
</code></pre>
<p>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... :)</p>
http://ask.sagemath.org/question/9870/nilpotent-adjacency-matrix/?comment=18114#post-id-18114OK, 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.Sun, 03 Mar 2013 08:49:40 -0600http://ask.sagemath.org/question/9870/nilpotent-adjacency-matrix/?comment=18114#post-id-18114Comment by jtaa for <p>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. </p>
<p>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. </p>
<pre><code>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()
</code></pre>
<p>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:</p>
<pre><code>def sum_of_coeffs(x):
return x.lift().subs({t:1 for t in R.gens()})
</code></pre>
<p>so, for instance, you could do</p>
<pre><code>sum_of_coeffs(nil(A,2))
</code></pre>
<p>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... :)</p>
http://ask.sagemath.org/question/9870/nilpotent-adjacency-matrix/?comment=18115#post-id-18115I 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()?Sun, 03 Mar 2013 06:42:41 -0600http://ask.sagemath.org/question/9870/nilpotent-adjacency-matrix/?comment=18115#post-id-18115Comment by Benjamin Young for <p>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. </p>
<p>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. </p>
<pre><code>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()
</code></pre>
<p>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:</p>
<pre><code>def sum_of_coeffs(x):
return x.lift().subs({t:1 for t in R.gens()})
</code></pre>
<p>so, for instance, you could do</p>
<pre><code>sum_of_coeffs(nil(A,2))
</code></pre>
<p>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... :)</p>
http://ask.sagemath.org/question/9870/nilpotent-adjacency-matrix/?comment=18112#post-id-18112Got it. Fixed in the edit. What a great problem for learning all this stuff!Sun, 03 Mar 2013 09:16:51 -0600http://ask.sagemath.org/question/9870/nilpotent-adjacency-matrix/?comment=18112#post-id-18112Comment by jtaa for <p>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. </p>
<p>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. </p>
<pre><code>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()
</code></pre>
<p>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:</p>
<pre><code>def sum_of_coeffs(x):
return x.lift().subs({t:1 for t in R.gens()})
</code></pre>
<p>so, for instance, you could do</p>
<pre><code>sum_of_coeffs(nil(A,2))
</code></pre>
<p>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... :)</p>
http://ask.sagemath.org/question/9870/nilpotent-adjacency-matrix/?comment=18111#post-id-18111I also learnt a lot - thanks! i tried it on a complete graph on 7 vertices and it worked perfectly :)Sun, 03 Mar 2013 10:48:29 -0600http://ask.sagemath.org/question/9870/nilpotent-adjacency-matrix/?comment=18111#post-id-18111Answer by jtaa for <p>i wish to define a nilpotent adjacency matrix.</p>
<p>example vertex adjacency matrix of a graph ($K_4$ minus an edge) is <br/>
A= <br/>
[0 1 1 0] <br/>
[1 0 1 1] <br/>
[1 1 0 1] <br/>
[0 1 1 0] </p>
<p>where N=4 vertices</p>
<p>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 <br/>
B= <br/>
[0 $b_2$ $b_3$ 0] <br/>
[$b_1$ 0 $b_3$ $b_4$] <br/>
[$b_1$ $b_2$ 0 1] <br/>
[0 $b_2$ $b_3$ 0] </p>
<p>where the $b_j$ where $i,j\in${1,2,3,4} obey the following rules of multiplication:</p>
<p>$b_jb_i=b_ib_j$ and $b_j^2=0$ (so i also need to define a function for these rules)</p>
<p>so for the nilpotent adjacency matrix i can define matrix multiplication using the above rules for its entries i.e. $B^N$</p>
<p>i'd like the function to be something like nil(B,k)
and for it to print the trace of $B^k$ </p>
<p>e.g. $nil(B,2)=2b_1b_2+2b_1b_3+2b_2b_3+2b_2b_4+2b_3b_4$ </p>
<p>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</p>
http://ask.sagemath.org/question/9870/nilpotent-adjacency-matrix/?answer=14622#post-id-14622I'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$.
Sun, 03 Mar 2013 11:12:31 -0600http://ask.sagemath.org/question/9870/nilpotent-adjacency-matrix/?answer=14622#post-id-14622