### General Conditions

This section summarizes and extends the above derivations in a more formal manner (following portions of chapter 4 of ). In particular, we establish that the sum of projections of onto vectors will give back the original vector whenever the set is an*orthogonal basis*for .

**Definition:**A set of vectors is said to form a

*vector space*if, given any two members and from the set, the vectors and are also in the set, where is any scalar.

**Definition:**The set of all -dimensional complex vectors is denoted . That is, consists of all vectors defined as a list of complex numbers .

**Theorem:**is a

*vector space*under elementwise addition and multiplication by complex scalars.

*Proof:*This is a special case of the following more general theorem.

**Theorem:**Let be an integer greater than 0. Then the set of all linear combinations of vectors from forms a vector space under elementwise addition and multiplication by complex scalars.

*Proof:*Let the original set of vectors be denoted . Form

**Corollary:**The set of all linear combinations of

*real*vectors , using real scalars , form a vector space.

**Definition:**The set of all linear combinations of a set of

*complex*vectors from , using complex scalars, is called a

*complex vector space*of dimension .

**Definition:**The set of all linear combinations of a set of

*real*vectors from , using real scalars, is called a

*real vector space*of dimension .

**Definition:**If a vector space consists of the set of all linear combinations of a finite set of vectors , then those vectors are said to

*span*the space.

**Example:**The

*coordinate vectors*in span since every vector can be expressed as a linear combination of the coordinate vectors as

**Definition:**The vector space spanned by a set of vectors from is called an -dimensional

*subspace*of .

**Definition:**A vector is said to be

*linearly dependent*on a set of vectors , , if can be expressed as a linear combination of those vectors. Thus, is linearly dependent on if there exist scalars such that . Note that the zero vector is linearly dependent on every collection of vectors.

**Theorem:**(i) If span a vector space, and if one of them, say , is linearly dependent on the others, then the same vector space is spanned by the set obtained by omitting from the original set. (ii) If span a vector space, we can always select from these a linearly independent set that spans the same space.

*Proof:*Any in the space can be represented as a linear combination of the vectors . By expressing as a linear combination of the other vectors in the set, the linear combination for becomes a linear combination of vectors other than . Thus, can be eliminated from the set, proving (i). To prove (ii), we can define a procedure for forming the required subset of the original vectors: First, assign to the set. Next, check to see if and are linearly dependent. If so (

*i.e.*, is a scalar times ), then discard ; otherwise assign it also to the new set. Next, check to see if is linearly dependent on the vectors in the new set. If it is (

*i.e.*, is some linear combination of and ) then discard it; otherwise assign it also to the new set. When this procedure terminates after processing , the new set will contain only linearly independent vectors which span the original space.

**Definition:**A set of linearly independent vectors which spans a vector space is called a

*basis*for that vector space.

**Definition:**The set of coordinate vectors in is called the

*natural basis*for , where the th basis vector is

**Theorem:**The linear combination expressing a vector in terms of basis vectors for a vector space is

*unique*.

*Proof:*Suppose a vector can be expressed in two different ways as a linear combination of basis vectors :

*rotating*all vectors in by the same angle. In this way, an infinite number of basis sets can be generated. As we will soon show, the DFT can be viewed as a

*change of coordinates*from coordinates relative to the

*natural basis*in , , to coordinates relative to the

*sinusoidal basis*for , , where . The sinusoidal basis set for consists of length sampled complex sinusoids at frequencies . Any scaling of these vectors in by complex scale factors could also be chosen as the sinusoidal basis (

*i.e.*, any nonzero amplitude and any phase will do). However, for simplicity, we will only use unit-amplitude, zero-phase complex sinusoids as the Fourier ``frequency-domain'' basis set. To summarize this paragraph, the time-domain samples of a signal are its coordinates relative to the natural basis for , while its spectral coefficients are the coordinates of the signal relative to the sinusoidal basis for .

**Theorem:**Any two bases of a vector space contain the same number of vectors.

*Proof:*Left as an exercise (or see [47]).

**Definition:**The number of vectors in a basis for a particular space is called the

*dimension*of the space. If the dimension is , the space is said to be an

*dimensional space*, or

*-space*. In this book, we will only consider finite-dimensional vector spaces in any detail. However, the discrete-time Fourier transform (DTFT) and Fourier transform (FT) both require infinite-dimensional basis sets, because there is an infinite number of points in both the time and frequency domains. (See Appendix B for details regarding the FT and DTFT.)

**Next Section:**

Signal/Vector Reconstruction from Projections

**Previous Section:**

Projection onto Non-Orthogonal Vectors