Sylvester matrix

In mathematics, a Sylvester matrix is a matrix associated to two univariate polynomials with coefficients in a field or a commutative ring. The entries of the Sylvester matrix of two polynomials are coefficients of the polynomials. The determinant of the Sylvester matrix of two polynomials is their resultant, which is zero when the two polynomials have a common root (in case of coefficients in a field) or a non-constant common divisor (in case of coefficients in an integral domain).

Sylvester matrix is named after James Joseph Sylvester.

Definition

Formally, let p and q be two nonzero polynomials, respectively of degree m and n. Thus:

\( p(z)=p_0+p_1 z+p_2 z^2+\cdots+p_m z^m,\;q(z)=q_0+q_1 z+q_2 z^2+\cdots+q_n z^n. \)

The Sylvester matrix associated to p and q is then the \( (n+m)\times(n+m) \) matrix obtained as follows:

the first row is:

\( \begin{pmatrix} p_m & p_{m-1} & \cdots & p_1 & p_0 & 0 & \cdots & 0 \end{pmatrix}. \)

the second row is the first row, shifted one column to the right; the first element of the row is zero.
the following n − 2 rows are obtained the same way, still filling the first column with a zero.
the (n + 1)th row is:

\( \begin{pmatrix} q_n & q_{n-1} & \cdots & q_1 & q_0 & 0 & \cdots & 0 \end{pmatrix}. \)

the following rows are obtained the same way as before.

Thus, if m = 4 and n = 3, the matrix is:

\( S_{p,q}=\begin{pmatrix} p_4 & p_3 & p_2 & p_1 & p_0 & 0 & 0 \\ 0 & p_4 & p_3 & p_2 & p_1 & p_0 & 0 \\ 0 & 0 & p_4 & p_3 & p_2 & p_1 & p_0 \\ q_3 & q_2 & q_1 & q_0 & 0 & 0 & 0 \\ 0 & q_3 & q_2 & q_1 & q_0 & 0 & 0 \\ 0 & 0 & q_3 & q_2 & q_1 & q_0 & 0 \\ 0 & 0 & 0 & q_3 & q_2 & q_1 & q_0 \end{pmatrix}.\)

A variant

The above defined Sylvester matrix appears in a Sylvester's paper of 1840. In a paper of 1853, Sylvester has introduced the following matrix, which is, up to a permutation of the rows, the Sylvester matrix of p and q, considered as having both the degree max(m, n).[1] This is thus a \( 2\,\max(n, m)\times 2\,\max(n, m) \)-matrix containing \max(n, m) pairs of rows. Assuming m > n, it is obtained as follows:

the first pair is:

\( \begin{pmatrix} p_m & p_{m-1} &\cdots & p_n & \cdots & p_1 & p_0 & 0 & \cdots & 0 \\ 0 & \cdots & 0 & q_n & \cdots & q_1 & q_0 & 0 & \cdots & 0 \end{pmatrix}. \)

the second pair is the first pair, shifted one column to the right; the first elements in the two rows are zero.
the remaining max(n, m)-2 pairs of rows are obtained the same way as above.

Thus, if m = 4 and n = 3, the matrix is:

\( \begin{pmatrix} p_4 & p_3 & p_2 & p_1 & p_0 & 0 & 0 & 0\\ 0 & q_3 & q_2 & q_1 & q_0 & 0 & 0 & 0\\ 0 & p_4 & p_3 & p_2 & p_1 & p_0 & 0 & 0\\ 0 & 0 & q_3 & q_2 & q_1 & q_0 & 0 & 0\\ 0 & 0 & p_4 & p_3 & p_2 & p_1 & p_0 & 0\\ 0 & 0 & 0 & q_3 & q_2 & q_1 & q_0 & 0\\ 0 & 0 & 0 & p_4 & p_3 & p_2 & p_1 & p_0\\ 0 & 0 & 0 & 0 & q_3 & q_2 & q_1 & q_0\\ \end{pmatrix}. \)

The determinant of the 1853 matrix is, up to the sign, the product of the determinant of the Sylvester matrix (which is called the resultant of p and q) by \( p_m^{m-n} \) (still supposing \( m\ge n \) ).

Applications

These matrices are used in commutative algebra, e.g. to test if two polynomials have a (non constant) common factor. In such a case, the determinant of the associated Sylvester matrix (which is named the resultant of the two polynomials) equals zero. The converse is also true.

The solutions of the simultaneous linear equations

\( {S_{p,q}}^\mathrm{T}\cdot\begin{pmatrix}x\\y\end{pmatrix} = \begin{pmatrix}0\\0\end{pmatrix} \)

where x is a vector of size n and y has size m, comprise the coefficient vectors of those and only those pairs x, y of polynomials (of degrees n-1 and m-1, respectively) which fulfill

\( x(z) \cdot p(z) + y(z) \cdot q(z) = 0, \)

where polynomial multiplication and addition is used. This means the kernel of the transposed Sylvester matrix gives all solutions of the Bézout equation where \( \deg x < \deg q and \deg y < \deg p. \)

Consequently the rank of the Sylvester matrix determines the degree of the greatest common divisor of p and q:

\( \deg(\gcd(p,q)) = m+n-\mathrm{rank}~S_{p,q} \)

Moreover, the coefficients of this greatest common divisor may be expressed as determinants of submatrices of the Sylvester matrix (see Subresultant).
See also

Transfer matrix

References

Akritas, A.G., Malaschonok, G.I., Vigklas, P.S.:Sturm Sequences and Modified Subresultant Polynomial Remainder Sequences. Serdica Journal of Computing, Vol. 8, No 1, 29--46, 2014

Weisstein, Eric W., "Sylvester Matrix", MathWorld.

Every Eisenstein integer a + bω whose norm a2 − ab + b2 is a rational prime is an Eisenstein prime. In fact, every Eisenstein prime is of this form, or is a product of a unit and a rational prime congruent to 2 mod 3.

This is a discrete Fourier transform.

Mathematics Encyclopedia