Vector spaces are like potato chips. You cannot have only one.W. Kahan

One of the key ideas in linear algebra is that of a *dual
space*. If V is a finite-dimensional real vector space, then
the dual space V^{*} consists of all linear functions from V
into the real numbers. A function from V into the real numbers is
sometimes called a functional on V

, so we also sometimes say
that the dual space is the space of linear functionals on V. If V
is a finite-dimensional inner product space, then there is a natural
map between ordinary vectors and dual vectors: every function f in
the dual space V^{*} may be written as

Dual vectors can be identified with vectors in V, but they are not the same. Usually, we remind ourselves of the difference by writing vectors and dual vectors as columns and rows of coordinates, respectively (if you're a physicist, you write kets and bras; however, I was not exposed to Dirac notation until after my formative years, and tend not to use it except when making puns). The difference between vectors and dual vectors matters as soon as one tries to change coordinate systems, for instance. If you have ever seen the multi-dimensional chain rule, you have seen this distinction: if F is a nonlinear function from V into the reals, then (dF/dx)(x) is actually a dual vector, and so the chain rule looks like

*gradient vector*grad F(x) is the vector in V which identifies dF/dx(x); this vector transforms like

_{x}F(Ax) = A

^{T}grad

_{x}F(x).

What have dual vectors to do with programming? I think that the notion of a dual vector sometimes confuses people because they are unused to the idea of manipulating functions as interesting mathematical objects in their own right. Even for those who find the idea of a dual vector natural often are confused by the idea of contravariant and covariant components in a tensor -- though it's really the same idea. Certainly I found it confusing initially! The same source of confusion applies, I think, when people first learn about functional programming. A function can be a valid object of mathematical and programmatic manipulation: a simple enough statement, but oh! the confusion it causes.

In an attempt to reduce the confusion for at least one or two people,
I have been thinking about how to describe dual vectors in a functional
programming language (or at least in a programming language that allows
a functional style). For this exercise I will use Scheme (a LISP dialect)
and Lua (one of my favorite scripting languages). I start with functions
to compute the dot products of two vectors. In Lua, I would represent
a vector as a table: if `x` is a vector, then `x[i]` is the
ith component of the vector. Using this representation, I can compute
the dot product of two vectors with this function:

-- Dot product of two vectors (Lua version) function dot(x,y) local sum = 0 for i,xi in x do sum = sum + xi*y[i] end return sum end

In Scheme, I represent vectors as lists (we'll ignore Scheme's native
vector type for the moment). To compute the dot product of two vectors,
`x` and `y`, I use the following function:

;; Dot product of two vectors (define (dot x y) (apply + (map * x y)))

It's worth dwelling a moment on the Scheme implementation. The
Scheme code computes dot products in two phases. In the first
phase, the `map` procedure is used to apply the
multiplication operation to every pair of entries from `x`
and `y`. The resulting list of elementwise products is then
summed up in order to get the dot product. Note that there was no
need to explicitly specify a loop or a recursion: all that work was
done by the `map` and `apply` operations.

What if we want the linear functional identified by a particular vector? Because both Scheme and Lua allow functions to be treated as first-class objects, this mapping can be done very naturally. In Lua, we have

-- Produce a dual vector (a linear functional) function dualv(x) return function(y) return dot(x,y) end end

while in Scheme,

;; Produce a dual vector (a linear functional) (define (dual-v x) (lambda (y) (dot x y)))

The idea is the same in either case: the function `dualv`
returns another function. The returned function is never given a
name; in Scheme, such an anonymous function is called a
*lambda* (after Church's lambda calculus, the logical system
upon which LISP and its successors were directly based). In Lua, a
function is usually just called a function, without the
fancy-sounding adjective.

Now, what if we want to go one more step, and define double-dual
vectors? Just as a dual vector is a functional on the original space V,
a double-dual vector is a functional on the dual space V^{*}.
In a finite dimensional setting (and in many infinite-dimensional cases),
all the elements of the double-dual are identified with elements of the
original space V. A double-dual vector g identified with a vector v
acts on dual vectors by evaluation at v:

-- Produce a function x(f) for "evaluate f at x" function evalat(x) return function(f) return f(x) end end ;; Produce a function x(f) for "evaluate f at x" (define (eval-at x) (lambda (f) (f x)))

Now we've written routines to go from vectors to dual vectors or double dual vectors. Let's see a concrete use for these routines. Suppose we would like to produce a linear operator from its matrix representation. That is, we have a list of rows, and each row is a list; these rows represent linear functionals that map an input vector to some component of an output vector. We can produce a function that multiplies an input argument by the matrix using the following very simple Scheme functions:

;; Produce a function to evaluate a list of functions (define (f-list fs) (lambda (x) (map (eval-at x) fs))) ;; Produce an operator (define (make-linear m) (f-list (map dual-v m)))

The `make-matrix` command first converts each row in the
matrix to a corresponding dual vector, then (using `f-list`)
produces a function that applies each dual vector in turn to an
input argument, returning the result in another list. Note how
`f-list` takes advantage of the `eval-at` function.
The `map` routine applies one function to many arguments; by
thinking of `x` not as a vector, but as a function that acts
on functions (a double-dual vector when all is linear), we can adapt
`map` to apply many functions to a single argument, which is
what we want.

What about a Lua implementation? Idiomatic code in different
languages will naturally follow different patterns; in this case,
the lack of a `map` function in Lua (and the naturalness of
writing a `for` loop), suggested the following routine to
generate a linear function:

-- Produce an operator function makelinear(m) return function(x) local mx = {} for i,mi in m do mx[i] = dot(mi,x) end return mx end end

**Currently drinking:**Rooibos