Everything About Linear Algebra

Linear, advanced, and numerical viewpoints

Qiulin Fan

2026

Chapter 1Introduction

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

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.

Linear Algebra

Chapter 2Linear equations, vectors, and matrices

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

(complement: “MathHygine”) Principle of Mathematical Induction: .

For the system

place numbers in the columns of the augmented matrix .

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, is a vector in ; is a row vector with components.

  1. 1.

    is called a matrix (row, col; three by four).

  2. 2.

    Matrix if same size and .

  3. 3.

    If is , is called a square matrix, and the entries form the main diagonal of .

  4. 4.

    A square matrix is called diagonal provided all its entries above and below the diagonal are , i.e. whenever .

  5. 5.

    is called upper triangular provided all its entries below the main diagonal are ; lower triangular: entries above the main diagonal are .

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 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 where is arbitrary is represented as the line ; for a few special values of we may still use arrow representation. The source sketch labels the vectors for and for on that line.

Consider the system

The matrix which contains the coefficients is called its coefficient matrix, . By contrast, , which displays all numerical information, is called the augmented matrix.

2.2WS 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: .

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

Example: gives .

这个 equation 容易解是因为:

  1. 1.

    The leading coefficient is always .

  2. 2.

    The leading variable in each equation 在其他 equation 中不出现.

  3. 3.

    The leading variables in natural order 出现.

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

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

From top to down, move on to the th equation :

  1. 1.

    Divide by , so .

  2. 2.

    Eliminate from all other equations above and below.

  3. 3.

    Proceed to next equation.

  4. 4.

    Check: if non-, inconsistent.

  5. 5.

    Rearrange equations so the leading variables are in natural order.

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

  1. 1.

    若一 row 有 non- entries, the first non- entry must be , called the leading or pivot.

  2. 2.

    若一 col 中有 pivot,则 col 中其他 entries 必须为 .

  3. 3.

    若一 row 中有 pivot,则它后每个 row 必须有 pivot 在它右边(and rows of s must be at the bottom of matrix).

Definition 2.2 (Elementary row operation)

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

  1. 1.

    Divide a row by a non-zero scalar.

  2. 2.

    Subtract a multiple of a row from another.

  3. 3.

    Swap two rows.

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

Chapter 3Linear systems and matrices

The worksheet starts with a system of linear equations:

To solve for , we need to transform the system into the form . In other words:

  1. 1.

    Eliminate terms that are off the diagonal.

  2. 2.

    Make the coefficients of the variables along the diagonal equal to .

The row-reduction calculation on the page is

where the first arrow subtracts the first equation and the next arrow uses the first equation. Then

The intervening operations are the second equation and the second equation; then divide by ; finally use 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.

Chapter 4Linear combinations

4.1WS 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:

For

reduction gives , . Generally choose ; then , , and the general solution is . The general sol represents a line in space; the source sketch marks , , and .

For

reduction yields , , . Whatever value we choose, 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.2Number 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 sol; inconsistent: no sol (iff rref of its augmented matrix contains with ).

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

Definition 4.1 (Matrix rank)

The number of leading ′s in is denoted . For , , so .

For an coefficient matrix and the augmented matrix :

  1. 1.

    and .

  2. 2.

    If the system is inconsistent, .

  3. 3.

    If the system has one sol, .

  4. 4.

    If the system has infin sols, .

If system inconsistent, rref of augmented matrix contains a row , so no leading in that row for the coefficient part. Number of variables = total number of variables number of leading variables . Thus exactly one sol gives , whereas infinitely many sols gives .

As contrapositive: (1) if , the system has a sol; (2) if , the system has no sol or infin sols; (3) if , 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 linear equations in variables. 每个 都表示一个 plane,而两个 plane 要么平行无交点,要么交于一直线 (infin sols),不可能只有一个交点。

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

Definition 4.2 (Sum and scalar multiples of matrices)

For same-size matrices, addition is entrywise; for , multiplication by multiplies every entry by .

Definition 4.3 (Dot products of vectors)

For and , . Note that the definition is not row-column-sensitive; it does not distinguish between row and col vectors.

Definition 4.4 (The product of )

Let be an matrix with row vectors and let . Then . In words, the th component of is the dot product of the th row of with .

Example: . 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 . Then .

Definition 4.5 (Linear combination)

A vector is called a linear combination of vectors if there are scalars such that .

Example: is a linear combination of and ? Solve . Row reduction gives , , hence .

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 , the th equation. For , : , equivalently .

For , : . 如果我们可以 divide by matrix ,,就能直接解 。换言之我们是否能够找到 呢?Chapter 2.

Chapter 5Linear transformations

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

现在你的位置为 。用一个 vector 表示方位。现在你使用一个 encode 来加密你的方位:

这个加密方位的码为 . 我们做了一个 transformation,使得 the same but 坐标不变。例如 从 坐标 map 到 坐标后仍是 ;但 下的 同样在 下为 ,而 下的 在 下为 。The source sketch marks these corresponding points and axes.

Definition 5.1 (Linear transformation)

A function is called a linear transformation if for every there is an matrix such that .

Example: has input and output ; . 可以发现 is not a linear transformation of .

Definition 5.2 (Identity matrix)

Identity matrix, denoted by : and .

For , and ; it is a counterclockwise rotation by degrees. Also and have the same length: . The source diagram labels the two arrows and .

For with , and .

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

Theorem 5.1 (Standard matrix)

Consider a linear transformation . Let be the vector whose th component is and all other components are . Then . Equivalently, is the standard vector of (而 中的 都用 来 denote).

Theorem 5.2 (Linearity test)

A transformation is linear iff (a) , ; and (b) and scalar , .

Definition 5.3 (Distribution vectors and transition matrices)

A vector is said to be a distribution vector if its components (1) sum to and (2) are all . A square matrix is a transition matrix if its col vectors are distribution vectors.

Chapter 6Geometry of linear transformations

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

在 2-1 我们知道 是 中 counter clockwise 转 度的 linear transformation。现在再看几个:

The source diagrams apply them to and :

Theorem 6.1 (Scalings)

defines a scaling by , since .

Definition 6.1 (Orthogonal projection)

Consider a line in coordinate plane, 经过 . 任何 都可以写成 , where and . The transformation is the orthogonal projection of onto , denoted .

随意取 , . 特别地,如果 是 unit vector , then . 这一个 transformation 是 linear 的;with matrix .

Definition 6.2 (Reflection)

Consider a line in coordinate plane, 过 , and write . Then is reflection of about , denoted . 由 Definition 2.2.1, .

The matrix of has form where : .

6.2WS 5, p. 2: rotations and shearing

Theorem 6.2 (Rotations)

is a counterclockwise rotation in (rotate by ) iff , where .

For a nonzero vector , write its coordinate in polar form . Rotation gives , so and , which gives the displayed matrix.

Theorem 6.3 (Rotations combined with a scaling)

将 counterclockwise rotate 并放大至 倍. Let . Then , .

6.35. Shearing

Vertical shear:

Horizontal shear:

Theorem 6.4 (Horizontal and vertical shearing)

Horizontal shearing of slope has matrix ; vertical shearing of slope has matrix .

The source’s concluding table records:

Chapter 7Gram–Schmidt and QR factorization

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

Let be . Gram–Schmidt produces :

The are orthonormal. 因而 is an orthogonal matrix, and

The worksheet computes

Because , the entry is when ; the result is upper triangular. Thus , with upper triangular.

7.2Proof of matrix product theorem

For ordered bases and of :

where

Note that if , then ; hence

Chapter 8Orthogonal transformations

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

Definition 8.1 (Orthogonal transformation)

is orthogonal (正交变换) if it preserves dot products: , .

Theorem 8.1 (Equivalent characterizations)

is orthogonal iff it preserves the length of vectors: , .

因而 linear trans 保留 dot product iff 保留 length. The proof expands :

