# Multilinear polynomial

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Multilinear_polynomial
> Markdown URL: https://mediated.wiki/source/Multilinear_polynomial.md
> Source: https://en.wikipedia.org/wiki/Multilinear_polynomial
> Source revision: 1327085497
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

Type of polynomial

In algebra, a **multilinear polynomial**[1] is a [multivariate](/source/Multivariate_function) [polynomial](/source/Polynomial) that is [linear](/source/Linear) (meaning [affine](/source/Affine_transformation)) in each of its variables [separately](/source/Multilinear_map), but not necessarily [simultaneously](/source/Linear_map). It is a polynomial in which no variable occurs to a power of 2 {\displaystyle 2} or higher; that is, each [monomial](/source/Monomial) is a constant times a product of distinct variables. For example f ( x , y , z ) = 3 x y + 2.5 y − 7 z {\displaystyle f(x,y,z)=3xy+2.5y-7z} is a multilinear polynomial of [degree](/source/Degree_of_a_polynomial) 2 {\displaystyle 2} (because of the monomial 3 x y {\displaystyle 3xy} ) whereas f ( x , y , z ) = x 2 + 4 y {\displaystyle f(x,y,z)=x^{2}+4y} is not. The [degree](/source/Degree_of_a_polynomial) of a multilinear polynomial is the maximum number of distinct variables occurring in any monomial.

## Definition

Multilinear polynomials can be understood as a [multilinear map](/source/Multilinear_map) (specifically, a [multilinear form](/source/Multilinear_form)) applied to the vectors [1 x], [1 y], etc. The general form can be written as a [tensor contraction](/source/Tensor_contraction): f ( x ) = ∑ i 1 = 0 1 ∑ i 2 = 0 1 ⋯ ∑ i n = 0 1 a i 1 i 2 ⋯ i n x 1 i 1 x 2 i 2 ⋯ x n i n {\displaystyle f(x)=\sum _{i_{1}=0}^{1}\sum _{i_{2}=0}^{1}\cdots \sum _{i_{n}=0}^{1}a_{i_{1}i_{2}\cdots i_{n}}x_{1}^{i_{1}}x_{2}^{i_{2}}\cdots x_{n}^{i_{n}}}

For example, in two variables: f ( x , y ) = ∑ i = 0 1 ∑ j = 0 1 a i j x i y j = a 00 + a 10 x + a 01 y + a 11 x y = ( 1 x ) ( a 00 a 01 a 10 a 11 ) ( 1 y ) {\displaystyle f(x,y)=\sum _{i=0}^{1}\sum _{j=0}^{1}a_{ij}x^{i}y^{j}=a_{00}+a_{10}x+a_{01}y+a_{11}xy={\begin{pmatrix}1&x\end{pmatrix}}{\begin{pmatrix}a_{00}&a_{01}\\a_{10}&a_{11}\end{pmatrix}}{\begin{pmatrix}1\\y\end{pmatrix}}}

## Properties

A multilinear polynomial f {\displaystyle f} is linear (affine) when varying only one variable, x k {\displaystyle x_{k}} : f ( x 1 , x 2 , . . . , x k , . . . , x n ) = a x k + b {\displaystyle f(x_{1},x_{2},...,x_{k},...,x_{n})=ax_{k}+b} where a {\displaystyle a} and b {\displaystyle b} do not depend on x k {\displaystyle x_{k}} . Note that b {\displaystyle b} is generally not zero, so f {\displaystyle f} is linear in the "shaped like a line" sense, but not in the "directly proportional" sense of a [multilinear map](/source/Multilinear_map).

