Inner Product Spaces

Inner Products over \mathbb{R}

Suppose that V is a real vector space. An inner product (or “dot” product) on V is a map J: V\times V\to \mathbb{R} that satisfies the following properties:

  1. (symmetry) J(u,v) = J(v,u) for all u,v\in V.
  2. (linearity) If v\in V is fixed, then the function u\mapsto J(u,v) is linear in u. In other words, J(au_1+bu_2,v) = aJ(u_1,v)+bJ(u_2,v). Since J is symmetric, we also have J(u,av_1+bv_2)=aJ(u,v_1)+bJ(u,v_2). So J is bilinear.
  3. (positive definiteness) For all nonzero v\in V, we have J(v,v)>0.

The classic example of such an inner product is the Euclidean “dot” product: J((a_1,\ldots, a_n),(b_1,\ldots, b_n))=\sum_{i=1}^{n} a_{i}b_{i} or J((a_1,\ldots, a_n),(b_1,\ldots, b_n))=(a_1,\ldots,a_n)\cdot (b_1,\ldots, b_n).

We sometimes write J(u,v) = \langle u,v\rangle.

A vector space V over \mathbb{R} together with an inner product is called a (real) inner product space.

Note that inner product spaces make sense even for infinite-dimensional vector spaces, but we will focus on the finite-dimensional case.

Geometry in an Inner Product Space

Adding an inner product to a finite-dimensional real vector space introduces geometry into our study of linear algebra. First, an inner product space allows us to measure the size of a vector \|v\| = \sqrt{\langle v,v\rangle} and a distance between vectors: d(u,v) = \sqrt{\langle u-v,u-v\rangle} = \|u-v\|.

This distance measure satisfies the conditions for a “metric”:

  1. d(u,v)\ge 0 and d(u,v)=0 if and only if u=v.
  2. d(u,v)=d(v,u).
  3. d(u,w)\le d(u,v)+d(v,w) (the triangle inequality).

Of course, if \langle u,v\rangle is the standard dot product, this distance is the usual distance given by the Pythagorean theorem: d((u_1,\ldots, u_n),(v_1,\ldots, v_n))=\sqrt{\sum_{i=1}^{n} (u_i-v_i)^2} and the points \{v: \|v\|=r\} at constant distance r from 0 form a sphere.

There are, however, many other inner products. To construct them, first observe that if E=\{e_1,\ldots, e_n\} is a basis for V, we can compute \langle \sum a_{i}e_{i},\sum b_{i}e_{i}\rangle as long as we know all of the inner products \langle e_i, e_j \rangle.

In fact, if we let [J]^{E} be the n\times n matrix whose entries are [J]^{E}_{ij} = \langle e_{i},e_{j}\rangle ,

then

\langle \sum a_{i}e_{i},\sum b_{i}e_{i}\rangle = \left[\begin{matrix} a_1 &\ldots& a_n\end{matrix}\right][J]^{E}\left[\begin{matrix} b_1 \\ \vdots \\ b_n\end{matrix}\right].

Using the notation for coordinates in a basis we adopted earlier, we see that \langle a,b\rangle = [a]_{E}^{\top} [J]^{E} [b]_{E}.

Here, if X is an m\times n matrix, then X^{\top}, the “transpose” matrix, is the n\times m matrix with entries X^{\top}_{ij} = X_{ji}.

Remark: A computation shows that (XY)^{\top}=Y^{\top}X^{\top}.

Notice that if X=[J]^{E} is constructed in this way from an inner product, then:

  1. X is symmetric (since \langle e_{i},e_{j}\rangle = \langle e_{j}, e_{i}\rangle)
  2. The rank of X is n. Otherwise, if [b]_{E}\not=0 is in the null space of X, we’d have \langle b,b\rangle = [b]_{E}^{\top}X[b]_{E}=0 which isn’t allowed.
  3. X is positive definite, meaning that [a]_{E}^{\top}X[a]_{E}>0 when [a]_{E}\not=0.
  4. If T=\{t_1,\ldots, t_n\} is a different basis for V, and [I]_{E}^{T} is the change of basis matrix so that [a]_{T}=[I]_{E}^{T}[a]_{E} then [J]^{T} is related to [J]^{E} by [J]^{E} = ([I]_{E}^{T})^{\top}[J]^{T}[I]_{E}^{T}.