then cancels equal norm terms.

(a) An orthogonal trans is injective: , so 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

Definition 8.2 (Orthogonal matrix)

A square matrix is orthogonal if (即 ).

If , then the th entry of is . Therefore is orthogonal iff its cols are orthonormal. 我们也由此知道:由 orthonormal basis 组成的 matrix , 就是 .

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.2WS 18, p. 2: products and change of basis

If is orthogonal, then (也是 ) is orthogonal, since implies . 结论:这意味着对于 的 cols 是 orthonormal 的,那 的 rows 也是 orthonormal 的.

Theorem 8.2 (Products of orthogonal matrices)

If are orthogonal matrices, then is orthogonal.

Indeed,

so .

Theorem 8.3 (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

and

Thus .

8.3WS 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 .

Chapter 9Least squares

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

Theorem 9.1 (Projection and Least squares method)

对于任意 subspace , , is 中离 最近的 vector, i.e. , .

The source diagram labels as the 垂直距离.

(a) is consistent iff : if such that , then , and conversely. (b) 不可能 不在 而 be consistent. (c), least squares solutions: if is not consistent, let , . 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.2 (Image-kernel orthogonality)

For an matrix , .

Write , so . If , then for every , so . Conversely, if , then every , so .

A second proof uses the displayed transpose identity: for all , hence ; conversely for all implies .

Consequently , and . The rank computation is

9.2WS 19, p. 2: normal equations

The normal equation: 的 least square 解当且仅当 is a solution of

Theorem 9.3 (Kernel of )

For an matrix , .

If , then , so . Since and 与 only meet at , so . Conversely directly implies .

For the rest proof of normal equation, the source diagram records . Thus , whence

总结:对于 , , 使得对于 及 , 是 transpose 本质的性质;它告诉我们 是 到 的 linear map.

Chapter 10Inner-product spaces

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

For the Inner product space of functions on , :

  1. 1.

    .

  2. 2.

    Linearity: .

  3. 3.

    Positive definite: , and .

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

P4: find two different inner products in : (dot product; here are orthonormal), and different weight .

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

and, in general,

proof: generalized Gram–Schmidt.

10.2WS 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 have

where (1) is symmetric; (2) and . Indeed

(这个条件等价:充分条件为 且 .) Linearity is guaranteed by matrix multiplication. 因而这三条为完整条件。

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

Chapter 11Diagonalization and eigenspaces

11.1WS 23, p. 1: four theorems

Theorem 11.1 (Eigenbasis and diagonal matrix)

For a finite-dimensional vector space , a basis of is an eigenbasis for iff is diagonal.

Indeed,

Theorem 11.2 (Diagonalizable transformation)

is diagonalizable iff is similar to some diagonal matrix .

The definition notes: diagonalizable iff 其 matrix of is diagonal. 因而(所有 都相似于 ).

Theorem 11.3 (Diagonalizable matrix)

is diagonalizable iff is similar to some diagonal .

Theorem 11.4 (Eigenspace)

, so .

Proof: 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) 如果 是 an eigenbasis of for , then

Proof note: (). Then and

Hence the change of basis yields the diagonal matrix.

Chapter 12Eigenvalues and eigenspaces

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

Theorem 12.1 (Eigenvalues are roots)

The eigenvalues of are precisely the roots of its characteristic polynomial.

简明 proof: 是 的 eigenvalue iff iff iff nullity iff iff 不可逆 iff . Thus is a root of .

Theorem 12.2 (Distinct-eigenvalue eigenspaces)

且 , and 且 , if , then are linearly independent.

因而 eigenbases of distinct eigenspaces have linearly independent union, and if , that union is an eigenbasis of for .

Theorem 12.3 (Geometric and algebraic multiplicity)

For eigenvalue , .

Let , let be an eigenvalue and . Let be a basis of , put , and define . Then for ,

Therefore

so

and .

Theorem 12.4 (Degree of the characteristic polynomial)

For , has degree .

This is the corollary of the preceding two theorems: if has different eigenvalues, then . Proof: 见 P9.

Chapter 13Complex eigenvalues

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

P5(b). Let and . Then

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

(c) Fact: is a root of iff is a root when the coefficients of are real. If , then

For

(b) Factor into a scalar matrix and a rotation matrix :

where

(c) Diagonalization over :

For ,

so is a basis for ; similarly is a basis for . Hence

and

P9: 任何有一对 complex eigenvalue 的 都 similar to (一个 scaling matrix). 因为 diagonalizable: ,而 又 similar to by P8.

Chapter 14Spectral theorem

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

Theorem 14.1 (Spectral theorem)

is orthogonally diagonalizable iff is symmetric: such that and is diagonal iff is symmetric.

Equivalently, 的 cols 是 的一个 orthonormal basis, 且为 的 eigenvectors. 普通 diagonalization: , 的 cols 为 的一个 eigenbasis . 而 orthogonal diagonalization: , 的 cols 不但是 eigenbasis,而且还是一个 orthonormal eigenbasis. 这意味着对于不同的 eigenvectors,它们都是 orthogonal 的(可以为 orthonormal),也就是说 with .

Claim 1: if is orthogonally diagonalizable, then is symmetric. If and , 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, 有 个 complex roots 包含重复. Let be any complex eigenvalue, so , . Then , and, after transpose, because is symmetric. Multiply on the right:

Since , ; every complex eigenvalue is real.

Claim 2 pt.(2): consider and nonzero , , with . Then

Thus , so .

14.2WS 27, p. 2: induction proof

Claim 2 pt.(3): if is symmetric, then is orthogonally diagonalizable. Prove by induction.

Base case: a matrix is diagonal and symmetric. Inductive step: if every symmetric matrix is orthogonally diagonalizable, then every matrix is too.

Let be symmetric. Let be an eigenvalue and a corresponding unit eigenvector. Complete to an orthonormal basis of . Put

so is orthogonal and . 注意 为 , 因而 .

Then

for some : is symmetric, and

By the inductive hypothesis, is orthogonally diagonalizable, for an orthogonal and diagonal . Therefore

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

Personal Linear Algebra Homeworks

14.3Homework 1 — submitted work

Note

Visual transcription of the personal finished submission. Source: 217-Hw-1-finished.pdf; page references below are PDF pages.

14.3.1Source p. 1 — Exercise 20

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

.

The submitted row reduction is . For infinitely many solutions, the final row must be zero, so and . Thus .

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

For no solution, while , hence . For one solution, and , namely .

Exercise 32 asks for a polynomial of degree at most two, , passing through , , and . The submitted equations are , , and .

14.3.3Source p. 3 — Exercise 32

The augmented matrix is reduced as , giving , , and . Therefore a polynomial exists for all choices of , , and .

14.3.4Source p. 4 — Exercise 34

Find a polynomial of degree at most two which passes through and and satisfies . The submitted system is , , and , with its augmented matrix set up for row reduction.

14.3.5Source p. 5 — Exercise 34; Exercise 44

The reduction for Exercise 34 ends at , so the submitted answer is .

For Exercise 44, the line through and has direction . The submitted vector equation is , or , , , for arbitrary . Its equations are and .

14.3.6Source p. 6 — Exercise 12

The homogeneous augmented matrix recorded is . The first displayed operation divides the first row by before continuing the row reduction.

14.3.7Source p. 7 — Exercise 12

The submitted reduction clears the first column, then the second column. Its displayed intermediate rows include , followed by clearing the remaining pivot columns.

14.3.8Source p. 8 — Exercise 12

The final reduced matrix is . Setting and , the submission gives .

14.3.9Source p. 9 — Exercise 36

For a vector perpendicular to , let . The condition is . Setting and gives , where and are arbitrary real numbers.

14.3.10Source p. 10 — Exercise 44

For the traffic-flow diagram, the submitted equations are , , , and . They are rearranged as , , , and .

14.3.11Source p. 11 — Exercise 44

