Apprentice Linear Algebra, 6th day, 07/13/05

REU 2005

Instructor: László Babai Scribe: Niles Johnson

6 Real Euclidean Spaces

Definition 6.1. If V is a real vector space, an inner product on V is:

(∀a, b ∈ V)(a · b ∈ ℝ)

(∀λ ∈ ℝ)(∀a, b ∈ ℝ)((λa)b = λ(a · b))
(∀a, b ∈ V)(a · b = b · a)
(∀a, b, c ∈ V)(a · (b + c) = a · b + a · c)
(∀a ∈ V s.t. a ≠ 0)(a · a > 0)

Note: We will frequently omit the · from a · b for convenience. Definition 6.2. A real Euclidean space is a real vector space with an inner product. Exercise 6.3. Show that if V is a real Euclidean space and a ∈ V, then a · 0 = 0. Example 6.4. In ℝ^{2} and ℝ^{3}, a · b = |a||b| cos(θ), where θ is the angle between the vectors a and b, is an inner product. Note that distributivity (the fourth property listed in 6.1) in this example is highly nontrivial. Example 6.5. The standard dot product is an inner product on ℝ^{n}.

Example 6.6. A density function, μ : ℝ → ℝ, is function such that (∀x ∈ ℝ)(μ(x) ≥ 0)

∫_{−∞}^{+∞} μ(x)dx = 1
(∀k ∈ N) (∫_{−∞}^{+∞} x^{2k}μ(x)dx < ∞) .

Given a density function, μ, we can define an inner product on ℝ[x] by

f · g = ∫_{−∞}^{+∞} f(x)g(x)μ(x)dx.

• Hermite’s density function is \frac{1}{\sqrt{2π}} e^{−x^{2}/2}.

• Chebychev’s first density function is \frac{1}{π} \frac{1}{\sqrt{1−x^{2}}} .

• Chebychev’s second density function is \frac{1}{\sqrt{π}} \sqrt{1 − x^{2}}.

In what follows, we let V be a real Euclidean space. Definition 6.7. For a ∈ V, the norm of a is

||a|| = \sqrt{aa}.

Using the norm, we can define a distance on V. Definition 6.8. For two vectors a, b ∈ V, the distance between a and b is

dist(a, b) = ||(b − a)||.

Definition 6.9. Two vectors, a, b ∈ V, are called orthogonal, written a ⊥ b, if a · b = 0.

Definition 6.10. A set of vectors, {a_{i}} ⊂ V, is called an orthogonal system of vectors if the a_{i} are pairwise orthogonal; i.e.,

(∀i, j)(a_{i} ⊥ a_{j}).

Exercise 6.11. Prove that an orthogonal system of vectors is linearly independent.

Definition 6.12. An orthogonal family of polynomials with respect to μ is an orthogonal system in ℝ[x] with inner product induced by the density function μ.

Exercise 6.13. In ℝ[x], let f_{0}, f_{1}, f_{2}, … be an orthogonal family of polynomials with respect to a density function μ such that deg(f_{i}) = i. Show that the f_{i} form a basis for ℝ[x]. Show furthermore that, for any density function, there is a unique such family.

Exercise 6.14. * Show that, in the exercise above, all the roots of the f_{i} are real.

Example 6.15. The Hermite polynomials, H_{n}, are orthogonal with respect to the Hermite density function. The Chebyshev polynomials T_{n} are orthogonal with respect to the first Chebyshev density and U_{n} are orthogonal with respect to the second Chebyshev density.

The T_{n} and U_{n} are defined as functions of cos;

T_{0} = U_{0} = 1

T_{n}(cos θ) = cos nθ

U_{n}(cos θ) = \frac{sin((n + 1)θ)}{sin θ}.

Using the identity cos(2θ) = 2 cos^{2} θ − 1 we have

T_{2}(cos θ) = cos(2θ) = 2 cos^{2} θ − 1.

So as a function of x

T_{2}(x) = 2x^{2} − 1.

Similarly, the identity cos(3θ) = 4 cos^{3} θ − 3 cos θ yields

T_{3}(x) = 4x^{3} − 3x.

Likewise, the identities

sin(2θ) = 2 sin θ cos θ

sin(3θ) = 3 cos^{2} θ sin θ − sin^{3} θ = sin θ(4 cos^{2} θ − 1)

