Apprentice Linear Algebra, 5th day, 07/11/05

REU 2005

Instructor: László Babai Scribe: Ben Lee

7 More on Linear Transformations

7.1 Bases and Similarity

Suppose φ : V → V is linear transformation. Recall λ is an eigenvalue if (∃x ∈ V, x ≠ 0)(φx = λx).

To associate a matrix to a linear transformation: φ ↦ [φ], choose e = (e_{1}, …, e_{n}) a basis of V

x ↦ [x]_{e} = (x_{1} ; ⋮ ; x_{n}) the column matrix of coordinates, i.e. x = ∑_{i=1}^{n} x_{i}e_{i}.

Then the matrix [φ]_{e} is [[φe_{1}]_{e} ⋯ [φe_{n}]_{e}].

Example 7.1. ρ_{α} rotation by α in the plane:

ρ_{α}e_{1} = cos αe_{1} + sin αe_{2}
ρ_{α}e_{2} = − sin αe_{1} + cos αe_{2}
[ρ_{α}]_{e} = [\begin{matrix}cos α & − sin α \\ sin α & cos α \end{matrix}] .

Theorem 7.2. If A and B are the matrices associated with the same linear transformation in two bases then A ∼ B (A, B are similar.)

Definition 7.3. A ∼ B if (∃S, S^{−1})(B = S^{−1}AS). S is the matrix of change of basis transformation.

If we have the “old” basis a_{1}, …, a_{n} and “new” basis b_{1}, …, b_{n}, σ : a_{i} ↦ b_{i}, then

S = [σ]_{a} = [σ]_{b} = [[b_{1}]_{a}, …, [b_{n}]_{a}].

If you want to classify all linear transformations, you need to classify matrices up to similarity.

Theorem 7.4. If A ∼ B then f_{A}(x) = f_{B}(x) (f_{A}(x) = det(xI − A) is the characteristic polynomial.)

Proof: First prove that if A ∼ B then det A = det B: B = S^{−1}AS, det B = det S^{−1}AS = det S^{−1}SA = det A since det CD = det C det D.

Question: is xI − A ∼ xI − B? Yes: S^{−1}(xI − A)S = xS^{−1}IS − S^{−1}AS = xI − B. So we are done.

7.2 Diagonalizability and Eigenbases

Definition 7.5. An eigenbasis is a basis consisting of eigenvectors.

If e_{1}, …, e_{n} is an eigenbasis then φe_{i} = λ_{i}e_{i}.

φe_{1} = λ_{1}e_{1} + 0e_{2} + ⋯ + 0e_{n}

[φe_{1}]_{e} = (λ_{1} ; 0 ; ⋮ ; 0)

φe_{2} = 0e_{1} + λ_{2}e_{2} + 0e_{3} + ⋯ + 0e_{n}

[φe_{2}]_{e} = ( 0 ; λ_{2} ; ⋮ ; 0) et cetera, so

[φ]_{e} = (\begin{matrix}λ_{1} & & & & 0 \\ & . & . & . \\ 0 & & & & λ_{n} \end{matrix})

Corollary 7.6. e is an eigenbasis of φ ⇔ [φ]_{e} is a diagonal matrix.

Definition 7.7. A is diagonalizable if it is similar to a diagonal matrix.

Corollary 7.8. [φ]_{e} is diagonalizable iff φ has an eigenbasis.

Remark: the definitions involving eigenvectors only make sense for linear transformations, not linear maps.

Theorem 7.9. If f_{A}(x) = (x − λ_{1}) ⋯ (x − λ_{n}) with all λ_{i} distinct, then A is diagonalizable.

This is sufficient but not necessary – for example the identity matrix is already diagonal.

Lemma 7.10. If e_{1}, …, e_{k} are eigenvectors to distinct eigenvalues, then they are linearly independent.

Proof: [of the theorem from the lemma] Let A = [φ]_{f} . Take an eigenvector for each eigenvalue: φe_{i} = λ_{i}e_{i}. By the lemma the e_{i} are linearly independent. There are n of them = dim V so they are a basis. So φ has an eigenbasis ⇒ A is diagonalizable.

Proof: [of lemma] Assumption: φe_{i} = λ_{i}e_{i}, i = 1, …, k, λ_{i} distinct. Desired conclusion: e_{1}, …, e_{k} are linearly independent.

Suppose ∑_{i=1}^{k} α_{i}e_{i} = 0. Desired conclusion: all α_{i} = 0. Apply φ to both sides: φ(∑_{i=1}^{k} α_{i}e_{i}) = ∑_{i=1}^{k} α_{i}φe_{i} = ∑_{i=1}^{k} α_{i}λ_{i}e_{i} = 0. Would like to use induction.

Base case k = 1: single vector is linearly independent only if it is not zero. An eigenvector is always not zero.

