Solutions to Matrix Equation which are elements of a polynomial ring.

asked 2024-03-30 05:19:40 +0100

gian98863
13 ●1 ●1 ●3

updated 2024-04-14 16:07:30 +0100

5311 ●4 ●44 ●118

I'm VERY new to SageMath, and I'm having trouble understanding how polynomial rings work in this language... I have the following code:

sage: F = PolynomialRing(GF(3),'x'); x = F.gen()
sage: S = F.quotient(x^2,'a'); a = S.gen()

I'm trying to find solutions to the following matrix equation:

sage: var('d1,d2,d3')
sage: var('r1,r2,r3')
sage: laplacian = matrix([[d1, -1, 0], [-1, d2, -1], [0, -1, d3]])
sage: rstructure = laplacian.solve_right(vector([0,0,0]))

Now here is the caveat: I want the solutions of rstructure to only be elements of the quotient ring I've defined as S. If you've gotten this far, I'll boil down my main questions below:

(1) What are x=F.gen() and a=S.gen() doing?

(2) I want to see all the possible solutions of r_i, d_i that satisfy the matrix equation with the condition that they are elements of S (the quotient ring that I've defined earlier).

(3) If it is not clear, "rstructure" is an element of (F_3[x]/< x^2 >)^3. What I'm particularly interested in are solutions in (F_p[x])^3. Is computing this even possible for a given prime p?

Thanks for taking the time to read this! Hope to figure this out soon.

edit retag flag offensive close merge delete

add a comment

2 Answers

Sort by » oldest newest most voted

answered 2024-04-01 16:32:07 +0100

rburing

10929 ●4 ●80 ●218 https://www.rburing.nl/

Firstly, F = PolynomialRing(GF(3),'x') defines a polynomial ring F in one variable, where the variable is internally named 'x'. To access the variable, the generator of the ring, you use F.gen(); it is natural to assign it to a variable x, i.e. x = F.gen(). A convenient shorthand notation for use in Sage scripts/notebooks (but not usable in Python .py files) is F.<x> = PolynomialRing(GF(3),'x'); Sage's pre-parser expands this to (pretty much) the two aforementioned definitions of F and x.

To approach your problem you can do something like this:

p = 3
A.<d1a,d1b,d2a,d2b,d3a,d3b,r1a,r1b,r2a,r2b,r3a,r3b> = PolynomialRing(GF(p))
R.<X> = PolynomialRing(A)
S.<x> = R.quotient(X^2)
laplacian = matrix([[d1a*x + d1b, -1, 0], [-1, d2a*x + d2b, -1], [0, -1, d3a*x + d3b]])
r = vector([r1a*x + r1b, r2a*x + r2b, r3a*x + r3b])
err_vec = laplacian*r
err_polys = sum((entry.lift().coefficients() for entry in err_vec), [])
I = A.ideal(err_polys)

Here I manually expanded d1 = d1a*x + d1b etc.

To get all pairs of solutions (d, r) you can do e.g.:

sage: J = I + A.ideal([v^p - v for v in A.gens()])
sage: J.variety()
[{r3b: 0, r3a: 0, r2b: 0, r2a: 0, r1b: 0, r1a: 0, d3b: 0, d3a: 0, d2b: 0, d2a: 0, d1b: 0, d1a: 0},
 {r3b: 0, r3a: 0, r2b: 0, r2a: 0, r1b: 0, r1a: 0, d3b: 0, d3a: 0, d2b: 0, d2a: 0, d1b: 0, d1a: 2},
 {r3b: 0, r3a: 0, r2b: 0, r2a: 0, r1b: 0, r1a: 0, d3b: 0, d3a: 0, d2b: 0, d2a: 0, d1b: 0, d1a: 1},
  ...
 {r3b: 1, r3a: 1, r2b: 1, r2a: 1, r1b: 1, r1a: 0, d3b: 1, d3a: 0, d2b: 2, d2a: 2, d1b: 1, d1a: 1},
 {r3b: 1, r3a: 1, r2b: 1, r2a: 1, r1b: 1, r1a: 2, d3b: 1, d3a: 0, d2b: 2, d2a: 1, d1b: 1, d1a: 2},
 {r3b: 1, r3a: 1, r2b: 1, r2a: 1, r1b: 1, r1a: 1, d3b: 1, d3a: 0, d2b: 2, d2a: 0, d1b: 1, d1a: 0}]
sage: len(J.variety())
1485

To get more insight into the solution set you can look at the primary decomposition:

sage: I.associated_primes()
[Ideal (r3b, r3a, r2b, r2a, r1b, r1a) of Multivariate Polynomial Ring in d1a, d1b, d2a, d2b, d3a, d3b, r1a, r1b, r2a, r2b, r3a, r3b over Finite Field of size 3,
 Ideal (r3b, r2b, r1b, d3b*r3a - r2a, d2b*r2a - r1a - r3a, d1b*r1a - r2a, d1b*d2b*d3b - d1b - d3b) of Multivariate Polynomial Ring in d1a, d1b, d2a, d2b, d3a, d3b, r1a, r1b, r2a, r2b, r3a, r3b over Finite Field of size 3,
 Ideal (d3b*r3b - r2b, d3b*r3a + d3a*r3b - r2a, d2b*r2b - r1b - r3b, d2b*r2a + d2a*r2b - r1a - r3a, d1b*r1b - r2b, d1b*r1a + d1a*r1b - r2a, d3a*r3b^2 + r2b*r3a - r2a*r3b, d2a*r2b^2 + r1b*r2a - r1a*r2b - r2b*r3a + r2a*r3b, d1a*r1b^2 - r1b*r2a + r1a*r2b, d1b*d2b*d3b - d1b - d3b, d1b*d2b*d3a + d1b*d2a*d3b + d1a*d2b*d3b - d1a - d3a, d1b*d2a*d3b*r2b + d1a*d3b*r1b + d1b*d3a*r3b, d1b*d2a*d3b*r2a - d1b*d2a*d3a*r2b - d1a*d2a*d3b*r2b + d1a*d3b*r1a - d1a*d3a*r1b + d1b*d3a*r3a - d1a*d3a*r3b, d1a*d2b*d3b*r1b + d2a*d3b*r2b - d1a*r1b + d3a*r3b, d1a*d2b*d3b*r1a - d1a*d2b*d3a*r1b - d1a*d2a*d3b*r1b + d2a*d3b*r2a - d2a*d3a*r2b - d1a*r1a + d3a*r3a, d1b*d2a*d3b^2 + d1a*d2b*d3b^2 + d1b*d3a - d1a*d3b, d1b*d2a*d3a*r2b*r3b - d1b*d2a*r2a*r2b + d1a*d3a*r1b*r3b - d1b*d3a*r3a*r3b - d1a*r1b*r2a, d1a*d2b*d3a*r1b*r3b + d1a*d2a*r1b*r2b + d2a*d3a*r2b*r3b - d1a*r1a*r1b - d2a*r2a*r2b - d3a*r3a*r3b, d1b*d2a*d3a*r2b*r3a + d1b*d2a*d3a*r2a*r3b - d1a*d2a*d3a*r2b*r3b - d1b*d2a*r2a^2 + d1a*d2a*r2a*r2b + d1a*d3a*r1b*r3a - d1b*d3a*r3a^2 + d1a*d3a*r1a*r3b + d1a*d3a*r3a*r3b - d1a*r1a*r2a, d1a*d2b*d3a*r1b*r3a + d1a*d2b*d3a*r1a*r3b - d1a*d2a*d3a*r1b*r3b + d1a*d2a*r1b*r2a + d1a*d2a*r1a*r2b + d2a*d3a*r2b*r3a + d2a*d3a*r2a*r3b - d1a*r1a^2 - d2a*r2a^2 - d3a*r3a^2, d1a*d2a*d3b*r1b*r2b - d1a*d3b*r1a*r1b - d2a*d3b*r2a*r2b + d1a*d3a*r1b*r3b - d3a*r2a*r3b, d1a*d2a*d3b*r1b*r2a + d1a*d2a*d3b*r1a*r2b - d1a*d2a*d3a*r1b*r2b - d1a*d3b*r1a^2 + d1a*d3a*r1a*r1b - d2a*d3b*r2a^2 + d2a*d3a*r2a*r2b + d1a*d3a*r1b*r3a + d1a*d3a*r1a*r3b - d3a*r2a*r3a, d1a*d2b^2*d3b^2 + d1a*d2b*d3b + d2a*d3b^2 + d1a + d3a, d1a*d2a*d3a*r1b*r2b*r3b - d1a*d2a*r1b*r2a*r2b - d1a*d3a*r1a*r1b*r3b - d2a*d3a*r2a*r2b*r3b - d1a*d3a*r1b*r3a*r3b + d1a*r1a*r1b*r2a + d2a*r2a^2*r2b + d3a*r2a*r3a*r3b, d1a*d2a*d3a*r1b*r2b*r3a + d1a*d2a*d3a*r1b*r2a*r3b + d1a*d2a*d3a*r1a*r2b*r3b - d1a*d2a*r1b*r2a^2 - d1a*d2a*r1a*r2a*r2b - d1a*d3a*r1a*r1b*r3a - d2a*d3a*r2a*r2b*r3a - d1a*d3a*r1b*r3a^2 - d1a*d3a*r1a^2*r3b - d2a*d3a*r2a^2*r3b - d1a*d3a*r1a*r3a*r3b + d1a*r1a^2*r2a + d2a*r2a^3 + d3a*r2a*r3a^2) of Multivariate Polynomial Ring in d1a, d1b, d2a, d2b, d3a, d3b, r1a, r1b, r2a, r2b, r3a, r3b over Finite Field of size 3]

... or the intersection of those components with d-space:

sage: [P.elimination_ideal(A.gens()[6:]).gens() for P in I.associated_primes()]
[[0],
 [d1b*d2b*d3b - d1b - d3b],
 [d1b*d2b*d3b - d1b - d3b, d1b*d2b*d3a + d1b*d2a*d3b + d1a*d2b*d3b - d1a - d3a, d1b*d2a*d3b^2 + d1a*d2b*d3b^2 + d1b*d3a - d1a*d3b, d1a*d2b^2*d3b^2 + d1a*d2b*d3b + d2a*d3b^2 + d1a + d3a]]

This shows r = (0, 0, 0) is always a solution for any d (as expected), and there are other solutions when laplacian.determinant() vanishes, and other solutions when only the constant part of laplacian.determinant() vanishes (d1b*d2b*d3b - d1b - d3b = 0).

We can count the solutions with these properties, as a double check:

sage: len([p for p in J.variety() if all(p[v] == 0 for v in A.gens()[6:])])
729
sage: len([p for p in J.variety() if not all(p[v] == 0 for v in A.gens()[6:]) and laplacian.determinant().lift().map_coefficients(lambda c: c.subs(p)) == 0])
504
sage: len([p for p in J.variety() if not all(p[v] == 0 for v in A.gens()[6:]) and laplacian.determinant().lift().map_coefficients(lambda c: c.subs(p)) != 0 and (d1b*d2b*d3b - d1b - d3b).subs(p) == 0])
252
sage: 729 + 504 + 252
1485

edit flag offensive delete link

Comments

That's very cool! Unfortunately, I'm starting to realize there are consequences to finding solutions over quotient rings (there could be zero-divisors present, the polynomial I'm modding out by could be irreducible leading to F_p[x]/ < g(x) > being a field, etc.)

Rather than looking at solutions over F_p[x]/< x^n >, can I find solutions over F_p[x] but with the condition that deg(r_i) < n and deg(d_i) < n?

Again, I'm EXTREMELY new to using SageMath (and Python for that matter). It's pretty frustrating. Thanks again for your help.

gian98863 ( 2024-04-04 02:38:31 +0100 )edit

@gian98863 You're welcome. Please submit your revised question as a new self-contained post, ideally also adding a link to this question.

rburing ( 2024-04-04 09:19:04 +0100 )edit

add a comment

answered 2024-04-01 16:29:26 +0100

Max Alekseyev

6540 ●9 ●47 ●154

updated 2024-04-01 16:31:22 +0100

First, x=F.gen() defines x as the generating polynomial variable of the ring F. That is, any linear combinations of nonnegative powers of x will define a polynomial from F. Alternatively, you can define x and F via F.<x> = PolynomialRing(GF(3)) or F.<x> = GF(3)[], or just x via x = polygen(GF(3)).

Second, var('d1,d2,d3') defines d1, d2, d3 as generic symbolic variables. It may be not a good idea to simultaneously work with polynomial and symbolic variables unless there is a clear need to do so. Your equations are polynomial in nature and so it's better to stick with variables over S:

K.<d1,d2,d3,r1,r2,r3> = S[]

Third, your equations are quadratic over $d_i,r_i$, thus you cannot solve them using linear algebra. The (lhs of) equations can be obtained via:

eq = ( matrix([[d1, -1, 0], [-1, d2, -1], [0, -1, d3]]) * vector([r1,r2,r3]) ).list()
print(eq)

which gives [d1*r1 - r2, d2*r2 - r1 - r3, d3*r3 - r2]. All possible solutions form the variety of the ideal:

J = K.ideal( eq )

which gives Ideal (d1*r1 - r2, d2*r2 - r1 - r3, d3*r3 - r2) of Multivariate Polynomial Ring in d1, d2, d3, r1, r2, r3 over Univariate Quotient Polynomial Ring in a over Finite Field of size 3 with modulus x^2. For 0-dimensional ideals over fields, one can get all elements of the variety by calling J.variety().

Unfortunately, you cannot do much with ideals over non-field rings (which is S), but in the case of small underlying ring you can get all the solutions using bruteforce. Here is a complete code:

F = PolynomialRing(GF(3),'x'); x = F.gen()
S = F.quotient(x^2,'a'); a = S.gen()

for d1,d2,d3,r1,r2,r3 in Tuples(S,6):
    r = vector([r1,r2,r3])
    if r!=0 and matrix([[d1, -1, 0], [-1, d2, -1], [0, -1, d3]]) * r == 0:
        print([d1,d2,d3],[r1,r2,r3])

which will prints all 756 solutions with nonzero vector (r1,r2,r3).

edit flag offensive delete 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

Solutions to Matrix Equation which are elements of a polynomial ring.

2 Answers

Comments

Your Answer

Question Tools

Stats

Related questions

Solutions to Matrix Equation which are elements of a polynomial ring. edit

2 Answers

Comments

Your Answer

Question Tools

Stats

Related questions

Solutions to Matrix Equation which are elements of a polynomial ring.