Explicit Determinants of Homogeneous Polynomial Evaluation Matrices and Applications

Technical Summary: Explicit Determinants of Homogeneous Polynomial Evaluation Matrices and Applications

Problem Statement
This work investigates the algebraic properties, specifically the determinants, of matrices constructed by evaluating homogeneous bivariate polynomials at pairs of vectors. Given a homogeneous polynomial $p(x, y) = \sum_{i=0}^k \alpha_i x^{k-i}y^i$ of degree $k$ and two vectors $a = (a_1, \dots, a_n)$ and $b = (b_1, \dots, b_n)$ in $\mathbb{C}^n$, the paper analyzes the $n \times n$ evaluation matrix $A_{a,b}(p(x, y)) = [p(a_r, b_s)]_{r,s=1}^n$.

While classical results exist for specific cases—such as Vandermonde matrices or matrices of the form $[(a_i + b_j)^k]$—these are often restricted to specific polynomial forms or the specific case where the matrix size $n$ equals $k+1$. A unified framework explaining the behavior of these determinants for general homogeneous polynomials across all matrix sizes (particularly when $n$ exceeds the polynomial degree) has been lacking.

Methodology
The core methodological contribution is a systematic factorization of the evaluation matrix $A_{a,b}(p(x, y))$. The authors establish that for any homogeneous polynomial of degree $k$, the evaluation matrix can be decomposed into a product of three structured matrices:
$$A_{a,b}(p(x, y)) = V_a^{(k)} D_\alpha (W_b^{(k)})^T$$
where:

• $V_a^{(k)}$ and $W_b^{(k)}$ are $n \times (k+1)$ Vandermonde-type matrices containing powers of the vector components $a_r$ and $b_s$.
• $D_\alpha$ is a $(k+1) \times (k+1)$ diagonal matrix containing the coefficients $\alpha_i$ of the polynomial.

This factorization serves as the fundamental mechanism for deriving all subsequent results. The analysis proceeds by examining the rank and determinant properties based on the relationship between the matrix dimension $n$ and the polynomial degree $k$:

1. Case $n \ge k+2$: The matrix is a product of matrices with inner dimension $k+1$. By rank inequalities, the rank of $A_{a,b}$ is at most $k+1$, rendering the $n \times n$ matrix singular.
2. Case $n = k+1$: The factorization involves square matrices, allowing for explicit determinant computation via the product of determinants.
3. Case $n \le k$: The authors apply the Cauchy–Binet formula to the product $V_a^{(k)} D_\alpha (W_b^{(k)})^T$. This expresses the determinant as a sum over subsets of indices, involving generalized Vandermonde minors. These minors are further evaluated using complete homogeneous symmetric polynomials ($H_m$).

Key Contributions and Results

• General Vanishing Condition: The paper proves that for any homogeneous polynomial of degree $k$, if the matrix size $n \ge k+2$, the determinant is identically zero. This generalizes previous observations limited to specific polynomial forms.
• Closed-Form Formula for $n = k+1$: In the "borderline" square case, an explicit formula is derived:
  $$\det(A_{a,b}(p(x, y))) = (-1)^{\binom{k+1}{2}} \left( \prod_{i=0}^k \alpha_i \right) \left( \prod_{1 \le i < j \le n} (a_j - a_i) \right) \left( \prod_{1 \le i < j \le n} (b_j - b_i) \right)$$
  This result confirms that the determinant is non-zero if and only if all polynomial coefficients are non-zero and the vector entries are pairwise distinct.
• Special Cases: The general formula recovers and extends known results for:
  • The sum-form $(x+y)^k$.
  • The quotient form $\frac{a^{k+1}-b^{k+1}}{a-b}$.
  • The alternating sum form $\frac{a^{k+1}+b^{k+1}}{a+b}$ (for odd $k$).
• General Case $n \le k$: For $n \le k+1$, the determinant is expressed as a sum involving products of coefficients, Vandermonde differences, and determinants of matrices formed by complete homogeneous symmetric polynomials. This connects the problem to symmetric function theory.
• Sum-Form Specifics: For polynomials of the form $p(x, y) = f(x+y)$, the authors derive a specific closed-form formula for $n=k+1$ that depends only on the leading coefficient of $f$, showing independence from lower-order coefficients.
• Equivariance: An explicit rule is provided for how the determinant transforms under linear changes of variables $(x, y) \mapsto (x', y') = B \cdot (x, y)$. For sum-form polynomials, the determinant scales by factors related to the sum of the transformation matrix entries.
• Finite Fields: Applying the Schwartz–Zippel lemma, the paper establishes a probabilistic upper bound for the vanishing of the determinant when vectors are chosen uniformly at random from a finite field $\mathbb{F}_q$. Specifically, for $n \le k+1$, the probability of the determinant being zero is bounded by $nk/q$.

Significance and Scope
The paper claims to provide a "systematic and unified framework" for analyzing these matrices, moving beyond ad-hoc arguments for specific examples. By leveraging the homogeneity of the polynomial, the authors demonstrate that the evaluation matrix structure is inherently tied to Vandermonde-type factorizations.

The significance lies in:

1. Unification: It explains why determinants vanish for $n \ge k+2$ across all homogeneous polynomials, not just specific instances.
2. Explicit Formulas: It provides closed-form expressions for the critical square case $n=k+1$ and structured expansions for $n \le k$.
3. Applications: The results are applied to derive equivariance laws under linear transformations and to provide non-vanishing probability bounds over finite fields, which are relevant for coding theory and structured linear algebra.

The authors note that the current framework is specific to homogeneous polynomials and explicitly identify the analysis of non-homogeneous bivariate polynomials as a potential direction for future work, maintaining a modest scope regarding the current paper's limitations.