The submitted row reduction reaches . The free variable is recorded as .

14.3.12Source p. 12 — Exercise 44

The submitted solution is . Nonnegativity gives . The recorded flow ranges are , , , and .

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

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

(b) True: , 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 is false; thus the biconditional is false.

14.3.14Source 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 , 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.15Source p. 15 — Problem 2(b)–(d)

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

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

(d) False: the submitted contradiction uses to refute the stated universal claim.

14.3.16Source 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: has two square roots, and , which disproves the uniqueness statement.

14.3.17Source p. 17 — Problem 3

The submitted negations are:

14.3.18Source p. 18 — Problem 4

The submitted converses and contrapositives are:

14.3.19Source 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+ŷ2+ẑ2=1}. (b2) The submitted set notation is {sqrt(2)n : n in ZZ}.

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

14.3.20Source 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.21Source p. 21 — Problem 6(b)

The claimed least is . For , the submission writes (with one of allowed to be zero), proving inclusion in . It then rules out because is not in , and because is not in .

14.3.22Source p. 22 — Problem 7

Let mean “you can fool at time .” The submitted formalization of the recreational statement is .

14.3.23Source 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.4Homework 2 — submitted work

Note

Visual transcription of the personal finished submission. Source: 217-Hw-2-finished.pdf; page references below are PDF pages.

14.4.1Source p. 1 — Exercise 26

Let be a matrix and assume has a unique solution. The submission records . For , it begins the two RREF cases.

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

If reduces to a form with three pivots, it has one solution. If it has a row with , 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 .

14.4.3Source p. 3 — Exercise 34

For , the submitted work writes

, , and .

For a matrix with columns , it likewise records .

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

(a) If solves and solves , then .

(b) If and solve , then ; hence is a homogeneous solution.

14.4.5Source p. 5 — Exercise 48(c)

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

14.4.6Source p. 6 — Exercise 48(c)

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

14.4.7Source p. 7 — Exercise 6

For ,

.

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

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

For Exercise 38,

.

The submitted sketch shows this vector combination. Exercise 44 begins with equal to the cross product of and .

14.4.9Source p. 9 — Exercise 44

With and , the work expands

.

Thus the submitted matrix for is ; the work also verifies addition and scalar multiplication.

14.4.10Source p. 10 — Exercise 46

For and , . The submitted column computation gives

and .

Hence the matrix is .

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

(a) , , is injective but not surjective. A counterexample to surjectivity is . For injectivity, implies , and nonnegativity gives .

(b) , , is bijective. Surjectivity uses , and gives injectivity.

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

(c) , , is neither injective nor surjective: , and no negative number is in its image.

(d) sends odd to and even to . It is surjective but not injective: ; for a target , choose when is odd and when is even.

14.4.13Source 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 , , , and . Then A intersect B = emptyset but belongs to both images. The proof of (b) begins by contradiction.

14.4.14Source 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 gives .

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

For (d), using the same and , the submission gets , whereas .

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

14.4.16Source 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.17Source p. 17 — Part B, Problem 3(a)

Assume . The submission first records and . If , additivity follows. Otherwise, writing and applying the assumption to and gives

,

then division yields .

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

The submitted example is . It records , but says it is not additive: with and , the displayed norm values give .

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

For an additive , , hence ; also .

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

The induction for has base case and the inductive step

.

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

14.4.21Source 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.5Homework 3 — submitted work

Note

Visual transcription of the personal finished submission. Source: 217-Hw-3-finished.pdf; page references below are PDF pages.

14.5.1Source p. 1 — Exercise 20

Reflection about the plane sends to . The submitted standard matrix is , accompanied by a sketch of the reflected vector.

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

(a) Projection onto an arbitrary unit vector has matrix . Its determinant is , so it is not invertible.

(b) A reflection matrix is with ; its determinant is , so it is invertible.

(c) A rotation matrix is with ; its determinant is , so it is invertible.

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

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

For Exercise 18, let and . Equating and yields and , so .

14.5.4Source p. 4 — Exercise 34

For , the submitted computations are

, , , and .

Thus for positive . Geometrically, repeated application is a horizontal shear by one unit each time.

14.5.5Source p. 5 — Exercise 12

For , the submission applies the invertible-matrix test through row reduction of . The displayed operations first exchange the first two rows and then use pivots to clear the two blocks.

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

The final augmented matrix is , with

.

By Theorem 2.4.5, is invertible.

For a diagonal , the submitted answer says is invertible precisely when , and then . A diagonal matrix of arbitrary size is invertible iff every diagonal element is nonzero.

14.5.7Source 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 and . It computes , , , and , so .

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

14.5.8Source 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.9Source p. 9 — Part B, Problem 1(c)–(d)

The entry of is computed as

,

the entry of . Since are arbitrary, .

For (d), the submission begins induction: for a symmetric , is symmetric, and if , then .

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

The inductive multiplication is

,

which is symmetric. Hence is symmetric for all .

(e) is false: is not symmetric, while is recorded as symmetric in the submitted counterexample.

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

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

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

(c) True. If is an invertible matrix, then ; therefore is invertible.

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

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

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

If there is an matrix with , suppose and solve . Then . Multiplying on the left by gives ; hence and . Therefore has a unique solution.

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

Statement (a) is marked true. Write and . By Theorem 2.3.2,

.

If , then by Theorem 1.3.8,

.

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

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

Statement (b) is false. The counterexample uses and , so . Its first column is not a linear combination of the columns and of : the submitted RREF shows that the corresponding system is inconsistent.

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

For a linear , the proof by induction has base , where is linear. Assuming is linear, write . The key theorem gives a matrix with ; hence

,

so it is linear. Thus is linear for all .

14.5.17Source 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.18Source p. 18 — Part B, Problem 5(b)

Define by if , and otherwise. The submission says is not linear: choose with and , then while . But for all , so is the identity and is linear.

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

Let . If has a unique solution, then has a unique solution; by Theorem 1.3.4, , 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 , proving the claim.

14.6Homework 4 - submitted work

14.6.1Exercise 28 - inverse of a linear transformation

For

the standard matrix is

The submitted elimination of ends at

Thus

and for all .

14.6.2Exercise 30 - invertibility

Let . By Theorem 2.4.3, is invertible exactly when . Row reduction gives

Therefore is not invertible, regardless of the values of .

14.6.3Exercise 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

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.4Exercise 6 - kernel

For , the submitted row reduction is

Hence

so .

14.6.5Exercise 14 - image

For ,

Therefore .

14.7Part B

14.7.1Problem 1 - nilpotent transformations

Let have standard matrix .

14.7.1.1(a)

We prove by induction on that the standard matrix of is . For , . Assume . Using the composition rule and associativity,

Thus the statement holds for all .

14.7.1.2(b)

Assume that is nilpotent. Then, for some positive integer , for all . By part (a), for all . Suppose, for contradiction, that is invertible. Then is invertible, with inverse ( factors). Thus , its rref is , and the augmented system cannot have a solution for every right-hand side as required. This contradicts for all . Therefore is not invertible.

14.7.1.3(c)

If , then , hence and is invertible. For , set

Then

and, similarly, . Thus is invertible, and so is .

14.7.2Problem 2 - the vector space

For and , pointwise addition gives the vector-space axioms:

and the function is an additive identity. For each , the function is its additive inverse. For scalars ,

All expressions are defined in , so is a vector space.

The element is the function , whereas is an element of ; they are different elements although the function value is always .

is not necessarily a vector space. For example, take with , which is not in . The constant functions and lie in , but would have value , 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.3Problem 3 - polynomial transformation

Let .

14.7.3.1(a)

For ,

and for ,

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

we have although .

14.7.3.3(c)

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

take

Then .

14.7.4Problem 4 - left multiplication

For , :

14.7.4.1(a)

For and ,

So is linear.

14.7.4.2(b)

If is invertible and , multiplication by gives , 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 is impossible.

