在看量子计算之前，决定先复习一下线性代数，毕竟一年半没看了（逃
大概就是快速过一遍GSLA吧,顺便拿来训练阅读速度
（下面的前五章是对着第四版（前五章跟第五版差别不大）写的，后七章是对着第五版写的）
Contents
- 1 Introduction to Vectors
- 2 Solving Linear Equations
- 3 Vector Spaces and Subspaces
- 4 Orthogonality
- 5 Determinants
- 6 Eigenvalues and Eigenvectors
- 7 The Singular Value Decomposition (SVD)
- 8 Linear Transformations
- 9 Complex Vectors and Matrices
- 10 Applications
- 11 Numerical Linear Algebra
- 12 Linear Algebra in Probability & Statistics
1 Introduction to Vectors
1.1 Vectors and Linear combinations
- the basic operations on vectors are multiplication cv and vector addition v + w.
- The sum of cv and dw is a linear combination of v and w.
- there is a perfect match between the column vector and the arrow from the origin and the point where the arrow ends.
1.2 Lengths and Dot Products
- The dot product \(v \cdot w\) multiplies each component \(v_i\) by \(w_i\) and adds all \(v_iw_i\).
- The length \(\|v\|\) of a vector is the square root of \(v \cdot v\).
- Unit vectors u and U at angle \(\theta\) have \(u \cdot U = cos \theta\).
- Schwarz inequality: \(|v \cdot w| \le \|v\| \|w\|\).
- triangle inequality: \( \|v + w\| \le \|v\| + \|w\| \).
1.3 Matrices
- Ax = b:
The matrix A acts on the vector x. The output Ax is a combination b of the columns of A. (in column’s view)
Ax is also dot products with rows. (in row’s view) - The relationship between Difference Matrix and Derivative.
The Sum Matrix is the inverse matrix of the Difference Matrix.
the Integration is the inverse of the Differentiation. - Independent columns: Ax = 0 has one solution. A is an invertible matrix.
Dependent columns: Cx = 0 has many solutions. C is a singular matrix.
2 Solving Linear Equations
2.1 Vectors and Linear Equations
- Column picture: Ax = b asks for a combination of columns to produce b.
- Row picture: Each equation in Ax = 0 gives a line (n = 2) or a plane (n = 3) or a “hyperplane” (n > 3).
They intersect at the solution or solutions, if any. - but Ax should be understood as a combination of the columns of A.
2.2 The idea of Elimination
- A linear system (Ax = b) becomes upper triangular (Ux = c) after elimination.
- The upper triangular system is solved by back substitution (starting at the bottom).
- A zero in the pivot position can be repaired if there is a nonzero below it.
- When breakdown is permanent, the system has no solution or infinitely many.
2.3 Elimination Using Matrices
- The Identity Matrix has 1’s on the diagonal and otherwise 0’s.
Then \(Ib = b\) for all b. - The Elementary Matrix or Elimination Matrix \(E_{ij}\) that substracts a multiple \(l\) of row j from row i has the extra nonzero entry \(-l\) in the i,j position (sitll diagonal 1’s)
- The Row Exchange Matrix \(P_{ij}\) is the identity matrix with rows i and j reversed.
When this Permutation Matrix \(P_{ij}\) multiplies a matrix, it exchanges rows i and j. - Elimination does the same row operations to A and to b. We can include b as an extra column and follow it through elimination. The matrix A is enlarged or augmented by the extra column b.
2.4 Rules for Matrix Operations
- The (i, j) entry of AB is (row i of A) \(\cdot\) (column j of B).
AB is also the sum of these matrices: (column j of A) times (row j of B). - A row times a column is an inner product.
A column times a row is an outer product.
These are extreme cases of matrix multiplication. - Each column of AB is a combination of the columns of A. (matrix B acts from right)
Each row of AB is a combination of the rows of B. (matrix A acts from left) - Block multiplication is allowed when the block shapes match correctly.
Block elimination produces the Schur complement \(D – CA^{-1}B\). - The associative law for ABC is satisfied.
The commutative law is usually broken.
2.5 Inverse Matrices
- The inverse matrix gives \(AA^{-1} = I\) and \(A^{-1}A = I\)
- The algorithm to test invertibility is elimination : A is invertible if and only if it has n pivots (row exchanges allowed).
The algebra test for invertibility is the determinant of A: det A must not be zero.
The equation that tests for invertibility is Ax = 0: x = 0 must be the only solution. - The inverse of \(AB\) is the reverse product \(B^{-1}A^{-1}\).
- The Gauss-Jordan method solves \(AA^{-1} = I\) to find the n columns of \(A^{-1}\).
The augmented matrix \([A I]\) is row-reduced to \([I A^{-1}]\). - If A is symmetric or triangular, so is \(A^{-1}\).
- Diagonally dominant matrices are invertible. Each \(|a_{ii}|\) dominates its row.
2.6 Elimination = Factorization: A = LU
- Gaussian elimination (with no row exchanges) factors A into L times U.
- The lower triangular L contains the multiplier \(l_{ij}\) that multipy pivot rows, while going from A to U.
The product LU add those rows back to recover A. - The original system Ax = b is factored into two triangular systems:
solve Lc = b (forward) and Ux = c (backward)
2.7 Transposes and Permutations
- The transpose puts the rows of A into the columns of \(A^T\). Then \((A^T)_{ij} = A_{ji}\).
- The transpose of \(AB\) is \(B^TA^T\). The transpose of \(A^{-1}\) is the inverse of \(A^T\).
- The dot product is \(x \cdot y = x^Ty\). Then \((Ax)^Ty\) equals the dot product \(x^T(A^Ty)\).
- When A is symmetric \((A^T = A)\), its LDU factorization is symmetric: \(A = LDL^T\).
- A Permutation Matrix P has the rows of the identity \(I\) in any order, and \(P^T = P^{-1}\).
- If A is invertible then a Permutation P will reorder its rows for \(PA = LU\).
3 Vector Spaces and Subspaces
3.1 Spaces of Vectors
- \(R^n\) contains all column vectors with n real components.
- A vector space must closed under linear combination.
A subspace containing v and w must contain all their combinations \(cv + dw\). - The combinations of the columns of A form the column space \(C(A)\). Then the column space is spanned by the columns.
- \(Ax = b\) has a solution exactly when b is in the column space of A.
3.2 The Nullspace of A: solving \(Ax = 0\)
- The nullspace \(N(A)\) is a subspace of \(R^n\). It contains all solutions to \(Ax = 0\).
- Elimination produces an echelon matrix U, and then a row reduced R, with pivot columns and free columns.
Every free column of U or R leads to a special solution.
The complete solution to \(Ax = 0\) is a combination of the special solutions. - Suppose \(Ax = 0\) has more unknowns than equations (n > m, more columns than rows).
Then there are nonzero solutions. There must be free columns.
3.3 The Rank and the Row Reduced Form
- The rank r of A is the number of pivots.
The true size of A is given by its rank. - The r pivot columns are not combinations of earlier columns.
The n – r free columns are combinations of earlier columns (pivot columns). - Those combinations (using -F taken from R) give the n – r special solutions to \(Ax = 0\) and \(Rx = 0\).
They are the n – r columns of the nullspace matrix N.
3.4 The Complete Solution to \(Ax = b\)
- \(Ax = b\) is solvable if and only if the last m – r equations reduce to 0 = 0.
- One particular solution \(x_p\) has all free variables equal to zero.
The pivot variables are determined after the free variables are chosen. - \(x = x_p + x_n\)
The particular solution \(x_p\) will be one point on the “line”.
Adding the nullspace vector \(x_n\) will move us along the “line”. - Full column rank r = n means no free variables: one solution is m = n or none if m > n (overdetermined).
- Full row rank r = m means one solution if m = n or infinitely many if m < n (underdetermined).
3.5 Independence, Basis and Dimension
- The columns of A are independent if x = 0 if the only solution to \(Ax = 0\).
- The vectors \(v_1, \dots ,v_r\) span a space if their combinations fill that space.
- A basis consists of linearly independent vectors that span the space.
Every vector in the space is a unique combination of the basis vectors. - All bases for a space have the same number of vectors.
This number of vectors in a basis is the dimension of the space. - The pivot columns are one basis for the column space. The dimension is r.
- The vectors \(v_1, \dots ,v_n\) are a basis for \(R^n\) exactly when they are the columns of an n by n invertible matrix.
Thus \(R^n\) has infinitely many different bases. - Space Z contains only the zero vector.
The dimension of this space is zero.
The empty set is a basis for Z (We never allow the zero vector into a basis).
3.6 Dimension of the Four Subspaces
- Fundamental Theorem of Linear Algebra, Part 1:
The column space \(C(A)\) and the row space \(C(A^T)\) both have dimension r (the rank of A).
The nullspace \(N(A)\) has dimension n − r. The left nullspace \(N(A^T)\) has dimension m − r. - Elimination produces bases for the row space and nullspace of A: They are the same as for R.
- Elimination often changes the column space and left nullspace (but dimensions don’t change).
- Rank one matrices: \(A = uv^T = \text{column times row}\): \(C(A)\) has basis u, \(C(A^T)\) has basis v.
4 Orthogonality
4.1 Orthogonality of the Four Subspaces
- Fundamental Theorem of Linear Algebra, Part 2:
\(N(A)\) is the orthogonal complement of the row space \(C(A^T)\) (in \(R^n\)).
\(N(A^T)\) is the orthogonal complement of the column space \(C(A)\) (in \(R^m\)). - Subspace V and W are orthogonal if every v in V is orthogonal to every w in W.
- V and W are orthogonal complements if W contains all vectors perpendicular to V (and vice versa).
Inside \(R^n\), the dimensions of complements V and W add to n.
Orthogonality is impossible when dim V + dim W > dimension of whole space. - When a vector is in two orthogonal subspaces, it must be zero which is perpendicular to itself.
- Any n independent vectors in \(R^n\) will span \(R^n\).
- Every x in \(R^n\) has a nullspace component \(x_n\) and a row space component \(x_r\).
- Every vector b in column space comes from one and only one vector in the row space.
From the row space to the column space, A is invertible (pseudoinverse).
4.2 Projections
- The rank one projection matrix \(P = aa^T / a^Ta\) multiplies b to produce the projection p onto the line through a.
- Projecting b onto a subspace leaves \(e = b – p\) perpendicular to subspace.
When \(P\) projects onto subspace, \(I – P\) projects onto the perpendicular subspace. - To project any b onto the column space of any matrix A
The projection p is the combination \(A\hat{x}\) which is closest to b
The error vector \(b – A\hat{x}\) is perpendicular to the column space of A
Therefore \(b – A\hat{x}\) is in the nullspace of \(A^T\). This means \(A^T(b – A\hat{x}) = 0\).
When A has full rank n, the equation \(A^TA\hat{x} = A^Tb\) leads to \(\hat{x}\) and \(p = A\hat{x}\). - The projection matrix \(P = A(A^TA)^{-1}A^T\) has \(P^T = P\) and \(P^2 = P\).
The matrix A is rectangular, which means that A may be singular.
When A is singular, we cannot split \((A^TA)^{-1}\) into \(A^{-1}\) times \((A^T)^{-1}\) because there is no \(A^{-1}\) in the first place.
When A has independent columns, \(A^TA\) is square, symmetric, and invertible.
4.3 Least Squares Approximations
- When \(Ax = b = p + e\) is impossible, \(A\hat{x} = p\) is solvable.
b is outside the column space, and the nearest point in the column space is its projection p when the error e is orthogonal to the column space. - The best \(\hat{x}\) comes from the normal equations \(A^TA\hat{x} = A^Tb\).
The best \(\hat{x}\) minimizes \(E = \|Ax – b\|^2\) which is the sum of squares of the errors in the m equations (m > n). - If we try to fit m points by a combination of n < m functions, the m equations \(Ax = b\) are generally unsolvable.
The n equations \(A^TA\hat{x} = A^Tb\) give the least squares solution—— the combination with smallest MSE (mean square error).
4.4 Orthogonal Bases and Gram-Schmidt
- A matrix Q with orthonormal columns satisfies \(Q^TQ = I\)
When Q is square (an orthogonal matrix), \(Q^TQ = I\) means that \(Q^T = Q^{-1}\): transpose = inverse. - Q preserves length: \(\|Qx\| = \|x\|\)
Q preserves dot products: \((Qx)^T(Qy) = x^Ty\) - The projection onto the column space is \(P = QQ^T\)
if Q is square then \(P = I\) and every \(b = q_1(q_1^Tb) + \dots + q_n(q_n^Tb)\). - Gram-Schmidt process: subtract from every new vector its projections in the directions already set
In matrix form this is the factorization \(A = QR\).
R is upper triangular because of the non-involvement of later vectors (the key point of Gram-Schmidt) - The least squares solution of \(Qx = b\) is \(\hat{x} = Q^Tb\)
The least squares solution of \(Ax = b\) is \(\hat{x} = R^{-1}Q^Tb\)
5 Determinants
5.1 The Properties of Determinants
- The determinant is defined by det I = 1, sign reversal, and linearity in each row.
- After elimination det A is \(\pm\) (product of the pivots).
- The determinant is zero exactly when A is not invertible.
- Two remarkable properties are det AB = (det A)(det B) and det \(a^T\) = det A.
5.2 Permutations and Cofactors
- The first k pivots come from the k by k matrix \(A_k\) in the top left conrner of A.
The determinant of that corner submatrix \(A_k\) is \(d_1d_2 \dots d_k\). - det A = sum over all n! column permutations \(P = (\alpha, \beta, \dots, \omega)\) = \(\Sigma(\text{det P})a_{1\alpha}a_{2\beta}\dots a_{n\omega}\) = BIG FORMULA
- The cofactor \(C_{ij}\) is \((-1)^{i+j}\) times the smaller determinant that omits row i and column j (because \(a_{ij}\) uses that row and column).
- The determinant is the dot product of any row of A with its row of cofactors.
When a row of A has lot of zeros, we only need a few cofactors.
The idea behind cofactors is to reduce the order one step at a time.
5.3 Cramer’s Rule, Inverses, and Volumes
- Cramer’s Rule solves \(Ax = b\) by ratios like \(x_1 = |B_1|/|A| = |ba_2 \dots a_n|/|A|\).
- When C is the cofactor matrix for A, the inverse is \(A^{-1} = C^T / \text{det A}\).
- The volume of a box is |det A|, when the box edges going out from the origin are the rows of A.
- The cross product is a vector with length \(\|u\|\|v\||sin\theta|\). Its direction is perpendicular to u and v. Its points “up” or “down” by the right hand rule.
6 Eigenvalues and Eigenvectors
6.1 Introduction to Eigenvalues
- An eigenvector x lies along the same line as Ax: \(Ax = \lambda x\). The eigenvalue is \(\lambda\).
If \(Ax = \lambda x\) then \(A^2 x = \lambda^2 x\) and \(A^{-1}x = \lambda^{-1} x\): the same x. - If \(Ax = \lambda x\) then \((A-\lambda I)x = 0\) and \(A-\lambda I\) is singular and \(det(A-\lambda I) = 0\): n eigenvalues (may be repeated or complex).
- The product of n eigenvalues equals determinant.
The sum of n eigenvalues equals trace. - Projections have \(\lambda\) = 1 and 0. Reflections have 1 and -1. Rotations have \(e^{i\theta}\) and \(e^{-i\theta}\).
- A and B shared the same n independent eigenvalues if and only if AB = BA.
6.2 Diagonalizing a Matrix
- n independent eigenvectors in X diagonalize A to the eigenvalue matrix \(\Lambda\): \(A = X\Lambda X^{-1}\) and \(\Lambda = X^{-1}AX\).
The columns of \(AX = X\Lambda\) are \(Ax_k = \lambda_k x_k\).
Moreover, if those n eigenvectors are orthogonal then \(A = \Sigma \lambda_k x_k x_k^T\). - A is diagonalizable if every eigenvalue is different (which means that every eigenvector is independent).
A is diagonalizable if every eigenvalue has enough eigenvectors. - Every matrix \(C = B^{-1}AB\) has the same eigenvalues as A.
These C’s are similar to A. - Solve \(u_{k+1} = Au_k\) by \(u_k = A^k u_0 = X\Lambda^k X^{-1}u_0 = \Sigma c_i \lambda_i^k x_i\) (transforming to an eigenvector basis).
6.3 Systems of Differential Equations
6.4 Symmetric Matrices
- A real symmetric matrix S has n real eigenvalues and n orthonormal eigenvectors.
- For symmetric matrices the pivots and the eigenvalues have the same signs.
- N has n orthonormal eigenvectors if and only if N is normal (\(\overline{N}^T N = N \overline{N}^T\)).
6.5 Positive Definite Matrices
- Symmetric S: all eigenvalues > 0 \(\Leftrightarrow\) all pivots > 0 \(\Leftrightarrow\) all upper left determinants > 0 \(\Leftrightarrow\) \(x^T Sx\) if positive except at x = 0 \(\Leftrightarrow\) \(S = A^T A\) for A with independent columns.
The matrix S is then positive definite. - S is positive simidefinite if 0 is allowed in the above inequalities (or dependent columns is allowed in A (\(S = A^T A\))).
7 The Singular Value Decomposition (SVD)
7.1 Image Processing by Linear Algebra
- An image is a large matrix of grayscale values, one for each pixel and color.
When nearby pixels are correlated (not random) the image can be compressed. - The SVD separates any matrix A into rank one pieces \(\lambda uv^T\).
The SVD chooses rank one pieces in order of importance. - Images mostly have full rank, but they do have low effective rank which means that many singular values are small and can be set to zero: we transmit a low rank approximation.
7.2 Bases and Matrices in the SVD
- What we want from the SVD: the right basis for the four subspaces.
\(
A
\left[\begin{matrix}
v_1 & \cdots & v_r & \cdots & v_n
\end{matrix}\right]
=
\left[\begin{matrix}
u_1 & \cdots & u_r & \cdots & u_n
\end{matrix}\right]
\left[\begin{matrix}
\sigma_1 & & && \\
& \ddots & && \\
& & \sigma_r && \\
& & &&
\end{matrix}\right]
\)
SVD of any matrix: \(A = U \Sigma V^T = \Sigma \sigma_i u_i v_i^T\)
\(A^T A = (U\Sigma V^T)^T (U\Sigma V^T) = V\Sigma^TU^TU\Sigma V^T = V\Sigma^T\Sigma V^T\) - A has two sets of singular vectors, u’s and v’s:
\(u_1 \dots u_r\) and \(v_1 \dots v_r\) are orthonormal basis for the column space and the row space.
\(u_{r+1} \dots u_m\) and \(v_{r+1} \dots v_n\) are orthonormal basis for the left nullspace and the nullspace.
u’s are eigenvectors of \(AA^T\), and v’s are eigenvectors of \(A^T A\). - A has one set of singular values, \(\sigma\)‘s:
Each \(\sigma^2\) is \(\lambda(A^T A)\)
\(\sigma_i \dots \sigma_r\) will be positive numbers
Because columns of A may be dependent, \(A^T A\) is positive semidefinite, the extra \(\sigma\)‘s are zero - There are serious instability of eigenvalues when \(AA^T\) is far from \(A^T A\).
The singular values of any matrix are stable. - In \(S = \Sigma \lambda_i q_iq_i^T\), \(\lambda_1\) is the max ratio \(\frac{x^TSx}{x^Tx}\) and the winning vector x is \(q_1\).
In \(A = \Sigma \lambda_i u_iv_i^T\), \(\sigma_1\) is the max ratio \(\frac{\Vert Ax\Vert}{\Vert x\Vert}\) and the winning vector x is \(v_1\).
7.3 Principal Component Analysis
7.4 The Geometry of the SVD
- A typical square matrix \(A = U\Sigma V^T\) factors into (rotation)(stretching)(rotation).
A transform vectors x on a circle to vectors Ax on an ellipse.
This picture not applies to every 2by2 matrix because U and V didn’t allow for a reflection (A must be invertible). - The norm of A is \(\Vert A \Vert = \sigma_1\).
- Polar decomposition factors A into QS: rotation \(Q = UV^T\) (orthogonal) times stretching \(S = V\Sigma V^T\) (positive semidefinite).
- \(Q = UV^T\) is the nearest orthogonal matrix to A. (This Q makes norm \(\Vert Q-A \Vert\) as small as possible.)
The nearest singular matrix A0 to A comes by changing the smallest \(\sigma_{min}\) to zero.
- The pseudoinverse \(A^+ = V\Sigma^+ U^T\) brings Ax in the column space bask to x in the row space (send \(N(A^T)\) to Z).
\(A^+ u_i = \frac{1}{\sigma_i}v_i\) for \(i \le r\) and \(A^+ u_i = 0\) for i > r.
\(AA^+\) is the projection onto the column space of A.
\(A^+A\) is the projection onto the row space of A. - In least squares, when \(A^TA\) is singular, the equation \(A^TAx = A^Tb\) has infinitely many solutions.
The pseudoinverse gives the shortest solution: \(x^+ = A^+b\).
8 Linear Transformations
8.1 The Idea of a Linear Transformation
- A linear transformation T takes vectors v to vectors T(v).
Linearity requires T(cv+dw) = cT(v)+dT(w). - The input vectors v and the outputs T(v) can be in \(R^n\) or matrix space or function space…
If A is m by n, T(x) = Ax is linear from the input space \(R^n\) to the output space \(R^m\).
The derivative \(T(f) = \frac{df}{dx}\) is linear.
The integral \(T^+(f) = \int_0^x f(t)dt\) is it pseudoinverse. - The range of T is the set of all outputs T(v) (corresponds to column space).
The kernel of T is the set of all inputs for which T(v) = 0 (corresponds to nullspace). - The product ST of two linear transformation is still linear: (ST)(v) = S(T(v)).
8.2 The Matrix of a Linear Transformation
- We know all T(v) if we know all \(T(v_1) \dots T(v_n)\) for all input basis \(v_1 \dots v_n\) (linearity).
- When the input basis is in the columns of V, and the output basis is in the columns of W, the change of basis matrix (\(T(v)=v\)) is \(B=W^{-1}V\)
\(
\left[\begin{matrix}
v_1 & \cdots & v_n
\end{matrix}\right]
\left[\begin{matrix}
c_1 \\
\vdots \\
c_n
\end{matrix}\right]
=
\left[\begin{matrix}
w_1 & \cdots & w_n
\end{matrix}\right]
\left[\begin{matrix}
d_1 \\
\vdots \\
d_n
\end{matrix}\right]
\)
\(u = Vc = Wd\quad d = W^{-1}Vc\)
c and d are two presentation of u in two set of basis, the change of basis matrix change u from c to d. - Column j of the “matrix of T” comes from applying T to the input basis vector \(v_j\).
\(T(v_j) = \Sigma a_{ij} w_i\) is the combination of output basis. - If A and B represent T and S, and output basis for S is the input basis for T, then the matrix AB represents the transformation T(S(u)).
- The same T represented by different matrices when we choose different bases.
The best input-output bases choose are eigenvectors / singular vectors of A: - eigenvectors:
If the input space equals the output space, and if there are n independent eigenvectors, choose those as the input and output basis, the matrix for T is \(B^{-1}AB = \Lambda\) = eigenvalues (because \(T = ITI\)).
\(A_{\text{b’s to b’s}} = B_{\text{standard to b’s}}^{-1}A_{\text{standard}}B_{\text{b’s to standard}}\) is similar to \(A_{\text{standard}}\). - singular vectors:
If the input space may be different from the output sapce, the SVD says that \(A = U\Sigma V^{-1}\), use the v’s and u’s as the input and output basis, the matrix for T is \(B_{out}^{-1}AB_{in} = U^{-1}AV = \Sigma\) = singular values (because \(T = ITI\)).
\(C = Q_1^{-1}AQ_2\) is isometric to A if \(Q_1\) and \(Q_2\) are orthogonal.