The last point follows from the computation: \begin{aligned} J(a,b) &= [a]_{T}^{\top}[J]^{T}[b]_{T} = \left([I]_{E}^{T}[a]_{E}\right)^{\top}[J]^{T}\left([I]_{E}^{T}[b]_{E}\right) \\ &= [a]_{E}^{\top}([I]_{E}^{T})^{\top}[J]^{T}[I]_{E}^{T}[b]_{E}. \end{aligned}

Proposition: If X is any real symmetric n\times n positive definite matrix, then the function J:\mathbb{R}^{n}\times\mathbb{R}^{n} \to \mathbb{R} defined by J(a,b) = a^{\top}Xb is an inner product, and X=[J]^{E} relative to the standard basis of \mathbb{R}^{n}.

The symmetry follows from the fact that J(b,a)=b^{\top}Xa = (b^{\top}Xa)^{\top} = a^{\top}X^{\top}b = a^{\top}Xb=J(a,b).

Linearity follows from properties of matrix multiplication, and the positive definiteness follows from the positive definite property of the matrix.

Proposition: Suppose J is an inner product on V. A choice of basis E for V gives an isomorphism between V and \mathbb{R}^{n}. Using this basis, we can construct the symmetric positive definite matrix X=[J]^{E} whose i,j entry is J(e_{i},e_{j}). Then J(a,b) = [a]_{E}^{\top}[J]^{E}[b]_{E}.

For r>0, the set \{a: J(a,a)=r\} is, in these coordinates, an ellipsoid.

Orthogonality

Let V be an n-dimensional inner product space and let J:V\times V\to \mathbb{R} be the inner product.

Definition: Two vectors a and b in V are orthogonal (relative to J) if J(a,b)=0.

If J is the standard Euclidean inner product on \mathbb{R}^{n}, then to say that a and b are orthogonal is to say they are perpendicular.

Proposition: (The Gram–Schmidt Process) Let V be an inner product space of dimension n with inner product J, and let E=\{e_1,\ldots, e_m\} be a linearly independent subset of V spanning a subspace W. Then there exist vectors U=\{u_1,\ldots, u_m\} such that:

  1. The u_{i} are an orthonormal set, meaning:
    1. they are mutually orthogonal so J(u_{i}, u_{j})=0 if i\not=j.
    2. they have norm 1, so \|u_{i}\|=1 for i=1,\ldots, m.
  2. The span W_{j} of U_{j}=\{u_{1},\ldots, u_{j}\} equals the span of E_{j}=\{e_{1},\ldots, e_{j}\} for j=1,\dots, m.

Notice that:

  1. the statement in part (2) means that the change of basis matrix from U to E is upper triangular:

\begin{aligned} u_{1} &= a_{11}e_{1} \\ u_{2} &= a_{12}e_{1} + a_{22}e_{2} \\ &\;\;\vdots \\ u_{j} &= a_{1j}e_{1}+\cdots+a_{jj}e_{j} \end{aligned}

  1. If E spans V, then the matrix [J]^{U} of J in the U basis is the identity matrix. Another way of saying this is that, in the U basis, the inner product is just the standard dot product: J(a,b) = [a]_{U}\cdot [b]_{U} = \sum_{i=1}^{n} a_{i}b_{i} where a=\sum_{i=1}^{n} a_{i}u_{i} and similarly for b.

Proof of the Proposition: We proceed by induction. First, let u_{1} = \frac{e_1}{\|e_{1}\|}. This establishes the case j=1.

Now suppose we’ve constructed u_1,\ldots, u_{j} so that the span of these vectors is the span of E_{j}, they are mutually orthogonal of norm 1, and the change of basis matrix is triangular. Let v_{j+1} = e_{j+1}-\sum_{i=1}^{j} J(e_{j+1},u_{i})u_{i}.

Now, for k=1,\ldots, j, we compute: J(v_{j+1}, u_{k})=J(e_{j+1},u_{k})-\sum_{i=1}^{j} J(e_{j+1},u_{i})J(u_{i},u_{k}).