sin(4θ) = 4 cos^{3} θ sin θ − 4 cos θ sin^{3} θ = sin θ(8 cos^{3} θ − 4 cos θ

yield

U_{1}(x) = 2x

U_{2}(x) = 4x^{2} − 1

U_{3}(x) = 8x^{3} − 4x

Exercise 6.16. Verify that these families are orthogonal with respect to the respective density functions.

6.1 Orthogonal Transformations

We now return to an arbitrary real Euclidean space, V.

Exercise 6.17. Show that any finite dimensional real Euclidean space has an orthonormal basis

If e = (e_{1}, …, e_{n}) is a basis for V and x ∈ V, recall then the matrix of x with respect to e is written [x]_{e}.

If e is an orthonormal basis for V, then the inner product on V is related to the standard dot product in ℝ^{n} via the basis e.

Theorem 6.18. If e is an orthonormal basis for V and x, y ∈ ℝ, then

x · y = [x]_{e}^{T} [y]_{e}

where the left hand inner product is that of V and the right hand inner product is the dot product in ℝ^{n}.

Definition 6.19. An orthogonal transformation is a distance-preserving map φ : V → V. That is,

(∀a, b ∈ V)(dist(φ(a), φ(b)) = dist(a, b)).

Exercise 6.20. Check that any map φ : V → V is an orthogonal transformation iff φ is norm-preserving; i.e.,

(∀a ∈ V)(||φ(a)|| = ||a||.

Claim 6.21. Any orthogonal transformation φ : V → V preserves inner products.

Proof: For any x, y ∈ V we have

φ(x + y) · φ(x + y) = ||φ(x + y)||^{2} = ||x + y||^{2} = (x + y) · (x + y)

since φ preserves norms.

But now using linearity of φ and distributivity of the inner product allows us to expand each side of the equation above and gives

||φ(x)||^{2} + ||φ(y)||^{2} + 2φ(x)φ(y) = ||x||^{2} + ||y||^{2} + 2xy.

Using again the fact that φ is norm-preserving and canceling like terms yields our desired result,

φ(x)φ(y) = xy.

6.1.1 Matrix of an Orthogonal Transformation

An orthonormal basis allows us to compute the inner product on V by using the standard dot product. We will see now that an orthonormal basis can also help us understand orthogonal transformations on V.

Theorem 6.22. Given an orthonormal basis e = (e_{1}, …, e_{n}) for V and a linear transformation φ : V → V, φ is an orthogonal transformation iff [φ]_{e}^{T} [φ]_{e} = I.

Proof: Note: throughout we will drop e from our notation since the basis e will remain fixed.

Recall than if A and B are matrices and Ax = Bx for all x ∈ V, then A = B. Now if φ is orthogonal, then for all x, y ∈ V we have

φ(x)φ(y) = xy.

So, in matrix form,

[φ(x)]^{T} [φ(y)] = [x]^{T} [y].

Recalling that [φ(x)] = [φ][x] and (AB)^{T} = B^{T} A^{T} allows us to simplify the above to

[x]^{T} [φ]^{T} [φ][y] = [x]^{T} I[y]

and now since the equation above holds for all x and y, we use the first fact above (twice) to conclude that

[φ]^{T} [φ] = I.

Exercise 6.23. The proof given is one implication stated in the theorem. Prove the other. Exercise 6.24. Prove that for matrices A and B (AB)^{T} = B^{T} A^{T}.

We now use the result of this theorem as a definition for matrices. Definition 6.25. A matrix A ∈ M_{n}(ℝ) is an orthogonal matrix if

A^{T} A = I

Note that this is the same as saying that the columns of A form an orthonormal system. Exercise 6.26. MAGIC #3: Prove that if the columns of A form an orthonormal system, so do the rows.

Hint: By definition A^{T} is a left inverse for A. By MAGIC #2 a right inverse for A exists. Show that the two must be equal. Corollary 6.27. The matrix A is orthogonal iff A is invertible and A^{T} = A^{−1}. Claim 6.28. If A is orthogonal, det(A) = ±1. Proof:

1 = det(I) = det(A^{T} A) = det(A) det(A^{T}) = (det(A))^{2}.

Exercise 6.29. Show that matrices of the form

[ \begin{matrix}cos α & − sin α \\ sin α & cos α \end{matrix} ] and [ \begin{matrix}cos 2α & sin 2α \\ sin 2α & − cos 2α \end{matrix} ]

are the only 2 × 2 orthogonal matrices.

Hint: Recall that the eigenvalues of the first matrix are cos α ± i sin α; numbers of this form have unit norm. What are the eigenvalues of the second matrix? Answer this question without calculation. Exercise 6.30. If λ ∈ ℂ is an eigenvalue of an orthogonal matrix, then |λ| = 1. Corollary 6.31. If A is an orthogonal n × n matrix, then | tr(A)| ≤ n.

Hint: tr(A) = ∑_{i=1}^{n} λ_{i}, where the λ_{i} are the eigenvalues of A.

Now let A be any matrix, and let a_{1}, …, a_{n} be the rows of A, so

A = [ a_{1} ; ⋮ ; a_{n} ]

Exercise 6.32. (Hadamard’s inequality) Show that for any matrix A

| det(A)| ≤ Π||a_{i}||

and furthermore equality holds iff either one of the a_{i} is zero or the a_{i} are pairwise orthogonal. Hint: Recall that det(A) is the volume of the parallelepiped spanned by the rows of A.

Exercise 6.33. Prove the Pythagorean theorem in n-dimensional real Euclidean space: for orthogonal vectors a_{1}, …, a_{k}, || ∑ a_{i}||^{2} = ∑ ||a_{i}||^{2}.