Multilinear polynomial
A multilinear polynomial is a multivariate polynomial over a field (such as the real or complex numbers) that is linear in each of its variables separately, meaning that in every monomial term, each variable appears with exponent at most 1 and no variable is repeated.[1] This distinguishes multilinear polynomials from general multivariate polynomials, where higher powers of individual variables are permitted.[2] Formally, for variables x_1, \dots, x_n, a multilinear polynomial can be written as \sum_{S \subseteq } c_S \prod_{i \in S} x_i, where c_S are coefficients and the sum is over subsets S of \{1, \dots, n\}, ensuring square-free monomials.[3] Multilinear polynomials form a vector space of dimension $2^n for n variables, as each possible subset corresponds to a basis monomial, and they uniquely represent any function from \{0,1\}^n to the field when evaluated on the boolean hypercube.[4] This property makes them foundational in the analysis of boolean functions, where the Fourier expansion over the hypercube uses multilinear terms.[4] Evaluation of a multilinear polynomial at a point can be computed efficiently using techniques like the sum-over-subsets method, with time complexity O(2^n) in the worst case but optimizations for sparse representations.[3] In applications, multilinear polynomials arise in algebraic combinatorics and computational complexity. They also play a role in finite field theory, where surjectivity properties hold under certain algebraic conditions, such as in unital algebras with surjective derivations.[5]Definition and Fundamentals
Formal Definition
A multilinear polynomial in n variables over a field \mathbb{F} is a polynomial where each variable appears with degree at most 1 in every monomial term.[6][3][7] Its general form is given by p(x_1, \dots, x_n) = \sum_{S \subseteq \{1, \dots, n\}} c_S \prod_{i \in S} x_i, where the c_S \in \mathbb{F} are coefficients.[3] Multilinearity means that the polynomial is linear in each variable x_i when the other variables are held fixed.[6][3] A multilinear polynomial is homogeneous of degree k (or k-linear) if every monomial term involves exactly k variables, so the sum is restricted to subsets S with |S| = k.[8] Unlike general multivariate polynomials, multilinear polynomials contain no terms with higher powers such as x_i^2 or x_i x_j^2.[6][7]Key Characteristics
Multilinear polynomials build upon foundational concepts in algebra, particularly univariate polynomials over fields such as the real numbers \mathbb{R} or the complex numbers \mathbb{C}, where these are finite sums of monomials with non-negative integer exponents and coefficients from the field. Extending this to multivariate polynomials involves considering expressions in several indeterminates, allowing interactions among variables through products, but with restrictions that define multilinearity. This prerequisite knowledge is essential, as multilinear polynomials operate within the polynomial ring K[x_1, \dots, x_n] over a field K, inheriting properties like addition and scalar multiplication while imposing degree constraints per variable.[9] A defining characteristic of multilinear polynomials is their structure as sums of multilinear monomials, where each monomial is a product of distinct variables raised to the first power only, ensuring no squared or higher powers of any single variable appear. In the ring K[x_1, \dots, x_n], this means every term has the form c \cdot x_{i_1} x_{i_2} \cdots x_{i_k} for distinct indices i_1, \dots, i_k and coefficient c \in K, with k \leq n. This linearity in each variable separately distinguishes multilinear polynomials from general multivariate ones, which may include higher-degree terms like x_i^2, and aligns them closely with multilinear forms in tensor algebra. The absence of higher powers per variable simplifies analysis in contexts like approximation and identity testing, as the polynomials exhibit controlled growth and sparsity relative to full-degree counterparts. The total degree of a multilinear polynomial, defined as the maximum degree across all its monomials, is inherently bounded by the number of variables n, since no monomial can exceed degree n without repeating variables, which is prohibited. This bound implies that multilinear polynomials are homogeneous of degree at most n if restricted to such terms, providing a natural cap on complexity that facilitates computational bounds in algorithms evaluating or factoring them. For instance, in n variables, the space of multilinear polynomials has dimension $2^n, spanned by the n-choose-k monomials for degrees up to n. The representation of a multilinear polynomial in the monomial basis \{x_{i_1} \cdots x_{i_k} \mid 1 \leq i_1 < \cdots < i_k \leq n\} (or including the constant term) is unique over any field K, due to the linear independence of these monomials in the polynomial ring. This uniqueness stems from the standard basis property of monomials in K[x_1, \dots, x_n], allowing unambiguous decomposition and coefficient extraction, which is crucial for theoretical results in algebraic complexity and proof systems.[10]Examples and Representations
Basic Examples
A multilinear polynomial in a single variable, known as the univariate case, is simply a linear polynomial of the form ax + b, where a and b are constants; this is trivially multilinear since the degree in the sole variable x is at most 1.[3] In two variables, a basic example is the polynomial xy + 2x + 3y + 4, which consists of monomials each having degree at most 1 in both x and y.[3] Similarly, for three variables, the polynomial xyz + xy + yz + x + y + z + 1 is multilinear, as no variable appears with exponent greater than 1 in any term.[3] A homogeneous multilinear polynomial, where all terms have the same total degree, can be seen in the quadratic form xy + yz + zx over three variables, which is linear in each variable separately and has total degree 2.[1] To highlight the distinction from general polynomials, consider the expansion of (x + y + z)^2: (x + y + z)^2 = x^2 + y^2 + z^2 + 2xy + 2yz + 2zx. The squared terms x^2, y^2, and z^2 each have degree 2 in one variable, violating multilinearity; thus, only the cross terms $2xy + 2yz + 2zx constitute a multilinear polynomial.[3]Matrix and Tensor Forms
In the bilinear case, a multilinear polynomial involving two sets of variables corresponds to a bilinear form on vector spaces, which admits a matrix representation. For finite-dimensional vector spaces V and W over a field K, with bases \{e_i\} and \{f_j\}, the bilinear form B: V \times W \to K defined by B(x, y) = \sum_{i,j} a_{ij} x_i y_j, where x = \sum x_i e_i and y = \sum y_j f_j, is represented by the matrix A = (a_{ij}). If the form is symmetric, meaning B(v, w) = B(w, v) for all v \in V, w \in W, then A is a symmetric matrix, allowing the form to be expressed as B(x, y) = x^T A y for column vectors x, y. This matrix encodes the coefficients directly, facilitating computations like diagonalization for quadratic forms derived from the bilinear case.[11] For higher degrees, multilinear polynomials generalize this to tensor representations. A multilinear polynomial of order n in variables grouped into vectors x^{(1)}, \dots, x^{(n)} from finite-dimensional spaces V_1, \dots, V_n is represented by an n-way tensor C \in V_1^* \otimes \cdots \otimes V_n^*, where the entries c_{i_1 \dots i_n} are the coefficients corresponding to the monomial \prod_{k=1}^n x^{(k)}_{i_k}. This tensor captures all multilinear terms without higher powers in individual variables, with the polynomial given by f(x^{(1)}, \dots, x^{(n)}) = \sum_{i_1, \dots, i_n} c_{i_1 \dots i_n} \prod_{k=1}^n x^{(k)}_{i_k}. The universal property of the tensor product ensures that every multilinear map from V_1 \times \cdots \times V_n to K corresponds uniquely to a linear functional on the tensor product space V_1 \otimes \cdots \otimes V_n, providing an algebraic foundation for this representation.[9] Evaluation of the polynomial involves tensor contraction, where the tensor C is multiplied with the input vectors to yield the scalar value. Specifically, the sum over multi-indices contracts the tensor with each x^{(k)}, effectively applying the multilinear map encoded by C. This operation is linear in each vector separately and scales efficiently in finite dimensions, with complexity tied to the tensor's order and dimensions. In applications, such contractions appear in coordinate expressions of multilinear maps between vector spaces, where the polynomial form arises from choosing bases in the domain and codomain.[12] As an example, consider a trilinear polynomial in three vector variables x, y, z \in K^m. It is represented by a 3-tensor C \in (K^m)^{\otimes 3} with entries c_{ijk}, and evaluates as f(x, y, z) = \sum_{i,j,k=1}^m c_{ijk} x_i y_j z_k, which is the full contraction C : x \otimes y \otimes z. This extends the bilinear matrix case, where the 3-tensor slices correspond to bilinear forms parameterized by the third index. Such representations are pivotal in multilinear algebra for decomposing complex forms into basis expansions.[9]Properties
Algebraic Properties
Multilinear polynomials form a vector space over the base field, meaning that the sum of two multilinear polynomials and the scalar multiple of a multilinear polynomial are themselves multilinear. This preservation follows directly from the linearity in each variable defining multilinearity, as addition and scalar multiplication are linear operations that do not introduce higher powers in any variable.[13] The product of two multilinear polynomials, however, is not necessarily multilinear, since multiplication can produce terms with repeated variables and thus higher degrees in those variables. For instance, consider the product (xy)(xz) = x^2 y z, where the resulting monomial has a quadratic term in x, violating multilinearity. If the coefficients of a multilinear polynomial are symmetric under permutations of its variables, the polynomial relates to classical invariant theory, where such symmetric multilinear forms serve as invariants or covariants under the action of groups like the general linear group.[13] These symmetric structures capture permutation-invariant properties essential for studying representations and decompositions in multilinear algebra.[13] The partial derivative of a multilinear polynomial with respect to one variable yields another multilinear polynomial of lower order, linear in the remaining variables.[14] This property arises because differentiation reduces the degree in the differentiated variable from 1 to 0 without affecting linearity in the others, preserving the multilinear structure overall.[14] To extend multilinearity to non-homogeneous polynomials, the homogenization process scales the terms by powers of an auxiliary variable, transforming the polynomial into a homogeneous form that can then be polarized into a multilinear expression.[13] Specifically, for a polynomial Q(p) of degree n, the homogenized form is Q(x, y) = y^n Q(x/y), which facilitates conversion to a multilinear symmetric form via polarization identities.[13]Domain-Specific Properties
Multilinear polynomials exhibit distinct behaviors when restricted to specific domains, such as the unit hypercube or rectangular regions, arising from their separability and linearity in each variable. Over the unit hypercube [0,1]^n, a multilinear polynomial attains its maximum value at one of the vertices due to its multilinearity, which implies convexity with respect to each variable when the others are fixed; this property ensures that extrema occur at the boundaries, propagating recursively to the cube's corners.[15] This vertex attainment simplifies optimization tasks over the hypercube, as evaluating the polynomial at the $2^n vertices suffices to identify the global maximum.[16] In the positive orthant \mathbb{R}_{\geq 0}^n, a multilinear polynomial with all positive coefficients is monotonically increasing, since each partial derivative with respect to a variable x_i yields a lower-degree multilinear polynomial with non-negative coefficients, ensuring non-negative gradients throughout the domain. This monotonicity facilitates analysis in optimization and probability contexts where positivity is assumed. On bounded rectangular domains, such as [a_1, b_1] \times \cdots \times [a_n, b_n], multilinear polynomials demonstrate separability: each monomial term factors into a product of univariate linear functions in distinct variables, allowing the overall expression to be decomposed into separable components without cross-variable dependencies beyond the product structure. This factorization enables efficient bounding and evaluation by reducing multivariate computations to univariate ones over individual intervals.[17] Regarding regularity, multilinear polynomials are Lipschitz continuous over compact rectangular domains, with the Lipschitz constant bounded by the supremum norm of the gradient; since each component of the gradient is a multilinear polynomial of degree at most n-1, it remains bounded on the compact set, yielding a finite constant that scales with the domain's size and the polynomial's coefficients. For volume computations, the integral of a multilinear polynomial over a rectangular domain factors into a product of univariate integrals due to the separability of its terms under Fubini's theorem: for a monomial c \prod_{i \in S} x_i where S \subseteq \{1, \dots, n\}, the integral equals c \left( \prod_{i \in S} \int_{a_i}^{b_i} x_i \, dx_i \right) \left( \prod_{j \notin S} (b_j - a_j) \right), extending linearly to the full polynomial. This property is particularly useful in probabilistic expectations and geometric measure theory.[18]Applications and Extensions
In Algebra and Combinatorics
In the 19th century, Arthur Cayley pioneered the study of invariants for binary forms, developing methods that extended to multilinear forms as a foundational aspect of classical invariant theory. His work on hyperdeterminants and partial differential operators provided tools for constructing invariants of homogeneous polynomials under linear transformations, laying the groundwork for later algebraic applications of multilinear structures.[19] Cycle index polynomials serve as generating functions for counting permutations under group actions, functioning as invariants that encode the cycle structure of elements in permutation groups like the symmetric group S_n. Defined as Z_G = \frac{1}{|G|} \sum_{g \in G} \prod_k x_k^{c_k(g)}, where c_k(g) is the number of cycles of length k in g, these polynomials facilitate enumeration via Pólya's theorem by substituting variables to generate counts of orbits. For example, substituting x_k = s^k yields the cycle polynomial, which counts permutations by fixed points and cycle types, providing a framework for symmetric invariants in combinatorial enumeration. In representation theory, characters of the symmetric group S_n are analyzed through multilinear polynomials, which decompose into components corresponding to irreducible representations labeled by partitions of n. A multilinear polynomial f(x_1, \dots, x_n) of degree n can be expressed as a sum over association types, with each term evaluated using the character \phi_\lambda of the irreducible representation V^\lambda, yielding matrices whose ranks determine polynomial identities in the group algebra \mathbb{F} S_n. This approach, rooted in the Wedderburn decomposition, allows characters to express the multiplicity and structure of representations, connecting multilinear forms to the Frobenius character formula for symmetric functions.[20] Multilinear extensions play a key role in combinatorial optimization, particularly for maximizing monotone submodular functions over matroid intersections. For a submodular function f: 2^X \to \mathbb{R}^+, the multilinear extension F(y) = \mathbb{E}[f(\hat{y})] for y \in [0,1]^X and random \hat{y} with coordinates independently 1 with probability y_i, relaxes the discrete problem to a continuous one over the matroid polytope. The continuous greedy algorithm iteratively maximizes F(y) over a single matroid constraint, achieving a (1 - 1/e)-approximation via pipage rounding to a feasible set, while extensions to multiple matroids (intersections) yield $1/(k + \epsilon)-approximations for k constraints using local search on the relaxation. This framework enables efficient algorithms for problems like sensor placement or diversity maximization under independence constraints.[21][22] Boolean multilinear polynomials provide a unique representation for switching functions—Boolean functions arising in switching circuit theory—eliminating higher-degree terms due to the identity x_i^2 = x_i over \{0,1\}. Any Boolean function f: \{ -1,1 \}^n \to \{ -1,1 \} expands uniquely as f(x) = \sum_{S \subseteq } \hat{f}(S) \prod_{i \in S} x_i, where \hat{f}(S) are Fourier coefficients computable via expectations, offering a degree-d characterization equivalent to approximation by d-juntas. This multilinear form underpins analysis in learning theory and complexity, with the degree measuring the function's sensitivity to variable subsets.[23]In Analysis and Approximation
Multilinear polynomials serve as effective approximators for continuous functions in analytical settings, particularly when higher-degree terms in individual variables are not required. While the full algebra of multivariate polynomials is dense in the space of continuous functions on compact sets by the Stone-Weierstrass theorem, which guarantees uniform approximation due to the algebra's separation of points and closure under multiplication and conjugation, multilinear polynomials impose strict degree constraints (at most degree 1 per variable), limiting their representational power for functions with significant nonlinearity in single variables. This makes them suitable for approximating functions that exhibit low interaction complexity across variables, such as those arising in sensitivity analysis or interaction models, where least-squares projections onto the multilinear subspace on domains like [0,1]^n yield interpretable coefficients representing variable interactions.[24] In high-dimensional analysis, multilinear polynomials facilitate tensor product approximations, which decompose multivariate functions into sums of products of univariate functions, thereby mitigating the curse of dimensionality that plagues full tensor grid methods requiring exponential storage and computation in the dimension d. For instance, the Tucker decomposition represents a function f: \mathbb{R}^d \to \mathbb{R} as a low-rank tensor product \sum_{k_1=1}^{r_1} \cdots \sum_{k_d=1}^{r_d} b_{k_1 \dots k_d} \prod_{j=1}^d V^{(j)}_{k_j}(x_j), where ranks r_j \ll n (grid size per dimension) reduce complexity from O(n^d) to O(d r n \log n), enabling efficient approximation of operators like convolutions or Green's functions in physics simulations.[25] Such approaches are particularly valuable for smooth functions on high-dimensional domains, preserving accuracy while scaling linearly with dimension. Error bounds for multilinear approximations of smooth functions draw from generalizations of Jackson-type theorems in multivariate settings, which relate the best approximation error to moduli of smoothness or mixed derivatives, adapted for bounded multi-degree (here, degree 1 per variable). For functions in Sobolev spaces on the unit cube, the error in best uniform approximation by multilinear polynomials satisfies E(f) \leq C \omega_k(f, h_1, \dots, h_d), where \omega_k is a mixed modulus of smoothness and h_j are grid spacings, with constants C depending on the smoothness order k; this establishes O(h) convergence for Lipschitz functions, though slower than higher-degree polynomials for univariate nonlinearity.[26] These bounds highlight multilinear methods' efficiency in anisotropic or tensor-structured problems, where error scales better than isotropic total-degree approximations. In numerical analysis, multilinear polynomials form the basis for interpolation on tensor product grids, providing a straightforward extension of linear interpolation to higher dimensions without introducing cross-derivatives. On a d-dimensional rectangular grid with nodes \{x_{i_j}^{(j)}\}_{i_j=1}^{n_j} for j=1,\dots,d, the interpolant is P(x) = \sum_{i_1=1}^{n_1} \cdots \sum_{i_d=1}^{n_d} f(x_{i_1}^{(1)}, \dots, x_{i_d}^{(d)}) \prod_{j=1}^d \ell_{i_j}^{(j)}(x_j), where \ell_{i_j}^{(j)} are univariate linear basis functions; this yields exact reproduction on grid points and O(h) error for smooth functions, commonly applied in finite element methods or data visualization to handle scattered high-dimensional data efficiently.[27] Fourier-Motzkin elimination extends to projecting systems of multilinear inequalities in optimization and feasibility analysis, where linear relaxations of multilinear terms (e.g., via McCormick envelopes) allow variable elimination to derive valid bounds without solving the full nonlinear program. By applying the elimination sequentially to the linearized constraints, one obtains a reduced system whose projection captures the feasible region of the original multilinear inequalities, useful for deriving cutting planes in mixed-integer nonlinear programming with 0-1 variables.[28] This technique ensures completeness in quantifier elimination for polynomial inequalities, though with exponential growth in the number of inequalities for high dimensions.In Computing and Optimization
Maximizing a multilinear polynomial over the unit hypercube [0,1]^n is NP-hard, as it generalizes challenging combinatorial optimization problems like quadratic assignment. Approximation algorithms leverage semidefinite programming (SDP) relaxations of the multilinear objective, followed by randomized rounding to obtain feasible points; for instance, dependent rounding schemes yield guarantees such as (1-1/e)-approximation for monotone submodular cases, while general multilinear maximization benefits from similar techniques with multiplicative error bounds.[29][30] In machine learning, multilinear polynomials model interactions in high-dimensional tensor data through decompositions like the canonical polyadic (CP) decomposition, which expresses a tensor as a sum of rank-1 components: \mathcal{X} \approx \sum_{r=1}^R \lambda_r \mathbf{a}_r \circ \mathbf{b}_r \circ \mathbf{c}_r \dots, where \circ denotes outer product and the factors correspond to coefficients in a symmetric multilinear polynomial representation. This approach enables dimensionality reduction and feature extraction in applications such as topic modeling, image classification, and web link analysis, preserving latent multilinear structures in multi-way arrays.[31] Software tools for symbolic manipulation of multilinear polynomials include Mathematica, which supports conversion to multilinear form via functions likeExpand and Collect on multivariate expressions with degree constraints, allowing efficient handling of homogeneous sums-of-products. Similarly, SageMath provides multivariate polynomial rings over various coefficient fields, enabling operations like factorization and substitution tailored to multilinear constraints through its PolyDict backend and libSINGULAR interface.[32][33]