Since J(u_{i},u_{k})=0 except when i=k, where it is 1, this simplifies to zero.

Also, the span of \{u_1,\ldots, u_{j},v_{j+1}\} is the same as the span of \{e_1,\ldots, e_{j+1}\}. Moreover, v_{j+1}\not=0, since otherwise e_{j+1} would lie in the span of u_1,\ldots,u_j, which is the span of E_{j}. If we then let u_{j+1}=\frac{v_{j+1}}{\|v_{j+1}\|}, we’ve constructed U as desired and the result follows by induction.

Proposition: Suppose V is an n-dimensional inner product space with inner product J, and u_1,\ldots, u_n is an orthonormal basis for V. Then for any v\in V we have v = \sum_{i=1}^{n} J(v,u_{i})u_{i}.

Proof: A calculation shows that z=v-\sum_{i=1}^{n} J(v,u_{i})u_{i} is orthogonal to every u_i for i=1,\ldots, n, and then by linearity to every linear combination of the u_{i}. Since the u_{i} are a basis for V, this means J(z, h)=0 for all h\in V, and in particular J(z,z)=0. Then z=0 as claimed.

Projection

Let V be an n-dimensional inner product space with inner product J, and let W\subset V be a subspace. The orthogonal complement W^{\perp} of W is the set

W^{\perp}=\{v\in V : J(v,w)=0\text{ for all } w\in W \}

Proposition: Under the above hypotheses:

  1. W^{\perp} is a subspace of V.
  2. The map W\oplus W^{\perp}\to V defined by (x,y)\mapsto x+y is an isomorphism.
  3. (W^{\perp})^{\perp}=W.

Proof: W^{\perp} is a subspace since J(0,w)=0, and if J(w,v_1)=J(w,v_2)=0 for all w\in W, then J(w,av_1+bv_2)=0 by linearity. For part (b), choose an (ordered) basis w_{1},\ldots, w_{m} for W and extend it to a basis for V. Apply Gram–Schmidt to this ordered basis to obtain orthonormal vectors u_1,\ldots, u_{n} where u_1,\ldots, u_m are a basis for W. Then u_{m+1},\ldots, u_{n} all belong to W^{\perp}. Given v\in V, we can write v=\sum_{i=1}^{n} J(v,u_{i})u_{i}=\sum_{i=1}^{m} J(v,u_{i})u_{i} + \sum_{i=m+1}^{n} J(v,u_{i})u_{i}. The first sum on the right belongs to W, and the second to W^{\perp}, so the map W\oplus W^{\perp}\to V is surjective. On the other hand, if x\in W\cap W^{\perp}, we’d have J(x,x)=0 so x=0. Therefore the map is injective and thus an isomorphism. In particular \dim(W)+\dim(W^{\perp}) = n.

For part (c), it’s clear that W\subset (W^{\perp})^{\perp}. On the other hand \dim(W^{\perp})+\dim((W^{\perp})^{\perp})=n so we must have \dim((W^{\perp})^{\perp})=\dim(W) and therefore the two spaces are equal.

Proposition: From the isomorphism W\oplus W^{\perp}\to V we have an inverse map V\to W\oplus W^{\perp} and then a map P_{W}:V\to V with image W and kernel W^{\perp}. This map is called the orthogonal projection of V onto W. Similarly we have the projection P_{W^{\perp}}:V\to V with kernel W and image W^{\perp}. Each of these linear maps is idempotent (meaning that P_W P_W=P_W and P_{W^{\perp}}P_{W^{\perp}}=P_{W^{\perp}}) and, in addition, their sum P_{W}+P_{W^{\perp}} is the identity map.

In the orthonormal basis u_1,\ldots, u_{n} constructed above, if I_{n\times n} is the identity matrix of size n, then the matrix of P_{W} looks like \begin{pmatrix} I_{m\times m} & 0 \\ 0 & 0 \\ \end{pmatrix} and P_{W^{\perp}} looks like: \begin{pmatrix} 0 & 0 \\ 0 & I_{(n-m)\times (n-m)} \\ \end{pmatrix}

Closest Points

