In Computer Science, a projection function is one of the basic building blocks of primitive recursive functions. Given a k-dimensional array, it returns the ith element, i.e., pik: Nk→N where p(x1 ,..., xk) = xi. This is heavily used due to the way in which composition is defined for primitive recursive functions- to obtain the effect of (g o f), i.e., g(f(x)) it is necessary to use projection to extract the single argument,x- g=Cn[f,p11]. In effect the projection reduces k-dimensional space into one dimensional space.
In Linear Algebra, a projection is a linear map on a vector space V, π : V→V, which satisfies a further constraint: π2=π; that is, ∀ v ∈ V, π(π(v)) = π(v). It follows that any higher powers of π are also equivalent to π, by repeated application of the definition of a projection. The power notation arises from the fact that composition of linear maps is equivalent to multiplication of corresponding matrices- if a matrix P represents a projection π, the product PP = P2 represents π o π = π, so powers of P are simply P itself.
Two fairly obvious projections exist: the zero map and the identity map. This makes intuitive sense, as 02=0 and 12=1. In the context of maps, repeated application of the zero map is redundant once it has been applied once, and the identity map never changes the value operated on and hence may also be applied an arbitrary number of times to no effect. It turns out that all projections can be thought of as a particular combination of these two maps:
Theorem: For a vector space V and a linear map α:V→V ; α is a projection iff there are subspaces U,W of V such that
- V= U ⊕ W
- α: u+w → u ∀u∈U, ∀w∈W.
Two proofs give very different insights into how this works. The first is self-contained, appealing only to the properties given or requested; whilst the second shows how a more general and hence powerful result of linear algebra, the primary decomposition theorem, can be applied to obtain an even more elegant proof.
Note first that the projections we identified earlier, the zero and identity maps, are rather degenerate cases of this theorem. For the zero map, W is V, whilst the other subspace is the trivial set {0} - Note that whilst this means that U and W have a common element, the zero vector, this is permitted by the definition of direct sum- there may be no other common vector, however. Thus any element of V is an element of W (itself) plus the zero vector from U, and gets mapped to that element of U; hence zero is yielded in every case. For the identity map, we take U to be the vector space V, and let W be {0}. Now every vector is mapped to itself (the thing in U). Thus this suggests a method of construction for a general projection.
Proof 1, forward implication
Suppose we have a linear map α: V→V such that α2=α. Take candidates for U and W as follows: U = Im α , W = Ker α .
We claim that V = U⊕W as desired.
Let v be an arbitrary element from V. Then obviously v= v + α(v) - α(v). Rearranging gives v= α(v) + (v-α(v)).
By definition of image, α(v) ∈ Im α = U. So we need to show that (v-α(v)) ∈ Ker α = W to obtain V = U+W.
The definition of Ker α is that it contains all elements of V such that when α is applied to them, the zero vector is obtained. So take α of (v-α(v)): = α(=v) - α(α(v)). Since α is a projection, this becomes α(v) - α(v) = 0 as desired.
We have V = U + W. We seek a direct sum; meaning that the expression of a v from V as u+w from U,W should be unique. This is equivalent to U∩W = {0}.
So consider x∈U∩W. Then x∈U=Im α, so there is a y∈V such that x=α(y). Further, x∈W=Ker α so α(x)=0. Yet α(x)=α(α(y)) = α(y) by property of projection = x. So x∈U∩W implies x=0: so U∩W ⊆ {0}. 0 is in U and W, so 0 is in U∩W, giving {0} ⊆ U∩W. So U∩W = {0}.
Hence V = U⊕W . We desired also that if v = u+w, then α(v)= u. However, α(v) = α(u+w) which by linearity gives α(v) = α(u) + α(w). Since u∈U=Im α, u=α(u') for some u' and by property of projection α(u) is therefore u, whilst w∈W=Ker α so by defintion α(w)=0. Hence α(v) = u + 0 = u . We are done.
Proof 1, backward implication
Suppose that V decomposes as a direct sum; i.e., if v∈V then v=u+w for unique u∈U, w∈W. We define α(v) = u, which by uniqueness is a well-defined function. It remains to show linearity and that α is a projection.
Let v=u+w and v'=u'+w' be elements of V. Now for scalars λ,μ from the field,
α(λv + μv') = α(λ(u+w) + μ(u'+w'))
=α( (λu + μu') + (λv + μv'))
=λu + μu' , Since U is a vector space over the field of V, λu + μu' ∈ U. So we can apply the definition of α
=λα(u) + μα(u')
So the definition of linearity is met. As α(α(v)) = α(u) = u = α(v), we also have that this map is a projection. We are done.
Introducing some more technology we can simplify this considerably (although some of the insight into the nuts and bolts of the process is lost.)
Proof 2
We have already discussed that the decomposition works for the identity and zero maps. So consider a projection π:V→V which is a projection but neither of these two maps. Then we can write the definition as π2 - π = 0. Hence π satisfies the polynomial p(t) = t2 -t. Since this is a degree two monic polynomial, it follows that the minimal polynomial of π is at most degree two.
Now P(t) = t(t-1). If the minimal polynomial has degree one rather than two, then it must be either m(t)=t or m(t)=(t-1), since any polynomial that is satisfied by a linear map has its minimal polynomial as a factor. But if m(t)=t, we have the zero map, and if m(t)=(t-1), we have the identity map. We assumed that neither of these applied; so the minimal polynomial cannot be of degree one. It is hence of degree two, and in fact must be p(t) = t(t-1) by uniqueness.
Now the primary decomposition theorem applies. mπ(t)=p(t)=q1(t)q2(t) with q(1)=(t-1), q2(t)=(t) coprime. So V = W1⊕W2 where the Wi are π invariant subspaces with minimal polynomial of π|Wi given by qi.
But then q1 indicates that π|W1 is the identity map, whilst q2 indicates that π|W2 is the zero map.
So given v=w1+w2, wi ∈ Wi, π(v) = π(w1 + w2) = π(w1) + π(w2) = id(w1) + zero(w2) = w1 + 0 = w1 . This completes the proof.