# Solving polynomial problems with matrices and vectors

When solving equations involving polynomials, I've seen a technique used where you use a vector to represent the coefficients of the various powers of $x$ of a polynomial.

One such technique is the answer to this question, which is about least squares fitting: Creating a function incrementally

Since matrices are linear, how is it possible for this "trick" to work for polynomials which are of any number of degree?

Is it also possible for this "trick" to work with non linear functions of multiple variables?

If you have some finite dimensional subspace of functions and a problem that is "linear" with regarding to the vector space structure, you can always translate it into a problem on matrices and vectors. Let me give an example:

Say you want to find a polynomial $p(X) \in \mathbb{R}[X]$ of degree two that satisfies $$p(0) = 1, p(1) = 2, p(2) = 3.$$ The relevant subspace here is $V = \mathbb{R}_{\leq 2}[x]$ (the subspace of all polynomials of degree less than or equal to $2$) and we have a map $T \colon V \rightarrow \mathbb{R}^3$ which is given by $T(p) = (p(0),p(1),p(2))$. We can then see that our problem is the same as finding $p \in V$ such that $T(p) = (1,2,3)$. Now, the functions in $V$ are non-linear but $V,\mathbb{R}^3$ are vector spaces with the obvious operations and $T$ is a linear map. Thus, by choosing a basis (say $\mathcal{B} = (1,x,x^2)$) we can transform our problem into a problem about vectors and matrices. In this case, we can write $p = a_0 \cdot 1 + a_1 \cdot x + a_2 \cdot x^2$ and try and solve the system $p(0) = 1, p(1) = 2, p(2) = 3$ for the coefficients $a_0,a_1,a_2$. This can be generalized for polynomials of arbitrary (but bounded degree) and solved explicitly resulting in a formula for interpolation polynomials. You can also consider various other constraints (given derivatives, given integrals over some interval, etc), as long as they respect the linear structure.

Nothing prevents you repeating the same thing with non-linear functions of several variables. For example, we might want to find a function

$$f(x,y) = a + b \sin(x) \sin(y) + c \sin(2x) \sin(y)$$

where $a,b,c \in \mathbb{R}$ that satisfies some constrains such as

$$f(0,0) = 2,\\ \int_{[0,2\pi]^2} f(x,y) \, dx dy = 3, \\ \frac{\partial f}{\partial x}|_{(0,0)} = 2$$

and again, this can be translated to linear equations on the coefficients $a,b,c$.

The trick is that while polynomials $\sum_n a_n x^n$ are not linear in their argument $x$, they are certainly linear in the coefficients $a_n$, no matter how large the degree. Therefore, if a fixed (grid of) $x$ is considered, fitting the coefficients $a_n$ can be expressed as a linear problem.

The same trick can be applied to other nonlinear functions, provided you can linearize them with respect to the parameters of interest. Many nonlinear functions can be well approximated by (e.g. Taylor) polynomials, which brings us back to the above.