14.7.5Problem 5 - rotations and projection

For :

14.7.5.1(a)

has image . Projection onto the -axis has image the -axis, and rotation clockwise by sends this to a line clockwise from the -axis. Thus the angle between and the -axis is .

14.7.5.2(b)

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

14.7.5.3(c)

For , the image is a line from the -axis and the kernel is a line from the -axis. They agree when

equivalently for .

14.8Homework 5 - submitted work

14.8.1Exercise 56 - linear independence

Rearrange the four given vectors as

Each has an entry where all preceding vectors have and it has a nonzero entry. Thus, in a relation , the sixth coordinate forces , and the same argument forces one by one. The vectors are linearly independent for all .

14.8.2Exercise 33 - hyperplanes

For , let . The hyperplane is , and the image of is nonzero because some . Hence its image has dimension , and rank-nullity gives

Thus a hyperplane in is a plane, and a hyperplane in is a line.

14.8.3Exercise 63 - equal-dimensional nested subspaces

Let be a basis of , with and . The vectors 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.4Exercise 12 - arithmetic sequences

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

then

For ,

Hence is a subspace.

14.8.5Exercise 28 - commuting matrices

Let and . The equation gives

so and . Therefore

The displayed matrices are linearly independent, so they are a basis and .

14.9Part A - Problem 6

For each diagram, the submitted dependent triples are:

(a) , , , , , , , , , (10 sets). (b) , , , , , , , (8 sets). (c) , , , , , (6 sets). (d) , , , , , .

14.10Part B

14.10.1Problem 1 - images of independent lists

14.10.1.1(a)

False. Let be . The vectors are linearly independent, but their images are both , so the image list is linearly dependent.

14.10.1.2(b)

True. Assume is linearly independent and . Then

Independence of gives , so is linearly independent.

14.10.2Problem 2 - prescribed kernel and image

The rref required by

is

The target image has basis . Choosing the first and second nonredundant columns accordingly gives

and is one solution.

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

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

14.10.3Problem 3 - maps defined on a basis

14.10.3.1(a)

Let be a basis of , and write . Define

For , , this rule gives

and , so it is linear. If has the same values on the basis, then , so it is unique.

14.10.3.2(b)

Let and let be a basis of . Extend it to a basis of . Since , choose a basis of and define

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.4Problem 4 - ranks and nullities of a composition

14.10.4.1(a)

True. Since ,

14.10.4.2(b)

True. View the composition in two stages. First ; then . Rank-nullity for the restricted second map gives

14.10.4.3(c)

True. Rank-nullity yields

Part (b) then implies .

14.10.4.4(d)

False. If is surjective, then , so and . When , the claimed inequality fails.

14.10.5Problem 5 - symmetric and skew-symmetric matrices

For :

14.10.5.1(a)

, and , so is linear.

14.10.5.2(b)

If , then , so . Conversely, implies , so . Also satisfies , whence . If , choose ; then . Therefore .

14.10.5.3(c)

Both are subspaces. Each contains the zero matrix. If and , then and ; this proves the subspace conditions for . Replacing by gives the same argument for .

14.10.5.4(d)

There are 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

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

14.11Homework 6 - submitted work

14.11.1Exercise 50 - hexagonal coordinates

For the basis in the hexagonal tiling,

The point with is the center of a tile. Further,

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

14.11.2Exercise 70 - upper triangular coordinate matrix

There is no basis of whose -matrix for

is upper triangular. Suppose, for a contradiction, that

Then the generalized key theorem gives

Writing yields

Thus , since and cannot both vanish. This is impossible because cannot be a basis vector.

14.11.3Exercise 58 - the solutions of

14.11.3.1(a)

For , . Let

Then

so is constant.

14.11.3.2(b)

If , the constant from part (a) is . Therefore for all , and for all .

14.11.3.3(c)

is a vector space; moreover, and . Hence for ,

is in . We have and

Part (b) gives , so

Thus spans .

14.11.4Exercise 46 - multiplication by

For ,

Thus is linear. It is not an isomorphism because it is not surjective: a nonzero constant target polynomial cannot be for a polynomial .

14.11.5Exercise 68 - isomorphism condition

For ,

The source and target have equal dimension, so is an isomorphism exactly when it is injective, equivalently when . This holds for . For or , the kernel has dimension , so is not an isomorphism.

14.12Part B

14.12.1Problem 1 - coefficient map

Let be defined by

14.12.1.1(a)

For coefficient columns and ,

and . Hence is linear.

14.12.1.2(b)

If is injective and , then

so for every . The list is linearly independent. Conversely, if is linearly independent and , then

Thus for all , and is injective.

14.12.1.3(c)

If is surjective, every equals , 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.2Problem 2 - coordinate matrices for symmetrization

Let for .

14.12.2.1(a)

With , the -matrix is

14.12.2.2(b)

For ,

14.12.2.3(c)

Solving gives

14.12.2.4(d)

The corresponding subspace of is

with basis .

14.12.2.5(e)

Solving gives

14.12.2.6(f) and (g)

The coordinate isomorphism sends

Hence the image of the -coordinate kernel is

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

14.12.2.7(h)

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

14.12.3Problem 3 - a trigonometric vector space

Let

and , .

14.12.3.1(a)

For , the identities , , and give

So spans . If , evaluate at , , and to get . Thus is an ordered basis.

14.12.3.2(b)
14.12.3.3(c)

For ,

Thus is closed under differentiation.

14.12.3.4(d)

has

so

14.12.3.5(e)

Row reduction of gives

Therefore

14.12.3.6(f)

The coordinate vector of is . Applying the inverse matrix gives , so

14.12.4Problem 4 - products of vector spaces

14.12.4.1(a)

If and are the zero vectors of and , the zero vector of is .

14.12.4.2(b)

Let be a basis of and a basis of . For , write

Then

so the listed vectors span. If their linear combination is , then and . Independence of the two bases forces all coefficients to vanish. Therefore

is a basis of .

14.12.4.3(c)

The basis in (b) has vectors, so

14.12.5Problem 5 - sum and intersection

Let be .

14.12.5.1(a)

, and , so is linear. Each has the form , so is surjective.

14.12.5.2(b)

If , then , so it belongs to both and . Hence

The map , , is linear, injective, and surjective; hence it is an isomorphism.

14.12.5.3(c)

Since is isomorphic to and is surjective, rank-nullity with part 4(c) gives

14.12.5.4(d)

For three-dimensional subspaces of , would give , contradicting . Thus it is impossible. In it is possible; for example,

Then and .

14.13Homework 7 — submitted work

Chapter 15Part A

15.14.3 Exercise 14

For relative to , the submission forms from . It finds

so

Hence

A basis for the kernel is ; a basis for the image is ; and .

15.24.3 Exercise 28

For and ,

This has full rank, so is invertible, is an isomorphism, and .

15.34.3 Exercise 60

In let

The submitted change-of-basis matrices are

and .

15.45.1 Exercise 6

For and ,

Thus rad (approximately 97.4 degrees).

15.55.1 Exercise 17

For , the equations for reduce as

Thus , , and

15.65.1 Exercise 26

With and ,

Chapter 16Part B

16.1Problem 1

For ordered bases , writing and taking ,

So

Taking makes corresponding columns equal; therefore

Consequently,

16.2Problem 2

For , , and ,

so .

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

16.3Problem 3

Let and . By the change-of-basis theorem, , where . The submission proves by induction that

for each integer . The inductive step is

Thus and are similar.

For the false kernel claim, it takes

It records

but

For equal nullities, rank-nullity gives

The page proves from , the analogous bound for by transposition, and equality when is invertible. Since , , so the kernel dimensions agree.

16.4Problem 4

For , bases and , define

The source diagram verifies

hence . Thus

For ,

and therefore

16.5Problem 5

For , , :

The source chooses . For it computes

so

16.6Problem 6

Let and . For ,