Let W be a subspace of the n-dimensional inner product space V. If v\in V, we can consider the “distance to W” as the minimum of \|v-w\| as w ranges over W.

Proposition: The distance from v to W is \|v-P_{W}(v)\|, or equivalently \|P_{W^{\perp}}(v)\|.

To prove this proposition, we first look at the case where W is one-dimensional, and spanned by a vector w. Then W consists of multiples of w, and for fixed v\not\in W, we have \|v-aw\|^2=J(v-aw,v-aw)=J(v,v)-2aJ(v,w)+a^2J(w,w) The minimum of this occurs when 2aJ(w,w)=2J(v,w) or a=\frac{J(v,w)}{J(w,w)}. In other words, the vector from the closest point in W to v is v_{0} = v-\frac{J(v,w)}{J(w,w)}w and the square of the distance from v to W is \|v_{0}\|^2 = J(v,v)-2\frac{J(v,w)^2}{J(w,w)}+\frac{J(v,w)^2}{J(w,w)} = J(v,v)-\frac{J(v,w)^2}{J(w,w)}.

Since J(v_0,w)=0 and v-v_{0}\in W, we have v_{0}=P_{W^{\perp}}(v), which proves the proposition when \dim(W)=1. Moreover, since \|v_{0}\|^2>0, we obtain J(v,v)-\frac{J(v,w)^{2}}{J(w, w)}>0. If instead v\in W, say v=aw, then both sides of the inequality below are equal, and if w=0 both sides are zero.

This is the “Cauchy–Schwarz Inequality.”

Proposition: Let v,w be vectors in a real inner product space V. Then J(v,w)^2\le J(v,v)J(w,w) with equality if and only if v and w are linearly dependent. Taking square roots, this is the same as |J(v,w)|\le\sqrt{J(v,v)J(w,w)} with equality if and only if v and w are linearly dependent.

For the general case of finding the closest point, we can generalize the calculus argument above, or instead use the decomposition V=W\oplus W^{\perp}. Write v = w_{0}+z with w_{0}\in W and z\in W^{\perp}. If w\in W, then w_{0}-w\in W is orthogonal to z, so \langle v-w,v-w\rangle = \langle z,z\rangle + \langle w_{0}-w,w_{0}-w\rangle, which is clearly minimized when w=w_{0}. So w_{0}=P_{W}(v) is the closest point and \|z\|=\|P_{W^{\perp}}(v)\| is the distance from v to W.

Application: Ordinary Least Squares

The “least squares problem” assumes we have a set of measurements (x_{i1},\ldots, x_{ik})_{i=1}^{N} and (y_{i})_{i=1}^{N}. We have a model which leads us to suspect that the y values are related to the x values by a linear relation y=\sum_{j=1}^{k} m_{j}x_{j}+b up to some random error, and we would like to infer the values of the m_{j} and b to obtain the “best” such linear relation.

The least squares approach says that the best choices for the m_{j} and b are the values that minimize the squared error S(m,b)=\sum_{i=1}^{N} \left(y_i-\sum_{j=1}^{k} m_{j}x_{ij}-b\right)^2.

We can use linear algebra to approach this problem. Let Y be the vector in \mathbb{R}^{N} whose entries are the y_{i} and let X be the N\times (k+1) matrix whose i-th row is (x_{i1},\ldots, x_{ik},1).

Notice then that S(m,b) = \|Y-XM\|^2

where M\in \mathbb{R}^{k+1} is the vector with entries m_{1},\ldots, m_{k},b.

So our problem can be interpreted as finding M so that \|Y-XM\|^2 is as small as possible. On the other hand, as M varies, the vector XM varies over the column space of X. So the value S(m,b) is minimized when XM is the point in the column space of X that is closest to Y.

From our work above, this happens when Y-XM is orthogonal to the column space of X. For this it suffices that Y-XM is orthogonal to all the columns of X. In other words, when X^{\top}(Y-XM)=0.

This gives the equation X^{\top}Y-X^{\top}XM=0.

The matrix D=X^{\top}X is a square, (k+1)\times (k+1) matrix. If X has rank k+1, then D is invertible and we obtain the solution to the least squares problem: M = D^{-1}X^{\top}Y.

