Question

Let \(f=x^{8}+x^{6}-3 x^{4}-3 x^{3}+8 x^{2}+2 x-5\) and \(y=3 x^{6}+5 x^{4}-4 x^{2}-9 x+21\) be polynomials in \(Z \mid x]\) and \(S_{k} \in \mathbb{Z}^{(14-2 k) \times(14-2 k)}\) be the submatrix of the Sylvester matrix of \(f\) and \(g\) whose determinant is the \(k\) th subresultant \(\sigma_{k}\), as in Section 6,10 , for \(0 \leq k \leq 6\). (i) Trace the Extended Euclidean Algorithm \(3.6\) for \(f\) and \(g\) over \(Q\), and check that \(s_{i} f+t_{i} g=r_{i}\) for \(2 \leq i \leq \ell\). Compute the degree sequence \(n_{0}=8, n_{1}=6, n_{2} \ldots, . n_{\ell}\). (ii) Set up the matrices \(S_{k}\) and compute \(\sigma_{k}\) for \(0 \leq k \leq 6\). Explain which of the \(S_{k}\) are singular and what this has to do with the remainders in the EEA. Say why the linear system \(S_{n_{i}} v=u_{n,}\), has a unique solution \(v \in \mathbb{Q}^{14-2 n_{j}}\) and state the coefficients of the solution without calculation. Then check your answer by actually computing \(S_{m}, v\). (iv) For those \(k \in\\{0 \ldots, 5\\}\) where \(\sigma_{k}=0\), find a nonzero vector \(v \in Q^{14-2 k}\) such that \(S_{k} v=0\) without calculation. Then check your answer by actually computing \(S_{k} v\).

Short answer

Use EEA to find gcd as linear form; calculate \(\sigma_k\) from Sylvester matrices; identify singular \(S_k\); solve system, verify solutions.

Step-by-step solution

Understanding the Problem

We have two polynomials, \(f\) and \(y\), defined over the integers. We need to perform operations related to the Sylvester matrix and the Euclidean algorithm. The problem requires us to trace the Extended Euclidean Algorithm (EEA) for these polynomials, calculate determinants of submatrices, and interpret results.

Applying Extended Euclidean Algorithm (EEA)

Using the EEA, we aim to express the greatest common divisor of \(f\) and \(g\) as a linear combination of \(f\) and \(g\). This involves iterative division steps, replacing each polynomial with the remainder from the division of the previous two polynomials. Track coefficients \(s_i\) and \(t_i\).

Constructing the Sylvester Matrix

The Sylvester matrix is constructed using the coefficients of the two polynomials, arranged such that it becomes square. Each row corresponds to an equation where terms are multiplied by monomial powers. Submatrix \(S_k\) is extracted from this matrix based on powers related to \(k\).

Calculating Subresultants \(\sigma_k\)

The subresultant \(\sigma_k\) is the determinant of the submatrix \(S_k\). Calculate this determinant for \(0 \leq k \leq 6\). This involves taking determinants of progressively smaller matrices from the Sylvester matrix.

Analyzing Singular Matrices

Identify which \(S_k\) matrices are singular (i.e., have zero determinant). A singular \(S_k\) indicates that the remainder at the corresponding step in the EEA is zero, suggesting a common factor between \(f\) and \(g\).

Solving Linear System

Solve the linear system \(S_{n_i} v = u_{n,i}\) to find a unique solution vector \(v\) in \(\mathbb{Q}^{14-2n_j}\). Verify that for non-singular matrices, this system provides a unique solution due to the invertibility of \(S_{n_i}\).

Finding Nonzero Vector for Singular Matrices

For every \(k\) where \(\sigma_k = 0\), find a nonzero vector \(v\) such that \(S_k v = 0\). This involves choosing vectors in the kernel of the singular matrix, often based on easy observation or specific row operations.

Verification through Computation

Verify computed vectors or coefficients by actually implementing calculations in the Sylvester matrix context, confirming that dims or results match expectations.

Key concepts

Sylvester Matrix

The Sylvester matrix is a structured matrix that plays a crucial role in algebra, especially in the polynomial context. For two given polynomials, this matrix is constructed using their coefficients. Its main purpose is to help determine solutions and relationships between polynomials, particularly in finding common roots or factors.

• It is square, meaning it has the same number of rows as columns.
• Each row of the Sylvester matrix represents a polynomial multiplied by a monomial power.
• The size of the Sylvester matrix depends on the degree of the given polynomials.

This matrix becomes essential when we need to extract its submatrices, denoted as \(S_k\), which help compute determinants known as subresultants. Subresultants provide valuable information about the roots and factorability of polynomials.

Extended Euclidean Algorithm

The Extended Euclidean Algorithm (EEA) is a powerful method used to find the greatest common divisor (GCD) of two polynomials while also expressing the GCD as a linear combination of the given polynomials. Here's how it works:

• The EEA involves a series of division steps where each polynomial is replaced by the remainder of the division of the two previous polynomials.
• Throughout these steps, we calculate coefficients \(s_i\) and \(t_i\) such that \(s_i f + t_i g = r_i\), where \(r_i\) is the current remainder.
• The process continues until a remainder of zero is achieved, indicating that the previous non-zero remainder is the GCD.

A unique aspect of the EEA is its ability to track coefficients, providing a way to write the GCD as a combination of the input polynomials. This is particularly useful when dealing with linear diophantine equations and polynomial arithmetic.

Subresultant Theory

Subresultant Theory involves determining the subresultants, \(\sigma_k\), from the Sylvester matrix, which conveys information about the common factors and roots of polynomials. Here's what you need to know:

• Subresultants are linked to the determinants of the submatrices \(S_k\) extracted from the full Sylvester matrix.
• They provide insight into the structure and decomposition of polynomial GCD calculations.
• The presence of a zero subresultant, \(\sigma_k = 0\), often indicates the existence of a common root or factor between the given polynomials.

By evaluating each \(\sigma_k\), mathematicians can gauge the degree of overlap between polynomial roots, simplifying factorization and root-finding endeavors. Understanding subresultants is vital for effectively deciphering polynomial relationships in algebra.

Singular Matrices

In linear algebra, a singular matrix is one that lacks an inverse, typically characterized by a determinant equal to zero. Understanding this concept is essential in the context of polynomial arithmetic, particularly when dealing with Sylvester matrices and their submatrices.

• A singular Sylvester submatrix \(S_k\) implies that its determinant, or subresultant \(\sigma_k\), is zero.
• This often indicates a remainder of zero at that step in the Extended Euclidean Algorithm, hinting at a common factor between the original polynomials.
• For singular submatrices, the system \(S_k v = 0\) has non-trivial solutions, meaning there exists a nonzero vector \(v\) satisfying the equation.

Understanding singularity is crucial as it guides mathematicians to common factors, thus simplifying further calculations involving polynomial GCD or factorization concerns.