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: .
For the system
place numbers in the columns of the augmented matrix .
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.
- is called a matrix (row, col; three by four).
- Matrix if same size and .
- If is , is called a square matrix, and the entries form the main diagonal of .
- A square matrix is called diagonal provided all its entries above and below the diagonal are , i.e. whenever .
- 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.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: .
我们可以把之前的对 equation 的操作用在 matrix 上,并且将 answer represented as a vector. Thus the displayed system has answer .
Example: gives .
这个 equation 容易解是因为:
- The leading coefficient is always .
- The leading variable in each equation 在其他 equation 中不出现.
- 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 :
- Divide by , so .
- Eliminate from all other equations above and below.
- Proceed to next equation.
- Check: if non-, inconsistent.
- Rearrange equations so the leading variables are in natural order.
The reduced row-echelon form (行阶梯矩阵 or Rref) satisfies:
- 若一 row 有 non- entries, the first non- entry must be , called the leading or pivot.
- 若一 col 中有 pivot,则 col 中其他 entries 必须为 .
- 若一 row 中有 pivot,则它后每个 row 必须有 pivot 在它右边(and rows of s must be at the bottom of matrix).
之前我们对 linear system 中 equations 的三种 operations 用在 matrix 上,这三种 operation 统称 elementary row operations:
- Divide a row by a non-zero scalar.
- Subtract a multiple of a row from another.
- 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:
To solve for , we need to transform the system into the form . In other words:
- Eliminate terms that are off the diagonal.
- 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.
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:
- planes having a line in common: a system with infinitely many sols.
- planes with no common intersection: a system without sols.
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.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 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).
For an coefficient matrix and the augmented matrix :
- and .
- If the system is inconsistent, .
- If the system has one sol, .
- 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.
To illustrate it: consider linear equations in variables. 每个 都表示一个 plane,而两个 plane 要么平行无交点,要么交于一直线 (infin sols),不可能只有一个交点。
4.3 WS 3, pp. 2–3: matrix algebra and linear combinations
Example: . The product is defined only when the num of col of equals the num of components in .
Example: is a linear combination of and ? Solve . Row reduction gives , , hence .
With augmented matrix , a linear system can be written . Its th component is , the th equation. For , : , equivalently .
For , : . 如果我们可以 divide by matrix ,,就能直接解 。 换言之我们是否能够找到 呢? Chapter 2.
5 Linear transformations
5.1 WS 4, p. 1: coordinate encoding and standard matrices
现在你的位置为 。用一个 vector 表示方位。现在你使用一个 encode 来加密你的方位:
这个加密方位的码为 . 我们做了一个 transformation,使得 the same but 坐标不变。例如 从 坐标 map 到 坐标后仍是 ;但 下的 同样在 下为 ,而 下的 在 下为 。The source sketch marks these corresponding points and axes.
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 .
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.2 WS 4, p. 2: linearity, bases, and transition matrices
6 Geometry of linear transformations
6.1 WS 5, p. 1: examples, scaling, and projection
在 2-1 我们知道 是 中 counter clockwise 转 度的 linear transformation。现在再看几个:
The source diagrams apply them to and :
- : 放大一倍, sending them to and .
- : orthogonal projection onto -axis, sending both to .
- : reflection about -axis.
- : clockwise 转 degrees, sending them to and .
- : 向右 shear, sending them to and .
- : counterclockwise shift + 放大 倍, sending them to and .
Consider a line in coordinate plane, 经过 . 任何 都可以写成 , where and . The transformation is the orthogonal projection of onto , denoted .
随意取 , . 特别地,如果 是 unit vector , then . 这一个 transformation 是 linear 的;with matrix .
The matrix of has form where : .
6.2 WS 5, p. 2: rotations and shearing
For a nonzero vector , write its coordinate in polar form . Rotation gives , so and , which gives the displayed matrix.
6.3 5. Shearing
Vertical shear:
Horizontal shear:
The source’s concluding table records:
- Scaling by : .
- Orthogonal projection onto line : , for and .
- Reflection about line : .
- Rotation through angle (逆时针): .
- Rotation through with scaling by : .
- Shear: horizontal ; vertical .
7 Gram–Schmidt and QR factorization
7.1 WS 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.2 Proof of matrix product theorem
For ordered bases and of :
where
Note that if , then ; hence
8 Orthogonal transformations
8.1 WS 18, p. 1: definition and matrix criteria
因而 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
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.2 WS 18, p. 2: products and change of basis
If is orthogonal, then (也是 ) is orthogonal, since implies . 结论:这意味着对于 的 cols 是 orthonormal 的,那 的 rows 也是 orthonormal 的.
Indeed,
so .
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.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
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
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.2 WS 19, p. 2: normal equations
The normal equation: 的 least square 解当且仅当 is a solution of
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.
10 Inner-product spaces
10.1 WS 20, p. 1: examples and generalized Gram–Schmidt
For the Inner product space of functions on , :
- .
- Linearity: .
- 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.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 have
where (1) is symmetric; (2) and . Indeed
(这个条件等价:充分条件为 且 .) 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
Indeed,
The definition notes: diagonalizable iff 其 matrix of is diagonal. 因而(所有 都相似于 ).
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.
12 Eigenvalues and eigenspaces
12.1 WS 24, p. 1: characteristic polynomial and multiplicities
简明 proof: 是 的 eigenvalue iff iff iff nullity iff iff 不可逆 iff . Thus is a root of .
因而 eigenbases of distinct eigenspaces have linearly independent union, and if , that union is an eigenbasis of for .
Let , let be an eigenvalue and . Let be a basis of , put , and define . Then for ,
Therefore
so
and .
This is the corollary of the preceding two theorems: if has different eigenvalues, then . Proof: 见 P9.
13 Complex eigenvalues
13.1 WS 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.
14 Spectral theorem
14.1 WS 27, p. 1: theorem and first two claims
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.2 WS 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 .
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:
.
The submitted row reduction is . For infinitely many solutions, the final row must be zero, so and . Thus .
14.3.2 Source 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.3 Source p. 3 — Exercise 32
The augmented matrix is reduced as , giving , , and . 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 and and satisfies . The submitted system is , , and , 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 , 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.6 Source 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.7 Source 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.8 Source p. 8 — Exercise 12
The final reduced matrix is . Setting and , the submission gives .
14.3.9 Source p. 9 — Exercise 36
For a vector perpendicular to , let . The condition is . Setting and gives , where and are arbitrary real numbers.
14.3.10 Source p. 10 — Exercise 44
For the traffic-flow diagram, the submitted equations are , , , and . They are rearranged as , , , and .
14.3.11 Source p. 11 — Exercise 44
The submitted row reduction reaches . The free variable is recorded as .
14.3.12 Source p. 12 — Exercise 44
The submitted solution is . Nonnegativity gives . The recorded flow ranges are , , , and .
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: , 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.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 , 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: 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.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: has two square roots, and , 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 or .
- (d) there are infinitely many even primes, and 10 is not even or is not odd.
- (e) every right triangle in 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 is irrational, then is irrational.” Contrapositive: “If is not rational, then is not rational.”
- (c) Converse: “If 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 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: true; 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 . 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.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 matrix and assume has a unique solution. The submission records . 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 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.3 Source p. 3 — Exercise 34
For , the submitted work writes
, , and .
For a matrix with columns , it likewise records .
14.4.4 Source p. 4 — Exercise 48(a)–(b)
(a) If solves and solves , then .
(b) If and solve , then ; hence 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 off that line. The submitted answer is the parallel affine line .
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 , with its tail at .
14.4.7 Source p. 7 — Exercise 6
For ,
.
The submitted standard matrix is , 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,
.
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 and , the work expands
.
Thus the submitted matrix for is ; the work also verifies addition and scalar multiplication.
14.4.10 Source p. 10 — Exercise 46
For and , . The submitted column computation gives
and .
Hence the matrix is .
14.4.11 Source 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.12 Source 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.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 , , , and . Then A intersect B = emptyset but 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 gives .
14.4.15 Source 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.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 and . If , 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 and , the displayed norm values give .
14.4.19 Source p. 19 — Part B, Problem 4(a)–(b)
For an additive , , hence ; also .
14.4.20 Source 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.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 to . The submitted standard matrix is , 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 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.3 Source 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.4 Source 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.5 Source 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.6 Source 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.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 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.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
,
the entry of . Since are arbitrary, .
For (d), the submission begins induction: for a symmetric , is symmetric, and if , then .
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: is not symmetric, while is recorded as symmetric in the submitted counterexample.
14.5.11 Source 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.12 Source 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.13 Source 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.14 Source 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.15 Source 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.16 Source 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.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 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.19 Source 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.6 Homework 4 - submitted work
14.6.1 Exercise 28 - inverse of a linear transformation
For
the standard matrix is
The submitted elimination of ends at
Thus
and for all .
14.6.2 Exercise 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.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
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 , the submitted row reduction is
Hence
so .
14.6.5 Exercise 14 - image
For ,
Therefore .
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 , . 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.2 Problem 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.3 Problem 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.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 , 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.5 Problem 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.8 Homework 5 - submitted work
14.8.1 Exercise 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.2 Exercise 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.3 Exercise 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.4 Exercise 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.5 Exercise 28 - commuting matrices
Let and . The equation gives
so and . Therefore
The displayed matrices are linearly independent, so they are a basis and .
14.9 Part A - Problem 6
For each diagram, the submitted dependent triples are:
(a) , , , , , , , , , (10 sets). (b) , , , , , , , (8 sets). (c) , , , , , (6 sets). (d) , , , , , .
14.10 Part B
14.10.1 Problem 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.2 Problem 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.3 Problem 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.4 Problem 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.5 Problem 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.11 Homework 6 - submitted work
14.11.1 Exercise 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.2 Exercise 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.3 Exercise 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.4 Exercise 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.5 Exercise 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.12 Part B
14.12.1 Problem 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.2 Problem 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.3 Problem 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.4 Problem 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.5 Problem 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.13 Homework 7 — submitted work
15 Part A
15.1 4.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.2 4.3 Exercise 28
For and ,
This has full rank, so is invertible, is an isomorphism, and .
15.3 4.3 Exercise 60
In let
The submitted change-of-basis matrices are
and .
15.4 5.1 Exercise 6
For and ,
Thus rad (approximately 97.4 degrees).
15.5 5.1 Exercise 17
For , the equations for reduce as
Thus , , and
15.6 5.1 Exercise 26
With and ,
16 Part B
16.1 Problem 1
For ordered bases , writing and taking ,
So
Taking makes corresponding columns equal; therefore
Consequently,
16.2 Problem 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.3 Problem 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.4 Problem 4
For , bases and , define
The source diagram verifies
hence . Thus
For ,
and therefore
16.5 Problem 5
For , , :
The source chooses . For it computes
so
16.6 Problem 6
Let and . For ,
, and
With ,
The source uses
to obtain
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 and , put . Orthogonality gives
so , , and
17.2 5.2 Exercise 14
For , the submitted Gram–Schmidt calculation gives
It states that is the orthonormal basis.
17.3 5.2 Exercise 26
For and ,
and
17.4 5.3 Exercise 36
For , the roles must be orthonormal. The page solves
giving and .
17.5 5.4 Exercise 26
For , , the normal equation is
Its reduced echelon form is
so
17.6 5.4 Exercise 32
For , let , with
The source gives
and
18 Part B
18.1 Problem 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.2 Problem 2
For the set of orthogonal matrices:
- (a) False. , but is not orthogonal; the page gives , whereas its inverse is .
- (b) True. The composition of the orthogonal maps represented by has standard matrix , so .
- (c) True by the same composition argument for .
- (d) True. If were orthogonal but were not, with and , then , a contradiction.
- (e) True. gives ; gives , so is symmetric.
18.3 Problem 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.4 Problem 4
The submitted answers are:
- (a) True. , from and double orthogonal complement.
- (b) True. , then rank-nullity gives .
- (c) True. and rank-nullity yield .
- (d) True. With (b), (c), and , .
- (e) False. but ; if they cannot be equal.
18.5 Problem 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.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:
19.2 5.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.3 5.5 Exercise 15
For the bilinear expression in the exercise, symmetry requires . The submitted positive-definiteness test yields the additional condition
19.4 5.5 Exercise 23
With
the answer verifies the inner-product properties and gives the orthonormal basis
19.5 5.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
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
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
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.3 Problem 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.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
for every .
21.2 6.1 Exercise 54
The answer uses positivity to conclude that the determinant of the displayed matrix is positive, and records
21.3 6.2 Exercise 42
For a QR factorization , the submission writes
so the determinant is positive.
21.4 6.2 Exercise 50
For the matrix whose entry is , repeated determinant reduction gives
21.5 6.3 Exercise 14
The parallelepiped volume is found from the determinant. Since the displayed vectors are linearly dependent, the result is
21.6 7.1 Exercise 12
For
the characteristic equation gives eigenvalues and . The corresponding eigenvector directions in the work are
Thus it diagonalizes to .
21.7 7.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.8 7.1 Exercise 42
The matrices in are written as
The five matrix units in positions form the submitted basis, so
22 Part B
22.1 Problem 1
The proof shows that an alternating bilinear form is antisymmetric:
Conversely, antisymmetry gives . Since , bilinearity then identifies the form with the determinant:
22.2 Problem 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.3 Problem 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.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 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.
23 Review on Basic Concepts
23.1 Subspace and direct sum
vector space 的 subset 为一个 subspace,if 它满足条件:
- 包含 0
- 对 addition 和 scalar multiplication 闭合
两个 subset 的和就是各取一个元素相加的所有情况.
很显然我们知道:
两个 subspace 的 sum 也是一个 subspace, 并且
且 是同时包含 和 的 的最小 subspace.
显然可以随便和。同一个 自己和自己的和就是自己。所以 subspace sum 这个概念比较大,没什么用。我们需要用 direct sum 来作为一个小一点但是更有用的概念,表达出一种垂直的 subspace 的直观.
我们显然发现:
我们发现,其实可以 direct sum 的 subspaces 是 “垂直的”,意思是:
并且:
24 Linear functional and Duality
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的。)
令 be vector spaces over ,我们定义一个 vector 与 vector 之间的 tensor product operation:
s.t. 对于 的 basis 和 ,我们给每个 都赋予一个不同的 image ,其 over 具有 bilinear 性。
对于
也是一个 over 的 vector space,且 。
如果我们有两个矩阵:
可以把它们的 tensor product 表示为:
can verify:这个表示是符合 tensor product 的 bilinearity 的。
(我们可以把 , 分别看作 , dim 的向量,这个 是 dim 的向量。)
对于 ,,我们定义它们的 outer product 为:
28.1 matrix product through outer product
对于 的矩阵 和 的矩阵 ,we have:
29 orthogonal vectors and matrices
^*:
(where each overline means complex conjuate.)
The standard inner product:
The standard norm:
Say 是 orthogonal vectors,if 。
Say 是 orthogonal 的,如果其中的 vectors 相互 orthogonal。
Say 是 orthonomal 的,如果其中的 vectors 相互 orthogonal,并且每个 vector 的 norm 都是 1。
29.1 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。
注意:由于 都是 unit vectors, is the projection of onto the direction of .
我们在两边取和 的 inner product,for each 。由 linearity 可拆开,由 orthgonality 可得到:
并且由于 是 unit vector,得到 ,从而右边为 0。 □
对于 unit vector ,我们刚才已经展示了一个 arbitrary vector 在它上面的 projection 是:
现在我们引入另一个形式的 projection 表达:projection matrix
对于任意的 unit vector ,we have
其中 is called the projection matrix onto .
In md.
Notice that this matrix is rank 1. □
如果 is unitrary,那么对于任意的 ,都有:
并且自然得到
30 norms
一个 norm on a vector space 是一个满足:
- nonnegativity (0 iff )
- trianglar ineq
- homogenity
的 function
30.1 norms on
以下为 上的典型 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.2 operator norms on matrix spaces
We know: 所有的 matrix, every entry in 也是一个 vector space of over 。
所以我们当然也可以给 matrix 赋范。
matrix 代表一个 linear transformation,所以 norm 的意义实际上是它 stretch vector 的程度的一种评估。
induced by vector norm. 表示它stretch vector 的最大程度。其中, source 和 image vector 分别用 norm n,m 来判定。
如果 source 和 image vector 的 norm 是一样的,比如都使用某个 norm,那么我们可以用单个符号表示(induced by -norm):
(这更加常用,因为通常我们会对 source 和 image vector 的大小使用相同的评估)
如果 是一个 diagonal matrix,那么不论取什么 -norm,我们都有:
其中 为对角线上的元素。
很直观。我们要把一个以 为衡量的 unit ball 上的哪个 vector 被拉伸的程度最大,而 diagonal matrix 把每个坐标 上的点固定放大 倍,
因而选择绝对值最大的 ,拉伸最大的 vector 一定是 where only the -th coordinate is ,因为这个 ball 上所有的 vectors 原本的 norm 都是一样的,而这个 vector 完整地吃到了最大的拉伸程度,其他 vectors 都或多或少吃到了其他 的拉伸效果。 □
matrix 的 1-norm 实则就是 1-norm 最大列的 1-norm.
因为
并且 ,因而这个和 。
并且我们发现,这个值是可以取到的: suppose 最大,那么取 就可以了。
直观而言,由于 1-norm 的单位球和它的 image 都是一个多面体,它取到最大的点一定是某个顶点。以这里的 为例,一定是 , 中的一个。 □
matrix 的 -norm 实则就是 -norm 最大行的 -norm.
直观上,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.3 Caychy-Swartz and Frobeniu norm
Let , let s.t.
Holder ineq:
Cauchy-Schwarz ineq(special case of Hölder ineq when ):
of Cauchy-Swartz:
By homogenity of inner product and norm, it suffices to prove for unit vector .
因而
等号成立 iff . □
Applying Cauchy-Swartz 可以发现: row vector 的 matrix 2-norm 等于它 (adjointed) 作为 vector 的 vector 2-norm.
这是因为 consider , 则 ,因而总有 。并且这个等号可以取到, by taking .
任取两个 vectors ,它们 outer product 成的 rank-one matrix,其 operator 2-norm 小于等于它们自身的 2-norm 的乘积。
这是因为: 这一 outer product 乘以一个向量,即每行都是 的一个倍数 ( 倍) 的矩阵乘以这个向量。因而,每行得到的都是 乘上 这个 inner product,最后得到的就是
即 的一个倍数,这个倍数等于 。
(并且通常取不到等号.)
等于把这个 matrix 展开为 的 vector 的 vector 2-norm.
因为 的每个 entry 作为 和 的 inner product, by Cauchy-Swartz, have
因而:
(虽然这看起来很不对, 但容易验证, 这上下两个 sum 是相等的. ) □
Let be unitrary, then
因为 for each .
Frobenius norm:
□
31 SVD
SVD 的 motivation:一个 linear transformation 可以通过 unit sphere 的 image 来唯一确定。并且,这个 unit sphere 的 image 一定是一个 hyperellipse (高维椭圆)。
对于一个 linear transformation ,我们 denote the unit sphere in as ,把 这一 hyperellipse 中相互 orthogonal 的各轴上的 vectors 表示为 。其中 decsending, 为 unit vectors。
我们称 为 left singular vectors, 为 singular values,而 作为
31.1 reduced SVD
32 QR factorization
32.1 projector
我们称一个 operator 为一个 projector, if
Note: 不要求是 linear 的. For linear case, 这是一个idempotent linear map.
(而我们将主要关注于 linear orthogonal projector.)
以下,我们都只考虑 projector linear 的情况. nonlinear 的情况是类似的.
一个 projector 的 eigenvalue 只有可能是 或者 . 它的 SVD 同时也是 eigenvalue decomposition:
其中 是一个前面全 1, 后面全 0 的对角矩阵.
如果 是一个 projector,那么 也是一个 projector.
我们称 为 的 complementary projector.
并且我们有: complementary projector 的 ker 是原 projector 的 im, im 是原 projector 的 ker.
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 的新列.
具体: 我们每次都把 减去 的 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.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
ENDFOR32.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.
我们把一个 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.1 absolute/relative condition number of a problem
表示 附近的一个 small perturbation,并用
来表示 随之产生的变化。
定义 absolute condition number 为:
这里还有另外一个 condition number:
(recall: 并不是 的倍数而是:
即 perturbated 后的函数值和原先的函数值的差.)
这里对于 absolute/relative condition number 有一种不严谨的记法: 我们把 看作 infinitesimal (当然,严格的分析里并不存在) 那么可以简写为:
问题 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.1 examples: 两数相减
问题 3: 两数字相减.
For simplicity, 取 -norm, 得到 , 于是
如果 large 时, 就会变的很大。因而 this problem is ill-conditioned when . 这符合 “cancellation error”: 相近的两个数相减会损失有效数字, 放大误差.
For example:
它们的差:
如果浮点数只能保留 7 位有效数字 (单精度), 那么 被存为 123456.8, 被存为 123456.8, 相减后结果是 , 完全错误. 这就是 cancellation error:由于精度丢失导致的小差值计算结果失真.
34.1.2 example: polynomial 求根
问题 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.3 example: matrix 乘 vector
这个 example 分为三部分:
- Fixing ,
- Fixing , inverse problem:
- fixing ,
Matrix-vector multiplication: (fixing )
即:
Note: 对于任意非零 , 都有
所以
(2) Inverse problem: given 求 , 即 , 也有同样的 condition number bound (这显然,因为对称):
因而我们把 称为 一个 matrix 的 condition number.
我们定义 condition number of a matrix:
Notice: 如果 , 那么 for , we have:
where 是最小的非零的 singular value.
对于 ,
即 image of the unit sphere 作为 hyperrellipse 的 eccentricity.
至此,我们可以总结这个 theorem (a general version of Theorem 12.2 in textbook Ch12):
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 可以达到. 选择
其中 是使得 的单位向量, 是单位方向向量. 于是:
从而我们可以得到这个结论:
对于 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.
这个 由这两个参数决定决定:
- base integer
- 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 有这些差别:
- 还要包括一个额外的参数: exponent offset , 控制 bounded by some 和 .
- 现实的 ieee standard 和我们的 ideal 模型 不同的点, 不仅是 bounded 具有 和 , 还有: 它的每个数其实是 而不是 . 前面的 称为 leading bit. 这是因为在 规格化二进制浮点数系统中, 所有非零数的尾数都可以唯一表示成以 开头的形式. 因为这个 总是存在, 可以省略它来节省空间.
- 考虑更多的 symbols, 例如:
| Symbol | Meaning |
| Postitive underflow; between and the smallest positive representable float | |
| Negative underflow | |
| Positive overflow; bigger than biggest representable float. E.g., | |
| Negative overflow | |
| NaN | Not-a-Number, e.g., . |
Note: 也是一个 symbol. 并且,现实的 system 里,还要区分正负方向上的 underflow 得到的 .
对于一个 discrete number system with precision 和 base ,我们定义:
为什么要这样定义: 因为这两点:
对于任意的 that is within machine 的表示范围,都存在一个 s.t. 使得
这一点是显然的. 任意的大小不能过大的实数,都可以在 machine epsilon 的误差内被 float number 表示.
更加好的是:
对于一个 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 .)
34.3 stability
Review: 一个 Problem (in our def) 是一个 function , 都是 NVS.
而我们现在定义什么是一个 algorithm:
34.3.1 def: algorithm, stability, accuracy
定义上就是这么简单.
注意: 我们这里的 algorithm 是一个比较 restricted 的定义. Specially, 它并不考虑 randomized algorithms.
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.
给定一个 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, 我们应该放低要求.
给定一个 problem 和一个对应的 algorithm , 如果对于每个 都存在一个 , 其满足
能够使得
那么则称,这个 algorithm 是 statble 的.
还有一个比 stable 更强的定义
给定一个 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.
我们用一个例子来阐明 “”:
problem: 给定 , solve system for . 假设我们有一个 algorithm 是 stable 的, 那么它满足: 对于给定的 , 存在 uniform bound 使得对于任意的 , 都具有 nearly the same question , 使得 algorithm 给出的 answer 几乎就是这个近似问题 的正确解 .
Formally: 对于任意的 , 都存在 s.t.
使得
这个 是和 input 进入的 无关的, 它被 problem 的参数固定 (here: ). For example, .
34.3.2 example: floating point arithmetic
当然,四种 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 都是 的.
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
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 的)
By backward stability, we have for some satisfying
我们把 作为 , 从而有:
而由于这里 已经是 numerically 最小的 error. 从而 By definition of :
这个不等式是因为: 的相对变化和 的相对变化的比例,其上极限就是 . 从而 this implies
□
这一 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