Case k = 2 (instructive, not needed for induction.) φe_{1} = λ_{1}e1, φe_{2} = λ_{2}e2. Assumption: α_{1}e_{1} + α_{2}e_{2} = 0, α_{1}λ_{1}e_{1} + α_{2}λ_{2}e_{2} = 0. Multiply first equation by λ_{1} : α_{1}λ_{1}e_{1} + α_{2}λ_{1}e_{2} = 0. Eliminate e_{1} : α_{2}λ_{2}e_{2} − α_{2}λ_{1}e_{2} = 0 ⇒ α_{2}(λ_{2} − λ_{1})e_{2} = 0 ⇒ α_{2}(λ_{2} − λ_{1}) = 0 ⇒ α_{2} = 0 since λ_{1} ≠ λ_{2}. But this can’t happen.

Inductive step: assume lemma is true for k−1. Need to prove it for k. Multiply ∑ α_{i}e_{i} = 0 by λ_{k}: ∑_{i=1}^{k} α_{i}λ_{k}e_{i}. Subtract: ∑_{i=1}^{k−1} α_{i}(λ_{i}−λ_{k})e_{i} = 0 is a linear relation between e_{1}, …, e_{k−1}. By the inductive hypothesis e_{1}, …, e_{k−1} are linearly independent, so α_{i}(λ_{i} − λ_{k−1}) = 0 for i = 1, …, k − 1. λ_{i} − λ_{k} ≠ 0 ⇒ α_{i} = 0 for i = 1, …, k − 1. We still need: α_{k} = 0. But α_{1}e_{1} + ⋯ + α_{k}e_{k} = 0 ⇒ α_{k}e_{k} = 0 ⇒ α_{k} = 0.

Alternative proof (illustrated for k = 3): we have

α_{1}e_{1} + α_{2}e_{2} + α_{3}e_{3} = 0.
Apply φ : λ_{1}α_{1}e_{1} + λ_{2}α_{2}e_{2} + λ_{3}α_{3}e_{3} = 0.
Apply φ again: λ_{1}^{2}α_{1}e_{1} + λ_{2}^{2}α_{2}e_{2} + λ_{3}^{2}α_{3}e_{3} = 0.

Call α_{i}e_{i} = x_{i}. We get

x_{1} + x_{2} + x_{3} = 0
λ_{1}x_{1} + λ_{2}x_{2} + λ_{3}x_{3} = 0
λ_{1}^{2}x_{1} + λ_{2}^{2}x_{2} + λ_{3}^{2}x_{3} = 0.

This is a system of three equations in three unknowns. If the x_{i} were numbers (as opposed to vectors) then the system has no nontrivial solutions because the matrix

[\begin{matrix}1 & 1 & 1 \\ λ_{1} & λ_{2} & λ_{3} \\ λ_{1}^{2} & λ_{2}^{2} & λ_{3}^{2} \end{matrix}]

is a Vandermonde matrix, with determinant (λ_{2} − λ_{1})(λ_{3} − λ_{1})(λ_{3} − λ_{2}). (In general there are \binom{n}{2} terms.) This is only zero if two of the λ_{i} are equal.

This system of equations works for numbers. To make it work for vectors, take a vector y. Take the inner product of each vector equation with y:

α_{1}e_{1} · y + α_{2}e_{2} · y + α_{3}e_{3} · y = 0
λ_{1}α_{1}e_{1} · y + λ_{2}α_{2}e_{2} · y + λ_{3}α_{3}e_{3} · y = 0
λ_{1}^{2}α_{1}e_{1} · y + λ_{2}^{2}α_{2}e_{2} · y + λ_{3}^{2}α_{3}e_{3} · y = 0

Set x_{i} = α_{i}e_{i} · y. Then all x_{i} must be zero by our Vandermonde argument. Therefore (∀y)(α_{i}e_{i}y = 0). In particular over the real numbers y = e_{i}, e_{i} · e_{i} ≠ 0 ⇒ α_{i} = 0. In general choose y ∉ e_{i}^{⊥}.

Problem 7.11. Find a curve in ℝ^{n} such that any n points on the curve are linearly independent. f : ℝ → ℝ^{n}. f(t) := (f_{1}(t), …, f_{n}(t)) where f_{i}(t) : ℝ → ℝ.

Solution. Set f(t) = (1, t, t^{2}, …, t^{n}) is the moment curve.

(f(t_{1}) ; ⋮ ; f(t_{n})) = (\begin{matrix}1 & t_{1} & ⋯ & t_{1}^{n−1} \\ ⋮ & & & ⋮ \\ 1 & t_{n} & ⋯ & t_{n}^{n−1} \end{matrix})

has nonzero Vandermonde determinant.

Aside: to make this bounded we can use the arctangent function – it will rescale ℝ a bounded open interval.

7.3 Relations between the roots and the coefficients of a polynomial

f(x) = (x − λ_{1}) ⋯ (x − λ_{n}) = ∑_{i=0}^{n} a_{i}x^{i}
a_{n} = 1
a_{n−1} = − ∑_{i=1}^{n} λ_{i}

a_{n−2} = ∑_{1≤i<j≤n} λ_{i}λ_{j} (there are \binom{n}{2} terms)

