Affine Maps

Linear Interpolation

Barycentric Coordinates

Symmetric Functions

Blossoming Principle

LaGrange Polynomials

Affine Maps --

An affine map F on a vector space V is just a linear transformation followed by a translation. F(x) = f x + v, where x is a member of V, f is a linear transformation on V and v is a fixed vector in V.
Special Cases:

  • v = 0: F is just a linear transformation
  • A = I: F is just a translation by a vector v

Linear Interpolation --

A Simple Example: We want to interpolate a line passing through two distinct points a and b in R3. Naturally we set x = x(t) = (1-t)a + tb; t is a member of R1.
Note:

  1. The coefficients (1-t) and t sum up to 1.
  2. If we want to get just the line segment between a and b, then we need to add a constraint 0 < t < 1. (Check: x(0) = a; x(1) = b).
  3. We can write x(t) in the following form: x(t) = a + (-t)a + tb. i.e. x(t) as a linear combination of (-t)a + tb followed by a translation a. Now notice that in the linear combination the coefficients of a and b sum up to 0.
  4. If a, b lie on R1 and a=0, b=1, then x(t) = (1-t)*0 + t*1 = t.

Thus a linear interpolation of a line is just an affine map x from R1 to a line in R3.

Now we are going to interpolate a plane P passing through four points x0, x1, x2, x3 which are in R3. Following the same idea as in the previous example, we form X = l0x0 + l1x1 + l2x2 + l3x3 with l0, l1, l2, l3 members of R1 and l0 + l1 + l2 + l3 = 1.
Note:

  1. If we want to get just the shaded quadrilateral, we require li > 0, i=1,2,3.
  2. If we are just given the plane P, then we need to choose points. We only need to choose three points {x0, x1, x2} to determine P. (This is the concept of an affine linearly independent set of points).
  3. If X = l0x0 + l1x1 + l2x2 with l0 + l1 + l2 = 1, then we can write X = x0 + l1(x1-x0) + l2(x2-x0). Thus X is a linear transformation followed by a translation x0.
Thus a linear interpolation of P is just an affine map X : R2 --> R3
X( l1, l2 ) = x0 + l1(x1-x0) + l2(x2-x0) = l0x0 + l1x1 + l2x2 with l0 + l1 + l2 = 1

Let P be a k-dimensional affine subspace generated by {x0, x1, ..., xk} in vector space V. A linear interpolation of P is a map X : Rk --> Rk+1 given by x(l) = x0 + l1 (x1-x0) + ... + lk (xk-x0) = l0x0 + l1x1 + ... + lkxk

Barycentric Coordinates --

The concept of barycentric coordinates is fundamental to the understanding of the material to follow.
Definitions:

  1. Let V be a vector space. Let {x0, x1, ..., xk} be k points in V. Let P be an affine subspace that passes through x0, x1, ..., xk. We call

    an affine (barycentric) combination of the points {x0, x1, ..., xk}. If {x0, x1, ..., xk} are affinely linearly independent then {l0, l1, ..., lk} are called barycentric coordinates of x with respect to the points {x0, x1, ..., xk}.
  2. When (l0, l1, ..., lk) is a fixed set of numbers, then is called a barycenter of the weighted points (xi, li), i=0, 1, 2, ..., k.
  3. If in addition, we require li > 0, i=0, 1, 2, ..., k, then we call (1) a convex combination. In this case, the set is called a convex hull of {x0, x1, ..., xk}.
  4. Moreover, if {x1-x0, ..., xk-x0} is a set of affinely linearly independent points and li > 0, i=0, 1, 2, ..., k, then the set is called a k-dimensional simplex spanned by {x0, x1, ..., xk}

An important property of an affine map: Recall that an affine map is just a linear transformation followed by a translation and is given by Fx = f x + v. An affine map leaves barycentric combinations invariant, i.e. if F is an affine map and

Symmetric Functions --

An arbitrary function f, in n variables x1, ..., xn, is called symmetric if for every permutation p we have

f(xp(1), ..., xp(n)) = f(x1, ..., xn)

where {p(1), ..., p(n)} is a permutation of {1, ..., n}. Given n variables x1, ..., xn, for each k, 0 < k < n, we define the k-th elementary symmetric function sk(x1, ..., xn), for short, sk, as follows:

s0 = 1

s1 = x1 + x2 + ... + xn

s2 = x1x2 + x1x3 + x1x4 + ... + x1xn + x2x3 + ... xn-1xn

sn = x1x2x3 ... xn

Note: s(x, x, x, ..., x) = ( n
k 		) xk

Blossoming Principle --

Given any polynomial F : R --> Rd of degree n, there exists a uniquely defined symmetric n-affine mapping f : Rn --> R with f(t, ..., t) = F(t)

The function f is called the blossom or polar form of F. To give an example, the polynomial F(t) = a0 + a1t + a2t2 + a3t3 corresponds to the symmetric 3-affine function

f(t1, t2, t3) = a0 + a1
3 		(t1+t2+t3) + a2
3 		(t1t2 + t1t3 + t2t3) + a3t1t2t3

In general, F(t) = a0 + a1t + a2t2 + ... antn

To obtain the blossom of F, we replace ti by si(t1, ..., tn)
( n
i 		)
, i = 1, ..., n.

where si(t1, ..., tn) are elementary polynomials.

LaGrange polynomials --

Definition: The Lagrange polynomials of degree n are defined by

Lni(t)= Pnj=0, j!=i(t-tj)
Pnj=0, j!=i(ti-tj) 		, i = 0, 1, ..., n

Remark: Here is an easy way to remember them: in order to find the Lagrange polynomial L32(t), we simply write all possible terms in the product and delete (t-t2) to get the numerator. Then we evalute the obtained product at t2 to get the denominator.

L32(t)= (t-t0) (t-t1) (t-t3)
(t2-t0) (t2-t1) (t2-t3)

Propositions of Lagrange Polynomials

  1. The Lagrange polynomials are cardinal i.e. they satisfy Lni(tj) = dij
  2. The set of Lagrange polynomials of degree n form a basis for the vector space of all polynomials of degree < n. Thus any polynomial p(t) of degree n can be written as
    p(t)= n
    S
    i=0     		piLni(t)
  3. n
    S
    i=0     		Lni(t)=1