Linear Algebra Collection

Everything About Linear Algebra

Linear, advanced, and numerical viewpoints

Qiulin Fan · 2026

1 Introduction

This is the public reading view for three source-preserving collections:

  • introductory linear algebra notes and personal homework submissions;
  • a short advanced linear algebra notebook based on LADR and GTM 135;
  • numerical linear algebra notes on norms, factorisations, conditioning, and stability.

The original course directories, source manifests, and migration receipts remain the authority for provenance. This file only groups those sources into one continuous reading path; source-authored omissions and explicit TODOs are not silently completed here.

2 Linear equations, vectors, and matrices

2.1 WS 1, p. 1: vectors and vector spaces

(complement: “MathHygine”) Principle of Mathematical Induction: [𝑆(𝑛)∧(∀𝑘∈ℕ,𝑆(𝑘)→𝑆(𝑘+1))]→(∀𝑚∈ℕ,𝑆(𝑚)).

For the system

{3𝑥+21𝑦−3𝑧=0−6𝑥−2𝑦−𝑧=622𝑥−3𝑦+8𝑧=32

place numbers in the columns of the augmented matrix (321−30−6−2−1622−3832).

Definition 2.1 : Vector space

A matrix with only one column is called a column vector, or simply a vector. The entries of a vector are called its components. The set of all column vectors with 𝑛 components is denoted by ℝ𝑛. We will refer to ℝ𝑛 as a vector space.

A matrix with only one row is a row vector. In this text, we refer to vectors as column vectors unless otherwise stated. 下一章会说 preference for column vectors 的 apparent reason.

For example, (1291) is a vector in ℝ4; (15537) is a row vector with 5 components.

  1. 𝐴=(𝑎11𝑎12…𝑎21……𝑎34) is called a 3×4 matrix (row, col; three by four).
  2. Matrix 𝐴=𝐵 if same size and ∀𝑖,𝑗,𝑎𝑖𝑗=𝑏𝑖𝑗.
  3. If 𝐴 is 𝑛×𝑛, 𝐴 is called a square matrix, and the entries 𝑎11,𝑎22,…,𝑎𝑛𝑛 form the main diagonal of 𝐴.
  4. A square matrix 𝐴 is called diagonal provided all its entries above and below the diagonal are 0, i.e. 𝑎𝑖𝑗=0 whenever 𝑖≠𝑗.
  5. 𝐴 is called upper triangular provided all its entries below the main diagonal are 0; lower triangular: entries above the main diagonal are 0.

Note that the 𝑚 columns of an 𝑛×𝑚 matrix are vectors in ℝ𝑛 but not ℝ𝑚: each vector in the 𝑚 vectors has 𝑛 components.

Standard representation of vectors: 𝑣=(𝑥𝑦) (in Cartesian plane; in ℝ3 defined analogously, and likewise in ℝ𝑛). When considering an infinite set of vectors, arrow representation becomes impractical. One may represent 𝑣=(𝑥𝑦) simply by the point (𝑥,𝑦), the head of the standard arrow representation of 𝑣. Example: the set of all vectors (𝑥𝑥+1) where 𝑥 is arbitrary is represented as the line 𝑦=𝑥+1; for a few special values of 𝑥 we may still use arrow representation. The source sketch labels the vectors (12) for 𝑥=1 and (−2−1) for 𝑥=−2 on that line.

Consider the system

{2𝑥+8𝑦+4𝑧=22𝑥+5𝑦+𝑧=54𝑥+10𝑦−𝑧=1.

The matrix which contains the coefficients is called its coefficient matrix, (284251410−1). By contrast, (28422515410−11), which displays all numerical information, is called the augmented matrix.

2.2 WS 1, p. 2: augmented matrices and RREF

For the sake of clarity, we will often indicate the position of the equal signs in the equations by a dotted line: (284|2251|5410−1|1).

我们可以把之前的对 equation 的操作用在 matrix 上,并且将 answer represented as a vector. Thus the displayed system has answer (𝑥𝑦𝑧)=(143).

Example: (1−100420010−120001−13) gives (𝑥1𝑥2𝑥3𝑥4𝑥5)=(2+𝑡+4𝑟𝑡2+𝑟3+𝑟𝑟).

这个 equation 容易解是因为:

  1. The leading coefficient is always 1.
  2. The leading variable in each equation 在其他 equation 中不出现.
  3. The leading variables in natural order 出现.

当一个 linear system 有这些三条性质后就非常容易解,因而我们希望将 linear system reduce 至满足 𝑃1,𝑃2,𝑃3.

For example, row operations reduce the displayed augmented matrix to (1200320010−140001−23000000). 只要朝一个 down,从第三条原则就可以完成这个获得满足 𝑃1,𝑃2,𝑃3 的 reduced matrix 而解 linear system 的 algorithm.

From top to down, move on to the 𝑖th equation 𝑐𝑥𝑗+…=𝑏:

  1. Divide by 𝑐, so 𝑥𝑗+…=𝑏𝑐.
  2. Eliminate 𝑥𝑗 from all other equations above and below.
  3. Proceed to next equation.
  4. Check: if 0= non-0, inconsistent.
  5. Rearrange equations so the leading variables are in natural order.

The reduced row-echelon form (行阶梯矩阵 or Rref) satisfies:

  1. 若一 row 有 non-0 entries, the first non-0 entry must be 1, called the leading or pivot.
  2. 若一 col 中有 pivot,则 col 中其他 entries 必须为 0.
  3. 若一 row 中有 pivot,则它后每个 row 必须有 pivot 在它右边(and rows of 0s must be at the bottom of matrix).
Definition 2.2 : Elementary row operation

之前我们对 linear system 中 equations 的三种 operations 用在 matrix 上,这三种 operation 统称 elementary row operations:

  1. Divide a row by a non-zero scalar.
  2. Subtract a multiple of a row from another.
  3. Swap two rows.

这种使用 elementary row operations 将 matrix 化为 rref 的解 linear system 的 algorithm 叫做 Gauss–Jordan elimination.

3 Linear systems and matrices

The worksheet starts with a system of linear equations:

{𝑥+2𝑦+3𝑧=39𝑥+3𝑦+2𝑧=343𝑥+2𝑦+𝑧=26.

To solve for 𝑥,𝑦,𝑧, we need to transform the system into the form {𝑥=…𝑦=…𝑧=…. In other words:

  1. Eliminate terms that are off the diagonal.
  2. Make the coefficients of the variables along the diagonal equal to 1.

The row-reduction calculation on the page is

{𝑥+2𝑦+3𝑧=39𝑥+3𝑦+2𝑧=343𝑥+2𝑦+𝑧=26→{𝑥+2𝑦+3𝑧=39𝑦−𝑧=−53𝑥+2𝑦+𝑧=26→{𝑥+2𝑦+3𝑧=39𝑦−𝑧=−5−4𝑦−8𝑧=−91,

where the first arrow subtracts the first equation and the next arrow uses −3× the first equation. Then

{𝑥+2𝑦+3𝑧=39𝑦−𝑧=−5−4𝑦−8𝑧=−91→{𝑥+5𝑧=49𝑦−𝑧=−5−12𝑧=−111→{𝑥+5𝑧=49𝑦−𝑧=−5𝑧=9.25→{𝑥=2.75𝑦=4.25𝑧=9.25.

The intervening operations are −2× the second equation and +4× the second equation; then divide by 12; finally use −5× the third equation and add the third equation.

Finally, we check the sol by substituting 𝑥,𝑦,𝑧 into the original linear system. Happily, in Linear Algebra it is easy to check.

4 Linear combinations

4.1 WS 3, p. 1: geometry and number of solutions

Geometric Interpretation: three planes can have a point of intersection (𝑥,𝑦,𝑧), three planes having a line in common, or three planes with no common intersection. 这是 common situation. 然而还有下面这两种 situation:

  • 3 planes having a line in common: a system with infinitely many sols.
  • 3 planes with no common intersection: a system without sols.

For

{2𝑥+4𝑦+6𝑧=04𝑥+5𝑦+6𝑧=37𝑥+8𝑦+9𝑧=6

reduction gives 𝑥−𝑧=2, 𝑦+2𝑧=−1. Generally choose 𝑧=𝑡; then 𝑥=𝑡+2, 𝑦=−2𝑡−1, and the general solution is (𝑥,𝑦,𝑧)=(𝑡+2,−2𝑡−1,𝑡)=(2,−1,0)+𝑡(1,−2,1). The general sol represents a line in space; the source sketch marks 𝑡=0:(2,−1,0), 𝑡=1:(3,−3,1), and 𝑡=2:(9,−5,2).

For

{𝑥+2𝑦+3𝑧=04𝑥+5𝑦+6𝑧=37𝑥+8𝑦+9𝑧=0

reduction yields 𝑥−𝑧=2, 𝑦+2𝑧=−1, 0=−6. Whatever value we choose, 0=−6 cannot be satisfied; this system is inconsistent and has no sol.

Complement (Joy of sets): To say a set is close under some operation ◇ is to mean that 𝑎,𝑏∈𝑆→𝑎◇𝑏∈𝑆.

4.2 Number of solutions of a linear system

本章:① examine how many sols a system of linear equations can possibly can. ② Then we will present some definitions and rules of matrix algebra.

A system of equa. is said to be consistent if it has at least 1 sol; inconsistent: no sol (iff rref of its augmented matrix contains (0…0|𝑐) with 𝑐≠0).

If consistent, either infinitely many sols (at least one free variable) or exactly one sol (if all variables are leading).

Definition 4.3 : Matrix rank
The number of leading 1′s in rref(𝐴) is denoted rank(𝐴). For 𝐴=(123456789), rref(𝐴)=(10−1012000), so rank(𝐴)=2.

For an 𝑛×𝑚 coefficient matrix 𝐴 and the 𝑛×(𝑚+1) augmented matrix [𝐴|𝑏]:

  1. rank(𝐴)≤𝑚 and rank(𝐴)≤𝑛.
  2. If the system is inconsistent, rank(𝐴)<𝑛.
  3. If the system has one sol, rank(𝐴)=𝑚.
  4. If the system has infin sols, rank(𝐴)<𝑚.

If system inconsistent, rref of augmented matrix contains a row [0…0|1], so no leading 1 in that row for the coefficient part. Number of variables = total number of variables − number of leading variables =𝑚−rank(𝐴). Thus exactly one sol gives 𝑚−rank(𝐴)=0, whereas infinitely many sols gives 𝑚−rank(𝐴)>0.

As contrapositive: (1) if rank(𝐴)=𝑛, the system has a sol; (2) if rank(𝐴)<𝑚, the system has no sol or infin sols; (3) if rank(𝐴)=𝑚, the system has no sol or exactly one sol.

Theorem 4.1 : Number of equations vs. number of unknowns
If a linear system has exactly one sol, then it has at least as many equations as variables (i.e. 𝑚≤𝑛 for coefficient matrix 𝐴𝑛×𝑚). Its contrapositive: a linear system with fewer equations than variables (𝑛<𝑚) has either no sol or infin sols.

To illustrate it: consider 2 linear equations in 3 variables. 每个 𝑎𝑥+𝑏𝑦+𝑐𝑧=𝑑 都表示一个 plane,而两个 plane 要么平行无交点,要么交于一直线 (infin sols),不可能只有一个交点。

4.3 WS 3, pp. 2–3: matrix algebra and linear combinations

Definition 4.4 : Sum and scalar multiples of matrices
For same-size matrices, addition is entrywise; for 𝑘∈ℝ, multiplication by 𝑘 multiplies every entry by 𝑘.
Definition 4.5 : Dot products of vectors
For 𝑣=<𝑣1,…,𝑣𝑛> and 𝑤=<𝑤1,…,𝑤𝑛>, 𝑣⋅𝑤=𝑣1𝑤1+𝑣2𝑤2+…+𝑣𝑛𝑤𝑛. Note that the definition is not row-column-sensitive; it does not distinguish between row and col vectors.
Definition 4.6 : The product of 𝐴𝑥
Let 𝐴 be an 𝑛×𝑚 matrix with row vectors 𝑤1,…,𝑤𝑛 and let 𝑥∈ℝ𝑚. Then 𝐴𝑥=(𝑤1⋅𝑥…𝑤𝑛⋅𝑥). In words, the 𝑖th component of 𝐴𝑥 is the dot product of the 𝑖th row of 𝐴 with 𝑥.

Example: (12310−1)(312)=(3+2+63+0−2)=(111). The product 𝐴𝑥 is defined only when the num of col of 𝐴 equals the num of components in 𝑥.

Theorem 4.2 : 𝐴𝑥 in terms of columns of 𝐴
Let the columns of 𝐴 be 𝑣1,…,𝑣𝑚. Then 𝐴𝑥=𝑥1𝑣1+𝑥2𝑣2+…+𝑥𝑚𝑣𝑚.
Definition 4.7 : Linear combination
A vector 𝑏∈ℝ𝑛 is called a linear combination of vectors 𝑣1,…,𝑣𝑚∈ℝ𝑛 if there are scalars 𝑥1,…,𝑥𝑚 such that 𝑏=𝑥1𝑣1+…+𝑥𝑚𝑣𝑚.

Example: is 𝑏=(111) a linear combination of 𝑣=(123) and 𝑤=(456)? Solve (111)=𝑥(123)+𝑦(456)=(𝑥+4𝑦2𝑥+5𝑦3𝑥+6𝑦). Row reduction gives 𝑥=−13, 𝑦=13, hence 𝑏=−13𝑣+13𝑤.

Theorem 4.3 : Algebraic rule for 𝐴𝑥
If 𝐴 is an 𝑛×𝑚 matrix, 𝑥,𝑦∈ℝ𝑚, and 𝑘 is a scalar, then 𝐴(𝑥+𝑦)=𝐴𝑥+𝐴𝑦 and 𝐴(𝑘𝑥)=𝑘(𝐴𝑥).
Theorem 4.4 : Matrix form of a linear system

With augmented matrix [𝐴|𝑏], a linear system can be written 𝐴𝑥=𝑏. Its 𝑖th component is 𝑎𝑖1𝑥1+…+𝑎𝑖𝑚𝑥𝑚=𝑏𝑖, the 𝑖th equation. For 3𝑥1+𝑥2=7, 𝑥1+2𝑥2=4: (3112)(𝑥1𝑥2)=(74), equivalently 𝑥1(31)+𝑥2(12)=(74).

For 2𝑥1−3𝑥2+5𝑥3=7, 9𝑥1+4𝑥2−6𝑥3=8: (2−3594−6)(𝑥1𝑥2𝑥3)=(78). 如果我们可以 divide by matrix 𝐴,𝑥=𝑏𝐴,就能直接解 𝑥。 换言之我们是否能够找到 𝐴−1 呢? Chapter 2.

5 Linear transformations

5.1 WS 4, p. 1: coordinate encoding and standard matrices

现在你的位置为 5○E,42○N。用一个 vector (542)∈ℝ2 表示方位。现在你使用一个 encode 来加密你的方位:

{𝑦1=𝑥1+3𝑥2𝑦2=2𝑥1+5𝑥2,(𝑦1𝑦2)=(1325)(𝑥1𝑥2).

这个加密方位的码为 (131220). 我们做了一个 transformation,使得 the same (𝑦1,𝑦2) but 坐标不变。例如 (0,1) 从 (𝑥1,𝑥2) 坐标 map 到 (𝑦1,𝑦2) 坐标后仍是 (0,1);但 (𝑦1,𝑦2) 下的 (3,5) 同样在 (𝑥1,𝑥2) 下为 (3,5),而 (𝑦1,𝑦2) 下的 (5,42) 在 (𝑥1,𝑥2) 下为 (131,220)。The source sketch marks these corresponding points and axes.

Definition 5.8 : Linear transformation

A function 𝑇:ℝ𝑚→ℝ𝑛 is called a linear transformation if for every 𝑥∈ℝ𝑚 there is an 𝑛×𝑚 matrix 𝐴 such that 𝑇(𝑥)=𝐴𝑥.

Example: 𝑦=𝑥12+𝑥22+𝑥32 has input (𝑥1𝑥2𝑥3) and output [𝑦]; 𝐴=(𝑥1𝑥2𝑥3). 可以发现 𝑦=𝑥⋅𝑥 is not a linear transformation of 𝑥.

Definition 5.9 : Identity matrix

Identity matrix, denoted by 𝐼𝑛: 𝐼2=(1001) and 𝐼3=(100010001).

For 𝑇(𝑥)=(0−110)𝑥, 𝑇((11))=(−11) and 𝑇((0−2))=(20); it is a counterclockwise rotation by 90 degrees. Also 𝑥 and 𝑇(𝑥) have the same length: 𝑥12+𝑥22=(−𝑥2)2+𝑥12. The source diagram labels the two arrows 𝑥 and 𝑇(𝑥).

For 𝑇(𝑥)=𝐴𝑥 with 𝐴=(123456789), 𝑇((100))=(147) and 𝑇((010))=(258).

5.2 WS 4, p. 2: linearity, bases, and transition matrices

Theorem 5.5 : Standard matrix
Consider a linear transformation 𝑇:ℝ𝑚→ℝ𝑛. Let 𝑒𝑖 be the vector whose 𝑖th component is 1 and all other components are 0. Then 𝐴=(𝑇(𝑒1)𝑇(𝑒2)…𝑇(𝑒𝑚)). Equivalently, 𝑒1,𝑒2,…,𝑒𝑚 is the standard vector of ℝ𝑛 (而 ℝ3 中的 𝑒1,𝑒2,𝑒3 都用 𝑖,𝑗,𝑘 来 denote).
Theorem 5.6 : Linearity test
A transformation 𝑇:ℝ𝑚→ℝ𝑛 is linear iff (a) ∀𝑣,𝑤∈ℝ𝑚, 𝑇(𝑣+𝑤)=𝑇(𝑣)+𝑇(𝑤); and (b) ∀𝑣∈ℝ𝑚 and scalar 𝑘, 𝑇(𝑘𝑣)=𝑘𝑇(𝑣).
Definition 5.10 : Distribution vectors and transition matrices
A vector 𝑥∈ℝ𝑛 is said to be a distribution vector if its components (1) sum to 1 and (2) are all ≥0. A square matrix 𝐴 is a transition matrix if its col vectors are distribution vectors.

6 Geometry of linear transformations

6.1 WS 5, p. 1: examples, scaling, and projection

在 2-1 我们知道 (0−110) 是 ℝ2 中 counter clockwise 转 90 度的 linear transformation。现在再看几个:

𝐴=(2002),𝐵=(1000),𝐶=(−1001),𝐷=(01−10),𝐸=(10.201),𝐹=(1−111).

The source diagrams apply them to (1,2) and (1,−1):

  • 𝐴: 放大一倍, sending them to (2,4) and (−2,−2).
  • 𝐵: orthogonal projection onto 𝑥-axis, sending both to (1,0).
  • 𝐶: reflection about 𝑦-axis.
  • 𝐷: clockwise 转 90 degrees, sending them to (−2,−1) and (1,−1).
  • 𝐸: 向右 shear, sending them to (1.4,2) and (0.8,−1).
  • 𝐹: counterclockwise shift + 放大 2 倍, sending them to (−1,3) and (2,0).
Theorem 6.7 : Scalings
(𝑘00𝑘) defines a scaling by 𝑘, since (𝑘00𝑘)(𝑥1𝑥2)=(𝑘𝑥1𝑘𝑥2)=𝑘(𝑥1𝑥2)=𝑘𝑥.
Definition 6.11 : Orthogonal projection

Consider a line 𝐿 in coordinate plane, 经过 (0,0). 任何 𝑥∈ℝ2 都可以写成 𝑥=𝑥∥+𝑥⟂, where 𝑥∥‖𝐿 and 𝑥⟂⟂𝐿. The transformation 𝑇(𝑥)=𝑥∥ is the orthogonal projection of 𝑥 onto 𝐿, denoted proj𝐿(𝑥).

随意取 𝑤‖𝐿, proj𝐿(𝑥)=𝑥⋅𝑤𝑤⋅𝑤𝑤. 特别地,如果 𝑤 是 unit vector 𝑢=(𝑢1𝑢2)‖𝐿, then proj𝐿(𝑥)=(𝑥⋅𝑢)𝑢. 这一个 transformation 是 linear 的;with matrix 𝑃=(𝑢12𝑢1𝑢2𝑢1𝑢2𝑢22).

Definition 6.12 : Reflection
Consider a line 𝐿 in coordinate plane, 过 (0,0), and write 𝑥=𝑥∥+𝑥⟂. Then 𝑇(𝑥)=𝑥∥−𝑥⟂ is reflection of 𝑥 about 𝐿, denoted ref𝐿(𝑥). 由 Definition 2.2.1, ref𝐿(𝑥)=𝑥∥−(𝑥−𝑥∥)=2proj𝐿(𝑥)−𝑥=(2𝑃−𝐼2)𝑥.

The matrix of 𝑇 has form (𝑎𝑏𝑏−𝑎) where 𝑎2+𝑏2=1: 𝑆=2𝑃−𝐼2=(2𝑢12−12𝑢1𝑢22𝑢1𝑢22𝑢22−1)=(𝑢12−𝑢222𝑢1𝑢22𝑢1𝑢2𝑢22−𝑢12).

6.2 WS 5, p. 2: rotations and shearing

Theorem 6.8 : Rotations
𝑇(𝑥)=𝐴𝑥 is a counterclockwise rotation in ℝ2 (rotate by 𝜃) iff 𝐴=(cos(𝜃)−sin(𝜃)sin(𝜃)cos(𝜃))=(𝑎−𝑏𝑏𝑎), where 𝑎2+𝑏2=1.

For a nonzero vector 𝑥, write its coordinate in polar form (𝑟cos(𝜑),𝑟sin(𝜑)). Rotation gives 𝑥′=(𝑟cos(𝜑+𝜃),𝑟sin(𝜑+𝜃)), so 𝑥1′=𝑥cos(𝜃)−𝑦sin(𝜃) and 𝑦′=𝑥sin(𝜃)+𝑦cos(𝜃), which gives the displayed matrix.

Theorem 6.9 : Rotations combined with a scaling
将 𝑣∈ℝ2 counterclockwise rotate 𝜃 并放大至 𝑟 倍. Let 𝑇(𝑎,𝑏)=(𝑟cos(𝜃)𝑟sin(𝜃)). Then 𝑇(𝑥)=𝐴𝑥, 𝐴=(𝑎−𝑏𝑏𝑎)=𝑟(cos(𝜃)−sin(𝜃)sin(𝜃)cos(𝜃)).

6.3 5. Shearing

Vertical shear:

𝑇((𝑥1𝑥2))=(𝑥1𝑘𝑥1+𝑥2)=(10𝑘1)(𝑥1𝑥2).

Horizontal shear:

𝑇((𝑥1𝑥2))=(𝑥1+𝑘𝑥2𝑥2)=(1𝑘01)(𝑥1𝑥2).
Theorem 6.10 : Horizontal and vertical shearing
Horizontal shearing of slope 𝑘𝑥2 has matrix (1𝑘01); vertical shearing of slope 𝑘𝑥1 has matrix (10𝑘1).

The source’s concluding table records:

  • Scaling by 𝑘: 𝑘𝐼2=(𝑘00𝑘).
  • Orthogonal projection onto line 𝐿: (𝑢12𝑢1𝑢2𝑢1𝑢2𝑢22), for 𝑢‖𝐿 and ‖𝑢‖=1.
  • Reflection about line 𝐿: (2𝑢12−12𝑢1𝑢22𝑢1𝑢22𝑢22−1).
  • Rotation through angle 𝜃 (逆时针): (cos(𝜃)−sin(𝜃)sin(𝜃)cos(𝜃)).
  • Rotation through 𝜃 with scaling by 𝑟: 𝑟(cos(𝜃)−sin(𝜃)sin(𝜃)cos(𝜃)).
  • Shear: horizontal (1𝑘01); vertical (10𝑘1).

7 Gram–Schmidt and QR factorization

7.1 WS 17, p. 1: proof of QR factorization QR factorization

Let 𝑀=(𝑚1…𝑚𝑑) be 𝑛×𝑑. Gram–Schmidt produces 𝑄=(𝑞1…𝑞𝑑):

𝑞1=𝑚1‖𝑚1‖,𝑞𝑖=𝑚𝑖−∑𝑘=1𝑖−1(𝑚𝑖⋅𝑞𝑘)𝑞𝑘‖𝑚𝑖−∑𝑘=1𝑖−1(𝑚𝑖⋅𝑞𝑘)𝑞𝑘‖.

The (𝑞1,…,𝑞𝑑) are orthonormal. 因而 𝑄 is an orthogonal matrix, and

𝑆𝑀→𝑄=([𝑚1]𝑄…[𝑚𝑑]𝑄).

The worksheet computes

𝑄𝑡𝑀=(𝑚1⋅𝑞1𝑚2⋅𝑞1…𝑚𝑑⋅𝑞1𝑚1⋅𝑞2𝑚2⋅𝑞2………𝑚𝑑⋅𝑞𝑑).

Because 𝑞𝑖⟂span(𝑚1,…,𝑚𝑖−1), the entry 𝑞𝑖⋅𝑚𝑗 is 0 when 𝑖>𝑗; the result is upper triangular. Thus 𝑀=𝑄𝑅, with 𝑅=𝑄𝑡𝑀 upper triangular.

7.2 Proof of matrix product theorem

For ordered bases 𝐵=(𝑏1,…,𝑏𝑑) and 𝐴=(𝑎1,…,𝑎𝑑) of 𝑊⊆ℝ𝑛:

(𝑏1…𝑏𝑑)=(𝑎1…𝑎𝑑)𝑆𝐵→𝐴,

where

𝑆𝐵→𝐴=([𝑏1]𝐴…[𝑏𝑑]𝐴).

Note that if 𝑏𝑖=𝑐1𝑎1+…+𝑐𝑑𝑎𝑑, then [𝑏𝑖]𝐴=(𝑐1…𝑐𝑑); hence

𝐴𝑆𝐵→𝐴=(𝐴[𝑏1]𝐴…𝐴[𝑏𝑑]𝐴)=(𝑏1…𝑏𝑑)=𝐵.

8 Orthogonal transformations

8.1 WS 18, p. 1: definition and matrix criteria

Definition 8.13 : Orthogonal transformation
𝑇:ℝ𝑛→ℝ𝑛 is orthogonal (正交变换) if it preserves dot products: ∀𝑥,𝑦∈ℝ𝑛, 𝑥⋅𝑦=𝑇(𝑥)⋅𝑇(𝑦).
Theorem 8.11 : Equivalent characterizations
𝑇:ℝ𝑛→ℝ𝑛 is orthogonal iff it preserves the length of vectors: ∀𝑥∈ℝ𝑛, ‖𝑇(𝑥)‖=‖𝑥‖.

因而 linear trans 保留 dot product iff 保留 length. The proof expands ‖𝑇(𝑥+𝑦)‖2=‖𝑥+𝑦‖2:

‖𝑇(𝑥)‖2+2𝑇(𝑥)⋅𝑇(𝑦)+‖𝑇(𝑦)‖2=‖𝑥‖2+2𝑥⋅𝑦+‖𝑦‖2,

then cancels equal norm terms.

(a) An orthogonal trans 𝑇 is injective: 𝑇(𝑥)=0→‖𝑇(𝑥)‖=0→‖𝑥‖=0, so ker𝑇={0} and 𝑇 is inj. (b) It is an isomorphism because a same-dimension linear trans is inj iff surj. (c) The standard matrix of 𝑇 has orthonormal columns. (d) The composition of orthogonal trans is orthogonal, since

‖𝑇𝑘⋅𝑇𝑘−1⋅…⋅𝑇1(𝑥)‖=…=‖𝑥‖.
Definition 8.14 : Orthogonal matrix
A square matrix 𝐴 is orthogonal if 𝐴𝑡𝐴=𝐼𝑛 (即 𝐴𝑡=𝐴−1).

If 𝐴=(𝑣1…𝑣𝑛), then the 𝑖𝑗th entry of 𝐴𝑡𝐴 is 𝑣𝑖⋅𝑣𝑗. Therefore 𝐴 is orthogonal iff its cols are orthonormal. 我们也由此知道:由 orthonormal basis 组成的 matrix 𝐴, 𝐴−1 就是 𝐴𝑡.

The worksheet proves (𝐴𝐵)𝑡=𝐵𝑡𝐴𝑡: the 𝑖𝑗th entry of 𝐴𝐵 is the 𝑖th row of 𝐴 dot the 𝑗th col of 𝐵, while the 𝑖𝑗th entry of 𝐵𝑡𝐴𝑡 is 𝑏𝑖⋅𝑎𝑗. Thus they agree.

8.2 WS 18, p. 2: products and change of basis

If 𝐴 is orthogonal, then 𝐴−1 (也是 𝐴𝑡) is orthogonal, since 𝔸𝑡=𝐼𝑛 implies (𝐴𝑡)(𝐴𝑡)𝑡=𝔸𝑡=𝐼𝑛. 结论:这意味着对于 𝐴 的 cols 是 orthonormal 的,那 𝐴 的 rows 也是 orthonormal 的.

Theorem 8.12 : Products of orthogonal matrices
If 𝐴,𝐵 are orthogonal 𝑛×𝑛 matrices, then 𝐴𝐵 is orthogonal.

Indeed,

(𝐴𝐵)(𝐴𝐵)𝑡=𝐴(𝐵𝐵𝑡)𝐴𝑡=𝐼𝑛,

so (𝐴𝐵)𝑡=(𝐴𝐵)−1.

Theorem 8.13 : Orthogonal maps and their matrices
𝑇:ℝ𝑛→ℝ𝑛 is orthogonal iff [𝑇]𝜀 is orthogonal, where 𝜀 is the standard basis. More generally, 𝑇 is orthogonal iff [𝑇]𝛽 is orthogonal for any orthonormal basis 𝛽.

For the reverse direction,

𝑇(𝑎)⋅𝑇(𝑏)=([𝑇]𝜀𝑎)[𝑇]𝜀𝑏̇=𝑎𝜀𝜀𝑡[𝑇]𝑡[𝑇]𝑏=𝑎⋅𝑏.

Claim 1: If 𝐴,𝐵 are orthonormal basis matrices, their change-of-basis matrices are orthogonal. On WS 16, the entries are

𝑆𝐴→𝐵=(𝑎1⋅𝑏1𝑎2⋅𝑏1…𝑎𝑛⋅𝑏1𝑎1⋅𝑏2………𝑎𝑛⋅𝑏𝑛)

and

𝑆𝐵→𝐴=(𝑏1⋅𝑎1𝑏2⋅𝑎1………𝑏𝑛⋅𝑎𝑛)=𝑆𝐴→𝐵𝑡.

Thus 𝑆𝐴→𝐵=𝑆𝐵→𝐴−1.

8.3 WS 18, p. 3: conclusion

Claim 2: orthogonal matrices 的 product 也是 orthogonal matrix. 这是因为 orthogonal transformations 的 composition 也是 orthogonal transformation, 且它的自身的 matrix 代表为 orthogonal matrix。

Claim 3: 如果 𝑇 orthogonal,则 [𝑇]𝛽 orthogonal for 任意 orthonormal basis 𝛽:

[𝑇]𝛽=𝑆𝜀→𝛽[𝑇]𝜀𝑆𝛽→𝜀.

All three factors are orthogonal, hence so is [𝑇]𝛽.

Claim 4: 𝛽 为任意 orthonormal basis; 如果 [𝑇]𝛽 orthogonal,则 𝑇 orthogonal. Since

[𝑇]𝛽=𝑆𝜀→𝛽[𝑇]𝜀𝑆𝛽→𝜀,

we obtain

[𝑇]𝜀=𝑆𝛽→𝜀[𝑇]𝛽𝑆𝜀→𝛽,

a product of orthogonal matrices; hence [𝑇]𝜀 is orthogonal and therefore 𝑇 is orthogonal.

总结:𝑇 is orthogonal (保留 dot product) =𝑇 保留 length =𝑇 保留 distance =𝑇 把 ℝ𝑛 的某个 orthonormal basis map 到另一个 orthonormal basis =[𝑇]𝛽 为 orthogonal 的,𝛽 为任意 orthonormal basis =[𝑇]𝛽 的 rows/cols 为一个 orthonormal basis of ℝ𝑛.

9 Least squares

9.1 WS 19, p. 1: projection and image/kernel theorem

Theorem 9.14 : Projection and Least squares method
对于任意 subspace 𝑉⊆ℝ𝑛, ∀𝑥∈ℝ𝑛, proj𝑉(𝑥) is 𝑉 中离 𝑥 最近的 vector, i.e. 𝑣∈𝑉, ‖𝑥−proj𝑉(𝑥)‖≤‖𝑥−𝑣‖.

The source diagram labels ‖𝑥−proj𝑉(𝑥)‖ as the 垂直距离.

(a) 𝐴𝑥=𝑏 is consistent iff 𝑏∈im𝐴: if ∃𝑥 such that 𝐴𝑥=𝑏, then 𝑏∈im𝐴, and conversely. (b) 不可能 𝑏 不在 span(cols of A) 而 𝐴𝑥=𝑏 be consistent. (c), least squares solutions: if 𝐴𝑥=𝑏 is not consistent, let 𝑉=im𝐴, 𝑏′=proj𝑉(𝑏). Then 𝐴𝑥=𝑏′ has a solution because 𝑏′∈𝑉; the solutions in that solution set are the least squares solution to this system.

The worksheet also records

𝐴𝑥⋅𝑦=(𝐴𝑥)𝑡𝑦=𝑥𝑡𝐴𝑡𝑦=𝑥⋅(𝐴𝑡𝑦).
Theorem 9.15 : Image-kernel orthogonality
For an 𝑚×𝑛 matrix 𝐴, ker(𝐴𝑡)=(im𝐴)⟂.

Write 𝐴=(𝑣1…𝑣𝑛), so 𝐴𝑡=(𝑣1𝑡…𝑣𝑛𝑡). If 𝑥∈ker𝐴𝑡, then 𝑣𝑖⋅𝑥=0 for every 𝑖, so 𝑥⟂im𝐴. Conversely, if 𝑥∈(im𝐴)⟂, then every 𝑣𝑖⋅𝑥=0, so 𝐴𝑡𝑥=0.

A second proof uses the displayed transpose identity: 𝑦∈ker𝐴𝑡→𝐴𝑥⋅𝑦=0 for all 𝑥, hence 𝑦∈(im𝐴)⟂; conversely 𝐴𝑥⋅𝑦=0 for all 𝑥 implies 𝐴𝑡𝑦=0.

Consequently (ker𝐴𝑡)⟂=im𝐴, and ker𝐴=(im𝐴𝑡)⟂. The rank computation is

rank(𝐴𝑡)=𝑛−dim(ker𝐴𝑡)=dim(im𝐴)=rank(𝐴).

9.2 WS 19, p. 2: normal equations

The normal equation: 𝐴𝑥=𝑏 的 least square 解当且仅当 𝐴𝑥=proj(𝑏) is a solution of

𝐴𝑡𝐴𝑥=𝐴𝑡𝑏.
Theorem 9.16 : Kernel of 𝐴𝑡𝐴
For an 𝑚×𝑛 matrix 𝐴, ker𝐴=ker(𝐴𝑡𝐴).

If 𝑥∈ker(𝐴𝑡𝐴), then 𝐴𝑡𝐴𝑥=0, so 𝐴𝑥∈ker𝐴𝑡=(im𝐴)⟂. Since 𝐴𝑥∈im𝐴 and im𝐴 与 (im𝐴)⟂ only meet at 0, so 𝐴𝑥=0. Conversely 𝐴𝑥=0 directly implies 𝐴𝑡𝐴𝑥=0.

For the rest proof of normal equation, the source diagram records 𝑏−projim𝐴(𝑏)∈(im𝐴)⟂=ker(𝐴𝑡). Thus 𝐴𝑥−𝑏∈ker(𝐴𝑡), whence

𝐴𝑡(𝐴𝑥−𝑏)=0,𝐴𝑡𝐴𝑥=𝐴𝑡𝑏.

总结:对于 𝑇𝐴:ℝ𝑛→ℝ𝑚, 𝑇𝐴𝑡:ℝ𝑚→ℝ𝑛, 使得对于 𝑥∈ℝ𝑛 及 𝑦∈ℝ𝑚,(𝐴𝑥)⋅𝑦=𝑥𝐴𝑡𝑦̇ 是 transpose 本质的性质;它告诉我们 𝐴 是 ℝ𝑛 到 ℝ𝑚 的 linear map.

10 Inner-product spaces

10.1 WS 20, p. 1: examples and generalized Gram–Schmidt

For the Inner product space 𝑉 of functions on [−𝜋,𝜋], <𝑓,𝑔≥1𝜋∫−𝜋𝜋𝑓(𝑡)𝑔(𝑡)d𝑡:

  1. <𝑓,𝑔≥<𝑔,𝑓>.
  2. Linearity: <𝑎𝑓1+𝑏𝑓2,𝑔≥𝑎𝜋∫−𝜋𝜋𝑓1(𝑡)𝑔(𝑡)d𝑡+𝑏𝜋∫−𝜋𝜋𝑓2(𝑡)𝑔(𝑡)d𝑡=𝑎<𝑓1,𝑔>+𝑏<𝑓2,𝑔>.
  3. Positive definite: <𝑓,𝑓≥1𝜋∫−𝜋𝜋𝑓2(𝑡)d𝑡, and 𝑓2(𝑡)>0→<𝑓,𝑓≫0.

(b) 同 (a),inner product space 𝑉. (c) 不是 inner prod space: can diverge, ∞ 不在 ℝ.

P4: find two different inner products in ℝ2: <𝑥,𝑦≥𝑥1𝑦1+𝑥2𝑦2 (dot product; here 𝑒1,𝑒2 are orthonormal), and different weight <𝑥,𝑦≥3𝑥1𝑦1+2𝑥2𝑦2.

P5: Every finite dimensional inner product space has an orthonormal basis. Take

𝑢1=𝑣1norm(𝑣1),𝑢2=𝑣2−(𝑣2⋅𝑢1)𝑢1‖𝑣2−(𝑣2⋅𝑢1)𝑢1‖,

and, in general,

𝑢𝑛=𝑣𝑛−∑𝑗=1𝑛−1(𝑣𝑛⋅𝑢𝑗)𝑢𝑗‖𝑣𝑛−∑𝑗=1𝑛−1(𝑣𝑛⋅𝑢𝑗)𝑢𝑗‖.

proof: generalized Gram–Schmidt.

10.2 WS 20, p. 2: coordinates and matrix inner products

P8: 任选 orthonormal basis 𝑈 for inner product <⋅,⋅>. Then (𝑉,<⋅,⋅>) 上

<𝑥,𝑦≥[𝑥]𝑈⋅[𝑦]𝑈.

Indeed 𝑥=∑𝑖𝑎𝑖𝑢𝑖, 𝑦=∑𝑗𝑏𝑗𝑢𝑗, so

<𝑥,𝑦≥∑𝑖∑𝑗𝑎𝑖𝑏𝑗<𝑢𝑖,𝑢𝑗>=∑𝑖𝑎𝑖𝑏𝑖=[𝑥]𝑈⋅[𝑦]𝑈.

P9: ∀ inner product <⋅,⋅> on ℝ𝑛, ∃ an 𝑛×𝑛 symmetric matrix 𝐴 such that

∀𝑥,𝑦∈ℝ𝑛,<𝑥,𝑦≥𝑥𝑡𝐴𝑦.

For the standard basis, the (𝑖,𝑗)th entry of 𝐴 is <𝑒𝑖,𝑒𝑗>. Hence

<𝑥,𝑦≥∑𝑖∑𝑗𝑥𝑖𝑦𝑗<𝑒𝑖,𝑒𝑗>=𝑥𝑡𝐴𝑦.

Because the inner product is symmetric, so is 𝐴. Its diagonal entries are positive; 𝐴 is 可逆 (full rank).

P10: All inner products on ℝ2 have

𝐵𝐴(𝑥,𝑦)=𝑥𝑡𝐴𝑦,𝐴=(𝑎𝑏𝑏𝑐),

where (1) 𝐴 is symmetric; (2) 𝑎>0 and det𝐴=𝑎𝑐−𝑏2>0. Indeed

(𝑥𝑦)(𝑎𝑏𝑏𝑐)(𝑥𝑦)=𝑎𝑥2+2𝑏𝑥𝑦+𝑐𝑦2>0.

(这个条件等价:充分条件为 𝑐>0 且 𝑎𝑐−𝑏2>0=det𝐴.) Linearity is guaranteed by matrix multiplication. 因而这三条为完整条件。

实际上的理解为:把 ℝ𝑛 的任何 inner product 都是:把一个 vector 做一个 linear trans 后再做一个 dot product.

11 Diagonalization and eigenspaces

11.1 WS 23, p. 1: four theorems

Theorem 11.17 : Eigenbasis and diagonal matrix
For a finite-dimensional vector space 𝑉, a basis 𝛽 of 𝑉 is an eigenbasis for 𝑇:𝑉→𝑉 iff [𝑇]𝛽 is diagonal.

Indeed,

[𝑇]𝛽=([𝑇(𝑏1)]𝛽…[𝑇(𝑏𝑛)]𝛽)=(𝜆1𝑏1…𝜆𝑛𝑏𝑛).
Theorem 11.18 : Diagonalizable transformation
𝑇:𝑉→𝑉 is diagonalizable iff [𝑇]𝛽 is similar to some diagonal matrix 𝐷.

The definition notes: 𝑇 diagonalizable iff 其 𝐷=𝑛×𝑛 matrix of 𝑇 is diagonal. 因而(所有 [𝑇]𝛼 都相似于 [𝑇]𝛽).

Theorem 11.19 : Diagonalizable matrix
𝐴∈ℝ𝑛×𝑛 is diagonalizable iff 𝐴 is similar to some diagonal 𝐷.
Theorem 11.20 : Eigenspace
𝐸𝜆=ker(𝑇−𝜆𝐼𝑛), so dim(𝐸𝜆)=dim(ker(𝑇−𝜆𝐼𝑛))=𝑛−rank(𝑇−𝜆𝐼𝑛).

Proof: (𝑇−𝜆𝐼)(𝑣)=0 iff 𝑇(𝑣)=𝜆𝐼(𝑣)=𝜆𝑣, so the kernel is exactly the vectors changed only by 𝑇 stretching by 𝜆, i.e. the eigenvectors with eigenvalue 𝜆 together with zero. 没有被 𝑇−𝜆𝐼 改变的 vectors,即只被 𝑇 拉伸 𝜆 倍的 vectors.

(Thm 7.1.3) 如果 𝐷=(𝑣1,…,𝑣𝑛) 是 an eigenbasis of 𝑉 for 𝑇, then

[𝑇]𝐷=𝑆𝐷→𝜀−1[𝑇]𝜀𝑆𝐷→𝜀=(𝜆1……𝜆𝑛).

Proof note: 𝑇𝐴(𝑥)=𝐴𝑥 (𝐴=[𝑇]𝜀). Then 𝑆𝐷→𝜀=(𝑣1…𝑣𝑛) and

[𝑇]𝜀𝑆𝐷→𝜀=(𝐴𝑣1…𝐴𝑣𝑛)=(𝜆1𝑣1…𝜆𝑛𝑣𝑛).

Hence the change of basis yields the diagonal matrix.

12 Eigenvalues and eigenspaces

12.1 WS 24, p. 1: characteristic polynomial and multiplicities

Theorem 12.21 : Eigenvalues are roots
The eigenvalues of 𝑇 are precisely the roots of its characteristic polynomial.

简明 proof: 𝜆 是 𝑇 的 eigenvalue iff 𝐸𝜆≠{0} iff ker(𝑇−𝜆𝐼)≠{0} iff nullity(𝑇−𝜆𝐼)>0 iff rank(𝑇−𝜆𝐼)<𝑛 iff 𝑇−𝜆𝐼 不可逆 iff det(𝑇−𝜆𝐼)=0. Thus 𝜆 is a root of det(𝑇−𝜆𝐼)=0.

Theorem 12.22 : Distinct-eigenvalue eigenspaces
∀𝑥∈𝐸𝜆1 且 𝑥≠0, and 𝑦∈𝐸𝜆2 且 𝑦≠0, if 𝜆1≠𝜆2, then 𝑥,𝑦 are linearly independent.

因而 eigenbases of distinct eigenspaces have linearly independent union, and if ∑𝑖dim(𝐸𝜆𝑖)=dim𝑉, that union is an eigenbasis of 𝑉 for 𝑇.

Theorem 12.23 : Geometric and algebraic multiplicity
For eigenvalue 𝜆, gem(𝜆)≤alm(𝜆).

Let 𝐴∈ℝ𝑛×𝑛, let 𝜆 be an eigenvalue and gem(𝜆)=𝑚. Let (𝑣1,…,𝑣𝑚) be a basis of 𝐸𝜆, put 𝑆=(𝑣1…𝑣𝑚), and define 𝐵=𝑆−1𝐴𝑆. Then for 1≤𝑖≤𝑚,

𝐵𝑒𝑖=𝑆−1𝐴𝑆𝑒𝑖=𝑆−1𝐴𝑣𝑖=𝑆−1𝜆𝑣𝑖=𝜆𝑒𝑖.

Therefore

𝐵=(𝜆𝐼𝑚𝑃0𝑄),

so

𝑓𝐴(𝑥)=𝑓𝐵(𝑥)=det(𝐵−𝑥𝐼𝑛)=(𝑥−𝜆)𝑚𝑓𝑄(𝑥),

and alm(𝜆)≥𝑚.

Theorem 12.24 : Degree of the characteristic polynomial
For 𝑇:𝑉→𝑉, 𝜒𝑇(𝑥) has degree dim𝑉.

This is the corollary of the preceding two theorems: if 𝑇 has 𝑛 different eigenvalues, then ∑𝑖alm(𝜆𝑖)≤dim𝑉. Proof: 见 P9.

13 Complex eigenvalues

13.1 WS 26, p. 1: complex roots and real 2×2 matrices

P5(b). Let 𝑧=𝑎+𝑏𝑖 and 𝑤=𝑐+𝑑𝑖. Then

𝑧+𝑤=(𝑎+𝑐)+(𝑏+𝑑)𝑖,

z w=(a c-b d)+(b c+a d)i,

conjugate(𝑧)conjugate(𝑤)=(𝑎−𝑏𝑖)(𝑐−𝑑𝑖)=𝑎𝑐−𝑏𝑑−(𝑏𝑐+𝑎𝑑)𝑖=conjugate(𝑧𝑤).

(c) Fact: 𝜆 is a root of 𝑓(𝑥) iff 𝜆 is a root when the coefficients of 𝑓(𝑥) are real. If 𝜆𝑛+𝑎𝑛−1𝜆𝑛−1+…+𝑎0=0, then

∑𝑘𝑎𝑘𝜆𝑘=conjugate(∑𝑘𝑎𝑘𝜆𝑘)=0.

For

𝐴=(𝑎−𝑏𝑏𝑎)∈ℝ2×2,𝜒𝐴(𝜆)=(𝑎−𝜆)2+𝑏2,𝜒𝐴(𝜆)=0→𝜆=𝑎±𝑏𝑖.

(b) Factor 𝐴 into a scalar matrix 𝑟𝐼2 and a rotation matrix 𝑅𝜃:

𝐴=𝑎2+𝑏2(cos(𝜃)−sin(𝜃)sin(𝜃)cos(𝜃)),

where

cos(𝜃)=𝑎𝑎2+𝑏2,sin(𝜃)=𝑏𝑎2+𝑏2,𝜃=arctan(𝑏𝑎).

(c) Diagonalization over ℂ:

𝐷=(𝑎+𝑏𝑖00𝑎−𝑏𝑖).

For 𝜆1=𝑎+𝑏𝑖,

det(𝐴−𝜆1𝐼2)=det((−𝑏𝑖−𝑏𝑏−𝑏𝑖)),

so (𝑖1) is a basis for 𝐸𝜆1; similarly (−𝑖1) is a basis for 𝐸𝜆2. Hence

𝐷=𝑆−1𝐴𝑆=(𝑖−𝑖11)−1𝐴(𝑖−𝑖11),

and

𝐴=(𝑖−𝑖11)(𝑎+𝑏𝑖00𝑎−𝑏𝑖)(𝑖−𝑖11)−1.

P9: 任何有一对 complex eigenvalue 𝑎±𝑏𝑖 的 𝐴∈ℝ2×2 都 similar to (𝑎−𝑏𝑏𝑎)(一个 scaling matrix). 因为 𝐴 diagonalizable: 𝐷=(𝑎+𝑏𝑖00𝑎−𝑏𝑖),而 𝐷 又 similar to (𝑎−𝑏𝑏𝑎) by P8.

14 Spectral theorem

14.1 WS 27, p. 1: theorem and first two claims

Theorem 14.25 : Spectral theorem
𝐴 is orthogonally diagonalizable iff 𝐴 is symmetric: ∃𝑆∈ℝ𝑛×𝑛 such that 𝑆−1=𝑆𝑡 and 𝑆𝑡𝐴𝑆 is diagonal iff 𝐴 is symmetric.

Equivalently, 𝑆 的 cols 是 ℝ𝑛 的一个 orthonormal basis, 且为 𝐴 的 eigenvectors. 普通 diagonalization: 𝐷=𝑆𝐴𝑆−1, 𝑆 的 cols 为 𝑉 的 一个 eigenbasis (𝑣1,…,𝑣𝑛). 而 orthogonal diagonalization: 𝐷=𝑆𝑡𝐴𝑆, 𝑆 的 cols 不但是 eigenbasis,而且还是一个 orthonormal eigenbasis. 这意味着对于不同的 eigenvectors,它们都是 orthogonal 的 (可以为 orthonormal),也就是说 𝑉,𝐸𝜆1,𝐸𝜆2 with 𝐸𝜆1⟂𝐸𝜆2.

Claim 1: if 𝐴 is orthogonally diagonalizable, then 𝐴 is symmetric. If 𝑆𝑡𝐴𝑆=𝐷 and 𝑆−1=𝑆𝑡, then

𝐴=𝑆𝐷𝑆𝑡,

and

𝐴𝑡=(𝑆𝐷𝑆𝑡)𝑡=𝑆𝐷𝑡𝑆𝑡=𝑆𝐷𝑆𝑡=𝐴.

Claim 2: if 𝐴∈ℝ𝑛×𝑛 is symmetric, then 𝐴 is orthogonally diagonalizable over ℝ. This claim is divided into three parts.

Claim 2 pt.(1): if 𝐴∈ℝ𝑛×𝑛 is symmetric, then 𝐴 has real eigenvalues. By the fundamental theorem of Algebra, 𝜒𝑇(𝑥)=0 有 𝑛 个 complex roots 包含重复. Let 𝜆 be any complex eigenvalue, so ∃𝑧∈ℂ𝑛, 𝐴𝑧=𝜆𝑧. Then 𝐴𝑏(..) => ..{𝑧}=𝑏(..) => ..𝜆𝑏(..) => ..{𝑧}, and, after transpose, 𝑏(..) => ..{𝑧}𝑡𝐴=𝑏(..) => ..𝜆𝑏(..) => ..{𝑧}𝑡 because 𝐴 is symmetric. Multiply 𝑧 on the right:

𝑏(..) => ..{𝑧}𝑡𝐴𝑧=𝜆(𝑏(..) => ..{𝑧}𝑡𝑧)=𝑏(..) => ..𝜆(𝑏(..) => ..{𝑧}𝑡𝑧).

Since 𝑏(..) => ..{𝑧}𝑡𝑧=∑𝑖|𝑧𝑖|2>0, 𝜆=𝑏(..) => ..𝜆; every complex eigenvalue is real.

Claim 2 pt.(2): consider 𝜆1,𝜆2 and nonzero 𝑣1∈𝐸𝜆1, 𝑣2∈𝐸𝜆2, with 𝜆1≠𝜆2. Then

𝜆1𝑣1𝑡𝑣2=(𝐴𝑣1)𝑡𝑣2=𝑣1𝑡𝐴𝑡𝑣2=𝑣1𝑡(𝐴𝑣2)=𝜆2𝑣1𝑡𝑣2.

Thus 𝑣1⋅𝑣2=0, so 𝑣1⟂𝑣2.

14.2 WS 27, p. 2: induction proof

Claim 2 pt.(3): if 𝐴∈ℝ𝑛×𝑛 is symmetric, then 𝐴 is orthogonally diagonalizable. Prove by induction.

Base case: a 1×1 matrix is diagonal and symmetric. Inductive step: if every symmetric 𝑛×𝑛 matrix is orthogonally diagonalizable, then every (𝑛+1)×(𝑛+1) matrix is too.

Let 𝐴∈ℝ(𝑛+1)×(𝑛+1) be symmetric. Let 𝜆 be an eigenvalue and 𝑢 a corresponding unit eigenvector. Complete 𝑈=(𝑢,𝑢1,…,𝑢𝑛) to an orthonormal basis of ℝ𝑛+1. Put

𝑄=(𝑢𝑢1…𝑢𝑛),

so 𝑄 is orthogonal and 𝑄𝑡=𝑄−1. 注意 𝑄 为 𝑆𝑈→𝜀, 因而 𝑄𝑡=𝑄−1=𝑆𝜀→𝑈.

Then

𝑄𝑡𝐴𝑄=[𝜆,0;0,𝐵]

for some 𝐵∈ℝ𝑛×𝑛: 𝑄𝑡𝐴𝑄 is symmetric, and

𝑄𝑡𝐴𝑄𝑒1=𝑄𝑡(𝐴𝑢)=𝑄𝑡(𝜆𝑢)=𝜆𝑆𝜀→𝑈𝑢=𝜆𝑒1.

By the inductive hypothesis, 𝐵 is orthogonally diagonalizable, 𝐵=𝑅𝐷𝑅𝑡 for an orthogonal 𝑅 and diagonal 𝐷. Therefore

𝑄𝑡𝐴𝑄=(100𝑅)(𝜆00𝐷)(100𝑅)𝑡.

The middle matrix is diagonal and (100𝑅) is orthogonal, since its transpose equals its inverse. Therefore we have constructed an orthogonal diagonalization of 𝐴.

14.3 Homework 1 — submitted work

14.3.1 Source p. 1 — Exercise 20

Find the values of 𝑘 for which the system has infinitely many solutions, no solution, or one solution:

(11−112111𝑘2−5)𝑥=(23𝑘).

The submitted row reduction is (11−12121311𝑘2−5𝑘)→(11−12012100𝑘2−4𝑘−2)→(10−31012100𝑘2−4𝑘−2). For infinitely many solutions, the final row must be zero, so 𝑘2−4=0 and 𝑘−2=0. Thus 𝑘=2.

14.3.2 Source p. 2 — Exercise 20; Exercise 32 begins

For no solution, 𝑘2−4=0 while 𝑘−2≠0, hence 𝑘=−2. For one solution, 𝑘≠−2 and 𝑘≠2, namely (−∞,−2)∪(−2,2)∪(2,∞).

Exercise 32 asks for a polynomial of degree at most two, 𝑓(𝑡)=𝑎+𝑏𝑡+𝑐𝑡2, passing through (1,𝑝), (2,𝑞), and (3,𝑟). The submitted equations are 𝑎+𝑏+𝑐=𝑝, 𝑎+2𝑏+4𝑐=𝑞, and 𝑎+3𝑏+9𝑐=𝑟.

14.3.3 Source p. 3 — Exercise 32

The augmented matrix is reduced as (111𝑝124𝑞139𝑟)→(111𝑝013𝑞−𝑝028𝑟−𝑝), giving 𝑎=3𝑝−3𝑞+𝑟, 𝑏=−5𝑝2+4𝑞−3𝑟2, and 𝑐=𝑝2−𝑞+𝑟2. Therefore a polynomial exists for all choices of 𝑝, 𝑞, and 𝑟.

14.3.4 Source p. 4 — Exercise 34

Find a polynomial of degree at most two which passes through (1,1) and (2,0) and satisfies ∫12𝑓(𝑡)d𝑡=−1. The submitted system is 𝑎+𝑏+𝑐=1, 𝑎+2𝑏+4𝑐=0, and 𝑎+3𝑏2+7𝑐3=−1, with its augmented matrix set up for row reduction.

14.3.5 Source p. 5 — Exercise 34; Exercise 44

The reduction for Exercise 34 ends at (10020010−280019), so the submitted answer is 𝑓(𝑡)=20−28𝑡+9𝑡2.

For Exercise 44, the line through (1,1,1) and (3,5,0) has direction (24−1). The submitted vector equation is (𝑥𝑦𝑧)=(111)+𝑡(24−1), or 𝑥=1+2𝑡, 𝑦=1+4𝑡, 𝑧=1−𝑡, for arbitrary 𝑡. Its equations are 2𝑥−𝑦=−3 and 𝑥+2𝑧=3.

14.3.6 Source p. 6 — Exercise 12

The homogeneous augmented matrix recorded is (20−30770−2160−6−12001−301500−20111021−30870). The first displayed operation divides the first row by 2 before continuing the row reduction.

14.3.7 Source p. 7 — Exercise 12

The submitted reduction clears the first column, then the second column. Its displayed intermediate rows include (10−3207272001−301500−2011100100100), followed by clearing the remaining pivot columns.

14.3.8 Source p. 8 — Exercise 12

The final reduced matrix is (10007210010010000100−53000013100000000). Setting 𝑥5=𝑡 and 𝑥6=𝑟, the submission gives (𝑥1𝑥2𝑥3𝑥4𝑥5𝑥6)=(7𝑡2+𝑟−𝑡5𝑟3−3𝑡−𝑟𝑡𝑟)=𝑡(72−10−310)+𝑟(1053−101).

14.3.9 Source p. 9 — Exercise 36

For a vector 𝑝 perpendicular to (13−1), let 𝑝=(𝑎𝑏𝑐). The condition is 𝑎+3𝑏−𝑐=0. Setting 𝑏=𝑡 and 𝑐=𝑟 gives 𝑝=(−3𝑡+𝑟𝑡𝑟), where 𝑡 and 𝑟 are arbitrary real numbers.

14.3.10 Source p. 10 — Exercise 44

For the traffic-flow diagram, the submitted equations are 300+𝑥=400+𝑦, 300+𝑤=320+𝑥, 150+120=𝑤+𝑧, and 𝑦+𝑧+100=250. They are rearranged as 𝑥−𝑦=100, 𝑤−𝑥=20, 𝑤+𝑧=270, and 𝑦+𝑧=150.

14.3.11 Source p. 11 — Exercise 44

The submitted row reduction reaches (10012700101250001115000000). The free variable is recorded as 𝑧=𝑡.

14.3.12 Source p. 12 — Exercise 44

The submitted solution is (𝑤𝑥𝑦𝑧)=(270−𝑡250−𝑡150−𝑡𝑡). Nonnegativity gives 0≤𝑡≤150. The recorded flow ranges are 𝑤∈[120,270], 𝑥∈[100,250], 𝑦∈[0,150], and 𝑧∈[0,150].

14.3.13 Source p. 13 — Problem 1(a)–(c)

(a) True: “2 is even” and “3 is odd” are true, hence their disjunction is true.

(b) True: 217=7×31, so the conclusion is true; an if–then statement is true regardless of the truth value of its hypothesis.

(c) False: the derivative claim is true, but the submitted work states that tan(𝜋6)=3 is false; thus the biconditional is false.

14.3.14 Source p. 14 — Problem 1(d)–(e); Problem 2(a)

(d) True: the premise “there are infinitely many even primes” is false, since the only even prime is 2, so the implication is true.

(e) True: each right triangle has two acute angles and every positive real number has a positive cube root; the implication is true.

For Problem 2(a), the table in the submission says that a proof proves nothing for a universal statement and that an existential statement is true; a counterexample proves a universal statement false and proves nothing for an existential statement.

14.3.15 Source p. 15 — Problem 2(b)–(d)

(b) True: every prime integer is either even or odd.

(c) False: 2 is a prime which is even, so not every prime is odd; 3 is a prime which is odd, so not every prime is even. Hence the asserted “or” is false.

(d) False: the submitted contradiction uses 𝑥=𝑛−1 to refute the stated universal claim.

14.3.16 Source p. 16 — Problem 2(e)–(g)

(e) True: the submitted argument chooses the integer immediately above 𝑥, so there is an integer 𝑛>𝑥. [TODO(217-Hw-1-finished.pdf, p. 16): one handwritten bracket symbol in the displayed floor/ceiling argument is not visually unambiguous.]

(f) True: every square is a rectangle.

(g) False: 4 has two square roots, 2 and −2, which disproves the uniqueness statement.

14.3.17 Source p. 17 — Problem 3

The submitted negations are:

  • (a) 2 is not even and 3 is not odd.
  • (b) the Riemann hypothesis is true and 217 is prime.
  • (c) the derivative is not 2𝑥 or tan(𝜋6)≠3.
  • (d) there are infinitely many even primes, and 10 is not even or 1010 is not odd.
  • (e) every right triangle in ℝ2 has two acute angles, and some real number has no positive cube root.
  • (f) ∀𝑛∈ℕ there exists 𝑥∈ℝ with 𝑥≥𝑛.
  • (g) all squares are not rectangles.

14.3.18 Source p. 18 — Problem 4

The submitted converses and contrapositives are:

  • (a) Converse: “If something exists, it can think.” Contrapositive: “If something does not exist, it cannot think.”
  • (b) Converse: “If 𝑝2 is irrational, then 𝑝 is irrational.” Contrapositive: “If 𝑝2 is not rational, then 𝑝 is not rational.”
  • (c) Converse: “If 𝑛2+1 is prime, then 𝑛 is a natural number greater than 2 such that its Collatz sequence does not reach 1.” The contraposition is also written in terms of 𝑛2+1 not being prime and the alternatives concerning 𝑛 and its Collatz sequence.

14.3.19 Source p. 19 — Problem 5

(a1) The set is all odd natural numbers. (a2) The graph is the right half of the unit circle centred at the origin, including the boundary.

(b1) The submitted set notation is {(x,y,z) in RR^3 : x^2+y^2+z^2=1}. (b2) The submitted set notation is {sqrt(2)n : n in ZZ}.

(c) The submitted truth values are: 2∈ℝ true; 2⊂ℝ false; {sqrt(2)} in RR false; {sqrt(2)} subset RR true; ∅∈ℝ false; ∅⊂ℝ true; ∅∈∅ false; and ∅⊂∅ true.

14.3.20 Source p. 20 — Problem 6(a)

The submitted lists are 1/2 NN = {1/2,1,3/2,2,5/2,3,...}, 1/3 NN = {1/3,2/3,1,4/3,5/3,2,...}, and 3NN = {3,6,9,12,15,18,...}. It records 1/2 NN intersect 1/3 NN = NN, and writes the union beginning {1/3,1/2,2/3,1,4/3,3/2,...}. It also gives 1/2 NN without 1/3 NN = {1/2,3/2,5/2,7/2,9/2,11/2,...} and (3NN)^c = NN without 3NN = {1,2,4,5,7,8,10,...}.

14.3.21 Source p. 21 — Problem 6(b)

The claimed least 𝑛 is 6. For 𝑥∈12ℕ∪13ℕ, the submission writes 𝑥=3𝑚+2𝑝6 (with one of 𝑚,𝑝 allowed to be zero), proving inclusion in 16ℕ. It then rules out 𝑛=1,3,5 because 12 is not in 1𝑛ℕ, and 𝑛=2,4 because 13 is not in 1𝑛ℕ.

14.3.22 Source p. 22 — Problem 7

Let 𝐹(𝑥,𝑡) mean “you can fool 𝑥 at time 𝑡.” The submitted formalization of the recreational statement is (∃𝑡∀𝑥𝐹(𝑥,𝑡))∧(∃𝑥∀𝑡𝐹(𝑥,𝑡))∧¬(∀𝑡∀𝑥𝐹(𝑥,𝑡)).

14.3.23 Source p. 23 — Problem 7

Applying De Morgan’s law, the submitted negation is (∀𝑡∃𝑥¬𝐹(𝑥,𝑡))∨(∀𝑥∃𝑡¬𝐹(𝑥,𝑡))∨(∀𝑡∀𝑥𝐹(𝑥,𝑡)).

The accompanying English reads: “for all time there are some people you cannot fool, or for some time you can fool no people in the world, or for all time you can fool all people. (You can at least achieve one of three things).”

14.4 Homework 2 — submitted work

14.4.1 Source p. 1 — Exercise 26

Let 𝐴 be a 4×3 matrix and assume 𝐴𝑥=𝑏 has a unique solution. The submission records rank(𝐴)=rank(𝐴|𝑏)=3. For 𝐴𝑥=𝑐, it begins the two RREF cases.

14.4.2 Source p. 2 — Exercise 26; Exercise 34 begins

If [𝐴:𝑐] reduces to a form with three pivots, it has one solution. If it has a row (000𝜀) with 𝜀≠0, it has no solution. By Theorem 1.3.1, infinitely many solutions cannot occur because there is no free variable.

Exercise 34 introduces the standard coordinate vectors 𝑒1,𝑒2,𝑒3.

14.4.3 Source p. 3 — Exercise 34

For 𝐴=(𝑎𝑏𝑐𝑑𝑒𝑓𝑔ℎ𝑘), the submitted work writes

𝐴𝑒1=(𝑎𝑑𝑔)=𝑣1, 𝐴𝑒2=(𝑏𝑒ℎ)=𝑣2, and 𝐴𝑒3=(𝑐𝑓𝑘)=𝑣3.

For a matrix 𝐵 with columns 𝑣1,𝑣2,𝑣3, it likewise records 𝐵𝑒𝑖=𝑣𝑖.

14.4.4 Source p. 4 — Exercise 48(a)–(b)

(a) If 𝑥ℎ solves 𝐴𝑥=0 and 𝑥1 solves 𝐴𝑥=𝑏, then 𝐴(𝑥1+𝑥ℎ)=𝐴𝑥1+𝐴𝑥ℎ=𝑏+0=𝑏.

(b) If 𝑥1 and 𝑥2 solve 𝐴𝑥=𝑏, then 𝐴(𝑥2−𝑥1)=𝐴𝑥2−𝐴𝑥1=𝑏−𝑏=0; hence 𝑥2−𝑥1 is a homogeneous solution.

14.4.5 Source p. 5 — Exercise 48(c)

The drawing places the homogeneous solutions on a line through the origin and the particular solution 𝑥1 off that line. The submitted answer is the parallel affine line 𝑥1+𝑥ℎ.

14.4.6 Source p. 6 — Exercise 48(c)

The geometric explanation concludes: all solutions form the line parallel to the homogeneous-solution line through the head of 𝑥1, with its tail at 0.

14.4.7 Source p. 7 — Exercise 6

For 𝑇:ℝ2→ℝ3,

𝑇(𝑥1𝑥2)=𝑥1(123)+𝑥2(456).

The submitted standard matrix is (142536), and the work verifies linearity by the definition cited on Worksheet 4.

14.4.8 Source p. 8 — Exercise 38; Exercise 44 begins

For Exercise 38,

𝑇(2−1)=2𝑣1−𝑣2.

The submitted sketch shows this vector combination. Exercise 44 begins with 𝑇(𝑥) equal to the cross product of 𝑣 and 𝑥.

14.4.9 Source p. 9 — Exercise 44

With 𝑣=(𝑣1𝑣2𝑣3) and 𝑥=(𝑥1𝑥2𝑥3), the work expands

𝑣×𝑥=(𝑣2𝑥3−𝑣3𝑥2𝑣3𝑥1−𝑣1𝑥3𝑣1𝑥2−𝑣2𝑥1)=(0−𝑣3𝑣2𝑣30−𝑣1−𝑣2𝑣10)𝑥.

Thus the submitted matrix for 𝑇 is (0−𝑣3𝑣2𝑣30−𝑣1−𝑣2𝑣10); the work also verifies addition and scalar multiplication.

14.4.10 Source p. 10 — Exercise 46

For 𝐴=(𝑎𝑏𝑐𝑑) and 𝐵=(𝑝𝑞𝑟𝑠), 𝑇(𝑥)=𝐵(𝐴𝑥). The submitted column computation gives

𝑇(𝑒1)=(𝑎𝑝+𝑐𝑞𝑎𝑟+𝑐𝑠) and 𝑇(𝑒2)=(𝑏𝑝+𝑑𝑞𝑏𝑟+𝑑𝑠).

Hence the matrix is (𝑎𝑝+𝑐𝑞𝑏𝑝+𝑑𝑞𝑎𝑟+𝑐𝑠𝑏𝑟+𝑑𝑠).

14.4.11 Source p. 11 — Part B, Problem 1(a)–(b)

(a) 𝑓:[0,4]→[0,18], 𝑓(𝑥)=𝑥2+2, is injective but not surjective. A counterexample to surjectivity is 𝑦=0. For injectivity, 𝑎2+2=𝑏2+2 implies 𝑎=+−∨−−𝑏, and nonnegativity gives 𝑎=𝑏.

(b) 𝑔:ℝ→ℝ, 𝑔(𝑥)=2𝑥−5, is bijective. Surjectivity uses 𝑥=𝑦+52, and 2𝑥1−5=2𝑥2−5 gives injectivity.

14.4.12 Source p. 12 — Part B, Problem 1(c)–(d)

(c) ℎ:ℝ2→ℝ, ℎ(𝑥,𝑦)=2𝑥2+5𝑦2, is neither injective nor surjective: ℎ(1,2)=ℎ(−1,−2)=22, and no negative number is in its image.

(d) 𝑞:ℕ→ℕ sends odd 𝑛 to 𝑛 and even 𝑛 to 𝑛2. It is surjective but not injective: 𝑞(1)=𝑞(2)=1; for a target 𝑦, choose 𝑥=𝑦 when 𝑦 is odd and 𝑥=2𝑦 when 𝑦 is even.

14.4.13 Source p. 13 — Part B, Problem 2(a)–(b)

The submitted truth values are (a) false, (b) true, (c) false, (d) false, (e) true.

For (a), take 𝑓:[−2,2]→[0,4], 𝑓(𝑥)=𝑥2, 𝐴=[−2,−1], and 𝐵=[1,2]. Then A intersect B = emptyset but 4 belongs to both images. The proof of (b) begins by contradiction.

14.4.14 Source p. 14 — Part B, Problem 2(b)–(c)

For (b), if 𝐴 and 𝐵 had a common 𝑎, then 𝑓(𝑎) would lie in both 𝑓[𝐴] and 𝑓[𝐵], contradicting their disjointness.

For (c), the same squaring map with 𝐴=[0,2] gives 𝑓−1[𝑓[𝐴]]=[−2,2]≠𝐴.

14.4.15 Source p. 15 — Part B, Problem 2(d)–(e)

For (d), using the same 𝑓 and 𝐴=[0,2], the submission gets 𝑓[𝑋∖𝐴]=𝑓[−2,0]=[0,4], whereas 𝑌∖𝑓[𝐴]=∅.

For (e), it begins the two inclusions for a bijection 𝑓.

14.4.16 Source p. 16 — Part B, Problem 2(e)

If m in f[A intersect B], then 𝑚=𝑓(𝑥) for some x in A intersect B, so m in f[A] intersect f[B]. Conversely, 𝑚=𝑓(𝑥)=𝑓(𝑦) with 𝑥∈𝐴 and 𝑦∈𝐵; injectivity gives 𝑥=𝑦, thus m in f[A intersect B].

14.4.17 Source p. 17 — Part B, Problem 3(a)

Assume 𝑓(𝑐𝑥)=𝑐𝑓(𝑥). The submission first records 𝑓(0)=0 and 𝑓(−𝑥)=−𝑓(𝑥). If 𝑥+𝑦=0, additivity follows. Otherwise, writing 𝑐=𝑥+𝑦 and applying the assumption to 𝑥𝑥+𝑦 and 𝑦𝑥+𝑦 gives

(𝑥+𝑦)𝑓(𝑥+𝑦)=(𝑥+𝑦)(𝑓(𝑥)+𝑓(𝑦)),

then division yields 𝑓(𝑥+𝑦)=𝑓(𝑥)+𝑓(𝑦).

14.4.18 Source p. 18 — Part B, Problem 3(b)

The submitted example is 𝑓(𝑥)=‖𝑥‖. It records 𝑓(𝑐𝑥)=𝑐𝑓(𝑥), but says it is not additive: with 𝑥=(12) and 𝑦=(22), the displayed norm values give 𝑓(𝑥+𝑦)≠𝑓(𝑥)+𝑓(𝑦).

14.4.19 Source p. 19 — Part B, Problem 4(a)–(b)

For an additive 𝑓, 𝑓(0)=𝑓(0)+𝑓(0), hence 𝑓(0)=0; also 𝑓(−𝑥)=−𝑓(𝑥).

14.4.20 Source p. 20 — Part B, Problem 4(c)–(d) begins

The induction for 𝑓(𝑛𝑥)=𝑛𝑓(𝑥) has base case 𝑛=1 and the inductive step

𝑓((𝑛+1)𝑥)=𝑓(𝑛𝑥+𝑥)=𝑓(𝑛𝑥)+𝑓(𝑥)=(𝑛+1)𝑓(𝑥).

Part (d), for negative integers, begins on this page.

14.4.21 Source p. 21 — Part B, Problem 4(d); recreational part (e)

The work completes the negative-integer case using 𝑓(−𝑥)=−𝑓(𝑥). For the recreational rational case it concludes that 𝑓(𝑞𝑥)=𝑞𝑓(𝑥) for rational 𝑞, using numerator/denominator multiplication and the preceding integer cases.

14.5 Homework 3 — submitted work

14.5.1 Source p. 1 — Exercise 20

Reflection about the 𝑥−𝑧 plane sends (𝑣1𝑣2𝑣3) to (𝑣1−𝑣2𝑣3). The submitted standard matrix is (1000−10001), accompanied by a sketch of the reflected vector.

14.5.2 Source p. 2 — Exercise 38(a)–(c)

(a) Projection onto an arbitrary unit vector 𝑢=(𝑢1𝑢2) has matrix (𝑢12𝑢1𝑢2𝑢1𝑢2𝑢22). Its determinant is 0, so it is not invertible.

(b) A reflection matrix is (𝑎𝑏𝑏−𝑎) with 𝑎2+𝑏2=1; its determinant is −1, so it is invertible.

(c) A rotation matrix is (𝑎−𝑏𝑏𝑎) with 𝑎2+𝑏2=1; its determinant is 𝑎2+𝑏2=1, so it is invertible.

14.5.3 Source p. 3 — Exercise 38(d); Exercise 18 begins

(d) The horizontal and vertical shear matrices are (1𝑘01) and (10𝑘1). Each has determinant 1, so each is invertible.

For Exercise 18, let 𝐴=(23−32) and 𝐵=(𝑎𝑏𝑐𝑑). Equating 𝐴𝐵 and 𝐵𝐴 yields 𝑏=−𝑐 and 𝑎=𝑑, so 𝐵=(𝑎𝑏−𝑏𝑎).

14.5.4 Source p. 4 — Exercise 34

For 𝐴=(1101), the submitted computations are

𝐴2=(1201), 𝐴3=(1301), 𝐴4=(1401), and 𝐴1001=(1100101).

Thus 𝐴𝑘=(1𝑘01) for positive 𝑘. Geometrically, repeated application is a horizontal shear by one unit each time.

14.5.5 Source p. 5 — Exercise 12

For 𝐴=(2500130000120025), the submission applies the invertible-matrix test through row reduction of [𝐴:𝐼4]. The displayed operations first exchange the first two rows and then use pivots to clear the two 2×2 blocks.

14.5.6 Source p. 6 — Exercise 12; Exercise 34 begins

The final augmented matrix is [𝐼4:𝐴−1], with

𝐴−1=(3−500−1200005−200−21).

By Theorem 2.4.5, 𝐴 is invertible.

For a diagonal 𝐴=(𝑎000𝑏000𝑐), the submitted answer says 𝐴 is invertible precisely when 𝑎,𝑏,𝑐≠0, and then 𝐴−1=(1𝑎0001𝑏0001𝑐). A diagonal matrix of arbitrary size is invertible iff every diagonal element is nonzero.

14.5.7 Source p. 7 — Part B, Problem 1(a)–(b)

The source defines trace, determinant, transpose, and symmetric matrix, then asks truth values for transpose claims. The submission marks (a) false and takes 𝐴=(1221) and 𝐵=(1212). It computes 𝐴𝐵=(3636), 𝐵𝑇=(1122), 𝐴𝑇=(1221), and 𝐴𝑇𝐵𝑇=(5544), so (𝐴𝐵)𝑇≠𝐴𝑇𝐵𝑇.

For (b), it marks false using the same matrices and records 𝐴𝐵=𝐴𝑇𝐵𝑇=(5445) as a counterexample to the universal inequality.

14.5.8 Source p. 8 — Part B, Problem 1(c)

The statement (𝐴𝐵)𝑇=𝐵𝑇𝐴𝑇 is marked true. Let 𝐴 be 𝑛×𝑝 and 𝐵 be 𝑝×𝑚. The work writes both matrices by entries and notes that (𝐵𝑇𝐴𝑇) has the same 𝑚×𝑛 shape as (𝐴𝐵)𝑇.

14.5.9 Source p. 9 — Part B, Problem 1(c)–(d)

The 𝑗,𝑖 entry of 𝐵𝑇𝐴𝑇 is computed as

∑𝑘=1𝑝𝑏𝑘𝑗𝑎𝑖𝑘=∑𝑘=1𝑝𝑎𝑖𝑘𝑏𝑘𝑗,

the 𝑗,𝑖 entry of (𝐴𝐵)𝑇. Since 𝑖,𝑗 are arbitrary, (𝐴𝐵)𝑇=𝐵𝑇𝐴𝑇.

For (d), the submission begins induction: for a symmetric 𝐴=(𝑎𝑏𝑏𝑎), 𝐴1=𝐴 is symmetric, and if 𝐴𝑛=(𝑐𝑑𝑑𝑐), then 𝐴𝑛+1=𝐴𝑛𝐴.

14.5.10 Source p. 10 — Part B, Problem 1(d)–(e)

The inductive multiplication is

(𝑐𝑑𝑑𝑐)(𝑎𝑏𝑏𝑎)=(𝑎𝑐+𝑏𝑑𝑎𝑑+𝑏𝑐𝑎𝑑+𝑏𝑐𝑎𝑐+𝑏𝑑),

which is symmetric. Hence 𝐴𝑛 is symmetric for all 𝑛∈ℕ.

(e) is false: 𝐴=(1327) is not symmetric, while 𝐴2=(7241655) is recorded as symmetric in the submitted counterexample.

14.5.11 Source p. 11 — Part B, Problem 2(a)–(c)

(a) True. A 3×3 matrix with a zero row has at most two leading 1s, so rank(𝐴)≤2; by Theorem 2.4.3 it is not invertible.

(b) False. The counterexample is (110110001), whose RREF has rank 2≠3, so it is not invertible.

(c) True. If 𝐴 is an invertible 𝑛×𝑛 matrix, then 𝐴−1𝐴=𝔸−1=𝐼𝑛; therefore 𝐴−1 is invertible.

14.5.12 Source p. 12 — Part B, Problem 2(d)

(d) True. If 𝐴 is invertible, then (𝐴−1)𝑛 is an inverse for 𝐴𝑛. By associativity, the submission writes the products until adjacent 𝐴−1𝐴 pairs become 𝐼𝑛, so both products equal 𝐼𝑛.

14.5.13 Source p. 13 — Part B, Problem 3(a)

If there is an 𝑛×𝑚 matrix 𝐵 with 𝐵𝐴=𝐼𝑛, suppose 𝑥1 and 𝑥2 solve 𝐴𝑥=0. Then 𝐴(𝑥1−𝑥2)=0. Multiplying on the left by 𝐵 gives 𝐵𝐴(𝑥1−𝑥2)=𝐵0=0; hence 𝑥1−𝑥2=0 and 𝑥1=𝑥2. Therefore 𝐴𝑥=0 has a unique solution.

14.5.14 Source p. 14 — Part B, Problem 4(a)

Statement (a) is marked true. Write 𝐴=[𝑣1,𝑣2,…,𝑣𝑚] and 𝐵=[𝑤1,𝑤2,…,𝑤𝑘]. By Theorem 2.3.2,

𝐴𝐵=𝐴[𝑤1,𝑤2,…,𝑤𝑘]=[𝐴𝑤1,𝐴𝑤2,…,𝐴𝑤𝑘].

If 𝑤𝑖=(𝑤1𝑖…𝑤𝑚𝑖), then by Theorem 1.3.8,

𝐴𝑤𝑖=𝑤1𝑖𝑣1+𝑤2𝑖𝑣2+…+𝑤𝑚𝑖𝑣𝑚.

Thus every column of 𝐴𝐵 is a linear combination of the columns of 𝐴.

14.5.15 Source p. 15 — Part B, Problem 4(b)

Statement (b) is false. The counterexample uses 𝐴=(1000) and 𝐵=(1111), so 𝐴𝐵=(1100). Its first column (10) is not a linear combination of the columns (11) and (11) of 𝐵: the submitted RREF shows that the corresponding system is inconsistent.

14.5.16 Source p. 16 — Part B, Problem 5(a)

For a linear 𝑓:ℝ𝑑→ℝ𝑑, the proof by induction has base 𝑛=1, where 𝑓1(𝑥)=𝑓(𝑓0(𝑥))=𝑓(𝑥) is linear. Assuming 𝑓𝑛 is linear, write 𝑓(𝑥)=𝐴𝑥. The key theorem gives a matrix 𝐵 with 𝑓𝑛(𝑥)=𝐵𝑥; hence

𝑓𝑛+1(𝑥)=𝑓(𝑓𝑛(𝑥))=𝑓(𝐵𝑥)=𝐴(𝐵𝑥)=(𝐴𝐵)𝑥,

so it is linear. Thus 𝑓𝑛 is linear for all 𝑛∈ℕ.

14.5.17 Source p. 17 — Part B, Problem 5(a)

The submission restates the inductive conclusion: the base case and inductive step prove that if 𝑓 is a linear transformation, then 𝑓𝑛 is a linear transformation for all 𝑛∈ℕ.

14.5.18 Source p. 18 — Part B, Problem 5(b)

Define 𝑓:ℝ2→ℝ2 by 𝑓(𝑥)=−𝑥 if ‖𝑥‖=2, and 𝑓(𝑥)=𝑥 otherwise. The submission says 𝑓 is not linear: choose 𝑥1,𝑥2 with ‖𝑥1‖=2 and ‖𝑥2‖≠2, then 𝑓(𝑥1+𝑥2)=𝑥1+𝑥2 while 𝑓(𝑥1)+𝑓(𝑥2)=−𝑥1+𝑥2. But 𝑓2(𝑥)=𝑥 for all 𝑥, so 𝑓2 is the identity and is linear.

14.5.19 Source p. 19 — Part B, Problem 5(c)

Let 𝑓(𝑥)=𝐴𝑥. If 𝑓(𝑥)=0 has a unique solution, then 𝐴𝑥=0 has a unique solution; by Theorem 1.3.4, rank(𝐴)=𝑑, hence by Theorem 2.4.3 𝐴 is invertible. Problem 3 has shown that 𝐴𝑛 is invertible for every 𝑛∈ℕ. Since 𝑓𝑛(𝑥)=𝐴𝑛𝑥, Theorem 1.3.4 gives a unique solution to 𝐴𝑛𝑥=0, proving the claim.

14.6 Homework 4 - submitted work

14.6.1 Exercise 28 - inverse of a linear transformation

For

𝑇(𝑥1𝑥2𝑥3𝑥4)=(221383−16−3−2−289725431)(𝑥1𝑥2𝑥3𝑥4),

the standard matrix is

𝐴=(221383−16−3−2−289725431).

The submitted elimination of (𝐴|𝐼4) ends at

(𝐼4|(1−29−25−25−22604−941−112−917−80222)).

Thus

𝐴−1=(1−29−25−25−22604−941−112−917−80222),

and 𝑇−1(𝑥)=𝐴−1𝑥 for all 𝑥∈ℝ4.

14.6.2 Exercise 30 - invertibility

Let 𝐴=(01𝑏−10𝑐−𝑏−𝑐0). By Theorem 2.4.3, 𝐴 is invertible exactly when rref(𝐴)=𝐼3. Row reduction gives

(01𝑏−10𝑐−𝑏−𝑐0)→(10−𝑐01𝑏000).

Therefore 𝐴 is not invertible, regardless of the values of 𝑏,𝑐.

14.6.3 Exercise 42 - permutation matrices

By elementary transformations that change row order, any permutation matrix can be transformed into 𝐼𝑛. Hence its rref is 𝐼𝑛, so it is invertible by Theorem 2.4.3. If 𝐴 is an arbitrary permutation matrix, then

rref(𝐴|𝐼𝑛)=(𝐼𝑛|𝐵)

and 𝐵 is the inverse of 𝐴. Since the calculation only changes row order, every row of 𝐵 is chosen from 𝐼𝑛 without repetition. Thus 𝐵 is again a permutation matrix.

14.6.4 Exercise 6 - kernel

For 𝐴=(111123), the submitted row reduction is

(111|0123|0)→(10−1|0012|0).

Hence

(𝑥1𝑥2𝑥3)=(𝑡−2𝑡𝑡)=𝑡(1−21),𝑡∈ℝ,

so ker(𝐴)=span((1−21)).

14.6.5 Exercise 14 - image

For 𝐴=(123123123),

𝑇(𝑥)=𝐴𝑥=(111)𝑥1+(222)𝑥2+(333)𝑥3=(111)(𝑥1+2𝑥2+3𝑥3).

Therefore im(𝐴)=span((111)).

14.7 Part B

14.7.1 Problem 1 - nilpotent transformations

Let 𝑇:ℝ𝑛→ℝ𝑛 have standard matrix 𝐴.

14.7.1.1 (a)

We prove by induction on 𝑘 that the standard matrix of 𝑇𝑘 is 𝐴𝑘. For 𝑘=1, 𝑇(𝑥)=𝐴𝑥=𝐴1𝑥. Assume 𝑇𝑛(𝑥)=𝐴𝑛𝑥. Using the composition rule and associativity,

𝑇𝑛+1(𝑥)=𝑇(𝑇𝑛(𝑥))=𝑇(𝐴𝑛𝑥)=𝐴(𝐴𝑛𝑥)=𝐴𝑛+1𝑥.

Thus the statement holds for all 𝑘.

14.7.1.2 (b)

Assume that 𝑇 is nilpotent. Then, for some positive integer 𝑘, 𝑇𝑘(𝑥)=0 for all 𝑥∈ℝ𝑛. By part (a), 𝐴𝑘𝑥=0 for all 𝑥. Suppose, for contradiction, that 𝐴 is invertible. Then 𝐴𝑘 is invertible, with inverse (𝐴−1⋅𝐴−1⋅…⋅𝐴−1) (𝑘 factors). Thus rank(𝐴𝑘)=𝑛, its rref is 𝐼𝑛, and the augmented system (𝐴𝑘|0) cannot have a solution for every right-hand side as required. This contradicts 𝐴𝑘𝑥=0 for all 𝑥. Therefore 𝐴 is not invertible.

14.7.1.3 (c)

If 𝑘=1, then 𝑇=0, hence 𝐴=0 and 𝐴−𝐼𝑛=−𝐼𝑛 is invertible. For 𝑘≥2, set

𝐵=𝐼𝑛+𝐴+𝐴2+…+𝐴𝑘−1.

Then

(𝐼𝑛−𝐴)𝐵=𝐼𝑛−𝐴𝑘=𝐼𝑛

and, similarly, 𝐵(𝐼𝑛−𝐴)=𝐼𝑛. Thus 𝐼𝑛−𝐴 is invertible, and so is 𝐴−𝐼𝑛=−(𝐼𝑛−𝐴).

14.7.2 Problem 2 - the vector space ℱ︀(𝑆,𝑉)

For 𝑓,𝑔,ℎ∈ℱ︀(𝑆,𝑉) and 𝑥∈𝑆, pointwise addition gives the vector-space axioms:

(𝑓+𝑔)(𝑥)∈𝑉,(𝑓+𝑔)(𝑥)+ℎ(𝑥)=𝑓(𝑥)+(𝑔(𝑥)+ℎ(𝑥)),𝑓(𝑥)+𝑔(𝑥)=𝑔(𝑥)+𝑓(𝑥),

and the function 𝑝(𝑥)=0𝑉 is an additive identity. For each 𝑓, the function 𝑛(𝑥)=−𝑓(𝑥) is its additive inverse. For scalars 𝛼,𝛽,

𝛼(𝑓+𝑔)(𝑥)=𝛼𝑓(𝑥)+𝛼𝑔(𝑥),(𝛼+𝛽)𝑓(𝑥)=𝛼𝑓(𝑥)+𝛽𝑓(𝑥),

𝛼(𝛽𝑓(𝑥))=(𝛼𝛽)𝑓(𝑥),1𝑓(𝑥)=𝑓(𝑥).

All expressions are defined in 𝑉, so ℱ︀(𝑆,𝑉) is a vector space.

The element 0ℱ︀(𝑆,𝑉) is the function 𝑥↦0𝑉, whereas 0𝑉 is an element of 𝑉; they are different elements although the function value is always 0𝑉.

ℱ︀(𝑉,𝑆) is not necessarily a vector space. For example, take 𝑆={1,2} with 1+2=3, which is not in 𝑆. The constant functions 𝑓(𝑣)=1 and 𝑔(𝑣)=2 lie in ℱ︀(𝑉,𝑆), but 𝑓+𝑔 would have value 3, hence is not a function into 𝑆.

Finally,

𝒫︀⊂ℱ︀(ℝ,ℝ),𝒫︀𝑛⊂ℱ︀(ℝ,ℝ),𝐶∞⊂ℱ︀(ℝ,ℝ),

where 𝒫︀ is the set of all real polynomial functions, 𝒫︀𝑛 those of degree at most 𝑛, and 𝐶∞ the infinitely differentiable real functions.

14.7.3 Problem 3 - polynomial transformation

Let 𝑇(𝑝)(𝑡)=𝑝′(𝑡)+𝑝(0).

14.7.3.1 (a)

For 𝑝1,𝑝2∈𝒫︀,

𝑇(𝑝1+𝑝2)=(𝑝1+𝑝2)′(𝑡)+(𝑝1+𝑝2)(0)=𝑇(𝑝1)+𝑇(𝑝2),

and for 𝑘∈ℝ,

𝑇(𝑘𝑝)(𝑡)=𝑘𝑝′(𝑡)+𝑘𝑝(0)=𝑘𝑇(𝑝)(𝑡).

Thus 𝑇 is linear.

14.7.3.2 (b)

𝑇𝑛:𝒫︀𝑛→𝒫︀𝑛 is not surjective: 𝑝(𝑡)=𝑡𝑛 is in the target, but no element of 𝒫︀𝑛 maps to it because differentiation lowers the degree by one. It is not injective: for

𝑝1(𝑡)=1+2𝑡+𝑡2,𝑝2(𝑡)=2+𝑡+𝑡2,

we have 𝑇𝑛(𝑝1)=3+2𝑡=𝑇𝑛(𝑝2) although 𝑝1≠𝑝2.

14.7.3.3 (c)

𝑇 is not injective by the same counterexample. It is surjective: if

𝑝(𝑡)=𝑘+𝑎1𝑡+𝑎2𝑡2+…+𝑎𝑚𝑡𝑚,

take

𝑞(𝑡)=𝑘𝑡+12𝑎1𝑡2+13𝑎2𝑡3+…+1𝑚+1𝑎𝑚𝑡𝑚+1.

Then 𝑞′(𝑡)+𝑞(0)=𝑝(𝑡).

14.7.4 Problem 4 - left multiplication

For 𝐿𝐴:ℝ𝑛×𝑛→ℝ𝑛×𝑛, 𝐿𝐴(𝐵)=𝐴𝐵:

14.7.4.1 (a)

For 𝐵,𝐶∈ℝ𝑛×𝑛 and 𝑘∈ℝ,

𝐿𝐴(𝐵+𝐶)=𝐴(𝐵+𝐶)=𝐴𝐵+𝐴𝐶=𝐿𝐴(𝐵)+𝐿𝐴(𝐶),

𝐿𝐴(𝑘𝐵)=𝐴(𝑘𝐵)=𝑘𝐴𝐵=𝑘𝐿𝐴(𝐵).

So 𝐿𝐴 is linear.

14.7.4.2 (b)

If 𝐴 is invertible and 𝐿𝐴(𝐵1)=𝐿𝐴(𝐵2), multiplication by 𝐴−1 gives 𝐵1=𝐵2, so 𝐿𝐴 is injective and hence invertible. Conversely, if 𝐿𝐴 is invertible, it is surjective. Thus some 𝐶 satisfies 𝐿𝐴(𝐶)=𝐼𝑛, so 𝐴𝐶=𝐼𝑛 and 𝐴 is invertible.

14.7.4.3 (c)

If 𝐿𝐴=𝐿𝐵, then evaluating both maps at 𝐼𝑛 gives 𝐴=𝐿𝐴(𝐼𝑛)=𝐿𝐵(𝐼𝑛)=𝐵. Hence 𝐴↦𝐿𝐴 is injective.

14.7.4.4 (d)

The map 𝐿:ℝ𝑛×𝑛→ℱ︀ is not surjective. The constant function 𝑓(𝐶)=𝐼𝑛 is in ℱ︀, but if 𝐿(𝐴)=𝑓, then 𝐴𝐶=𝐼𝑛 for all 𝐶. Taking 𝐶=0𝑛×𝑛 is impossible.

14.7.5 Problem 5 - rotations and projection

For 𝑇=Rot−80°∘Proj𝑦∘Rot35°:

14.7.5.1 (a)

Rot35° has image ℝ2. Projection onto the 𝑦-axis has image the 𝑦-axis, and rotation clockwise by 80° sends this to a line 80° clockwise from the 𝑦-axis. Thus the angle between im(𝑇) and the 𝑥-axis is 90°−80°=10°.

14.7.5.2 (b)

The final rotation does not affect the kernel. Projection kills exactly the 𝑥-axis, and undoing the initial 35° counter-clockwise rotation gives a kernel line 35° counter-clockwise from the 𝑥-axis.

14.7.5.3 (c)

For 𝑇𝜑,𝜃=Rot𝜑∘Proj𝑦∘Rot𝜃, the image is a line −𝜑 from the 𝑦-axis and the kernel is a line 𝜃 from the 𝑥-axis. They agree when

𝜑=𝜋2−𝜃+𝑘𝜋,

equivalently 𝜃−𝜑=𝜋2+𝑘𝜋 for 𝑘∈ℤ.

14.8 Homework 5 - submitted work

14.8.1 Exercise 56 - linear independence

Rearrange the four given vectors as

𝑣1=(𝑒10000),𝑣2=(𝑘𝑚1000),𝑣3=(𝑎𝑏𝑐𝑑10),𝑣4=(𝑓𝑔ℎ𝑖𝑗1).

Each 𝑣𝑖 has an entry where all preceding vectors have 0 and it has a nonzero entry. Thus, in a relation 𝑐1𝑣1+𝑐2𝑣2+𝑐3𝑣3+𝑐4𝑣4=0, the sixth coordinate forces 𝑐4=0, and the same argument forces 𝑐3,𝑐2,𝑐1=0 one by one. The vectors are linearly independent for all 𝑎,𝑏,…,𝑚∈ℝ.

14.8.2 Exercise 33 - hyperplanes

For 𝑐1𝑥1+…+𝑐𝑛𝑥𝑛=0, let 𝐴=(𝑐1𝑐2…𝑐𝑛). The hyperplane is ker(𝑇𝐴), and the image of 𝑇𝐴:ℝ𝑛→ℝ is nonzero because some 𝑐𝑖≠0. Hence its image has dimension 1, and rank-nullity gives

dim(𝑉)=𝑛−1.

Thus a hyperplane in ℝ3 is a plane, and a hyperplane in ℝ2 is a line.

14.8.3 Exercise 63 - equal-dimensional nested subspaces

Let (𝑣1,…,𝑣𝑚) be a basis of 𝑉, with 𝑉⊂𝑊 and dim(𝑉)=dim(𝑊)=𝑚. The vectors 𝑣1,…,𝑣𝑚 lie in 𝑊 and are linearly independent. By Theorem 3.3.4 they form a basis of 𝑊. Every 𝑤∈𝑊 is therefore a linear combination of the 𝑣𝑖, so 𝑤∈𝑉. Thus 𝑊⊂𝑉, and 𝑉=𝑊.

14.8.4 Exercise 12 - arithmetic sequences

Let 𝑆 be the set of all arithmetic sequences. It contains the zero sequence. If

𝑚=(𝑚0,𝑚0+𝑘,𝑚0+2𝑘,…),𝑛=(𝑛0,𝑛0+𝑙,𝑛0+2𝑙,…),

then

𝑚+𝑛=(𝑚0+𝑛0,𝑚0+𝑛0+(𝑘+𝑙),𝑚0+𝑛0+2(𝑘+𝑙),…)∈𝑆.

For 𝑟∈ℝ,

𝑟(𝑚0,𝑚0+𝑘,𝑚0+2𝑘,…)=(𝑟𝑚0,𝑟𝑚0+𝑟𝑘,𝑟𝑚0+2𝑟𝑘,…)∈𝑆.

Hence 𝑆 is a subspace.

14.8.5 Exercise 28 - commuting 2×2 matrices

Let 𝐴=(𝑎𝑏𝑐𝑑) and 𝐵=(1101). The equation 𝐴𝐵=𝐵𝐴 gives

(𝑎𝑎+𝑏𝑐𝑐+𝑑)=(𝑎+𝑐𝑏+𝑑𝑐𝑑),

so 𝑐=0 and 𝑎=𝑑. Therefore

𝑆={(𝑎𝑏0𝑎)|𝑎,𝑏∈ℝ}={𝑎(1001)+𝑏(0100)|𝑎,𝑏∈ℝ}.

The displayed matrices are linearly independent, so they are a basis and dim(𝑆)=2.

14.9 Part A - Problem 6

For each diagram, the submitted dependent triples are:

(a) (𝑣1,𝑣2,𝑣3), (𝑣1,𝑣2,𝑣5), (𝑣1,𝑣2,𝑣4), (𝑣1,𝑣3,𝑣5), (𝑣1,𝑣3,𝑣4), (𝑣2,𝑣3,𝑣4), (𝑣2,𝑣3,𝑣5), (𝑣3,𝑣4,𝑣5), (𝑣2,𝑣4,𝑣5), (𝑣1,𝑣4,𝑣5) (10 sets). (b) (𝑣1,𝑣2,𝑣3), (𝑣1,𝑣2,𝑣5), (𝑣1,𝑣2,𝑣4), (𝑣1,𝑣3,𝑣5), (𝑣2,𝑣3,𝑣4), (𝑣3,𝑣4,𝑣5), (𝑣2,𝑣4,𝑣5), (𝑣1,𝑣4,𝑣5) (8 sets). (c) (𝑣1,𝑣2,𝑣3), (𝑣1,𝑣2,𝑣5), (𝑣1,𝑣3,𝑣5), (𝑣2,𝑣3,𝑣4), (𝑣3,𝑣4,𝑣5), (𝑣2,𝑣4,𝑣5) (6 sets). (d) (𝑣1,𝑣2,𝑣3), (𝑣1,𝑣3,𝑣5), (𝑣1,𝑣3,𝑣4), (𝑣2,𝑣3,𝑣4), (𝑣2,𝑣3,𝑣5), (𝑣2,𝑣4,𝑣5).

14.10 Part B

14.10.1 Problem 1 - images of independent lists

14.10.1.1 (a)

False. Let 𝑇:ℝ2→ℝ2 be 𝑇(𝑥)=(0000)𝑥. The vectors (10),(01) are linearly independent, but their images are both 0, so the image list is linearly dependent.

14.10.1.2 (b)

True. Assume 𝑌=(𝑇(𝑥1),…,𝑇(𝑥𝑘)) is linearly independent and 𝑑1𝑥1+…+𝑑𝑘𝑥𝑘=0𝑉. Then

𝑑1𝑇(𝑥1)+…+𝑑𝑘𝑇(𝑥𝑘)=𝑇(0𝑉)=0𝑊.

Independence of 𝑌 gives 𝑑1=…=𝑑𝑘=0, so 𝑋 is linearly independent.

14.10.2 Problem 2 - prescribed kernel and image

The rref required by

ker(𝑇)={𝑥∈ℝ5|𝑥1=5𝑥2,𝑥3=7𝑥4}

is

(1−5000001−7000000).

The target image has basis (101),(010). Choosing the first and second nonredundant columns accordingly gives

𝐴=(1−5000001−701−5000),

and 𝑇(𝑥)=𝐴𝑥 is one solution.

The transformation is not unique. For example, elementary transformations preserve the rref, and

𝐴′=(5−25000001−705−25000)

has the same required kernel and image but is different from 𝐴.

14.10.3 Problem 3 - maps defined on a basis

14.10.3.1 (a)

Let ℬ︀=(𝑥1,…,𝑥𝑛) be a basis of 𝑋, and write 𝑣=𝑐1𝑥1+…+𝑐𝑛𝑥𝑛. Define

𝑇(𝑣)=𝑐1𝑇(𝑥1)+…+𝑐𝑛𝑇(𝑥𝑛)=𝑐1𝑦1+…+𝑐𝑛𝑦𝑛.

For 𝑣1=∑𝑑𝑖𝑥𝑖, 𝑣2=∑𝑒𝑖𝑥𝑖, this rule gives

𝑇(𝑣1+𝑣2)=∑(𝑑𝑖+𝑒𝑖)𝑇(𝑥𝑖)=𝑇(𝑣1)+𝑇(𝑣2)

and 𝑇(𝑘𝑣1)=𝑘𝑇(𝑣1), so it is linear. If 𝑇′ has the same values on the basis, then 𝑇′(𝑣)=∑𝑐𝑖𝑇′(𝑥𝑖)=∑𝑐𝑖𝑦𝑖=𝑇(𝑣), so it is unique.

14.10.3.2 (b)

Let dim(𝑋)=𝑛 and let (𝑢1,…,𝑢𝑘) be a basis of 𝑈. Extend it to a basis (𝑢1,…,𝑢𝑘,𝑤𝑘+1,…,𝑤𝑛) of 𝑋. Since dim(𝑉)=𝑛−𝑘, choose a basis (𝑣1,…,𝑣𝑛−𝑘) of 𝑉 and define

𝑇𝑈,𝑉(𝑢𝑖)=0,𝑇𝑈,𝑉(𝑤𝑘+𝑗)=𝑣𝑗.

By part (a), this is a valid linear transformation. Its image is 𝑉 and its kernel is 𝑈.

14.10.3.3 (c)

The map is not unique: the construction depends on an arbitrarily chosen basis of 𝑉. Choosing a different basis can give different images for the 𝑤𝑘+𝑗 while retaining the required kernel and image.

14.10.4 Problem 4 - ranks and nullities of a composition

14.10.4.1 (a)

True. Since im(𝑆∘𝑇)⊂im(𝑆),

rank(𝑆∘𝑇)=dim(im(𝑆∘𝑇))≤rank(𝑆).

14.10.4.2 (b)

True. View the composition in two stages. First 𝑇:𝑈→𝑉; then 𝑆:im(𝑇)→𝑊. Rank-nullity for the restricted second map gives

rank(𝑆∘𝑇)=rank(𝑇)−dim(ker(𝑆′))≤rank(𝑇).

14.10.4.3 (c)

True. Rank-nullity yields

rank(𝑇)+nullity(𝑇)=rank(𝑆∘𝑇)+nullity(𝑆∘𝑇).

Part (b) then implies nullity(𝑆∘𝑇)≥nullity(𝑇).

14.10.4.4 (d)

False. If 𝑇 is surjective, then 𝑆(𝑉)=0𝑊, so nullity(𝑆)=dim(𝑉) and nullity(𝑆∘𝑇)=dim(𝑈). When dim(𝑈)<dim(𝑉), the claimed inequality fails.

14.10.5 Problem 5 - symmetric and skew-symmetric matrices

For 𝑇(𝐴)=𝐴+𝐴𝑇:

14.10.5.1 (a)

𝑇(𝐴1+𝐴2)=(𝐴1+𝐴2)+(𝐴1+𝐴2)𝑇=𝑇(𝐴1)+𝑇(𝐴2), and 𝑇(𝑘𝐴)=𝑘𝐴+(𝑘𝐴)𝑇=𝑘𝑇(𝐴), so 𝑇 is linear.

14.10.5.2 (b)

If 𝐴∈ker(𝑇), then 𝐴𝑇=−𝐴, so 𝐴∈Skew𝑛. Conversely, 𝐵𝑇=−𝐵 implies 𝑇(𝐵)=0, so ker(𝑇)=Skew𝑛. Also 𝐶=𝑀+𝑀𝑇 satisfies 𝐶𝑇=𝐶, whence im(𝑇)⊂Sym𝑛. If 𝐷∈Sym𝑛, choose 𝑁=12𝐷; then 𝑁+𝑁𝑇=𝐷. Therefore im(𝑇)=Sym𝑛.

14.10.5.3 (c)

Both are subspaces. Each contains the zero matrix. If 𝐴𝑇=−𝐴 and 𝐵𝑇=−𝐵, then (𝐴+𝐵)𝑇=−(𝐴+𝐵) and (𝑘𝐴)𝑇=−𝑘𝐴; this proves the subspace conditions for Skew𝑛. Replacing −𝐴,−𝐵 by 𝐴,𝐵 gives the same argument for Sym𝑛.

14.10.5.4 (d)

There are 𝑛2 free entries in an arbitrary 𝑛×𝑛 matrix. In a symmetric matrix, entries below the diagonal mirror entries above it, while the diagonal entries are free. Thus

dim(Sym𝑛)=𝑛2−𝑛2+𝑛=𝑛2+𝑛2.

For a skew-symmetric matrix, the lower entries are the negations of the upper entries and every diagonal entry is zero. Thus

dim(Skew𝑛)=𝑛2−𝑛2.

14.11 Homework 6 - submitted work

14.11.1 Exercise 50 - hexagonal coordinates

For the basis ℬ︀=(𝑣,𝑤) in the hexagonal tiling,

[OP⃗]ℬ︀=[2𝑣+𝑤]ℬ︀=(21),

[OQ⃗]ℬ︀=[𝑣+2𝑤]ℬ︀=(12).

The point with [OR⃗]ℬ︀=(32) is the center of a tile. Further,

(1713)=8(21)+(12)+(03).

Moving by the first two summands means moving in parallel to OQ⃗ and OP⃗ by whole tile lengths, which does not change whether a point is a vertex or center. Since (03) is a vertex, (1713) is a vertex.

14.11.2 Exercise 70 - upper triangular coordinate matrix

There is no basis ℬ︀=(𝑣1,𝑣2) of ℝ2 whose ℬ︀-matrix for

𝑇(𝑥)=(0−110)𝑥

is upper triangular. Suppose, for a contradiction, that

[𝑇]ℬ︀=(𝑎𝑏0𝑐).

Then the generalized key theorem gives

(0−110)𝑣1=𝑎𝑣1.

Writing 𝑣1=(𝑥𝑦) yields

−𝑦=𝑎𝑥,𝑥=𝑎𝑦,(𝑎−1)𝑥=(−𝑎−1)𝑦.

Thus 𝑥=𝑦=0, since 𝑎−1 and −𝑎−1 cannot both vanish. This is impossible because 0 cannot be a basis vector.

14.11.3 Exercise 58 - the solutions of 𝑓″=−𝑓

14.11.3.1 (a)

For 𝑔∈𝑉, 𝑔″=−𝑔. Let

𝑓(𝑥)=𝑔(𝑥)2+𝑔′(𝑥)2.

Then

𝑓′(𝑥)=2𝑔(𝑥)𝑔′(𝑥)+2𝑔′(𝑥)𝑔″(𝑥)=2𝑔(𝑥)𝑔′(𝑥)−2𝑔(𝑥)𝑔′(𝑥)=0,

so 𝑓 is constant.

14.11.3.2 (b)

If 𝑔(0)=𝑔′(0)=0, the constant from part (a) is 𝑘=𝑔(0)2+𝑔′(0)2=0. Therefore 𝑔(𝑥)2+𝑔′(𝑥)2=0 for all 𝑥, and 𝑔(𝑥)=𝑔′(𝑥)=0 for all 𝑥.

14.11.3.3 (c)

𝑉 is a vector space; moreover, (sin𝑥)″=−sin𝑥 and (cos𝑥)″=−cos𝑥. Hence for 𝑓∈𝑉,

𝑔(𝑥)=𝑓(𝑥)−𝑓(0)cos𝑥−𝑓′(0)sin𝑥

is in 𝑉. We have 𝑔(0)=0 and

𝑔′(𝑥)=𝑓′(𝑥)+𝑓(0)sin𝑥−𝑓′(0)cos𝑥,𝑔′(0)=0.

Part (b) gives 𝑔=0, so

𝑓(𝑥)=𝑓(0)cos𝑥+𝑓′(0)sin𝑥.

Thus (cos𝑥,sin𝑥) spans 𝑉.

14.11.4 Exercise 46 - multiplication by 𝑡−1

For 𝑇(𝑓(𝑡))=(𝑡−1)𝑓(𝑡),

𝑇(𝑓+𝑔)=(𝑡−1)(𝑓+𝑔)=𝑇(𝑓)+𝑇(𝑔),

𝑇(𝑘𝑓)=(𝑡−1)𝑘𝑓=𝑘𝑇(𝑓).

Thus 𝑇 is linear. It is not an isomorphism because it is not surjective: a nonzero constant target polynomial cannot be (𝑡−1)𝑓(𝑡) for a polynomial 𝑓.

14.11.5 Exercise 68 - isomorphism condition

For 𝑀=(𝑎𝑏𝑐𝑑),

𝑇(𝑀)=(5𝑎𝑏5𝑐𝑑)−(2𝑎2𝑏𝑘𝑐𝑘𝑑)=(3𝑎−𝑏(5−𝑘)𝑐(1−𝑘)𝑑).

The source and target have equal dimension, so 𝑇 is an isomorphism exactly when it is injective, equivalently when ker(𝑇)={0}. This holds for 𝑘≠1,5. For 𝑘=1 or 𝑘=5, the kernel has dimension 1, so 𝑇 is not an isomorphism.

14.12 Part B

14.12.1 Problem 1 - coefficient map

Let 𝑇:ℝ𝑛→𝑉 be defined by

𝑇((𝑐1⋮𝑐𝑛))=𝑐1𝑣1+…+𝑐𝑛𝑣𝑛.

14.12.1.1 (a)

For coefficient columns 𝑎=(𝑎𝑖) and 𝑐=(𝑐𝑖),

𝑇(𝑎+𝑐)=∑(𝑎𝑖+𝑐𝑖)𝑣𝑖=𝑇(𝑎)+𝑇(𝑐),

and 𝑇(𝑘𝑎)=∑𝑘𝑎𝑖𝑣𝑖=𝑘𝑇(𝑎). Hence 𝑇 is linear.

14.12.1.2 (b)

If 𝑇 is injective and 𝑐1𝑣1+…+𝑐𝑛𝑣𝑛=0, then

𝑇((𝑐1⋮𝑐𝑛))=𝑇((0⋮0)),

so 𝑐𝑖=0 for every 𝑖. The list is linearly independent. Conversely, if (𝑣1,…,𝑣𝑛) is linearly independent and 𝑇(𝑎)=𝑇(𝑏), then

(𝑎1−𝑏1)𝑣1+…+(𝑎𝑛−𝑏𝑛)𝑣𝑛=0.

Thus 𝑎𝑖=𝑏𝑖 for all 𝑖, and 𝑇 is injective.

14.12.1.3 (c)

If 𝑇 is surjective, every 𝑣∈𝑉 equals 𝑇((𝑎1⋮𝑎𝑛))=𝑎1𝑣1+…+𝑎𝑛𝑣𝑛, so the list spans 𝑉. Conversely, if it spans 𝑉, each 𝑣∈𝑉 has this form and is in the image of 𝑇. Therefore 𝑇 is surjective.

14.12.1.4 (d)

An isomorphism is injective and surjective, so by (b) and (c) its list is linearly independent and spans 𝑉: it is an ordered basis. Conversely, an ordered basis gives both properties, so the linear map 𝑇 is a bijection and hence an isomorphism.

14.12.2 Problem 2 - coordinate matrices for symmetrization

Let 𝑇(𝐴)=12(𝐴+𝐴𝑇) for 𝐴=(𝑎𝑏𝑐𝑑).

14.12.2.1 (a)

𝑇(𝐴)=(𝑎𝑏+𝑐2𝑏+𝑐2𝑑).

With [𝐴]ℰ︀=(𝑎𝑏𝑐𝑑), the ℰ︀-matrix is

[𝑇]ℰ︀=(10000121200121200001).

14.12.2.2 (b)

For 𝒞︀=((0110),(1000),(0001),(01−10)),

[𝑇]𝒞︀=(1000010000100000).

14.12.2.3 (c)

Solving [𝑇]ℰ︀(𝑎𝑏𝑐𝑑)=0 gives

ker([𝑇]ℰ︀)={𝑟(0−110)|𝑟∈ℝ}.

14.12.2.4 (d)

The corresponding subspace of ℝ2×2 is

{𝑟(0−110)|𝑟∈ℝ},

with basis (0−110).

14.12.2.5 (e)

Solving [𝑇]𝒞︀(𝑎𝑏𝑐𝑑)=0 gives

ker([𝑇]𝒞︀)={𝑟(0001)|𝑟∈ℝ}.

14.12.2.6 (f) and (g)

The coordinate isomorphism sends

(𝑥𝑦𝑧𝑤)↦(𝑦𝑥+𝑤𝑥−𝑤𝑧).

Hence the image of the 𝒞︀-coordinate kernel is

{𝑟(01−10)|𝑟∈ℝ},

the same subspace as in part (d). Both are ker(𝑇).

14.12.2.7 (h)

Using 𝒞︀-coordinates, the image is spanned by the first three coordinate vectors. A basis is therefore

((0110),(1000),(0001)).

14.12.3 Problem 3 - a trigonometric vector space

Let

𝑓1=1,𝑓2=sin(2𝑥),𝑓3=cos(2𝑥),𝑓4=sin2(𝑥),𝑓5=cos2(𝑥),𝑓6=sin𝑥cos𝑥,

and 𝑉=Span(𝑓1,…,𝑓6), ℬ︀=(𝑓1,𝑓2,𝑓4).

14.12.3.1 (a)

For 𝑓=𝑎1+𝑎2sin(2𝑥)+𝑎3cos(2𝑥)+𝑎4sin2(𝑥)+𝑎5cos2(𝑥)+𝑎6sin𝑥cos𝑥, the identities cos(2𝑥)=1−2sin2(𝑥), cos2(𝑥)=1−sin2(𝑥), and sin𝑥cos𝑥=12sin(2𝑥) give

𝑓=(𝑎1+𝑎3+𝑎5)+(𝑎2+12𝑎6)sin(2𝑥)+(𝑎4−2𝑎3−𝑎5)sin2(𝑥).

So (𝑓1,𝑓2,𝑓4) spans 𝑉. If 𝑏1+𝑏2sin(2𝑥)+𝑏4sin2(𝑥)=0, evaluate at 𝑥=𝜋, 𝑥=𝜋2, and 𝑥=𝜋4 to get 𝑏1=𝑏4=𝑏2=0. Thus ℬ︀ is an ordered basis.

14.12.3.2 (b)
[𝑓1]ℬ︀=(100),[𝑓2]ℬ︀=(010),[𝑓3]ℬ︀=(10−2),[𝑓4]ℬ︀=(001),[𝑓5]ℬ︀=(10−1),[𝑓6]ℬ︀=(0120).
14.12.3.3 (c)

For 𝑓=𝑎1+𝑎2sin(2𝑥)+𝑎3sin2(𝑥),

𝑓′=2𝑎2cos(2𝑥)+𝑎3sin(2𝑥)=2𝑎2+𝑎3sin(2𝑥)−4𝑎2sin2(𝑥)∈𝑉.

Thus 𝑉 is closed under differentiation.

14.12.3.4 (d)

𝑇(𝑓)=𝑓′+2𝑓 has

[𝑇(𝑓)]ℬ︀=(2𝑎1+2𝑎22𝑎2+𝑎3−4𝑎2+2𝑎3),

so

[𝑇]ℬ︀=(2200210−42).

14.12.3.5 (e)

Row reduction of ([𝑇]ℬ︀|𝐼3) gives

[𝑇]ℬ︀−1=(12−1418014−1801214).

Therefore

𝑇−1(𝑎1+𝑎2sin(2𝑥)+𝑎3sin2(𝑥))=(12𝑎1−14𝑎2+18𝑎3)+(14𝑎2−18𝑎3)sin(2𝑥)+(12𝑎2+14𝑎3)sin2(𝑥).

14.12.3.6 (f)

The coordinate vector of 4+8sin2(𝑥) is (408). Applying the inverse matrix gives (3−12), so

𝑓(𝑥)=3−sin(2𝑥)+2sin2(𝑥).

14.12.4 Problem 4 - products of vector spaces

14.12.4.1 (a)

If 0𝑋 and 0𝑌 are the zero vectors of 𝑋 and 𝑌, the zero vector of 𝑋×𝑌 is (0𝑋,0𝑌).

14.12.4.2 (b)

Let (𝑥1,…,𝑥𝑚) be a basis of 𝑋 and (𝑦1,…,𝑦𝑛) a basis of 𝑌. For (𝑎,𝑏)∈𝑋×𝑌, write

𝑎=∑𝑎𝑖𝑥𝑖,𝑏=∑𝑏𝑗𝑦𝑗.

Then

(𝑎,𝑏)=∑𝑎𝑖(𝑥𝑖,0𝑌)+∑𝑏𝑗(0𝑋,𝑦𝑗),

so the listed vectors span. If their linear combination is (0𝑋,0𝑌), then ∑𝑎𝑖𝑥𝑖=0𝑋 and ∑𝑏𝑗𝑦𝑗=0𝑌. Independence of the two bases forces all coefficients to vanish. Therefore

((𝑥1,0𝑌),…,(𝑥𝑚,0𝑌),(0𝑋,𝑦1),…,(0𝑋,𝑦𝑛))

is a basis of 𝑋×𝑌.

14.12.4.3 (c)

The basis in (b) has 𝑚+𝑛 vectors, so

dim(𝑋×𝑌)=dim(𝑋)+dim(𝑌).

14.12.5 Problem 5 - sum and intersection

Let 𝑇:𝑋×𝑌→𝑋+𝑌 be 𝑇(𝑥,𝑦)=𝑥+𝑦.

14.12.5.1 (a)

𝑇((𝑥1,𝑦1)+(𝑥2,𝑦2))=𝑥1+𝑥2+𝑦1+𝑦2=𝑇(𝑥1,𝑦1)+𝑇(𝑥2,𝑦2), and 𝑇(𝑘(𝑥,𝑦))=𝑘𝑇(𝑥,𝑦), so 𝑇 is linear. Each 𝑧∈𝑋+𝑌 has the form 𝑧=𝑥+𝑦=𝑇(𝑥,𝑦), so 𝑇 is surjective.

14.12.5.2 (b)

If 𝑥+𝑦=0, then 𝑥=−𝑦, so it belongs to both 𝑋 and 𝑌. Hence

ker(𝑇)={(𝑎,−𝑎)|𝑎∈𝑋∩𝑌}.

The map 𝑇1:ker(𝑇)→𝑋∩𝑌, (𝑎,−𝑎)↦𝑎, is linear, injective, and surjective; hence it is an isomorphism.

14.12.5.3 (c)

Since ker(𝑇) is isomorphic to 𝑋∩𝑌 and 𝑇 is surjective, rank-nullity with part 4(c) gives

dim(𝑋+𝑌)+dim(𝑋∩𝑌)=dim(𝑋)+dim(𝑌).

14.12.5.4 (d)

For three-dimensional subspaces of ℝ5, 𝑋∩𝑌={0} would give dim(𝑋+𝑌)=6, contradicting dim(𝑋+𝑌)≤5. Thus it is impossible. In ℝ6 it is possible; for example,

𝑋={(𝑎𝑏𝑐000)|𝑎,𝑏,𝑐∈ℝ},𝑌={(000𝑥𝑦𝑧)|𝑥,𝑦,𝑧∈ℝ}.

Then 𝑋+𝑌=ℝ6 and 𝑋∩𝑌={0}.

14.13 Homework 7 — submitted work

15 Part A

15.1 4.3 Exercise 14

For 𝑇(𝑀)=(1122)𝑀 relative to ℬ︀=((10−10),(010−1),(1020),(0102)), the submission forms [𝑇]ℬ︀ from [𝑇(𝑏𝑖)]ℬ︀. It finds

𝑇(𝑏1)=𝑇(𝑏2)=(0000),𝑇(𝑏3)=(3060),𝑇(𝑏4)=(0306),

so

[𝑇]ℬ︀=(0000000000300003)↦(0010000100000000).

Hence

[ker𝑇]𝑀=span((1000),(0100)),

[im𝑇]𝑀=span((0010),(0001)).

A basis for the kernel is ((10−10),(010−1)); a basis for the image is ((1020),(0102)); and rank(𝑇)=2.

15.2 4.3 Exercise 28

For 𝑇(𝑓(𝑡))=𝑓(2𝑡−1) and ℬ︀=(1,𝑡−1,(𝑡−1)2),

[𝑇]ℬ︀=([1]ℬ︀[2𝑡−2]ℬ︀[4(𝑡−1)2]ℬ︀)=(100020004).

This has full rank, so 𝑇 is invertible, is an isomorphism, and rank(𝑇)=3.

15.3 4.3 Exercise 60

In 2𝑥1+𝑥2−2𝑥3=0 let

𝒜︀=((122),(2−21)),ℬ︀=((122),(303)).

The submitted change-of-basis matrices are

𝑆ℬ︀→𝒜︀=(1101),𝑆𝒜︀→ℬ︀=(1−101),

and [𝑎1⃗𝑎2⃗]=𝑆ℬ︀→𝒜︀[𝑏1⃗𝑏2⃗].

15.4 5.1 Exercise 6

For 𝑢=(1−12−2) and 𝑣=(2345),

cos𝜃=𝑢⋅𝑣‖𝑢‖‖𝑣‖=−3540=−1215.

Thus 𝜃=arccos(−1530)≈1.7 rad (approximately 97.4 degrees).

15.5 5.1 Exercise 17

For 𝑊=span((1234),(5678)), the equations for 𝑥=(𝑥1𝑥2𝑥3𝑥4)∈𝑊⟂ reduce as

(12345678)↦(10−1−20123).

Thus 𝑥1=𝑥3+2𝑥4, 𝑥2=−2𝑥3−3𝑥4, and

𝑊⟂={𝑟(1−210)+𝑠(2−301)|𝑟,𝑠∈ℝ}.

15.6 5.1 Exercise 26

With 𝑢1=17(236) and 𝑢2=17(3−62),

proj𝑊(𝑥)=(𝑢1⋅𝑥)𝑢1+(𝑢2⋅𝑥)𝑢2

=(2+3+6)(236)+(3−6+2)(3−62)=(193564).

16 Part B

16.1 Problem 1

For ordered bases 𝐴,𝐵,𝐶, writing 𝐶=(𝑐1,𝑐2,…,𝑐𝑛) and taking 𝑓∈𝑊,

[𝑓]𝐴=𝑆𝐶→𝐴[𝑓]𝐶=𝑆𝐵→𝐴[𝑓]𝐵,[𝑓]𝐵=𝑆𝐶→𝐵[𝑓]𝐶.

So

𝑆𝐶→𝐴[𝑓]𝐶=(𝑆𝐵→𝐴𝑆𝐶→𝐵)[𝑓]𝐶.

Taking [𝑓]𝐶=𝑒𝑖 makes corresponding columns equal; therefore

𝑆𝐶→𝐴=𝑆𝐵→𝐴𝑆𝐶→𝐵.

Consequently,

𝑆𝐶→𝐴𝑆𝐵→𝐶𝑆𝐴→𝐵=𝑆𝐵→𝐴𝑆𝐶→𝐵𝑆𝐵→𝐶𝑆𝐴→𝐵=𝑆𝐵→𝐴𝐼𝑛𝑆𝐴→𝐵=𝐼𝑛.

16.2 Problem 2

For 𝑓1=sin(2𝑥), 𝑓2=cos(2𝑥), 𝑓3=𝑒3𝑥 and ℬ︀=(𝑓1,𝑓2,𝑓3),

[𝐷(𝑓1)]ℬ︀=(020),[𝐷(𝑓2)]ℬ︀=(−200),[𝐷(𝑓3)]ℬ︀=(003),

so [𝐷]ℬ︀=(0−20200003).

The submitted interpretation is that it rotates every vector in ℝ2 counterclockwise by 𝜋2, stretches the 𝑥,𝑦 coordinates to twice their length, and the 𝑧 coordinate to three times its length.

16.3 Problem 3

Let 𝐵=[𝑇]ℬ︀ and 𝐶=[𝑇]𝒞︀. By the change-of-basis theorem, 𝐶=𝑆−1𝐵𝑆, where 𝑆=𝑆𝐶→𝐵. The submission proves by induction that

𝐵𝑘=𝑆−1𝐶𝑘𝑆

for each integer 𝑘≥1. The inductive step is

𝐵𝑘+1=𝐵𝑘𝐵=(𝑆−1𝐶𝑘𝑆)(𝑆−1𝐶𝑆)=𝑆−1𝐶𝑘+1𝑆.

Thus 𝐵𝑘 and 𝐶𝑘 are similar.

For the false kernel claim, it takes

𝐴=(100010000),

ℰ︀=((100),(010),(001)),

ℬ︀=((010),(100),(001)).

It records

[𝐴]ℰ︀=𝐴,[𝐴]ℬ︀=(100000011),

but

ker([𝐴]ℰ︀)={𝑟(001)|𝑟∈ℝ},

ker([𝐴]ℬ︀)={𝑟(01−1)|𝑟∈ℝ}.

For equal nullities, rank-nullity gives

dim(ker𝐵)=𝑛−rank(𝐵),dim(ker𝐶)=𝑛−rank(𝐶).

The page proves rank(𝑀𝑁)≤rank(𝑁) from ker𝑁⊆ker(𝑀𝑁), the analogous bound for 𝑀 by transposition, and equality rank(𝑀𝑁)=rank(𝑁) when 𝑀 is invertible. Since 𝐵=𝑆−1𝐶𝑆, rank(𝐵)=rank(𝐶), so the kernel dimensions agree.

16.4 Problem 4

For 𝑇:𝑈→𝑊, bases ℬ︀=(𝑢1,…,𝑢𝑘) and 𝒞︀=(𝑤1,…,𝑤𝑑), define

𝑇′([𝑢]ℬ︀)=[𝑤]𝒞︀whenever𝑇(𝑢)=𝑤.

The source diagram verifies

𝑇′∘𝐿ℬ︀(𝑢)=𝑇′([𝑢]ℬ︀)=[𝑤]𝒞︀=𝐿𝒞︀∘𝑇(𝑢),

hence 𝑇′∘𝐿ℬ︀=𝐿𝒞︀∘𝑇. Thus

[𝑇(𝑢)]𝒞︀=[𝑇]ℬ︀,𝒞︀[𝑢]ℬ︀.

For 𝑢=𝑎1𝑢1+…+𝑎𝑘𝑢𝑘,

[𝑇(𝑢)]𝒞︀=𝑎1[𝑇(𝑢1)]𝒞︀+…+𝑎𝑘[𝑇(𝑢𝑘)]𝒞︀,

and therefore

[𝑇]ℬ︀,𝒞︀=([𝑇(𝑢1)]𝒞︀[𝑇(𝑢2)]𝒞︀…[𝑇(𝑢𝑘)]𝒞︀).

16.5 Problem 5

For 𝑓1=sin𝑥, 𝑓2=cos𝑥, 𝑓3=𝑒𝑥:

𝑇(𝑓1)=𝑥−𝑥36,𝑇(𝑓2)=1−𝑥22,

𝑇(𝑓3)=1+𝑥+𝑥22+𝑥36.

The source chooses 𝒞︀=(1,𝑥,𝑥22,𝑥36). For ℬ︀=(𝑓1+𝑓2,𝑓1−𝑓2,𝑓3+𝑓1) it computes

[𝑇(𝑓1+𝑓2)]𝒞︀=(11−1−1),

[𝑇(𝑓1−𝑓2)]𝒞︀=(−111−1),

[𝑇(𝑓3+𝑓1)]𝒞︀=(1210),

so

[𝑇]ℬ︀,𝒞︀=(1−11112−111−1−10).

16.6 Problem 6

Let 𝐴=(−6−30−3019) and 𝑉=span((32)). For 𝑣=𝑎(32),

𝐴𝑣=𝑎(−78−52)=−26𝑎(32)∈𝑉.

𝑉⟂={𝑟(−23)|𝑟∈ℝ}, and

𝐴(−2𝑟3𝑟)=𝑟(−78117)=−39𝑟(−23)∈𝑉⟂.

With ℬ︀=((−23),(32)),

[𝑇]ℬ︀=(2600−39),[𝑇10]ℬ︀=(2610003910).

The source uses

𝑆ℬ︀→ℰ︀=(−2332),𝑆ℬ︀→ℰ︀−1=(213−313−313−213)

to obtain

[𝑇10]ℰ︀=(4⋅2610+9⋅391013−6⋅2610+6⋅391013−6⋅2610+6⋅3910139⋅2610+4⋅391013).

16.7 Homework 8 — submitted work

17 Part A

The assigned book exercises are 5.1: 45; 5.2: 14, 26; 5.3: 36; and 5.4: 26, 32.

17.1 5.1 Exercise 45

For 𝐴=(35115920112049) and 𝑉=span(𝑣2⃗,𝑣3⃗), put proj𝑉(𝑣1⃗)=𝑐2𝑣2⃗+𝑐3𝑣3⃗. Orthogonality gives

9𝑐2+20𝑐3=5,20𝑐2+49𝑐3=11,

so 𝑐2=2541, 𝑐3=−141, and

proj𝑉(𝑣1⃗)=2541𝑣2⃗−141𝑣3⃗.

17.2 5.2 Exercise 14

For (1717),(0727),(1816), the submitted Gram–Schmidt calculation gives

𝑢1=110(1717),𝑢2=12(−1010),𝑢3=12(010−1).

It states that (𝑢1,𝑢2,𝑢3) is the orthonormal basis.

17.3 5.2 Exercise 26

For 𝑚1=(2306) and 𝑚2=(44213),

𝑢1=17(2306),𝑢2=13(0−221),

and

𝑄=(27037−230236713),𝑅=(71403).

17.4 5.3 Exercise 36

For (2312𝑎23−12𝑏130𝑐), the roles must be orthonormal. The page solves

49−12+𝑎𝑏=0,29+𝑎𝑐=0,29+𝑏𝑐=0,

giving 𝑎=𝑏=26 and 𝑐=−223.

17.5 5.4 Exercise 26

For 𝐴=(123456789), 𝑏=(100), the normal equation is

(667890789310890108126)𝑥=(123).

Its reduced echelon form is

(10−17601210000),

so

𝑥∗=(−76+𝑡1−2𝑡𝑡)=(−7610)+𝑡(1−21).

17.6 5.4 Exercise 32

For (0,27),(1,0),(2,0),(3,0), let 𝑓(𝑥)=𝑐0+𝑐1𝑥+𝑐2𝑥2, with

𝐴=(100111124139),𝑏=(27000).

The source gives

(461461436143698)𝑥=(2700),

𝑥∗=(51320−56720214),

and

𝑓∗(𝑥)=51320−56720𝑥+214𝑥2=25.65−28.35𝑥+6.25𝑥2.

18 Part B

18.1 Problem 1

For 𝜋(𝑣)=∑𝑖=1𝑑𝑣⋅𝑣𝑖𝑣𝑖⋅𝑣𝑖𝑣𝑖:

18.1.1 (a)

If 𝑣𝑖⋅𝑣𝑗=0 for 𝑖≠𝑗, then (𝑣1‖𝑣1‖,…,𝑣𝑑‖𝑣𝑑‖) is an orthonormal basis. Writing 𝑢𝑖=𝑣𝑖‖𝑣𝑖‖,

𝜋(𝑣)=∑𝑖=1𝑑𝑣⋅𝑣𝑖‖𝑣𝑖‖2𝑣𝑖=∑𝑖=1𝑑(𝑣⋅𝑢𝑖)𝑢𝑖,

so 𝜋 is the orthogonal projection onto 𝑊.

18.1.2 (b)

If the basis is not perpendicular, some 𝑣𝑖⋅𝑣𝑗=𝑎≠0. While proj𝑊(𝑣𝑖)=𝑣𝑖,

𝜋(𝑣𝑖)=𝑣𝑖+…+𝑎‖𝑣𝑗‖2𝑣𝑗+…≠𝑣𝑖

by linear independence. Thus 𝜋 is not proj𝑊.

18.2 Problem 2

For the set 𝑂𝑛 of orthogonal matrices:

  • (a) False. 𝐼𝑛∈𝑂𝑛, but 𝐼𝑛+𝐼𝑛 is not orthogonal; the page gives (𝐼𝑛+𝐼𝑛)𝑇(𝐼𝑛+𝐼𝑛)=(2002), whereas its inverse is (120012).
  • (b) True. The composition of the orthogonal maps represented by 𝐴,𝐵 has standard matrix 𝐴𝐵, so 𝐴𝐵∈𝑂𝑛.
  • (c) True by the same composition argument for 𝐴2.
  • (d) True. If 𝐴2 were orthogonal but 𝐴 were not, with ‖𝑇𝐴(𝑥)‖=𝑎‖𝑥‖ and 𝑎≠1, then ‖𝑇𝐴∘𝑇𝐴(𝑥)‖=𝑎2‖𝑥‖≠‖𝑥‖, a contradiction.
  • (e) True. 𝐴∈𝑂𝑛 gives 𝐴𝑇=𝐴−1; 𝐴2=𝐼𝑛 gives 𝐴=𝐴−1=𝐴𝑇, so 𝐴 is symmetric.

18.3 Problem 3

For an orthonormal basis ℬ︀,

𝑣=𝑣1𝑏1+…+𝑣𝑟𝑏𝑟,𝑤=𝑤1𝑏1+…+𝑤𝑟𝑏𝑟,

and the calculation on the page is

𝑣⋅𝑤=∑𝑖=1𝑟𝑣𝑖𝑤𝑖=[𝑣]ℬ︀⋅[𝑤]ℬ︀.

For two orthonormal bases ℬ︀,𝒞︀, 𝑆𝒞︀→ℬ︀ has (𝑖,𝑗) entry 𝑐𝑗⋅𝑏𝑖 and 𝑆ℬ︀→𝒞︀ has transpose entry 𝑏𝑖⋅𝑐𝑗. Hence

𝑆𝒞︀→ℬ︀=𝑆ℬ︀→𝒞︀𝑇=𝑆ℬ︀→𝒞︀−1,

so 𝑆ℬ︀→𝒞︀ is orthogonal.

18.4 Problem 4

The submitted answers are:

  • (a) True. (ker𝐴)⟂=im𝐴𝑇, from ker(𝐴𝑇)=(im𝐴)⟂ and double orthogonal complement.
  • (b) True. ker𝐴=ker(𝐴𝑇𝐴), then rank-nullity gives rank𝐴=rank(𝐴𝑇𝐴).
  • (c) True. ker(𝐴𝑇)=(im𝐴)⟂ and rank-nullity yield rank𝐴=rank(𝐴𝑇).
  • (d) True. With (b), (c), and (𝐴𝑇)𝑇=𝐴, rank(𝐴𝑇𝐴)=rank(𝐴𝐴𝑇).
  • (e) False. dim(ker𝐴)=𝑚−rank𝐴 but dim(ker𝐴𝐴𝑇)=𝑛−rank𝐴; if 𝑛≠𝑚 they cannot be equal.

18.5 Problem 5

18.5.1 (a)

For 𝑋={𝑥1,…,𝑥𝑟}, 𝑌={𝑦1,…,𝑦𝑠} and 𝑋⟂𝑌,

𝑥=∑𝑎𝑖𝑥𝑖,𝑦=∑𝑏𝑗𝑦𝑗

implies 𝑥⋅𝑦=0, because every 𝑥𝑖⋅𝑦𝑗=0. Thus span𝑋⟂span𝑌.

18.5.2 (b)

For a relation

∑𝑎𝑖𝑥𝑖+∑𝑏𝑗𝑦𝑗=0,

if coefficients on both sides are nonzero then the equal nonzero vectors would belong to span𝑋∩span𝑌. But (a) and WS 16 give this intersection as 0. Hence all coefficients vanish and 𝑋∪𝑌 is linearly independent.

18.5.3 (c)

A pairwise orthogonal set with fewer than 𝑛+1 members is not maximal: append 0, use Gram–Schmidt, and add a new unit vector. A set with more than 𝑛+1 members would make 𝑌∪{0} linearly independent in ℝ𝑛, which is impossible. Therefore a maximal pairwise orthogonal set has exactly 𝑛+1 elements.

18.6 Problem 6

18.6.1 (a)

The source applies Gram–Schmidt to full-rank 𝐴 to obtain an orthonormal basis, reverses the chosen basis, and uses a QR factorization. It then sets

It takes the orthonormal basis matrix and the transpose of the upper factor, obtaining the stated QL factorization. The resulting lower factor is triangular with positive diagonal.

18.6.2 (b)

The finished submission stops after the construction for (a); no visible proof for part (b) appears in the source PDF.

18.7 Homework 9 — submitted work

19 Part A

The assigned exercises are 5.4: 27, 31; and 5.5: 15, 23, 32(a–d).

19.1 5.4 Exercise 27

The work observes that 𝑆⟂ means the least-squares error is orthogonal to 𝑆. Thus, for the displayed vector, the least-squares solution is unchanged:

𝑥=(711).

19.2 5.4 Exercise 31

For the three points (0,3),(1,3),(1,6), the line of best fit uses

𝐴=(101111),𝑏=(336).

The normal equations recorded in the submission are

(3222)(𝑐0𝑐1)=(129),

and solving them gives 𝑐0=3 and 𝑐1=32. Hence the submitted line is

𝑓(𝑥)=3+3𝑥2.

19.3 5.5 Exercise 15

For the bilinear expression in the exercise, symmetry requires 𝑏=𝑐. The submitted positive-definiteness test yields the additional condition

𝑑>𝑏2.

19.4 5.5 Exercise 23

With

∠(𝑓,𝑔)=12(𝑓(0)𝑔(0)+𝑓(1)𝑔(1)),

the answer verifies the inner-product properties and gives the orthonormal basis

1,2𝑥−1.

19.5 5.5 Exercise 32

For the weighted integral inner product

∠(𝑓,𝑔)=12∫−11𝑓(𝑡)𝑔(𝑡)d𝑡,

the computation in the submitted pages records

when 𝑛+𝑚 is even, and

∠(𝑡𝑛,𝑡𝑚)=1𝑛+𝑚+1

when 𝑛+𝑚 is odd. Also ‖𝑡𝑛‖=12𝑛+1. Applying Gram–Schmidt, it writes

𝑔0=1,𝑔1=3𝑡,𝑔2=52(3𝑡2−1),

𝑔3=14175(𝑡3−35𝑡).

The associated polynomial sequence is recorded as

1,𝑡,3𝑡2−12,5𝑡3−3𝑡2.

20 Part B

20.1 Problem 1

The submitted solution finds the plane of best fit for the three displayed points by writing its normal-equation system. Its computed coefficient vector is

(731−83),

which is also plotted on the graph in the original submission.

20.2 Problem 2

20.2.1 (a)

For (i), the proposed expression is not an inner product: the work uses

𝑓(𝑥)=𝑥2−4𝑥+3,

which is nonzero while 𝑓(1)=𝑓(3)=0. For (ii), it verifies the nonnegativity and definiteness of the sum-of-squares evaluation expression, and concludes that it is an inner product.

20.2.2 (b)

For (i), the weighted integral with weight 𝑥 fails positive definiteness; the submission gives 𝑓(𝑥)=sin(𝑥) as the counterexample. For (ii), the weight 𝑥2 gives the required symmetric, bilinear, positive-definite inner product.

20.3 Problem 3

Let

∠(𝑓,𝑔)=∫−𝜋2𝜋2𝑓(𝑥)𝑔(𝑥)sin2(𝑥)d𝑥.

20.3.1 (a)

The work finds ∠(1,𝑥)=0 and ‖1‖=𝜋2, then evaluates the remaining displayed polynomial inner products to prepare Gram–Schmidt.

20.3.2 (b)

The submitted orthonormalized functions are recorded approximately as

𝑢1=2𝜋,𝑢2=0.974𝑥,𝑢3=𝑥2−4.43515.8376.

20.3.3 (c)

For 𝑓(𝑥)=𝑒𝑥, the work records

proj𝑊(𝑓)=1.7521𝑢1+0.2492𝑢2−8.1697𝑢3

and, after expansion,

proj𝑊(𝑓)≈3.3472+0.0236𝑥−0.5142𝑥2.

20.4 Homework 10 — submitted work

21 Part A

The assigned exercises are 6.1: 20, 54; 6.2: 42, 50; 6.3: 14; and 7.1: 12, 18, 42.

21.1 6.1 Exercise 20

By the row operations shown in the submission, the determinant of the given 𝑘×𝑘 matrix reduces to

det(𝐴)=1

for every 𝑘.

21.2 6.1 Exercise 54

The answer uses positivity to conclude that the determinant of the displayed 5×5 matrix is positive, and records

det(𝐴)=1000.

21.3 6.2 Exercise 42

For a QR factorization 𝐴=𝑄𝑅, the submission writes

det(𝐴𝑇𝐴)=det(𝑅𝑇𝑄𝑇𝑄𝑅)=det(𝑅)2,

so the determinant is positive.

21.4 6.2 Exercise 50

For the matrix whose (𝑖,𝑗) entry is min(𝑖,𝑗), repeated determinant reduction gives

det(𝐴)=1.

21.5 6.3 Exercise 14

The parallelepiped volume is found from the determinant. Since the displayed vectors are linearly dependent, the result is

volume=0.

21.6 7.1 Exercise 12

For

𝐴=(2034),

the characteristic equation gives eigenvalues 2 and 4. The corresponding eigenvector directions in the work are

𝜆=2:(−231),𝜆=4:(01).

Thus it diagonalizes to 𝐷=(2004).

21.7 7.1 Exercise 18

For reflection in a plane, the plane is the 1-eigenspace and has dimension two; its normal direction is the −1-eigenspace. With an eigenbasis, the submitted diagonal form is

(10001000−1).

21.8 7.1 Exercise 42

The matrices in 𝑉 are written as

(𝑎𝑏00𝑐00𝑑𝑒).

The five matrix units in positions (1,1),(1,2),(2,2),(3,2),(3,3) form the submitted basis, so

dim(𝑉)=5.

22 Part B

22.1 Problem 1

The proof shows that an alternating bilinear form 𝐹 is antisymmetric:

𝐹(𝑢+𝑣,𝑢+𝑣)=0=𝐹(𝑢,𝑣)+𝐹(𝑣,𝑢).

Conversely, antisymmetry gives 𝐹(𝑢,𝑢)=0. Since 𝐹(𝑒1,𝑒2)=1, bilinearity then identifies the form with the determinant:

𝐹((𝑎𝑏),(𝑐𝑑))=𝑎𝑑−𝑏𝑐.

22.2 Problem 2

Let 𝑀=(𝑎𝑏𝑐𝑑) and let 𝑇(𝐴)=𝐴𝑀. The submission verifies linearity. In the ordered basis

ℰ︀=(𝐸11,𝐸12,𝐸21,𝐸22),

it computes

[𝑇]ℰ︀=(𝑎𝑐00𝑏𝑑0000𝑎𝑐00𝑏𝑑).

The determinant calculation is

det([𝑇]ℰ︀)=(𝑎𝑑−𝑏𝑐)2,

which agrees with the determinant in any other basis. Finally, for

𝑀=(2102),

the only eigenvalue is 2, with an eigenspace of dimension 2<4 for the induced map; therefore the submitted conclusion is that 𝑇 is not diagonalizable.

22.3 Problem 3

The construction defines 𝑧 by the determinant/cross-product functional in ℝ4. For the standard choice 𝑢=𝑒1, 𝑣=𝑒2, 𝑤=𝑒3, the work finds

𝑧=−𝑒4.

It proves that 𝑧=0 exactly when 𝑢,𝑣,𝑤 are linearly dependent, that 𝑧 is orthogonal to each of 𝑢,𝑣,𝑤, and that

det(𝑧,𝑢,𝑣,𝑤)=‖𝑧‖2.

22.4 Problem 4

The response uses the characteristic polynomial to find eigenvalues, and uses similarity to preserve the polynomial. It then applies the displayed eigenvector criterion to decide diagonalizability.

22.5 Problem 5

For a 2×2 matrix satisfying 𝐴2=𝐼, the submission separates the +1 and −1 eigenvector cases and obtains a diagonal form. The final argument extends this to every dimension by decomposing an arbitrary vector as

𝑣=12(𝑣+𝐴𝑣)+12(𝑣−𝐴𝑣),

where the two summands lie in the 1- and −1-eigenspaces respectively. Thus 𝐴 is diagonalizable.

23 Review on Basic Concepts

23.1 Subspace and direct sum

Definition 23.15 : Subspace

vector space 的 subset 𝑈⊂𝑉 为一个 subspace,if 它满足条件:

  1. 包含 0
  2. 对 addition 和 scalar multiplication 闭合

两个 subset 的和就是各取一个元素相加的所有情况.
很显然我们知道:

Proposition 23.1

两个 subspace 𝑈1,𝑈2 的 sum 𝑈1+𝑈2 也是一个 subspace, 并且

dim(𝑈1+𝑈2)≤dim(𝑈1)+dim(𝑈2)

且 𝑈1+𝑈2 是同时包含 𝑈1 和 𝑈2 的 𝑉 的最小 subspace.

显然可以随便和。同一个 𝑈 自己和自己的和就是自己。所以 subspace sum 这个概念比较大,没什么用。我们需要用 direct sum 来作为一个小一点但是更有用的概念,表达出一种垂直的 subspace 的直观.

Definition 23.16 : Direct sum
如果 𝑈1+𝑈2+…+𝑈𝑚 中的任意元素 𝑣,都存在唯一的 𝑣𝑘∈𝑈𝑘 for each 𝑘 使得 𝑣=∑𝑘𝑣𝑘,就称 𝑈1+…+𝑈𝑚=⊕𝑖=1𝑚𝑈𝑖 为一个 direct sum.

我们显然发现:

Proposition 23.2
dim(⊕𝑖=1𝑚𝑈𝑖)=∑𝑖=1𝑚dim(𝑈𝑖)

我们发现,其实可以 direct sum 的 subspaces 是 “垂直的”,意思是:

Theorem 23.26
𝑈1+𝑈2+…+𝑈𝑚 是一个 direct sum (这几个空间“垂直”) iff 任取 𝑢1,𝑢2,…,𝑢𝑚 分别来自 𝑈1,𝑈2,…,𝑈𝑚,它们都 lin. ind.

并且:

Theorem 23.27
𝑈1+𝑈2 为一个 direct sum iff 𝑈1∩𝑈2={0}.

24 Linear functional and Duality

Definition 24.17 : Linear functional

25 Eigenvalues and Operators

26 Operators on complex VS

27 Multilinear Algebra

28 tensor product and matrix multiplication

这里我们放弃陈述两个 over 同一 field 的 vector spaces 的 tensor product 的 algebraic definition,直接看应用的。(完整的 definition 是两个 over 同一个 ring 的 modules 𝐴,𝐵,取它们 free abelian group generated by 𝐴×𝐵,再 quotient 掉一个用来形成 bilinearity 的 subgroup,就是它们的 tensor product。当这两个东西是 vector spaces 时,它们并且是 isomorphic to 其对应的 bilinear functional vector space的。)

Definition 28.18 : (not rigorous) Tensor product

令 𝑉,𝑊 be vector spaces over 𝔽,我们定义一个 vector 与 vector 之间的 tensor product operation:

⊗:(𝑣,𝑤)→𝑣⊗𝑤

s.t. 对于 𝑉,𝑊 的 basis 𝑒1,…,𝑒𝑛 和 𝜀1,…,𝜀𝑚,我们给每个 (𝑒𝑖,𝜀𝑗) 都赋予一个不同的 image 𝑒𝑖⊗𝜀𝑗,其 over 𝔽 具有 bilinear 性。

对于

𝑉⊗𝑊≔span({𝑒𝑖⊗𝑒𝑗:1≤𝑖≤𝑛,1≤𝑗≤𝑚})

𝑉⊗𝑊 也是一个 over 𝔽 的 vector space,且 dim(𝑉⊗𝑊)=𝑚𝑛。

Proposition 28.3 : representing tensor product as matrix

如果我们有两个矩阵:

𝐴=(𝑎11𝑎12𝑎21𝑎22),𝐵=(𝑏11𝑏12𝑏21𝑏22)

可以把它们的 tensor product 𝐴⊗𝐵 表示为:

𝐴⊗𝐵=(𝑎11𝐵𝑎12𝐵𝑎21𝐵𝑎22𝐵)=(𝑎11𝑏11𝑎11𝑏12𝑎12𝑏11𝑎12𝑏12𝑎11𝑏21𝑎11𝑏22𝑎12𝑏21𝑎12𝑏22𝑎21𝑏11𝑎21𝑏12𝑎22𝑏21𝑎22𝑏22𝑎21𝑏21𝑎21𝑏22𝑎22𝑏21𝑎22𝑏22)

can verify:这个表示是符合 tensor product 的 bilinearity 的。

(我们可以把 𝐴,𝐵 分别看作 𝑚×𝑛,𝑝×𝑞 dim 的向量,这个 𝐴⊗𝐵 是 𝑚×𝑛×𝑝×𝑞 dim 的向量。)

Definition 28.19 : outer product of two vectors

对于 𝑣∈𝔽𝑛,𝑤∈𝔽𝑚,我们定义它们的 outer product 𝑣⊗𝑤为:

𝑣𝑤≔𝑣⊗𝑤𝑇=(𝑣1…𝑣𝑛)⊗(𝑤1…𝑤𝑚)=(𝑣1𝑤𝑇…𝑣𝑛𝑤𝑇)=(𝑤1𝑣…𝑤𝑚)

28.1 matrix product through outer product

Theorem 28.28 : representing matrix multiplication by outer products

对于 𝑚×𝑛 的矩阵 𝐴 和 𝑛×𝑘 的矩阵 𝐵,we have:

𝐴𝐵=∑𝑖=1𝑛𝐴∗𝑖⊗𝐵𝑖∗

Proof
In md. □

29 orthogonal vectors and matrices

Definition 29.20 : adjoint(hermitian conjugate)

^*: 𝐴=(𝑎11𝑎12𝑎21𝑎22𝑎31𝑎32)→𝐴∗=(|𝑎11||𝑎21||𝑎31||𝑎12||𝑎22||𝑎32|)

(where each overline means complex conjuate.)

Definition 29.21 : standard inner product and norm on ℂ𝑚

The standard inner product:

<𝑥,𝑦>≔𝑥∗𝑦=∑𝑖=1𝑚|𝑥𝑖|𝑦𝑖

The standard norm:

‖𝑥‖≔𝑥∗𝑥

Definition 29.22 : orthogonal, orthonomal vectors

Say 𝑥,𝑦∈ℂ𝑚 是 orthogonal vectors,if 𝑥∗𝑦=0。

Say 𝑆⊂ℂ𝑚 是 orthogonal 的,如果其中的 vectors 相互 orthogonal。

Say 𝑆⊂ℂ𝑚 是 orthonomal 的,如果其中的 vectors 相互 orthogonal,并且每个 vector 的 norm 都是 1。

Theorem 29.29 : orthogonal ⇒ lin.ind
orthogonal 的 vectors 一定 linearly independent。
Proof
trivial. □
Corollary 29.1
orthogonal 的 dim(𝑉) 个 vectors 一定是 𝑉 的一个 basis。

29.1 decomposing vector by an orthonormal set

Theorem 29.30 : decomposing vector by an orthonormal set

给定 ℂ𝑚 中的一个 orthonormal set {𝑞1,…,𝑞𝑛} (by inner product <⋅>,这里以 standard complex inner product 为例), 对于一个 arbitrary vector 𝑣,我们 define:

𝑟≔𝑣−∑𝑖=1𝑛<𝑞𝑖,𝑣>𝑞𝑖

Claim:这个 𝑟 is orthogonal to {𝑞1,…,𝑞𝑛}, 即我们把这个 𝑣 分解成了在这个 orthonormal set 上的投影与一个和它们都正交的 vector。

Proof

注意:由于 𝑞𝑖 都是 unit vectors,<𝑞𝑖,𝑣>𝑞𝑖=𝑣‖𝑣‖cos𝛼=proj𝑞𝑖(𝑣) is the projection of 𝑣 onto the direction of 𝑞𝑖.

我们在两边取和 𝑞𝑖 的 inner product,for each 𝑖。由 linearity 可拆开,由 orthgonality 可得到:

<𝑞𝑖,𝑟>=<𝑞𝑖,𝑣>−<𝑞𝑖,𝑣><𝑞𝑖,𝑞𝑖>

并且由于 𝑞𝑖 是 unit vector,得到 <𝑞𝑖,𝑞𝑖>=1,从而右边为 0。 □

对于 unit vector 𝑤,我们刚才已经展示了一个 arbitrary vector 𝑣 在它上面的 projection 是:

proj𝑤(𝑣)=<𝑤,𝑣>𝑤

现在我们引入另一个形式的 projection 表达:projection matrix

Theorem 29.31 : projection matrix

对于任意的 unit vector 𝑤,we have

proj𝑤(𝑣)=(𝑤⊗𝑤∗)𝑣

其中 𝑤⊗𝑤∗ is called the projection matrix onto 𝑤.

Proof

In md.

Notice that this matrix is rank 1. □

Definition 29.23 : Unitary matrix
一个 square matrix 𝑄∈ℂ𝑚×𝑚 被称为 unitrary 的,if 𝑄∗=𝑄−1。
Theorem 29.32 : unitrary matrix 的充要条件
𝑄∈ℂ𝑚×𝑚 is unitrary ⇔ its columns are orthonormal ⇔ its rows are orthonormal
Proof
显然,因为 unitrary ⇔𝑄𝑄∗=𝑄∗𝑄=𝐼⇔⟨𝑞𝑖,𝑞𝑗⟩=𝛿𝑖𝑗 □
Theorem 29.33 : unitrary transfromation preserves inner product and length

如果 𝑄∈ℂ𝑚×𝑚 is unitrary,那么对于任意的 𝑥,𝑦∈ℂ𝑚,都有:

(𝑄𝑥)∗(𝑄𝑦)=𝑥∗𝑦

并且自然得到 ‖𝑄𝑥‖=‖𝑥‖

Proof
Follows from: (𝐴𝐵)∗=𝐵∗𝐴∗: (𝑄𝑥)∗(𝑄𝑦)=𝑥∗𝑄∗𝑄𝑦=𝑥∗𝑦 □

30 norms

Definition 30.24 : norm

一个 norm on a vector space 𝑉是一个满足:

  1. nonnegativity (0 iff 𝑥=0)
  2. trianglar ineq
  3. homogenity

的 function ‖⋅‖:𝑉→ℝ

30.1 norms on ℂ𝑚

Example 30.1

以下为 ℂ𝑚 上的典型 norms: (absolute value 表示 length, 即 𝑥∗𝑥)

Lp-norm: 𝑝 越大,the largest length dimension 占 norm 的比重就越大

‖𝑥‖𝑝=(∑𝑖=1𝑚|𝑥𝑖|𝑝)1𝑝

𝐿∞-norm:最长维度.

‖𝑥‖∞=max𝑖|𝑥𝑖|

weighted norm: 给定一个 norm ‖⋅‖𝑘,这是 weighted version of this norm. 其中 𝑊 是一个 diagonal matrix, diag 上的是 weights.

‖𝑥‖𝑊,𝑘=‖𝑊𝑥‖𝑘

TODO (source 03-norms.tex, line 28): selected TeX refers to 01-fundamentals.assets/Screenshot 2025-01-29 at 22.41.10.png; the asset is not among the selected chapter sources.

TODO (source 03-norms.tex, line 29): selected TeX refers to 01-fundamentals.assets/Screenshot 2025-01-29 at 22.41.52.png; the asset is not among the selected chapter sources.

30.2 operator norms on matrix spaces

We know: 所有的 𝑚×𝑛 matrix, every entry in 𝔽 也是一个 vector space of dim𝑛𝑚 over 𝔽。

所以我们当然也可以给 matrix 赋范。

matrix 代表一个 linear transformation,所以 norm 的意义实际上是它 stretch vector 的程度的一种评估。

Example 30.2
Definition 30.25 : Operator norm

‖𝐴‖𝑚,𝑛=sup𝑧∈ℂ𝑚,‖𝑧‖𝑛=1‖𝐴𝑥‖𝑚

induced by vector norm. 表示它stretch vector 的最大程度。其中, source 和 image vector 分别用 norm n,m 来判定。

如果 source 和 image vector 的 norm 是一样的,比如都使用某个 𝐿𝑝 norm,那么我们可以用单个符号表示(induced by 𝑝-norm):

‖𝐴‖𝑝=sup𝑧∈ℂ𝑚,‖𝑧‖𝑝=1‖𝐴𝑥‖𝑝

(这更加常用,因为通常我们会对 source 和 image vector 的大小使用相同的评估)

Proposition 30.4 : diagonal matrix 的 norm: reduced to max diag element

如果 𝐷 是一个 diagonal matrix,那么不论取什么 𝑝-norm,我们都有:

‖𝐷‖𝑝=max1≤𝑖≤𝑚|𝑑𝑖|

其中 𝑑𝑖 为对角线上的元素。

Proof

很直观。我们要把一个以 ‖⋅‖𝑝 为衡量的 unit ball 上的哪个 vector 被拉伸的程度最大,而 diagonal matrix 把每个坐标 𝑖 上的点固定放大 𝑑𝑖 倍,

因而选择绝对值最大的 𝑑𝑘,拉伸最大的 vector 一定是 [0…1…0] where only the 𝑘-th coordinate is 1,因为这个 ball 上所有的 vectors 原本的 norm 都是一样的,而这个 vector 完整地吃到了最大的拉伸程度,其他 vectors 都或多或少吃到了其他 𝑑𝑖 的拉伸效果。 □

Proposition 30.5 : 1-norm: reduced to max column sum

‖𝐴‖1=max1≤𝑗≤𝑛‖𝐴∗𝑗‖1

matrix 的 1-norm 实则就是 1-norm 最大列的 1-norm.

Proof

因为

‖𝐴𝑥‖1=‖∑𝑖𝑥𝑗𝑎𝑗‖1≤∑𝑗|𝑥𝑗||𝑎𝑗|1

并且 ∑𝑗|𝑥𝑗|=1,因而这个和 ≤max𝑗‖𝑎𝑗‖1。

并且我们发现,这个值是可以取到的: suppose ‖𝑎𝑘‖1 最大,那么取 𝑒𝑘 就可以了。

直观而言,由于 1-norm 的单位球和它的 image 都是一个多面体,它取到最大的点一定是某个顶点。以这里的 ℝ2 为例,一定是 𝑒1, 𝑒2 中的一个。 □

Proposition 30.6 : ∞-norm: reduced to max row sum

‖𝐴‖1=max1≤𝑖≤𝑚‖𝐴𝑖∗‖1

matrix 的 ∞-norm 实则就是 1-norm 最大行的 1-norm.

Proof

直观上,image 的 sup norm 只取最大的那一个 entry,因而一定是取矩阵总(absolute)长度最大的一列, 因为每一列都只贡献 image vector 中的一个 entry。

并且,我们注意到,source vector (on单位球) 包括了所有的最大 entry 为 1 的 vectors,这些 vectors 的 sup norm 都是一样的。而要使得 image vector 的 entries 尽可能大,我们一定会取所有 entries 都为 1 的 vector 作为 input.

TODO (source 03-norms.tex, line 89): selected TeX refers to 01-fundamentals.assets/image-20250130003611232.png; the asset is not among the selected chapter sources.

Note: sup norm 的单位球和它的 image 也都是一个多面体。 □

30.3 Caychy-Swartz and Frobeniu norm

Theorem 30.34 : Hölder inequility and Cachy-Swartz

Let 𝑥,𝑦∈ℂ𝑚, let 𝑝≥1,𝑞≤∞ s.t.

1𝑝+1𝑞=1

Holder ineq:

|𝑥∗𝑦|≤‖𝑥‖𝑝‖𝑦‖𝑞

Cauchy-Schwarz ineq(special case of Hölder ineq when 𝑝=𝑞=2):

|𝑥∗𝑦|≤‖𝑥‖2‖𝑦‖2

Proof

of Cauchy-Swartz:

By homogenity of inner product and norm, it suffices to prove for unit vector 𝑢,𝑣.

(𝑢−𝑣)2=‖𝑢‖2−2𝑢∗𝑣+‖𝑣‖2

因而

𝑢∗𝑣≤‖𝑢‖2+‖𝑣‖22=1=‖𝑢‖‖𝑣‖

等号成立 iff 𝑢=𝑣. □

Example 30.3

Applying Cauchy-Swartz 可以发现: row vector 的 matrix 2-norm 等于它 (adjointed) 作为 vector 的 vector 2-norm.

这是因为 consider 𝑎≔𝐴∗, 则 ‖𝐴𝑥‖=|𝑎∗𝑥|≤‖𝑎‖2‖𝑥‖2,因而总有 ‖𝐴𝑥‖‖𝑥‖2≤‖𝑎‖2。并且这个等号可以取到, by taking 𝑥≔𝑎.

Example 30.4

任取两个 vectors 𝑢,𝑣,它们 outer product 成的 rank-one matrix,其 operator 2-norm 小于等于它们自身的 2-norm 的乘积。

‖𝐴𝑥‖2=‖𝑢𝑣∗𝑥‖2=‖𝑢‖2|𝑣∗𝑥|≤‖𝑢‖2‖𝑣‖2‖𝑥‖2

这是因为: 𝑢𝑣∗ 这一 outer product 乘以一个向量,即每行都是 𝑣∗ 的一个倍数 (𝑢𝑖 倍) 的矩阵乘以这个向量。因而,每行得到的都是 𝑢𝑖 乘上 𝑣∗𝑥 这个 inner product,最后得到的就是

𝐴𝑥=(𝑣∗𝑥)𝑢

即 𝑢 的一个倍数,这个倍数等于 𝑣∗𝑥。

Example 30.5
Theorem 30.35
‖𝐴𝐵‖𝑙,𝑛≤‖𝐴‖𝑙,𝑚‖𝐵‖𝑚,𝑛

(并且通常取不到等号.)

Proof
不证明了. Playing with definition 加上 Cauchy-Swartz. □
Definition 30.26 : Frobenious norm

‖𝐴‖𝐹≔(∑𝑚∑𝑛|𝑎𝑖𝑗|2)

等于把这个 matrix 展开为 𝑚×𝑛 的 vector 的 vector 2-norm.

Theorem 30.36 : equivalent form of Frobenius norm
‖𝐴‖𝐹=tr(𝐴∗𝐴)=tr(𝐴𝐴∗)
Proof
trivial. 𝐴∗𝐴, 𝐴𝐴∗ 的 trace 上每个元素,都是 𝐴 的一行与自己的 dot product,即这一行作为 row vector 的 2-norm 的平方; □
Proposition 30.7
‖𝐴𝐵‖𝐹2≤‖𝐴‖𝐹2‖𝐵‖𝐹2
Proof

因为 𝐴𝐵 的每个 entry 𝑐𝑖𝑗 作为 𝐴𝑖 和 𝐵𝑗 的 inner product, by Cauchy-Swartz, have

|𝑐𝑖𝑗|≤‖𝐴𝑖‖2‖𝐵𝑖‖2

因而:

‖𝐴𝐵‖𝐹≤∑𝑛∑𝑚(‖𝐴𝑖‖2‖𝐵𝑗‖2)

=(∑𝑛‖𝐴𝑖‖2)(∑𝑚‖𝐵𝑗‖2)

=‖𝐴‖𝐹‖𝐵‖𝐹

(虽然这看起来很不对, 但容易验证, 这上下两个 sum 是相等的. ) □

Theorem 30.37 : unitrary matrix preserves 2-norm 和 Frobenius norm

Let 𝑄 be unitrary, then

‖𝑄𝐴‖2=‖𝐴‖2,‖𝑄𝐴‖𝐹=‖𝐴‖𝐹

Proof

因为 ‖𝑄𝑥‖2=‖𝑥‖2 for each 𝑥.

Frobenius norm:

tr((𝑈𝐴)∗(𝑈𝐴))=tr(𝐴∗𝑈∗𝑈𝐴)=tr(𝐴∗𝐴) □

31 SVD

SVD 的 motivation:一个 linear transformation 可以通过 unit sphere 的 image 来唯一确定。并且,这个 unit sphere 的 image 一定是一个 hyperellipse (高维椭圆)。

Definition 31.27 : principal semiaxes, Singular value

对于一个 linear transformation 𝑇:ℝ𝑛→ℝ𝑚,我们 denote the unit sphere in ℝ𝑛 as 𝑆,把 𝑇(𝑆) 这一 hyperellipse 中相互 orthogonal 的各轴上的 vectors 表示为 {𝜎1𝑢1,…,𝜎𝑛𝑢𝑛}。其中 𝜎𝑖 decsending,𝑢1,…,𝑢𝑛 为 unit vectors。

我们称 𝑢1,…,𝑢𝑛 为 left singular vectors,𝜎1,…,𝜎𝑛 为 singular values,而 {𝑣1,…,𝑣𝑚} 作为

31.1 reduced SVD

32 QR factorization

32.1 projector

Definition 32.28

我们称一个 operator 𝑃:ℂ𝑛→ℂ𝑛 为一个 projector, if

𝑃2=𝑃

Note: 不要求是 linear 的. For linear case, 这是一个idempotent linear map.

(而我们将主要关注于 linear orthogonal projector.)

以下,我们都只考虑 projector linear 的情况. nonlinear 的情况是类似的.

Lemma 32.1
我们发现,一个 projector 𝑃 沿着 𝑆1≔ker(𝑃) 把空间投影到 𝑆2≔im(𝑃) 上.
Lemma 32.2

一个 projector 的 eigenvalue 只有可能是 0 或者 1. 它的 SVD 同时也是 eigenvalue decomposition:

𝑃=𝑄Σ𝑄∗

其中 Σ 是一个前面全 1, 后面全 0 的对角矩阵.

Lemma 32.3 : complement projector

如果 𝑃 是一个 projector,那么 𝐼−𝑃 也是一个 projector.

我们称 𝐼−𝑃 为 𝑃 的 complementary projector.

并且我们有: complementary projector 的 ker 是原 projector 的 im, im 是原 projector 的 ker.

Definition 32.29 : Orthogonal projector
我们称一个 projector 是 orthogonal projector,如果 ker(𝑃)⟂im(𝑃).
Theorem 32.38
一个 projector 𝑃 是 orthogonal projector ⇔𝑃=𝑃∗,即 𝑃 是 Hermitian 的.
Theorem 32.39
一个 projector 𝑃 是 orthogonal projector,则它的 complementary projector 𝐼−𝑃 也是 orthogonal projector.
Corollary 32.2
orthogonal projector 𝑃 的 complementary 𝐼−𝑃 把 vectors 投影到 im(𝑃)⟂ 上.

32.2 classical Gram-Schmidt orthogonalization

classical Gram-Schmidt 是计算 reduced QR 分解的算法.

TODO (source 05-qr-factorization.tex, lines 77–82): selected TeX includes the figure assets/Screenshot 2025-04-17 at 11.44.46.png, captioned reduced QR and labelled fig:reduced QR; the asset is not among the selected chapter sources.

32.2.1 idea of triangular orthogonalization

classical Gram-Schmidt orthogonalization 的 idea 是: 我们逐列地将 𝐴 的 columns 转变为相互 orthogonal 的新列.

具体: 我们每次都把 𝑎𝑗 减去 𝑎1,…,𝑎𝑗−1 的 span 包含的成分,从而制作成和 𝑎1,…,𝑎𝑗−1 的 span 正交的新列 𝑞𝑗:

𝑞𝑗≔normalized(𝑎𝑗−proj⟨𝑎1,…,𝑎𝑗−1⟩𝑎𝑗)

=normalized(𝑎𝑗−proj⟨𝑞1,…,𝑞𝑗−1⟩𝑎𝑗)

展开这个定义:

𝑣𝑗≔𝑎𝑗−(𝑞1∗𝑎𝑗)𝑞1−(𝑞2∗𝑎𝑗)𝑞2−…−(𝑞𝑗−1∗𝑎𝑗)𝑞𝑗−1

𝑞𝑗≔𝑣𝑗|𝑣𝑗|

这个过程可以通过定义:

𝑟𝑖𝑗=𝑞𝑖∗𝑎𝑗(𝑖≠𝑗),|𝑟𝑗𝑗|=‖𝑎𝑗−∑𝑖=1𝑗−1𝑟𝑖𝑗𝑞𝑖‖2

(Note that the sign of 𝑟𝑗𝑗 is not determined. Arbitrarily, we may choose 𝑟𝑗𝑗>0, in which case we shall finish with a factorization 𝐴=𝑄̂𝑅̂ in which 𝑅̂ has positive entries along the diagonal.)

从而这个过程写作:

𝑣𝑗≔𝑎𝑗−∑𝑖=1𝑗−1𝑟𝑖𝑗𝑞𝑖

𝑞𝑗≔𝑣𝑗𝑟𝑗𝑗

我们发现:

𝑞1=𝑎1𝑟11

𝑞2=𝑎2−𝑟12𝑞1𝑟22

𝑞3=𝑎3−𝑟13𝑞1−𝑟23𝑞2𝑟33

⋮

𝑞𝑛=𝑎𝑛−∑𝑖=1𝑛−1𝑟𝑖𝑛𝑞𝑖𝑟𝑛𝑛

这个过程使得:

𝑎𝑗=∑𝑖=1𝑗𝑟𝑖𝑗𝑞𝑖

从而:

𝐴=𝑄̂𝑅̂

32.2.2 algorithm

Classical Gram-Schmidt (unstable)

FOR j = 1 TO n
    v_j ← a_j
    FOR i = 1 TO j-1
        r_ij ← q_i* a_j
        v_j ← v_j - r_ij q_i
    ENDFOR
    r_jj ← ||v_j||_2
    q_j ← v_j / r_jj
ENDFOR

32.3 modified Gram-Shimitdt (triangular orthogonalization)

32.4 Household Triangularization

33 Discrete Fourier transform and FFT algorithm

34 conditioning and stability

Source attribution in the selected TeX chapter title: doi:10.1137/1.9780898719574.ch3.

接下来 chapter 中我们将讨论 numerical analysis 中的两个 fundamental issues: Conditioning 和 Stability. Conditioning 指的是 perturbation behavior of a mathematical problem; 而 Stability 指的是解决这一问题的 algorithm 的 perturbation behavior.

Definition 34.30 : problem, problem instance

我们把一个 problem 看作是一个 function, 把 normed VS 𝑋 of data map to normed VS 𝑌 of solutions. 即:

𝑓:𝑋→𝑌

其中,这个 problem 𝑓 together with a data point 𝑥 被称为一个 problem instance. (比如:输入是 𝑥,问题是求 𝑥 的平方根,𝑓:𝑥→𝑥,那么 𝑓 together with input 𝑥=3 就是一个 problem instance.)

Conditioning 研究的就是一个 problem instance (𝑓,𝑥), 其附近 solutions 的变动行为。

一个 well-conditioned problem instance 就是指,𝑥 附近的 small perturbations 只 lead to small changes; 而 ill-conditioned problem instance 就是指,𝑥 附近的 small perturbations 可能引起 big changes.

34.1 absolute/relative condition number of a problem

Definition 34.31 : absolute condition number

𝛿𝑥 表示 𝑥 附近的一个 small perturbation,并用

𝛿𝑓=𝑓(𝑥+𝛿𝑥)−𝑓(𝑥)

来表示 𝑓 随之产生的变化。

定义 absolute condition number 为:

𝜅̂(𝑥)≔lim𝛿→0sup‖𝛿𝑥‖≤𝛿‖𝛿𝑓‖𝑦‖𝛿𝑥‖𝑥

这里还有另外一个 condition number:

Definition 34.32 : relative condition number

𝜅(𝑥)≔lim𝛿→0sup‖𝛿𝑥‖≤𝛿‖𝛿𝑓‖‖𝑓(𝑥)‖‖𝛿𝑥‖‖𝑥‖

(recall: 𝛿𝑓 并不是 𝑓 的倍数而是:

𝛿𝑓=𝑓(𝑥+𝛿𝑥)−𝑓(𝑥)

即 𝑥 perturbated 后的函数值和原先的函数值的差.)

这里对于 absolute/relative condition number 有一种不严谨的记法: 我们把 𝛿𝑥,𝛿𝑓 看作 infinitesimal (当然,严格的分析里并不存在) 那么可以简写为:

𝜅̂=sup𝛿𝑥‖𝛿𝑓‖‖𝛿𝑥‖,𝜅=sup𝛿𝑥(‖𝛿𝑓‖‖𝑓(𝑥)‖‖𝛿𝑥‖‖𝑥‖)

Example 34.6

问题 1. 𝑓:𝑥→𝑥2, 即把一个数取半. 那么对于任意 𝑥 都有:

𝜅(𝑥)=‖𝐽(𝑥)‖‖𝑓(𝑥)‖‖𝑥‖=12𝑥2𝑥=1

well-conditioned.

问题 2. 𝑓:𝑥→𝑥, 即取一个数的 sqrt, 𝑥>0, 有:

𝜅(𝑥)=‖𝐽(𝑥)‖‖𝑓(𝑥)‖‖𝑥‖=12𝑥𝑥𝑥=12

well-conditioned.

TODO (source 07-conditioning-and-stability.tex, lines 70–73): selected TeX includes assets/condition1.png; the asset is not among the selected chapter sources.

34.1.1 examples: 两数相减

Example 34.7

问题 3: 𝑓:(𝑥1,𝑥2)→𝑥1−𝑥2 两数字相减.

𝐽(𝑥)=[𝜕𝑓𝜕𝑥1,𝜕𝑓𝜕𝑥2]=[1,−1]

For simplicity, 取 ∞-norm, 得到 ‖𝐽(𝑥)‖=2, 于是

𝜅(𝑥)=2|𝑥1−𝑥2|max{|𝑥1|,|𝑥2|}

如果 |𝑥1−𝑥2| large 时,𝜅 就会变的很大。因而 this problem is ill-conditioned when 𝑥1≈𝑥2. 这符合 “cancellation error”: 相近的两个数相减会损失有效数字, 放大误差.

For example:

𝑎=123456.789012,𝑏=123456.789011

它们的差:

𝑎−𝑏=0.000001

如果浮点数只能保留 7 位有效数字 (单精度), 那么 𝑎 被存为 123456.8, 𝑏 被存为 123456.8, 相减后结果是 0.0, 完全错误. 这就是 cancellation error:由于精度丢失导致的小差值计算结果失真.

34.1.2 example: polynomial 求根

Example 34.8

问题 4: polynomial 求根. 𝑓:ℂ𝑛→ℂ𝑛, 把 𝑛 个系数 maps to 𝑛 个 roots.

我们考虑

𝑝(𝑥)=𝑎0+𝑎1𝑥+𝑎2𝑥2+…+𝑎𝑛𝑥𝑛=∑𝑘=0𝑛𝑎𝑘𝑥𝑘

如果 coefficient 𝑎𝑖 被 perturbed by an infinitesimal quantity 𝛿𝑎𝑖, 那么 the perturbation of root 𝑥𝑗 是多少? 答案是:

𝛿𝑥𝑗=−(𝛿𝑎𝑖)𝑥𝑗𝑖𝑝′(𝑥𝑗)

从而对于这个问题:

𝜅𝑗(𝑎𝑖)=|𝛿𝑥𝑗||𝑥𝑗||𝛿𝑎𝑖||𝑎𝑖|=|𝑎𝑖𝑥𝑗𝑖−1||𝑝′(𝑥𝑗)|

证明 selected-TeX label perturbation of a root given perturbation of a coeff: (非 rigorous)

perturbed polynomial 即:

𝑝̃(𝑥)=𝑝(𝑥)+𝛿𝑎𝑖𝑥𝑖

我们要求的 perturbation 𝛿𝑥𝑗, 无法直接得到等式关系. 但是我们知道新的 root 是: 𝑥𝑗+𝛿𝑥𝑗.

即:

𝑝̃(𝑥𝑗+𝛿𝑥𝑗)=0

从而:

𝑝(𝑥𝑗+𝛿𝑥𝑗)+𝛿𝑎𝑖(𝑥𝑗+𝛿𝑥𝑗)𝑖=0

Using Taylor expansions:

𝑝(𝑥𝑗+𝛿𝑥𝑗)≈𝑝(𝑥𝑗)+𝑝′(𝑥𝑗)𝛿𝑥𝑗

其中 𝑝(𝑥𝑗)=0. 并且,(𝑥𝑗+𝛿𝑥𝑗)𝑖≈𝑥𝑗𝑖,因为在乘方的作用下这个 perturbation 作用可以忽略 (作为高阶无穷小). 从而得到

𝑝′(𝑥𝑗)𝛿𝑥𝑗+𝛿𝑎𝑖𝑥𝑗𝑖=0

从而得到 𝛿𝑥𝑗=−𝛿𝑎𝑖𝑥𝑗𝑖𝑝′(𝑥𝑗)

Polynomial rootfinding 是 ill-conditioned, 即便不涉及 multiple roots 问题. 比如经典的 “Wilkinson polynomial”:

𝑝(𝑥)=∏𝑖=120(𝑥−𝑖)=𝑎0+𝑎1𝑥+…+𝑎19𝑥19+𝑥20

它的 most sensitive root 是 𝑥=15, 并且对于这个 root, 最 sensitive 的 coefficient to change 是 𝑎15≈1.67×109, 这个 root 和这个 coeff 之间的 condition number 为:

𝜅≈1.67×109⋅15145!14!≈5.1×1013

TODO (source 07-conditioning-and-stability.tex, lines 138–143): selected TeX includes assets/Screenshot 2025-04-15 at 00.21.49.png, captioned Wilkinson's example 中 roots 的 perturbation, by $tilde(a)_k = a_k(1 + 10^(-10) r_k)$ and labelled fig:wilkinson-root-perturbation; the asset is not among the selected chapter sources.

34.1.3 example: matrix 乘 vector

这个 example 分为三部分:

  1. Fixing 𝐴, 𝑥→𝑏
  2. Fixing 𝐴, inverse problem: 𝑏→𝑥
  3. fixing 𝑏, 𝐴→𝑥
Example 34.9

Matrix-vector multiplication: 𝐴𝑥=𝑏 (fixing 𝐴)

𝜅fwd(𝑥)=sup𝛿𝑥(‖𝐴(𝑥+𝛿𝑥)−𝐴𝑥‖‖𝐴𝑥‖‖𝛿𝑥‖‖𝑥‖)=sup𝛿𝑥‖𝐴𝛿𝑥‖‖𝛿𝑥‖‖𝐴𝑥‖‖𝑥‖

即:

𝜅fwd(𝑥)=‖𝐴‖‖𝑥‖‖𝐴𝑥‖

Note: 对于任意非零 𝑥, 都有

‖𝐴𝑥‖≥1‖𝐴†‖⋅‖𝑥‖→‖𝑥‖‖𝐴𝑥‖≤‖𝐴†‖

所以

𝜅fwd(𝑥)=‖𝐴‖⋅‖𝑥‖‖𝐴𝑥‖≤‖𝐴‖‖𝐴†‖

(2) Inverse problem: given 𝑏 求 𝑥, 即 𝑥=𝐴−1𝑏, 也有同样的 condition number bound (这显然,因为对称):

𝜅inverse(𝑏)=‖𝐴†‖‖𝑏‖‖𝑥‖≤‖𝐴‖‖𝐴†‖

因而我们把 ‖𝐴‖‖𝐴−1‖ 称为 一个 matrix 的 condition number.

Definition 34.33 : Condition number of a matrix

我们定义 condition number of a matrix:

𝜅(𝐴)≔‖𝐴‖‖𝐴†‖

Notice: 如果 ‖⋅‖≔‖⋅‖2, 那么 for 𝐴∈ℂ𝑚×𝑛, we have:

‖𝐴‖2=𝜎1,‖𝐴†‖2=1𝜎𝑟

where 𝜎𝑟 是最小的非零的 singular value.

对于 ‖⋅‖≔‖⋅‖2,

𝜅(𝐴)=𝜎1𝜎𝑟

即 image of the unit sphere 作为 hyperrellipse 的 eccentricity.

至此,我们可以总结这个 theorem (a general version of Theorem 12.2 in textbook Ch12):

Theorem 34.40 : conditioning of matrix times vector

For problem 𝐴𝑥=𝑏 fixing 𝐴, 不论是 𝑥→𝑏 的 forward problem 还是 𝑏→𝑥 的 inverse problem,都有:

𝜅≤𝜅(𝐴)≔‖𝐴‖‖𝐴†‖

并且,对于 forward problem,等号当且仅当 𝑥 是 𝐴 的 minimal nonzero singular value 𝜎𝑟 的 right singular vector 时取到; 对于 inverse problem,等号当且仅当 𝑏 是 𝐴 的 maximal singular value 𝜎1 的 left singular vector 时取到.

现在我们来考虑: Fixing 𝑏, 求 𝐴→𝑥 的问题.

我们有:

(𝐴+𝛿𝐴)(𝑥+𝛿𝑥)=𝑏

我们知道 𝐴𝑥=𝑏, 并且可以 drop the doubly infinitesimal term (𝛿𝐴)(𝛿𝑥), 从而得到 (𝛿𝐴)𝑥+𝐴(𝛿𝑥)=0 即

𝛿𝑥=−𝐴†(𝛿𝐴)𝑥

By matrix norm 小于等于拆分后 norms 的乘积的定理,我们于是有:

‖𝛿𝑥‖≤‖𝐴†‖‖𝛿𝐴‖‖𝑥‖

即

‖𝛿𝑥‖‖𝑥‖‖𝛿𝐴‖‖𝐴‖≤‖𝐴†‖‖𝐴‖=𝜅(𝐴)

于是我们得到

𝜅𝐴→𝑥≤𝜅(𝐴)

神奇地发现,它也被 𝜅(𝐴) bound.

并且, equality in this bound will hold whenever 𝛿𝐴 is such that

‖𝐴†(𝛿𝐴)𝑥‖=‖𝐴†‖‖𝛿𝐴‖‖𝑥‖

而,我们可以发现对于任意 𝐴,𝑏, 这个 𝛿𝐴 一定存在,即等号一定可以取到. 这是因为 operator norm 与其 dual norm 的等价性:

𝐿:𝛿𝐴→𝐴†(𝛿𝐴)𝑥

是一个从 ℂ𝑚×𝑛→ℂ𝑛 的线性算子,它的 operator norm 是:

‖𝐿‖=sup𝛿𝐴≠0‖𝐴†(𝛿𝐴)𝑥‖‖𝛿𝐴‖

我们可以证明这个 supremum 可以达到. 选择

𝛿𝐴=𝑢𝑣∗

其中 𝑢∈ℂ𝑚 是使得 ‖𝐴†𝑢‖=‖𝐴†‖ 的单位向量,𝑣=𝑥‖𝑥‖ 是单位方向向量. 于是:

(𝛿𝐴)𝑥=(𝑢𝑣∗)𝑥=𝑢⋅(𝑣∗𝑥)=𝑢⋅‖𝑥‖⇒𝐴†(𝛿𝐴)𝑥=‖𝑥‖⋅𝐴†𝑢⇒‖𝐴†(𝛿𝐴)𝑥‖=‖𝑥‖⋅‖𝐴†𝑢‖=‖𝑥‖⋅‖𝐴†‖

从而我们可以得到这个结论:

Theorem 34.41 : conditioning of matrix times vector: given 𝑏, problem𝐴→𝑥

对于 𝐴𝑥=𝑏 fixing 𝑏, 考虑 problem 𝐴→𝑥, 这一问题一定有 condition number:

𝜅=𝜅(𝐴)

34.2 float number and machine epsilon

34.2.1 float number system

我们知道计算机处理的是离散的数值. 即,一个 computer 的 number system 并非 ℝ 而是 ℝ 的一个 discrete (and finite, 但是 ideally 可以看作 infinite) subset 𝐹, 称之为 float number system.

这个 𝐹 由这两个参数决定决定:

  1. base integer 𝛽
  2. precision integer 𝑡

(通常 𝛽=2 即 二进制,而 𝑡=24,53 for IEEE single/double precision.)

precision 决定了这个系统的对数字表示的相对精度 (即即将定义的 machine epsilon); biased exponent 决定了这个系统能够表示的数的范围的上下限.

从而,

𝐹={0}∪{±(𝑚𝛽𝑡)𝛽𝑒:𝑚∈[1,𝛽𝑡−1]int,𝑒int}

这里的 ±𝑚𝛽𝑡 称为 mantissa of 𝑥; 𝑒 称为 exponent.

现实中,𝑒 也有范围,取决于计算机位数和架构. 比如说 ieee 双精度 float: 这里 𝐸 的范围是 0∼2047, 因而 𝑒=𝐸−1023 的范围是 −1023∼1024.

TODO (source 07-conditioning-and-stability.tex, lines 297–302): selected TeX includes assets/Screenshot 2025-04-15 at 10.56.30.png, captioned IEEE and labelled fig:ieee-double-precision; the asset is not among the selected chapter sources.

IEEE double precision:

𝑥=(−1)2sign(1.𝑏51𝑏50…𝑏0)×2𝐸−1023

因而更加现实的 system 𝐹 和我们这里的理论 model 𝐹 有这些差别:

  1. 还要包括一个额外的参数: exponent offset 𝑠, 控制 𝑒 bounded by some 𝑒min 和 𝑒max.
  2. 现实的 ieee standard 和我们的 ideal 模型 𝐹 不同的点, 不仅是 𝑒 bounded 具有 𝑒min 和 𝑒max, 还有: 它的每个数其实是 ±(1+𝑚𝛽𝑡)𝛽𝑒 而不是 ±(𝑚𝛽𝑡)𝛽𝑒. 前面的 1 称为 leading bit. 这是因为在 规格化二进制浮点数系统中, 所有非零数的尾数都可以唯一表示成以 1. 开头的形式. 因为这个 1. 总是存在, 可以省略它来节省空间.
  3. 考虑更多的 symbols, 例如:
SymbolMeaning
+0Postitive underflow; between 0 and the smallest positive representable float
−0Negative underflow
+∞Positive overflow; bigger than biggest representable float. E.g., 10=1+0
−∞Negative overflow
NaNNot-a-Number, e.g., 00.

Note: 0 也是一个 symbol. 并且,现实的 system 里,还要区分正负方向上的 underflow 得到的 0.

Definition 34.34 : machine epsilon

对于一个 discrete number system 𝐹 with precision 𝑡 和 base 𝛽,我们定义:

𝜀machine≔12𝛽1−𝑡

为什么要这样定义: 因为这两点:

Proposition 34.8

对于任意的 𝑥∈ℝ that is within machine 的表示范围,都存在一个 𝜀 s.t. |𝜀|<𝜀machine 使得

fl(𝑥)=𝑥(1+𝜀)

这一点是显然的. 任意的大小不能过大的实数,都可以在 machine epsilon 的误差内被 float number 表示.

更加好的是:

Theorem 34.42 : Fundamental Axion of Floating Point Arithmetic

对于一个 discrete number system 𝐹, 对于任意的 𝑥,𝑦∈𝐹, 都存在一个 error 𝜀 s.t.

|𝜀|≤𝜀machine

such that:

𝑥⋆fl𝑦=(𝑥⋆ℝ𝑦)(1+𝜀)

for 任意的 ⋆≔+,−,×,÷.

(Exclusion: relative error 并不包括 𝑥−𝑥 时出现的 cancellation error, 以及其他的 overflow, underflow! 这些是symbolic hacks, 例如 perturbing 0 to 0.1 gives relative error 0.1−00=+∞; 并且需要注意的是, relative errors are only useful when small, well below 100%.)

即:任意基本运算的相对于自身的误差,都被 bound 在 𝜀machine 之内.

为什么是相对误差而不是绝对误差? 因为我们能表示的有效数字位数是固定的. 越大的数,其小数点后的有效数字就越小. 从而,绝对误差就越大. 但是相对误差仅和 𝑡 和 base 𝛽 有关.

(Note: On a computer in which intermediate quantities are truncated rather than rounded, Fundamental Axion of Floating Point Arithmetic hold with𝜀machine replaced by 2𝜀machine.)

34.3 stability

Review: 一个 Problem (in our def) 是一个 function 𝑓:𝑋→𝑌, 𝑋,𝑌 都是 NVS.

而我们现在定义什么是一个 algorithm:

34.3.1 def: algorithm, stability, accuracy

Definition 34.35 : algorithm
一个 algorithm for a problem 𝑓:𝑋→𝑌 是另一个函数 𝑓̃:𝑋→𝑌

定义上就是这么简单.

注意: 我们这里的 algorithm 是一个比较 restricted 的定义. Specially, 它并不考虑 randomized algorithms.

Example 34.10

Randomized rounding:

把 7.3 round to: 8, with a prob of 0.3; 7, with a prob of 0.7.

我们把 round 得到的结果标记为 𝑋, 那么它则是一个 random variable. 并且,它是一个 unbiased random variable,即:

𝔼[𝑋]=7.3

这个 rounding 是一个 algorithm, 但是不包含在我们这里的定义里. 因为原问题是 ℝ→ℕ 的, 而这个问题则是 maps to random variables (我们知道一个 random variable 是一个函数, 这是一个 function space) 的. 因而它并不是我们定义的算法.

因而我们的定义其实是 restricted 的. 我们这里只考虑 determinstic 的 algorithm.

Definition 34.36 : accuracy of an algorithm

给定一个 problem 𝑓 和一个对应的 algorithm 𝑓̃, 我们定义 𝑓̃ 的 relative error 为

‖𝑓̃(𝑥)−𝑓(𝑥)‖‖𝑓(𝑥)‖

即: algorithm 给出的答案和正确答案的相对 difference.

如果对于每个 𝑥∈𝑋 都有:

‖𝑓̃(𝑥)−𝑓(𝑥)‖‖𝑓(𝑥)‖=𝑂(𝜀machine)

即 relative error is on the order of machine epsilon, 那么我们称这个 algorithm 是 accurate 的.

Problem: 对于一个 well-conditioned 的问题,我们自然地想要一个足够 accurate 的 algorithm; 但是对于 ill-conditioned 的问题,要求给出一个足够 accurate 的 algorithm 是很困难的事情,因为 perturbations on ill-conditioned inputs 使得它给出准确结果的难度很大.

因而,generally, 我们应该放低要求.

Definition 34.37 : stability of an algorithm

给定一个 problem 𝑓 和一个对应的 algorithm 𝑓̃, 如果对于每个 𝑥∈𝑋 都存在一个 𝑥̃∈𝑋, 其满足

‖𝑥̃−𝑥‖‖𝑥‖=𝑂(𝜀machine)

能够使得

‖𝑓̃(𝑥)−𝑓(𝑥̃)‖‖𝑓(𝑥̃)‖=𝑂(𝜀machine)

那么则称,这个 algorithm 𝑓̃ 是 statble 的.

还有一个比 stable 更强的定义

Definition 34.38 : backward stability

给定一个 problem 𝑓 和一个对应的 algorithm 𝑓̃, 如果对于每个 𝑥∈𝑋 都存在一个 𝑥̃∈𝑋, 其满足

‖𝑥̃−𝑥‖‖𝑥‖=𝑂(𝜀machine)

能够使得 𝑓̃(𝑥)=𝑓(𝑥̃) 那么则称,这个 algorithm 𝑓̃ 是backward stable 的.

backward stable 的要求是: 这个 algorithm gives exactly the right answer to nearly the right question. 它蕴含的信息是: 对于这个算法 𝑓̃, 任意的 output perturbation 其实都等同于某些 input perturbation. (从而可以被 input perturbation 给完全控制.)

backward stable 和 accurate 是 dual 的: accurate 要求的是这个 algorithm gives nearly the right answer to the right question.

Example 34.11

我们用一个例子来阐明 “𝑂(𝜀machine)”:

problem: 给定 𝑏, solve system 𝐴𝑥=𝑏 for 𝐴→𝑥. 假设我们有一个 algorithm 𝑓̃:𝐴→𝑥 是 stable 的, 那么它满足: 对于给定的 𝑛,𝑚, 存在 uniform bound 𝐶1,𝐶2 使得对于任意的 𝐴∈ℂ𝑛×𝑚, 都具有 nearly the same question 𝐴̃, 使得 algorithm 𝑓̃ 给出的 answer 𝑓̃(𝐴) 几乎就是这个近似问题 𝐴̃ 的正确解 𝑓(𝐴̃).

Formally: 对于任意的 𝐴∈ℂ𝑛×𝑚, 都存在 𝐴̃∈ℂ𝑛×𝑚 s.t.

‖𝐴̃−𝐴‖‖𝐴‖≤𝐶1𝜀machine

使得

‖𝑓̃(𝐴)−𝑓(𝐴̃)‖‖𝑓(𝐴̃)‖≤𝐶2𝜀machine

这个 𝐶1,𝐶2 是和 input 进入的 𝐴 无关的, 它被 problem 的参数固定 (here: 𝑛,𝑚). For example, 𝐶1=10,𝐶2=100.

34.3.2 example: floating point arithmetic

Example 34.12

当然,四种 floating point arithmetic 是有 backward statble 的算法的.

我们以两数相减 from 𝑓:ℂ2→ℂ 为例: 我们 canonical 的算法就是把这两个数 round 为 float,然后进行 float 的减法.

𝑓̃(𝑥1,𝑥2)=fl(𝑥1)⊖fl(𝑥2)

其中,

fl(𝑥1)=𝑥1(1+𝜀1),fl(𝑥2)=𝑥2(1+𝜀2)

where by def, |𝜀1|,|𝜀2|<𝜀machine.

并且我们知道, float 减法的 error 也是 within machine epsilon 的:

fl(𝑥1)⊖fl(𝑥2)=(fl(𝑥1)−fl(𝑥2))(1+𝜀3)

从而

fl(𝑥1)⊖fl(𝑥2)=[𝑥1(1+𝜀1)−𝑥2(1+𝜀2)](1+𝜀3)

=𝑥1(1+𝜀1)(1+𝜀3)−𝑥2(1+𝜀2)(1+𝜀3)

=𝑥1(1+𝜀4)−𝑥2(1+𝜀5)

where

|𝜀4|,|𝜀5|≤2𝜀machine+𝑂(𝜀machine2)=𝑂(𝜀machine)

我们把

𝑥1̂≔𝑥1(1+𝜀4),𝑥2̂≔𝑥2(1+𝜀5)

从而,这个 canonical algorithm 计算出的是:

𝑓̃(𝑥1,𝑥2)=𝑓(𝑥1̂,𝑥2̂)

where for all (𝑥1,𝑥2), 它对应的这个 (𝑥1̂,𝑥2̂) 和它在 ℂ2 中的 relative distance, within any norm 都是 𝑂(𝜀machine) 的.

34.3.3 example: inner/outer product

For inner product: problem is 𝑓:ℂ𝑚×ℂ𝑚→ℝ, given vectors 𝑥,𝑦∈ℂ𝑚, wish to compute the inner product 𝛼=𝑥∗𝑦.

显然, canonical algorithm: compute the pairwise products |𝑥|𝑖𝑦𝑖 with ⊗ and add them with ⊕ to obtain a computed result 𝛼̃.

这个算法是 backward stable 的.

但是, for outer product: problem is 𝑓:ℂ𝑚×ℂ𝑛→ℂ𝑚×𝑛.

我们想要计算 𝐴=𝑥𝑦∗, for vectors 𝑥∈ℂ𝑚,𝑦∈ℂ𝑛.

Canonical algorithm: compute the 𝑚𝑛 products 𝑥𝑖|𝑦|𝑗 with ⊗ and collect them into a matrix 𝐴̃.

它是 stable 的,但却不是 backward stable 的. 因为直观而言: 我们每个 entry 的计算有不同的乘法误差,导致: 𝐴̃ will 不太可能 have rank exactly 1, 因而无法真的被写作 written in the form (𝑥+𝛿𝑥)(𝑦+𝛿𝑦)∗.

34.3.4 theorem: what backward stabililty implies about the accuracy

Theorem 34.43

Suppose a backward stable algorithm is applied to solve a problem 𝑓:𝑋→𝑌 with condition number 𝜅, 那么 relative errors:

‖𝑓̃(𝑥)−𝑓(𝑥)‖‖𝑓(𝑥)‖=𝑂(𝜅(𝑥)𝜀machine)

(notice: 这说明如果 𝜅 of this problem bounded,那么 backward stable algorithm 一定是 accurate 的)

Proof

By backward stability, we have 𝑓̃(𝑥)=𝑓(𝑥̃) for some 𝑥̃∈𝑋 satisfying

‖𝑥̃−𝑥‖‖𝑥‖=𝑂(𝜀machine)

我们把 𝑥̃−𝑥 作为 𝛿𝑥, 从而有:

‖𝛿𝑥‖‖𝑥‖=𝑂(𝜀machine)

而由于这里 ‖𝛿𝑥‖‖𝑥‖=𝑂(𝜀machine) 已经是 numerically 最小的 error. 从而 By definition of 𝜅(𝑥):

‖𝑓(𝑥+𝛿𝑥)−𝑓(𝑥)‖‖𝑓(𝑥)‖≤(𝜅(𝑥)+𝑜(1))⋅‖𝛿𝑥‖‖𝑥‖

这个不等式是因为: 𝑓 的相对变化和 𝑥 的相对变化的比例,其上极限就是 𝜅(𝑥). 从而 this implies

‖𝑓̃(𝑥)−𝑓(𝑥)‖‖𝑓(𝑥)‖=‖𝑓(𝑥)−𝑓(𝑥̃)‖‖𝑓(𝑥)‖=‖𝑓(𝑥+𝛿𝑥)−𝑓(𝑥)‖‖𝑓(𝑥)‖≤(𝜅(𝑥)+𝑜(1))⋅‖𝛿𝑥‖‖𝑥‖ □

这一 theorem 表明: backward stability + good conditioning ⇒ accuratcy

35 backward error analysis of NLA algorithms

Source attribution in the selected TeX chapter title: doi:10.1137/1.9780898719574.ch3.

我们在上一个 Ch 中介绍了 conditioning 和 stability. 现在我们用它们对经典的 NLA algorithms 进行 backward error analysis.

35.1 Stability of Householder Triangularization

我们 set 𝑅,𝑄 to be random upper triangular 和 orthogonal matrices (by orthogonizing 一个 random matrix),并 set 𝐴≔𝑄𝑅.

R = triu (randn(50));
[Q,X] = qr(randn(50));
A = Q*R

然后我们再对 𝐴 进行 QR 分解, via Household (Matlab 自带使用 Household), 看看 relative error:

[Q2,R2] = qr(A);
norm (Q2 - Q);
    ans = 0.00889
norm (R2-R) / norm(R);
    ans = 0.00071

我们发现 𝑄,𝑅 的 relative error 其实很大.

但是,当我们用这个 𝑄𝑅 计算 𝐴 时:

norm (A - Q2*R2) / norm(A);
    ans = 1.432e-15

我们发现一个惊人的事实: 这个 QR 分解的 error

Q3=𝑄+1e−4∗randn(50)

R3=𝑅+1e−4∗randn(50)

norm(𝐴−Q3∗R3)norm(𝐴)

ans=0.00088

35.2 Stability of Back Substitution

35.3 Conditioning of Least Squares

35.4 Stability of Least Squares