All repeated second [partial derivatives](/source/Partial_derivative) are zero: ∂ 2 f ∂ x k 2 = 0 {\displaystyle {\frac {\partial ^{2}f}{\partial x_{k}^{2}}}=0} In other words, its [Hessian matrix](/source/Hessian_matrix) is a symmetric [hollow matrix](/source/Hollow_matrix#Diagonal_entries_all_zero).

In particular, the [Laplacian](/source/Laplace_operator) ∇ 2 f = 0 {\displaystyle \nabla ^{2}f=0} , so f {\displaystyle f} is a [harmonic function](/source/Harmonic_function). This implies f {\displaystyle f} has [maxima and minima](/source/Maxima_and_minima) only on the boundary of the [domain](/source/Domain_of_a_function).

More generally, every restriction of f {\displaystyle f} to a subset of its coordinates is also multilinear, so ∇ 2 f = 0 {\displaystyle \nabla ^{2}f=0} still holds when one or more variables are fixed. In other words, f {\displaystyle f} is harmonic on every "slice" of the domain along coordinate axes.

### On a rectangular domain

When the domain is [rectangular in the coordinate axes](/source/Hyperrectangle) (e.g. a [hypercube](/source/Hypercube)), f {\displaystyle f} will have maxima and minima only on the [vertices](/source/Vertex_(geometry)) of the domain, i.e. the finite set of 2 n {\displaystyle 2^{n}} points with minimal and maximal coordinate values. The value of the function on these points completely determines the function, since the value on the edges of the boundary can be found by [linear interpolation](/source/Linear_interpolation), and the value on the rest of the boundary and the interior is fixed by [Laplace's equation](/source/Laplace's_equation), ∇ 2 f = 0 {\displaystyle \nabla ^{2}f=0} .[1]

The value of the polynomial at an arbitrary point can be found by repeated linear interpolation along each coordinate axis. Equivalently, it is a weighted mean of the vertex values, where the weights are the [Lagrange interpolation polynomials](/source/Lagrange_polynomial). These weights also constitute a set of [generalized barycentric coordinates](/source/Generalized_barycentric_coordinates) for the [hyperrectangle](/source/Hyperrectangle). Geometrically, the point divides the domain into 2 n {\displaystyle 2^{n}} smaller hyperrectangles, and the weight of each vertex is the (fractional) volume of the hyperrectangle opposite it.

Algebraically, the multilinear interpolant on the hyperrectangle [ a i , b i ] i = 1 n {\displaystyle [a_{i},b_{i}]_{i=1}^{n}} is: f ( x ) = ∑ v f ( v ) ∏ i | v i = b i x i − a i b i − a i ∏ i | v i = a i b i − x i b i − a i {\displaystyle f(x)=\sum _{v}f(v)\prod _{i|v_{i}=b_{i}}{\frac {x_{i}-a_{i}}{b_{i}-a_{i}}}\prod _{i|v_{i}=a_{i}}{\frac {b_{i}-x_{i}}{b_{i}-a_{i}}}} where the sum is taken over the vertices v {\displaystyle v} . Equivalently, f ( x ) = 1 V ∑ v f ( v ) ∏ i | v i = b i ( x i − a i ) ∏ i | v i = a i ( b i − x i ) {\displaystyle f(x)={\frac {1}{V}}\sum _{v}f(v)\prod _{i|v_{i}=b_{i}}(x_{i}-a_{i})\prod _{i|v_{i}=a_{i}}(b_{i}-x_{i})} where *V* is the volume of the hyperrectangle.

The value at the center is the [arithmetic mean](/source/Arithmetic_mean) of the value at the vertices, which is also the [mean](/source/Mean_of_a_function) over the domain boundary, and the mean over the interior. The components of the [gradient](/source/Gradient) at the center are proportional to the balance of the vertex values along each coordinate axis.

The vertex values and the coefficients of the polynomial are related by a [linear transformation](/source/Linear_transformation) (specifically, a [Möbius transform](/source/M%C3%B6bius_transform) if the domain is the unit hypercube { 0 , 1 } n {\displaystyle \{0,1\}^{n}} , and a [Walsh-Hadamard-Fourier transform](/source/Walsh-Hadamard_Transform) if the domain is the symmetric hypercube { − 1 , 1 } n {\displaystyle \{-1,1\}^{n}} ).

## Applications

Multilinear polynomials are the [interpolants](/source/Interpolant) of *multilinear* or *n-linear* interpolation on a rectangular grid, a generalization of [linear interpolation](/source/Linear_interpolation), [bilinear interpolation](/source/Bilinear_interpolation) and [trilinear interpolation](/source/Trilinear_interpolation) to an arbitrary number of variables. This is a specific form of [multivariate interpolation](/source/Multivariate_interpolation), not to be confused with *piecewise* linear interpolation. The resulting polynomial is *not* a linear function of the coordinates (its degree can be higher than 1), but it is a linear function of the fitted data values.

The [determinant](/source/Determinant), [permanent](/source/Permanent_(mathematics)) and other [immanants](/source/Immanant) of a matrix are [homogeneous](/source/Homogeneous_polynomial) multilinear polynomials in the elements of the matrix (and also [multilinear forms](/source/Multilinear_form) in the rows or columns).

The multilinear polynomials in n {\displaystyle n} variables form a 2 n {\displaystyle 2^{n}} -dimensional [vector space](/source/Vector_space), which is also the [basis](/source/Basis_(linear_algebra)) used in the [Fourier analysis of (pseudo-)Boolean functions](/source/Analysis_of_Boolean_functions). Every ([pseudo-](/source/Pseudo-Boolean_function))[Boolean function](/source/Boolean_function) can be [uniquely](/source/One_to_one_correspondence) expressed as a multilinear polynomial (up to a choice of domain and [codomain](/source/Codomain)).

Multilinear polynomials are important in the study of [polynomial identity testing](/source/Polynomial_identity_testing).[2]

## See also

- [Bilinear](/source/Bilinear_interpolation) and [trilinear interpolation](/source/Trilinear_interpolation), using multivariate polynomials with two or three variables

- [Zhegalkin polynomial](/source/Zhegalkin_polynomial), a multilinear polynomial over F 2 {\displaystyle \mathbb {F} _{2}}

- [Multilinear form](/source/Multilinear_form) and [multilinear map](/source/Multilinear_map), multilinear functions that are strictly linear (not affine) in each variable

- [Linear form](/source/Linear_form), a multivariate linear function

- [Harmonic polynomial](/source/Harmonic_polynomial)

## References

1. ^ [***a***](#cite_ref-:0_1-0) [***b***](#cite_ref-:0_1-1) Laneve, Cosimo; Lascu, Tudor A.; Sordoni, Vania (2010-10-01). ["The Interval Analysis of Multilinear Expressions"](https://doi.org/10.1016%2Fj.entcs.2010.09.017). *Electronic Notes in Theoretical Computer Science*. **267** (2): 43–53. [doi](/source/Doi_(identifier)):[10.1016/j.entcs.2010.09.017](https://doi.org/10.1016%2Fj.entcs.2010.09.017). [ISSN](/source/ISSN_(identifier)) [1571-0661](https://search.worldcat.org/issn/1571-0661).

1. **[^](#cite_ref-2)** A. Giambruno, Mikhail Zaicev. *Polynomial Identities and Asymptotic Methods.* AMS Bookstore, 2005 [ISBN](/source/ISBN_(identifier)) [978-0-8218-3829-7](https://en.wikipedia.org/wiki/Special:BookSources/978-0-8218-3829-7). Section 1.3.

---
Adapted from the Wikipedia article [Multilinear polynomial](https://en.wikipedia.org/wiki/Multilinear_polynomial) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Multilinear_polynomial?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.