, and

With ,

The source uses

to obtain

16.7Homework 8 — submitted work

Chapter 17Part A

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

17.15.1 Exercise 45

For and , put . Orthogonality gives

so , , and

17.25.2 Exercise 14

For , the submitted Gram–Schmidt calculation gives

It states that is the orthonormal basis.

17.35.2 Exercise 26

For and ,

and

17.45.3 Exercise 36

For , the roles must be orthonormal. The page solves

giving and .

17.55.4 Exercise 26

For , , the normal equation is

Its reduced echelon form is

so

17.65.4 Exercise 32

For , let , with

The source gives

and

Chapter 18Part B

18.1Problem 1

For :

18.1.1(a)

If for , then is an orthonormal basis. Writing ,

so is the orthogonal projection onto .

18.1.2(b)

If the basis is not perpendicular, some . While ,

by linear independence. Thus is not .

18.2Problem 2

For the set of orthogonal matrices:

18.3Problem 3

For an orthonormal basis ,

and the calculation on the page is

For two orthonormal bases , has entry and has transpose entry . Hence

so is orthogonal.

18.4Problem 4

The submitted answers are:

18.5Problem 5

18.5.1(a)

For , and ,

implies , because every . Thus .

18.5.2(b)

For a relation

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

18.5.3(c)

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

18.6Problem 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.7Homework 9 — submitted work

Chapter 19Part A

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

19.15.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:

19.25.4 Exercise 31

For the three points , the line of best fit uses

The normal equations recorded in the submission are

and solving them gives and . Hence the submitted line is

19.35.5 Exercise 15

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

19.45.5 Exercise 23

With

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

19.55.5 Exercise 32

For the weighted integral inner product

the computation in the submitted pages records

when is even, and

when is odd. Also . Applying Gram–Schmidt, it writes

The associated polynomial sequence is recorded as

Chapter 20Part B

20.1Problem 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

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

20.2Problem 2

20.2.1(a)

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

which is nonzero while . 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 as the counterexample. For (ii), the weight gives the required symmetric, bilinear, positive-definite inner product.

20.3Problem 3

Let

20.3.1(a)

The work finds and , then evaluates the remaining displayed polynomial inner products to prepare Gram–Schmidt.

20.3.2(b)

The submitted orthonormalized functions are recorded approximately as

20.3.3(c)

For , the work records

and, after expansion,

20.4Homework 10 — submitted work

Chapter 21Part A

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

21.16.1 Exercise 20

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

for every .

21.26.1 Exercise 54

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

21.36.2 Exercise 42

For a QR factorization , the submission writes

so the determinant is positive.

21.46.2 Exercise 50

For the matrix whose entry is , repeated determinant reduction gives

21.56.3 Exercise 14

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

21.67.1 Exercise 12

For

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

Thus it diagonalizes to .

21.77.1 Exercise 18

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

21.87.1 Exercise 42

The matrices in are written as

The five matrix units in positions form the submitted basis, so

Chapter 22Part B

22.1Problem 1

The proof shows that an alternating bilinear form is antisymmetric:

Conversely, antisymmetry gives . Since , bilinearity then identifies the form with the determinant:

22.2Problem 2

Let and let . The submission verifies linearity. In the ordered basis

it computes

The determinant calculation is

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

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

22.3Problem 3

The construction defines by the determinant/cross-product functional in . For the standard choice , , , the work finds

It proves that exactly when are linearly dependent, that is orthogonal to each of , and that

22.4Problem 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.5Problem 5

For a matrix satisfying , the submission separates the and eigenvector cases and obtains a diagonal form. The final argument extends this to every dimension by decomposing an arbitrary vector as

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

Advanced Linear Algebra

Chapter 23Review on Basic Concepts

23.1Subspace and direct sum

Definition 23.1 (Subspace)

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

  1. 1.

    包含 0

  2. 2.

    对 addition 和 scalar multiplication 闭合

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

Proposition 23.1

两个 subspace 的 sum 也是一个 subspace, 并且

且 是同时包含 和 的 的最小 subspace.

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

Definition 23.2 (Direct sum)

如果 中的任意元素 ,都存在唯一的 for each 使得 ,就称 为一个 direct sum.

我们显然发现:

Proposition 23.2

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

Theorem 23.1

是一个 direct sum (这几个空间“垂直”) iff 任取 分别来自 ,它们都 lin. ind.

并且:

Theorem 23.2

为一个 direct sum iff .

Remark

实际上两个 subspace 的交集里只要有一个非 0 点,那么这个点 span 的整个 dim 为 1 的线都在交集里.

Note

Chapter 24Linear functional and Duality

Definition 24.1 (Linear functional)

Chapter 25Eigenvalues and Operators

Chapter 26Operators on complex VS

Chapter 27Multilinear Algebra

Numerical Linear Algebra

Chapter 28tensor 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.1 ((not rigorous) Tensor product)

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

s.t. 对于 的 basis 和 ,我们给每个 都赋予一个不同的 image ,其 over 具有 bilinear 性。

对于

也是一个 over 的 vector space,且 。

Proposition 28.1 (representing tensor product as matrix)

如果我们有两个矩阵:

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

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

(我们可以把 , 分别看作 , dim 的向量,这个 是 dim 的向量。)

Definition 28.2 (outer product of two vectors)

对于 ,,我们定义它们的 outer product 为:

28.1matrix product through outer product

Theorem 28.1 (representing matrix multiplication by outer products)

对于 的矩阵 和 的矩阵 ,we have:

Proof

In md.

Remark

两个 vectors 的 outer product,一定是一个 rank 为 1 的 matrix。因为它每一 column 都是 的一个倍数。

但是我们可以累加 个这样的 outer products,从而得到一个可以是 full rank 的矩阵。(我们知道当然,矩阵相加不保留 rank。)

Chapter 29orthogonal vectors and matrices

Definition 29.1 (adjoint(hermitian conjugate))

̂*:

(where each overline means complex conjuate.)

Remark

Can easily comfirm:

Definition 29.2 (standard inner product and norm on )

The standard inner product:

The standard norm:

Remark

,其中 。

Note: It is actually , but not ,这是因为 等于这个 complex scalar isomorphic 到 上的 Euclidean norm,

这是因为两个复数相乘等于长度相乘幅角相加,而 conjugate 的幅角是相反的,所以 conjugate 之间相乘等于幅角相互抵消,结果在 positive real axis 上,取开方得到长度。

而平方得到的则是一个转两次的幅角。

Remark

Can easily verifies:

且注意:By bilinearity,对于 上的 scaling 在拿出 inner product 外后要进行 conjugate。

Definition 29.3 (orthogonal, orthonomal vectors)

Say 是 orthogonal vectors,if 。

Say 是 orthogonal 的,如果其中的 vectors 相互 orthogonal。

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

Theorem 29.1 (orthogonal lin.ind)

orthogonal 的 vectors 一定 linearly independent。

Proof

trivial.

Corollary 29.1

orthogonal 的 个 vectors 一定是 的一个 basis。

29.1decomposing vector by an orthonormal set

Theorem 29.2 (decomposing vector by an orthonormal set)

给定 中的一个 orthonormal set (by inner product ,这里以 standard complex inner product 为例),对于一个 arbitrary vector ,我们 define:

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

Proof

注意:由于 都是 unit vectors, is the projection of onto the direction of .

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

并且由于 是 unit vector,得到 ,从而右边为 0。

Remark

如果 ,那么 ,我们把 arbitrary vector 分解成了 方向上的向量,相当于对它进行了 change of basis。这个 change of basis matrix 就等于 。

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

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

Theorem 29.3 (projection matrix)

对于任意的 unit vector ,we have

其中 is called the projection matrix onto .

Proof

In md.

Notice that this matrix is rank 1.

Definition 29.4 (Unitary matrix)

一个 square matrix 被称为 unitrary 的,if 。

Remark

