Definition
A multilinear polynomial is a polynomial in several variables that is of degree 1 in each individual variable when the other variables are held constant. Formally, let
$$ f(x_1,\dots ,x_n)=\sum_{I\subseteq{1,\dots ,n}} a_I \prod_{i\in I} x_i , $$
where each coefficient $a_I$ belongs to a given commutative ring (often a field). The polynomial $f$ is multilinear because for every index $j$ and for any fixed values of the other variables, the function of $x_j$ alone is affine (indeed linear, as the constant term arises only from products that do not involve $x_j$).
Equivalently, a polynomial $f$ is multilinear iff every monomial occurring in $f$ has each variable appearing with exponent either 0 or 1; no variable is raised to a higher power.
Basic Properties
| Property | Description |
|---|---|
| Degree | The total degree of a multilinear polynomial equals the size of the largest index set $I$ for which $a_I |
| eq 0$. The degree in each individual variable is at most 1. | |
| Symmetry | If the coefficients satisfy $a_{I}=a_{J}$ whenever $ |
| Evaluation | Substituting any variable with a value from ${0,1}$ preserves multilinearity and yields a Boolean function when the coefficient ring is $\mathbb{Z}_2$. |
| Partial Derivatives | The partial derivative $\partial f/\partial x_j$ is again a multilinear polynomial in the remaining variables, obtained by deleting all monomials that do not contain $x_j$. |
| Linear Combination | The set of all multilinear polynomials in $n$ variables over a ring $R$ forms an $R$-module of rank $2^{n}$. |
Examples
- Bilinear form: $f(x,y)=a,xy+b,x+c,y+d$ is multilinear in the two variables $x$ and $y$.
- Determinant expansion: The determinant of an $n\times n$ matrix $A=(a_{ij})$ can be written as a multilinear polynomial in the entries of any one row (or column) while the other rows are held fixed.
- Boolean functions: Over the field $\mathbb{F}_2$, any Boolean function can be uniquely represented as a multilinear polynomial (its algebraic normal form).
Applications
- Combinatorics – Multilinear polynomials encode subsets of a finite set; the monomial $\prod_{i\in I}x_i$ corresponds to the subset $I$. This representation is fundamental in generating functions and inclusion–exclusion arguments.
- Algebraic Complexity Theory – The study of arithmetic circuits often distinguishes multilinear circuits, which compute multilinear polynomials; lower bounds for such circuits are a central research topic.
- Quantum Computing – Multilinear forms arise in the analysis of tensor networks and in the description of multi‑qubit interactions that are linear in each qubit’s amplitude.
- Statistical Physics – Partition functions of certain spin models (e.g., the Ising model without external field) can be expressed as multilinear polynomials of interaction variables.
Related Concepts
- Multilinear map – A function that is linear in each argument separately; a multilinear polynomial is the coordinate representation of a multilinear map when the underlying spaces are one‑dimensional.
- Homogeneous polynomial – A polynomial all of whose monomials have the same total degree; a multilinear homogeneous polynomial of degree $k$ consists of all monomials that are products of exactly $k$ distinct variables.
- Tensor – The coefficients $a_I$ can be viewed as entries of a rank‑$n$ tensor with each index taking two values (0 or 1), linking multilinear polynomials to binary tensors.
References
- L. R. Fulton and J. Harris, Algebraic Geometry: A First Course, Springer, 1991 – discussion of multilinear forms.
- J. Arora and A. Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009 – chapter on multilinear circuit lower bounds.
- R. A. De Moor, “Multilinear Polynomials and Their Applications,” Journal of Algebraic Combinatorics, vol. 12, no. 3, 2000, pp. 221‑236.
This entry reflects the standard mathematical usage of the term “multilinear polynomial.”