⋮

a_{n−i} = (−1)^{i} ∑_{1≤j_{1}<···<j_{i}≤n} ∏ λ_{j_{ℓ}} (there are \binom{n}{i} terms.)

⋮

a_{0} = f(0) = (−1)^{n} ∏_{i=1}^{n} λ_{i}

Notation 7.12. The elementary symmetric polynomials:

σ_{1}(x_{1}, …, x_{n}) = x_{1} + ⋯ + x_{n}
σ_{2}(x_{1}, …, x_{n}) = x_{1}x_{2} + x_{1}x_{3} + ⋯ + x_{n−1}x_{n} = ∑_{1≤i<j≤n} x_{i}x_{j}

σ_{i}(x_{1}, …, x_{n}) = ∑ all i-wise products of the x_{i} (\binom{n}{i} terms.)

So a_{n−i} = (−1)^{i}σ_{i}(λ_{1}, …, λ_{n}). This is the relationship between roots and coefficients of a polynomial.

We apply this to the characteristic polynomial.

For A ∈ M_{n}(F) we have f_{A}(x) = ∏_{i=1}^{n}(x − λ_{i}) = ∑_{i=0}^{n} a_{i}x^{i}. Then

a_{n} = 1
a_{n−1} = − tr(A)
⋮
a_{n−i} = (−1)^{i} ∑ det(i × i symmetric submatrices)
⋮
a_{0} = (−1)^{n} det(A).

Hence,

tr(A) = ∑_{i=1}^{n} λ_{i} = σ_{1}(λ_{1}, …, λ_{n})
∑ det(2 × 2 symmetric submatrices) = ∑_{i<j} λ_{i}λ_{j} = σ_{2}(λ_{1}, …, λ_{n})

det(A) = ∏_{i=1}^{n} λ_{i}.

7.4 Real roots of polynomials

Exercise 7.13. x^{100} + 5x^{99} + 13x^{98} + ⋯ = 0 all remaining coefficients real. Prove this polynomial must have roots that are not real, whatever the remaining coefficients are.

If f(x) ∈ ℝ[x], a_{n} = 1, write f(x) = ∏(x − λ_{i})λ_{i} ∈ ℂ.

Exercise 7.14. If λ is a root, then \overline{λ} (the complex conjugate: \overline{a + ib} = a − ib) is also a root with the same multiplicity.

(x − λ)(x − \overline{λ}) = x^{2} − (λ + \overline{λ})x + λ\overline{λ} = x^{2} − 2ℜ(λ) + |λ|^{2} (where ℜz = the real part of z.) This implies

f(x) = product of real polynomials of degree 2 without real roots · ∏_{λ_{i}∈ℝ}(x − λ_{i}).

Corollary 7.15. A real polynomial of odd degree has a real root.

A calculus proof uses the intermediate value theorem.

7.5 Orthonormality and Sense-preservation

Definition 7.16. An othornomal basis is a basis of pairwise orthogonal unit vectors.

An orthonormal basis for ℝ^{n} has e_{i} · e_{j} = 1 if i = j, 0 otherwise.

Definition 7.17. A congruence is a transformation that preserves orthonomality.

If φ is a congruence, and A = [φ]_{e} = [[φe_{1}]_{e} ⋯ [φe_{n}]_{e}] = [a_{1} … a_{n}] then a_{i} · a_{j} = 1 if i = j, 0 if i ≠ j. This is the same as A^{T} · A = I.

Definition 7.18. A real n × n matrix A is called an orthogonal matrix if A^{T} A = I.

Question: what is det A?

det(A^{T} A) = det I = 1. So det(A^{T}) det(A) = 1. But det(A^{T}) = det(A), so det(A)^{2} = 1 ⇒ det(A) = ±1.

A “sense preserving” transformation is a congruence that can be deformed little by little into the identity matrix. Therefore a “sense preserving” matrix must have the same determinant as the identity matrix (by continuity), i.e. 1.

Claim: in ℝ^{3} every sense preserving congruence is a rotation. (We are excluding translations, i.e. the origin is fixed.)

Lemma 7.19 (Key Lemma). For every sense preserving congruence in three dimensions, there is an eigenvector with eigenvalue 1, i.e. λ = 1 is an eigenvalue.

Proof: deg = 3 ⇒ ∃ a real root λ. Because it is a congruence, λ = ±1 because length of x = length of λx.

Write f_{A}(x) = (x − λ_{1})(x − λ_{2})(x − λ_{3}). If all λ_{i} are real, then they are all ±1. If all of them are −1 then det A = −1. So one must be 1. If not all are real, then λ_{1} = ±1, λ_{2} = \overline{λ_{3}}. Then λ_{2} · λ_{3} = λ_{2} · \overline{λ_{2}} = |λ|^{2} > 0. But λ_{1} · |λ_{2}|^{2} > 0 ⇒ λ_{1} > 0.

Exercise 7.20. Finish proof that every sense-preserving congruence in ℝ^{3} is a rotation.