unitrary: 即 。

In real case, 它被称为 orthogonal matrix.

Theorem 29.4 (unitrary matrix 的充要条件)

is unitrary its columns are orthonormal its rows are orthonormal

Proof

显然,因为 unitrary

Theorem 29.5 (unitrary transfromation preserves inner product and length)

如果 is unitrary,那么对于任意的 ,都有:

并且自然得到

Proof

Follows from: :

Remark

并不 preserve 自定义的 inner product,只 preserve standard inner product 和 standard norm.

Chapter 30norms

Definition 30.1 (norm)

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

  1. 1.

    nonnegativity (0 iff )

  2. 2.

    trianglar ineq

  3. 3.

    homogenity

的 function

30.1norms on

Example 30.1

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

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

-norm:最长维度.

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.2operator norms on matrix spaces

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

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

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

Example 30.2

Definition 30.2 (Operator norm)

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

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

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

Proposition 30.1 (diagonal matrix 的 norm: reduced to max diag element)

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

其中 为对角线上的元素。

Proof

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

因而选择绝对值最大的 ,拉伸最大的 vector 一定是 where only the -th coordinate is ,因为这个 ball 上所有的 vectors 原本的 norm 都是一样的,而这个 vector 完整地吃到了最大的拉伸程度,其他 vectors 都或多或少吃到了其他 的拉伸效果。

Proposition 30.2 (1-norm: reduced to max column sum)

matrix 的 1-norm 实则就是 1-norm 最大列的 1-norm.

Proof

因为

并且 ,因而这个和 。

并且我们发现,这个值是可以取到的: suppose 最大,那么取 就可以了。

直观而言,由于 1-norm 的单位球和它的 image 都是一个多面体,它取到最大的点一定是某个顶点。以这里的 为例,一定是 , 中的一个。

Proposition 30.3 (-norm: reduced to max row sum)

matrix 的 -norm 实则就是 -norm 最大行的 -norm.

Proof

直观上,image 的 sup norm 只取最大的那一个 entry,因而一定是取矩阵总(absolute)长度最大的一列, 因为每一列都只贡献 image vector 中的一个 entry。

并且,我们注意到,source vector (on单位球) 包括了所有的最大 entry 为 的 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.3Caychy-Swartz and Frobeniu norm

Theorem 30.1 (Hölder inequility and Cachy-Swartz)

Let , let s.t.

Holder ineq:

Cauchy-Schwarz ineq(special case of Hölder ineq when ):

Remark

Holder’ ineq 可以 generalize 到 -measurable space, Cauchy-Swartz 可以推广到任何 Banach space. 此处不展开.

Proof

of Cauchy-Swartz:

By homogenity of inner product and norm, it suffices to prove for unit vector .

因而

等号成立 iff .

Example 30.3

Applying Cauchy-Swartz 可以发现: row vector 的 matrix 2-norm 等于它 (adjointed) 作为 vector 的 vector 2-norm.

这是因为 consider , 则 ,因而总有 。并且这个等号可以取到, by taking .

Example 30.4

任取两个 vectors ,它们 outer product 成的 rank-one matrix,其 operator 2-norm 小于等于它们自身的 2-norm 的乘积。

这是因为: 这一 outer product 乘以一个向量,即每行都是 的一个倍数 ( 倍) 的矩阵乘以这个向量。因而,每行得到的都是 乘上 这个 inner product,最后得到的就是

即 的一个倍数,这个倍数等于 。

Example 30.5

Theorem 30.2

(并且通常取不到等号.)

Proof

不证明了. Playing with definition 加上 Cauchy-Swartz.

Definition 30.3 (Frobenious norm)

等于把这个 matrix 展开为 的 vector 的 vector 2-norm.

Theorem 30.3 (equivalent form of Frobenius norm)

Proof

trivial. , 的 trace 上每个元素,都是 的一行与自己的 dot product,即这一行作为 row vector 的 2-norm 的平方;

Proposition 30.4

Proof

因为 的每个 entry 作为 和 的 inner product, by Cauchy-Swartz, have

因而:

(虽然这看起来很不对, 但容易验证, 这上下两个 sum 是相等的. )

Theorem 30.4 (unitrary matrix preserves 2-norm 和 Frobenius norm)

Let be unitrary, then

Proof

因为 for each .

Frobenius norm:

Chapter 31SVD

SVD 的 motivation:一个 linear transformation 可以通过 unit sphere 的 image 来唯一确定。并且,这个 unit sphere 的 image 一定是一个 hyperellipse (高维椭圆)。

Definition 31.1 (principal semiaxes, Singular value)

对于一个 linear transformation ,我们 denote the unit sphere in as ,把 这一 hyperellipse 中相互 orthogonal 的各轴上的 vectors 表示为 。其中 decsending, 为 unit vectors。

我们称 为 left singular vectors, 为 singular values,而 作为

31.1reduced SVD

Chapter 32QR factorization

32.1projector

Definition 32.1

我们称一个 operator 为一个 projector, if

Note: 不要求是 linear 的. For linear case, 这是一个idempotent linear map.

(而我们将主要关注于 linear orthogonal projector.)

Remark

一个 projector 总有:

对于任意 次 composition。

即:在第一次作用后,之后再对其结果进行这一映射不作出任何改变。

直观:这个映射的效果是把一个向量投影到一个低维度子空间上,从而,在作用过一次后,再次施加这一映射将没有任何改变。

Remark

对于 orthogonal 的 projector,我们称其为 orthogonal projector; 对于 non-orthogonal 的 projector,我们称其为 oblique projector.

Remark

projector 虽然不保证是 linear 的,但是要么是 linear 的,要么就是个 affine transformation. 和 linear 也差不多. 不用在意这些细节.

以下,我们都只考虑 projector linear 的情况. nonlinear 的情况是类似的.

Lemma 32.1

我们发现,一个 projector 沿着 把空间投影到 上.

Lemma 32.2

一个 projector 的 eigenvalue 只有可能是 或者 . 它的 SVD 同时也是 eigenvalue decomposition:

其中 是一个前面全 1, 后面全 0 的对角矩阵.

Lemma 32.3 (complement projector)

如果 是一个 projector,那么 也是一个 projector.

我们称 为 的 complementary projector.

并且我们有: complementary projector 的 ker 是原 projector 的 im, im 是原 projector 的 ker.

Remark

把 vectors 沿着 投影到 ;

把 vectors 沿着 投影到 .

Definition 32.2 (Orthogonal projector)

我们称一个 projector 是 orthogonal projector,如果 .

Theorem 32.1

一个 projector 是 orthogonal projector ,即 是 Hermitian 的.

Theorem 32.2

一个 projector 是 orthogonal projector,则它的 complementary projector 也是 orthogonal projector.

Corollary 32.1

orthogonal projector 的 complementary 把 vectors 投影到 上.

32.2classical 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.1idea of triangular orthogonalization

classical Gram-Schmidt orthogonalization 的 idea 是: 我们逐列地将 的 columns 转变为相互 orthogonal 的新列.

具体: 我们每次都把 减去 的 span 包含的成分,从而制作成和 的 span 正交的新列 :

展开这个定义:

这个过程可以通过定义:

(Note that the sign of is not determined. Arbitrarily, we may choose , in which case we shall finish with a factorization in which has positive entries along the diagonal.)

从而这个过程写作:

我们发现:

这个过程使得:

从而:

32.2.2algorithm

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.3modified Gram-Shimitdt (triangular orthogonalization)

32.4Household Triangularization

Chapter 33Discrete Fourier transform and FFT algorithm

