Resultant

发表于

极简 Sylvester 结式消元介绍

Resultant

两个一元多项式在一个域或者交换环上的 Resultant 为它们对应的 Sylvester matrix 的行列式。

记两个一元多项式 f(x),g(x)f(x),g(x) 为

f(x)=a0xn+a1xn−1+...+ang(x)=b0xm+b1xm−1+...+bnf(x)=a_0x^n+a_1x^{n-1}+...+a_n\\ g(x)=b_0x^m+b_1x^{m-1}+...+b_n

其的 Sylvester matrix 构造方式如下

  • 取 f(x)f(x) 的系数，依次在左上角起向下构造 mm 行，每行右移一格补零
  • 取 g(x)g(x) 的系数，依次在左下角起向下构造 nn 行，每行右移一格补零

具体表示为

R(f,g)=[a0a1⋯an0⋯00a0⋯an−1an⋯0⋮⋱⋱⋮00⋯a0a1⋯anb0b1⋯bm0⋯00b0⋯bm−1bm⋯0⋮⋱⋱⋮00⋯b0b1⋯bm]\text{R}(f, g) = \begin{bmatrix} a_0 & a_1 & \cdots & a_n & 0 & \cdots & 0 \\ 0 & a_0 & \cdots & a_{n-1} & a_n & \cdots & 0 \\ \vdots & & \ddots & & & \ddots & \vdots \\ 0 & 0 & \cdots & a_0 & a_1 & \cdots & a_n \\ b_0 & b_1 & \cdots & b_m & 0 & \cdots & 0 \\ 0 & b_0 & \cdots & b_{m-1} & b_m & \cdots & 0 \\ \vdots & & \ddots & & & \ddots & \vdots \\ 0 & 0 & \cdots & b_0 & b_1 & \cdots & b_m \end{bmatrix}

然后定义结式 res(f,g)=det⁡(R(f,g))\text{res}(f,g)=\det(\text{R}(f,g))

其有如下重要性质

  • 多项式 ff 和 gg 有公共根的充要条件就是 R(f,g)=0R(f,g)=0

也就是根据这个性质，其在 ctf 中解决一些方程消元的问题有着重要的地位

example:

一个简单的例子，设

f(x)=x2−2x+1g(x)=x−1f(x)=x^2-2x+1\\ g(x)=x-1

我们知道 deg⁡(f)=2,deg⁡(g)=1\deg(f)=2,\deg(g)=1，所以只要让 f(x)f(x) 从左上角起向下构造 11 行，g(x)g(x) 从左下角起向下构造 22 行，那么我们可以构造一个 3×33\times 3 的矩阵，即

[1−211−1001−1]\begin{bmatrix}1&-2&1\\1&-1&0\\0&1&-1\\\end{bmatrix}

简单的计算一下行列式可以发现是 0，然后简单验算一下它们全是用共根 1。

Sylvester 结式消元

假设现在有二元多项式

f(x,y)=a0xmyn+aixm−1yn−1+...+ang(x,y)=b0xiyj+bixi−1yj−1+...+bmf(x,y)=a_0x^my^n+a_ix^{m-1}y^{n-1}+...+a_n\\ g(x,y)=b_0x^iy^j+b_ix^{i-1}y^{j-1}+...+b_m\\

我们可以考虑将 xx 视为常数，构造 Sylvester matrix，然后计算行列式，这样子就会得到消去 xx 的新式子，然后对该式子求解即可得到 yy，最后进行回代就可以计算出 xx。

python 实现

根据结式的定义，我们可以很容易写出代码来实现计算两个多项式的 Sylvester matrix

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from sympy import Matrix, Poly
from sympy.abc import x, y, z

def sylvester_matrix(f, g, x):
    F = Poly(f, x)
    G = Poly(g, x)
    a = F.all_coeffs()
    b = G.all_coeffs()
    m = F.degree()
    n = G.degree()

    def b_row(cf, c, l):
        rows = []
        pad_l = l - len(cf)
        for i in range(c):
            row = [0]*i + cf + [0]*(pad_l - i)
            rows.append(row)
        return rows

    row_f = b_row(a, n, m + n)
    row_g = b_row(b, m, m + n)
    return Matrix(row_f + row_g)

可以简单测试一下，假设有一元多项式

f(x,y)=7x+xy+123yg(x,y)=4y+x5+6xy2f(x,y) = 7x + xy + 123y\\ g(x,y) = 4y + x^5 + 6xy^2

我们直接调用上面的代码

1
2
3
4
f = 7 * x + x * y + 123 * y
g = 4 * y + x**5 + 6 * x * y**2
R = sylvester_matrix(f, g, x).det()
print(R)

得到

−738y7−20660∗y6−28153273675y5−1010576y4−1758218y3+48020y2+67228y-738y^7 - 20660*y^6 - 28153273675y^5 - 1010576y^4 - 1758218y^3 + 48020y^2 + 67228y

可以和 sage 比对一下

1
2
3
4
5
R.<x, y> = QQ[]
f = 7 * x + x * y + 123 * y
g = 4 * y + x**5 + 6 * x * y**2
f.sylvester_matrix(g,x).det()
# -738*y^7 - 20660*y^6 - 28153273675*y^5 - 1010576*y^4 - 1758218*y^3 + 48020*y^2 + 67228*y

实际上是一样的，如果要实际使用并且解这个方程的话其实还是推荐用 sage 了，因为自己写的肯定没 sage 好的啦 XD