The “closest point” in the column space of X is the vector XM=XD^{-1}X^{\top}Y which is the projection of Y onto the column space of X.

Projection Operator in General

The argument we made above for the least squares problem gives us a way to construct the projection operator P_{W} when W is a subspace of a real inner product space V of dimension n. Choose a basis E for V and, to simplify the notation, let’s write J (instead of [J]^{E}) for the matrix of the inner product in this basis. Let X be the matrix whose columns are ([w_{i}]_{E})_{i=1}^{k} where the w_1,\ldots, w_k form a basis for W. So W is the column space of X.

If y\in V and Y=[y]_{E} is its coordinate vector, then as in the least squares problem we want to find M so that Y-XM is orthogonal to W, and for this it’s enough that Y-XM is orthogonal to all of the columns of X.

This means X^{\top}J(Y-XM)=0

and as above we get the formula (the matrix X^{\top}JX is invertible because it is the matrix of the inner product restricted to W in the basis w_1,\ldots,w_k, and hence is positive definite) M = (X^{\top}JX)^{-1}X^{\top}JY

and the projection of Y onto W is XM=X(X^{\top}JX)^{-1}X^{\top}JY.

Therefore the matrix [P_{W}]_{E}^{E} of P_{W} is [P_{W}]_{E}^{E} = X(X^{\top}JX)^{-1}X^{\top}J.

Notice that \begin{aligned} [P_{W}]_{E}^{E}[P_{W}]_{E}^{E}&=X(X^{\top}JX)^{-1}X^{\top}JX(X^{\top}JX)^{-1}X^{\top}J \\ &= X(X^{\top}JX)^{-1}X^{\top}J \\ &= [P_{W}]_{E}^{E} \end{aligned}

Complex (Hermitian) Inner Products

Now suppose V is a finite-dimensional complex vector space. A Hermitian inner product on V is a function J:V\times V\to \mathbb{C} that:

  1. Is linear in the first variable and conjugate linear in the second: J(au+bv,w)=aJ(u,w)+bJ(v,w) and J(u,av+bw)=\overline{a}J(u,v)+\overline{b}J(u,w).
  2. Is conjugate symmetric: J(u,v)=\overline{J(v,u)}. (Notice this means that J(u,u) is a real number.)
  3. Is positive definite: J(u,u)\ge 0 with J(u,u)=0 only if u=0.

The key ideas for inner products over \mathbb{R} hold, suitably modified, for Hermitian inner products over \mathbb{C}.

First, let E=\{e_1,\ldots, e_n\} be a basis for V. Define a matrix [J]^{E} where [J]^{E}_{ij} = J(e_{i},e_{j}). Then J(u,v) = [u]_{E}^{\top}[J]^{E}\overline{[v]_{E}} where \overline{[v]_{E}} is the vector whose entries are the conjugates of the entries of [v]_{E}.

This is because J(\sum a_{i}e_{i}, \sum b_{j}e_{j})=\sum a_{i}\overline{b_{j}}J(e_{i},e_{j}).

In addition, the matrix [J]^{E} satisfies the “Hermitian condition”: its transpose is its conjugate: ([J]^{E})^{\top} = \overline{[J]^{E}}

Notice that since J(v,v) is a nonnegative real number we can define \|v\|=\sqrt{J(v,v)} as in the real case.

The Gram–Schmidt process works (suitably modified) in this setting. Let \{v_{1},\ldots, v_{n}\} be a basis for a Hermitian inner product space V. We construct vectors u_{1},\ldots,u_{n} inductively. First let u_{1} = \frac{v_{1}}{\|v_{1}\|}. Then, assuming that u_{1},\ldots, u_{k} are orthonormal, let u_{k+1}' = v_{k+1}-\sum_{i=1}^{k} J(v_{k+1},u_{i})u_{i} and u_{k+1}=\frac{u_{k+1}'}{\|u_{k+1}'\|}.

This gives an orthonormal basis u_{1},\ldots, u_{n} for V such that, for each j, the span of u_{1},\ldots, u_{j} is the same as the span of v_{1},\ldots, v_{j}.