Chapter 34conditioning 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.1 (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 就是一个 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.1absolute/relative condition number of a problem

Definition 34.2 (absolute condition number)

表示 附近的一个 small perturbation,并用

来表示 随之产生的变化。

定义 absolute condition number 为:

Remark

即, 附近比较小的区域上, 的值随 的变化的变化量。

我们发现,这和导数的定义很相近,就是加了一个 norm。当然,并不完全是。因为这里取的是 。导数未必存在,但是这个 总是存在的(如果 count into infty 的话). absolute condition number 是一种上极限概念,表示 周围的 变动幅度最大的值; 而它也不完全是导数值 (recall: 导数是 best linear approximation of this function near this point, 和原 function 的形状是一样的, 这里 take 的是导数的某个 matrix operator norm, determined by 我们对 使用的 norm)

具体:我们发现,当 足够小的时候,we have:

(这里使用 approx,但是可以严格证明.) 从而,如果 differentiable,

简写:

这里还有另外一个 condition number:

Definition 34.3 (relative condition number)

(recall: 并不是 的倍数而是:

即 perturbated 后的函数值和原先的函数值的差.)

Remark

它表示的是,对于 附近的 perturbation, 相对自身的比例变化,引发的 相对自身的比例变化,的最坏情况。

对于 differentiable ,有

这里对于 absolute/relative condition number 有一种不严谨的记法: 我们把 看作 infinitesimal (当然,严格的分析里并不存在) 那么可以简写为:

Example 34.1

问题 1. , 即把一个数取半. 那么对于任意 都有:

well-conditioned.

问题 2. , 即取一个数的 sqrt, , 有:

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.1examples: 两数相减

Example 34.2

问题 3: 两数字相减.

For simplicity, 取 -norm, 得到 , 于是

如果 large 时, 就会变的很大。因而 this problem is ill-conditioned when . 这符合 “cancellation error”: 相近的两个数相减会损失有效数字, 放大误差.

For example:

它们的差:

如果浮点数只能保留 7 位有效数字 (单精度), 那么 被存为 123456.8, 被存为 123456.8, 相减后结果是 , 完全错误. 这就是 cancellation error:由于精度丢失导致的小差值计算结果失真.

34.1.2example: polynomial 求根

Example 34.3

问题 4: polynomial 求根. , 把 个系数 maps to 个 roots.

我们考虑

如果 coefficient 被 perturbed by an infinitesimal quantity , 那么 the perturbation of root 是多少? 答案是:

从而对于这个问题:

证明 selected-TeX label perturbation of a root given perturbation of a coeff: (非 rigorous)

perturbed polynomial 即:

我们要求的 perturbation , 无法直接得到等式关系. 但是我们知道新的 root 是: .

即:

从而:

Using Taylor expansions:

其中 . 并且,,因为在乘方的作用下这个 perturbation 作用可以忽略 (作为高阶无穷小). 从而得到

从而得到

Polynomial rootfinding 是 ill-conditioned, 即便不涉及 multiple roots 问题. 比如经典的 “Wilkinson polynomial”:

它的 most sensitive root 是 , 并且对于这个 root, 最 sensitive 的 coefficient to change 是 , 这个 root 和这个 coeff 之间的 condition number 为:

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.3example: matrix 乘 vector

这个 example 分为三部分:

  1. 1.

    Fixing ,

  2. 2.

    Fixing , inverse problem:

  3. 3.

    fixing ,

Example 34.4

Matrix-vector multiplication: (fixing )

即:

Note: 对于任意非零 , 都有

所以

(2) Inverse problem: given 求 , 即 , 也有同样的 condition number bound (这显然,因为对称):

因而我们把 称为一个 matrix 的 condition number.

Definition 34.4 (Condition number of a matrix)

我们定义 condition number of a matrix:

Notice: 如果 , 那么 for , we have:

where 是最小的非零的 singular value.

对于 ,

即 image of the unit sphere 作为 hyperrellipse 的 eccentricity.

Remark

我们已经知道了,对于 (): 不论是 forward problem 还是 inverse problem ,都有

那么等号在什么时候取到呢? 我们以 forward problem 为例: 取 的 SVD: , where

  1. 1.

    unitary,

  2. 2.

  3. 3.

我们令 ,因为 unitary 不改变范数,

所以

这个最大值就是:

这在 只有一个非零坐标, 且对应于最小非零奇异值 时最大. 所以最大值是 。因此:

即,当 是 的 minimal nonzero singular value 的 right singular vector 时, 取到

同理,对于 inverse problem,令 , 有:

其中 . 所以:

最大值发生在 对应于最大奇异值 , 此时

因此

即,当 是 的 maximal singular value 的 left singular vector 时, 取到

至此,我们可以总结这个 theorem (a general version of Theorem 12.2 in textbook Ch12):

Theorem 34.1 (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 的 left singular vector 时取到.

现在我们来考虑: Fixing , 求 的问题.

我们有:

我们知道 , 并且可以 drop the doubly infinitesimal term , 从而得到 即

By matrix norm 小于等于拆分后 norms 的乘积的定理,我们于是有:

即

于是我们得到

神奇地发现,它也被 bound.

并且, equality in this bound will hold whenever is such that

而,我们可以发现对于任意 , 这个 一定存在,即等号一定可以取到. 这是因为 operator norm 与其 dual norm 的等价性:

是一个从 的线性算子,它的 operator norm 是:

我们可以证明这个 supremum 可以达到. 选择

其中 是使得 的单位向量, 是单位方向向量. 于是:

从而我们可以得到这个结论:

Theorem 34.2 (conditioning of matrix times vector: given , problem)

对于 fixing , 考虑 problem , 这一问题一定有 condition number:

34.2float number and machine epsilon

34.2.1float number system

我们知道计算机处理的是离散的数值. 即,一个 computer 的 number system 并非 而是 的一个 discrete (and finite, 但是 ideally 可以看作 infinite) subset , 称之为 float number system.

这个 由这两个参数决定决定:

  1. 1.

    base integer

  2. 2.

    precision integer

(通常 即二进制,而 for IEEE single/double precision.)

precision 决定了这个系统的对数字表示的相对精度 (即即将定义的 machine epsilon); biased exponent 决定了这个系统能够表示的数的范围的上下限.

从而,

这里的 称为 mantissa of ; 称为 exponent.

现实中, 也有范围,取决于计算机位数和架构. 比如说 ieee 双精度 float: 这里 的范围是 , 因而 的范围是 .

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:

因而更加现实的 system 和我们这里的理论 model 有这些差别:

  1. 1.

    还要包括一个额外的参数: exponent offset , 控制 bounded by some 和 .

  2. 2.

    现实的 ieee standard 和我们的 ideal 模型 不同的点, 不仅是 bounded 具有 和 , 还有: 它的每个数其实是 而不是 . 前面的 称为 leading bit. 这是因为在规格化二进制浮点数系统中, 所有非零数的尾数都可以唯一表示成以 开头的形式. 因为这个 总是存在, 可以省略它来节省空间.

  3. 3.

    考虑更多的 symbols, 例如:

SymbolMeaning +0 Postitiveunderflow;between 0 andthesmallestpositiverepresentablefloat − 0 Negativeunderflow + ∞ Positiveoverflow;biggerthanbiggestrepresentablefloat.E.g., 1 0 = 1 +0 −∞ NegativeoverflowNaNNot-a-Number,e.g., 0 0 .

Note: 也是一个 symbol. 并且,现实的 system 里,还要区分正负方向上的 underflow 得到的 .

Definition 34.5 (machine epsilon)

对于一个 discrete number system with precision 和 base ,我们定义:

为什么要这样定义: 因为这两点:

Proposition 34.1

对于任意的 that is within machine 的表示范围,都存在一个 s.t. 使得

这一点是显然的. 任意的大小不能过大的实数,都可以在 machine epsilon 的误差内被 float number 表示.

更加好的是:

Theorem 34.3 (Fundamental Axion of Floating Point Arithmetic)

对于一个 discrete number system , 对于任意的 , 都存在一个 error s.t.

such that:

for 任意的 .

(Exclusion: relative error 并不包括 时出现的 cancellation error, 以及其他的 overflow, underflow! 这些是symbolic hacks, 例如 perturbing to gives relative error ; 并且需要注意的是, relative errors are only useful when small, well below .)

即:任意基本运算的相对于自身的误差,都被 bound 在 之内.

为什么是相对误差而不是绝对误差? 因为我们能表示的有效数字位数是固定的. 越大的数,其小数点后的有效数字就越小. 从而,绝对误差就越大. 但是相对误差仅和 和 base 有关.

(Note: On a computer in which intermediate quantities are truncated rather than rounded, Fundamental Axion of Floating Point Arithmetic hold with replaced by .)

Remark

之所以 Float number 的讨论是重要的,因为它是计算机用来近似表示一个实数的方法,而所有的数值计算都要经由此为媒介. 需要注意的是:ultimate access to numbers is via +,−,⋆,÷, 复杂度和误差最终由基本运算衡量.

对于 losing 1 bit 的 round off error 等问题,我们并不在意; 但是,当大量计算 iteratively 堆叠时,一些 first algorithms for many problems might lose half the bits. 这是一个很大的数量: 例如 Classical Gram Schmidt 会失去 half the digits, 相比 modified Gram-Schmidt 而言. 例如, accurate bits 从 52 变为 26.

因而,基于 float number (via machine epsilon) 对一个 algorithm 的 stability 进行分析是重要的. 接下来我们将讲解 stability of an algorithm 这个概念.

34.3stability

Review: 一个 Problem (in our def) 是一个 function , 都是 NVS.

而我们现在定义什么是一个 algorithm:

34.3.1def: algorithm, stability, accuracy

Definition 34.6 (algorithm)

一个 algorithm for a problem 是另一个函数

定义上就是这么简单.

注意: 我们这里的 algorithm 是一个比较 restricted 的定义. Specially, 它并不考虑 randomized algorithms.

Example 34.5

Randomized rounding:

把 round to: 8, with a prob of ; , with a prob of .

我们把 round 得到的结果标记为 , 那么它则是一个 random variable. 并且,它是一个 unbiased random variable,即:

这个 rounding 是一个 algorithm, 但是不包含在我们这里的定义里. 因为原问题是 的, 而这个问题则是 maps to random variables (我们知道一个 random variable 是一个函数, 这是一个 function space) 的. 因而它并不是我们定义的算法.

因而我们的定义其实是 restricted 的. 我们这里只考虑 determinstic 的 algorithm.

Definition 34.7 (accuracy of an algorithm)

给定一个 problem 和一个对应的 algorithm , 我们定义 的 relative error 为

即: algorithm 给出的答案和正确答案的相对 difference.

如果对于每个 都有:

即 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.8 (stability of an algorithm)

给定一个 problem 和一个对应的 algorithm , 如果对于每个 都存在一个 , 其满足

能够使得

那么则称,这个 algorithm 是 statble 的.

Remark

显然,stable 是比 accurate 稍微宽松的要求. 它的要求是: 这个 algorithm gives nearly the right answer to nearly the right question. 比起 accurate, 它放宽在于: 不需要 solve exactly the same question, 只需要 solve 一个很相近的 question 就可以了.

为什么要这样要求? 因为一个计算机很大的问题是: 我们的 input 和理论上的 input 还是不一样的. 比如,我们要输入一个 , 这是一个无限循环的小数,而计算机只能输入有限位数的小数来近似. 因而关于它的计算问题,从输入起就有了误差. 这个误差可能很小,但是一旦遇到 ill-conditioned 的问题,在 condition 比较差的地方 (比如说某个问题在 处, ),那么这个 input 的小误差很可能导致很大的 Output 不同.

从而,我们需要对 input 放宽,尽可能去容忍类似于 round up 这样的问题.

这个时候我有一个问题: stable 这个概念,相比于 accurate,是为了迁就 ill-conditioned 的问题,只要保证我们的算法给出的结果一定是原问题周围某个相似的问题的数值解就可以了. 但是如果这个 problem 是 ill-conditioned,那么原问题的解可能和它周围的其他问题的解差别非常大. 一个 stable 但不 accuratae 的 algorithm,意思就是: 在某些 ill-conditioned 的 input 上,给出的解和我们想要的原问题的解差别非常大,那这个算法还能成为好吗?

这就是数值分析的核心哲学问题之一. stability 已经是一个足够的条件,因为你并不能要求算法给你“一个问题本身都无法承诺”的东西. Stable algorithm 是对现实的诚实反应,承认输入的不可避免误差,并保证: 你得到的结果是“某个微小扰动问题”的真实答案. 它告诉你: 在你所能拥有的误差范围内, 这就是最合理的答案了. 稳定性 = 不人为放大错误.

之所以我们只要求算法的稳定性,就是因为: 如果非要要求准确性,那么很多优秀的 algorithm 可能会因为仅仅几个 problem 本身就 ill-condtioned 的点上的大误差,被判为 inaccurate.

还有一个比 stable 更强的定义

Definition 34.9 (backward stability)

给定一个 problem 和一个对应的 algorithm , 如果对于每个 都存在一个 , 其满足

能够使得 那么则称,这个 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.

Remark

这些定义里面的 是 across all 的, 即存在一个 uniform bound among all , 使得这些误差值 bounded by it.

Example 34.6

我们用一个例子来阐明 “”:

problem: 给定 , solve system for . 假设我们有一个 algorithm 是 stable 的, 那么它满足: 对于给定的 , 存在 uniform bound 使得对于任意的 , 都具有 nearly the same question , 使得 algorithm 给出的 answer 几乎就是这个近似问题 的正确解 .

Formally: 对于任意的 , 都存在 s.t.

使得

这个 是和 input 进入的 无关的, 它被 problem 的参数固定 (here: ). For example, .

Remark

对于 finite dimensional NVS 而言,我们不需要关注使用的是哪个 norm,因为我们知道,finite dimensional NVS 上所有 norms 都是 topologically equiv 的. 这个等价在这里对 asympototic bound 的讨论中很有用,因为 topologically equiv 即: 对于任意两个 norms , 都存在 使得对于任何元素 都有

因而,对于 finite dimensional NVS 而言,如果任意一个 norm 满足

那么任意的 norm 都满足这一点.

34.3.2example: floating point arithmetic

Example 34.7

当然,四种 floating point arithmetic 是有 backward statble 的算法的.

我们以两数相减 from 为例: 我们 canonical 的算法就是把这两个数 round 为 float,然后进行 float 的减法.

其中,

where by def, .

并且我们知道, float 减法的 error 也是 within machine epsilon 的:

从而

where

我们把

从而,这个 canonical algorithm 计算出的是:

where for all , 它对应的这个 和它在 中的 relative distance, within any norm 都是 的.

Remark

值得提的是: 两个数相加的问题 的 canonial algorithm 是 backward stable 的,而一个数加一个固定的常数: 的 canonial algorithm 却不是 backward stable 的.

34.3.3example: 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 .

Remark

对于 solution space 的 dimension 比 problem space 更加大的问题 (以及 problem space 是多个输入, 其中每个输入的 space 的 dimension 比 solution space 的要小), 很少会有 backward stability.

34.3.4theorem: what backward stabililty implies about the accuracy

Theorem 34.4

Suppose a backward stable algorithm is applied to solve a problem with condition number , 那么 relative errors:

(notice: 这说明如果 of this problem bounded,那么 backward stable algorithm 一定是 accurate 的)

Proof

By backward stability, we have for some satisfying

我们把 作为 , 从而有:

而由于这里 已经是 numerically 最小的 error. 从而 By definition of :

这个不等式是因为: 的相对变化和 的相对变化的比例,其上极限就是 . 从而 this implies

这一 theorem 表明: backward stability + good conditioning accuratcy

Chapter 35backward 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.1Stability 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

35.2Stability of Back Substitution

35.3Conditioning of Least Squares

35.4Stability of Least Squares