LinAlg Notes

Type cmd + P $\to$ Fold all to fold bullet points.

• Properties of Euclidean Norms
  • $\Vert u^{T}v\Vert \le \Vert u\Vert \Vert v\Vert$ (Cauchy-Schwartz)
    • $u^{T}v=\Vert u\Vert \Vert v\Vert \cdot \cos \theta$
    • $|\cos \theta |\le 1$
  • $\Vert u+v\Vert \le \Vert u\Vert +\Vert v\Vert$
    • The direct way is always shorter or as long as the way with a stop in between
• Linear Transformation; Matrix Multiplication
  • $T$ linear transformation $⟺$ $T({\lambda }_1{x}_1+{\lambda }_2{x}_2)={\lambda }_{1}T(x_1)+{\lambda }_{2}T(x_2)$
  • $T$ linear transformation $⟺$ exists matrix that acts like $T$
  • Matrix mult. distributive and associative (why?)
  • Why $(M^T{)}^{-1}=(M^{-1}{)}^T$?
• Transposes and Inverses
  • $(AB{)}^T=B^T{A}^T$
    • Makes sense: $(Ax{)}^T=$x^T A^T$. Matrix is simply a series of vectors.
  • $(AB{)}^{-1}=B^{-1}{A}^{-1}$
    • When you perform $AB$, you first perform $B$, then $A$. Therefore, to undo, you first have to undo $A$, then $B$.
• Rank, Column Space, Nullspace
  • $N(A)=R(A{)}^{\perp }=C(A^T{)}^{\perp }$
    • $x$ in nullspace $⟺Ax=0$. $x$ is therefore orthogonal to every row of $A$.
    • Since the rows span the rowspace, $x$ must be orth. to the rowspace.
  • $N(A)=N(A^{T}A)$ (and therefore $N(A^T)=N(A{A}^T)$)
    • $Ax=0$ $⟹A^T(Ax)=0$
    • $A^{T}Ax=0⟹x^T{A}^{T}Ax=0⟹\Vert Ax{\Vert }^2=0⟹Ax=0$
    • $N(A^T)=N(A{A}^T)$ follows because $(A^T{)}^T(A^T)=A{A}^T$
  • $C(A^T)=C(A^{T}A)$ (and therefore $C(A)=C(A{A}^T)$)
    • $C(A^T)=N(A{)}^{\perp }$ $=N(A^{T}A{)}^{\perp }$ $=C((A^{T}A{)}^T)$ $=C(A^{T}A)$
  • $\mathrm{rank}(A)$ $=\mathrm{rank}(A^T)$
    • Result of reduced row echelon form. There are always as many rows as pivot columns.
  • $\mathrm{rank}(A)=\mathrm{rank}(A{A}^T)$ (and therefore $\mathrm{rank}(A^T)$ $=\mathrm{rank}(A^{T}A)$)
    • $C(A)=C(A{A}^T)$, and $\mathrm{rank}(A)=\dim (C(A))$ by def.
    • All four are equal b/c of $\mathrm{rank}(A)$ $=\mathrm{rank}(A^T)$
  • $\{x\in {\mathbb{R}}^n\mid Ax=b\}\ne \varnothing$ $⟹$ $\{x\in {\mathbb{R}}^n\mid Ax=b\}=x_1+N(A)$ with $x_1\in R(A)$ unique
    • You can add an arbitrary element to a unique solution in the row space and still have a solution.
    • Intuition: We can move a solution up and down the nullspace b/c adding a vector $x_0$ in the nullspace to a solution $x$ doesn’t change the validity ($A{x}_0=0$). Since the nullspace is the orth. complement of the rowspace, it must intercept the rowspace in exactly one position ($N(A)\cap C(A^T)=\{0\}$, which gets moved along $C(A^T)$)
    • Direct result $A{x}_1=b$
    • If there exists a solution $x_1$, then $A{x}_1=A{x}_1+A{x}_0=A(x_1+x_0)=b$ is also a solution, where $x_0\in N(A)$
    • $x_1\in R(A)$ $⟹A{x}_1=A{A}^{T}c=b$ for some $c$
    • $A$ underdetermined ($A$ wide) $⟹$ $A$ full row rank $⟹$ $A{A}^T$ full rank $⟹$ $A{A}^{T}c=b$ has a unique solution $c$ (so $x$ unique b/c matrix mult. is well defined)
• CR-Decomposition
  • Any $A$ can be decomposed into $A=CR$
    • $C$: Lin ind. columns of $A$
    • $R$: Each col contains the coeffecients of the lin. comb. of the cols of $C$ that make up the cols of $A$ (How much of each $C$ col goes into each $A$ col)
  • $C(A)=C(C)$ by construction b/c $C$ are the lin. ind. cols of $A$
  • $R(A)=R(R)$
    • $R(A)\subseteq R(R)$: Each row of $A$ is a lin. comb. of the rows of $R$, with each row of $C$ offering the coefficients
    • $R(A)\supseteq R(R)$: $C$ has full col. rank $⟹$ $(C^{T}C{)}^{-1}{C}^T$ left inverse (see pseudoinverse). Therefore: $CR=A$ $⟹R=\underset{P}{\underbrace{(C^{T}C{)}^{-1}{C}^T}}A$ $⟹$ Each row of $R$ is a lin. comb. of the rows of $A$, with each row of $P$ offering the coefficients
  • $CR$ composition can be done using Gauss-Jordan elimination. $C$ = the cols of $A$ where $\mathrm{RREF}(A)$ has pivots, and $R$ = the non-zero rows of $\mathrm{RREF}(A)$
    • $C$: cols follows def (since cols with pivots are lin. ind.)
    • $R$: We can write the Gauss-Jordan steps into an $m\times m$ matrix $M$: $MA$ $=MCR$ $=\left[\begin{array}{c}R\\ 0\end{array}\right]$ w/ as many 0 rows as $\mathrm{RREF}(C)$, which yields 1s on diag. & 0 rows below
• Certificates
  • $\{x\in {\mathbb{R}}^n\mid Ax=b\}=\varnothing ⟺\{z\in {\mathbb{R}}^m\mid A^{T}z=0\wedge b^{T}z=1\}\ne \varnothing$
    • $A^{T}z=0⟺z\in N(A^T)$
    • $Ax=b$ has a solution $⟹b\in C(A)$ $⟹b^{T}z=0$ b/c $C(A)\perp N(A^T)$
    • Therefore: $Ax=b$ has no solution $⟹b^{T}z\ne 0$ $⟹b^{T}z=1$ since any nonzero $z$ that satisfies $b^{T}z\ne 0$ can be scaled by $b^{T}z$ without leaving $N(A^T)$, i.e. while maintaining the condition $A^{T}z=0$ (vectorspace axioms).
• Projections onto Subspaces (https://youtu.be/Y_Ac6KiQ1t0)
  • $Ax=b$ may have no solution. Solve $A\hat{x}={\mathrm{proj}}_A(b)$ instead, where ${\mathrm{proj}}_A(b)$ is projection of $b$ onto col. space. projection = closest point in col. space to $b$.
  • $e=b-{\mathrm{proj}}_A(b)=b-A\hat{x}$ is error of $b$, i.e. the vector from $b$ to its projection. $e$ is orth. to $C(A)$ b/c that’s the directest and therefore shortest way to reach the col. space. $⟹A^{T}e=0$ $⟹A^T(b-A\hat{x})=0$ $⟹A^{T}A\hat{x}=A^{T}b$ (normal equation) $⟹\hat{x}=(A^{T}A{)}^{-1}{A}^{T}b$ $⟹{\mathrm{proj}}_A(b)=A(A^{T}A{)}^{-1}{A}^{T}b$ $⟹$ projection matrix $P=A(A^{T}A{)}^{-1}{A}^T$
  • $P^2=P$ b/c projecting something in the col. space (the first projection) changes nothing
  • $P^T=P$ b/c
    • $(A(A^{T}A{)}^{-1}{A}^T{)}^T=A(A^{T}A{)}^{-1}{A}^T$
  • Intuitively: Projection matrix annihilates orth. vector component
    • $Pb=P(b_{\perp }+b_{\parallel })$ $=P{b}_{\perp }+P{b}_{\parallel }$ $=P{b}_{\perp }+PAc$ for some $c$ ($b_{\parallel }\in C(A)$) $=A(A^{T}A{)}^{-1}{A}^T{b}_{\perp }+A(A^{T}A{)}^{-1}{A}^{T}Ac$ $=A(A^{T}A{)}^{-1}{A}^T{b}_{\perp }+Ac$ $=0+Ac$ (dot prod. between $b_{\perp }$ & every col. of $A$ 0; $b_{\perp }\perp C(A)$ $⟺b_{\perp }\in N(A^T)$) $=b_{\parallel }$
• Least Squares Regression
  • Goal: calculate coefficients of function so that we minimize the squared error, i.e. the sum of the squared distances from our function output to actual datapoints
  • Example: we have datapoints $(x_1,y_1),\dots ,(x_4,y_4)$ and want a quadratic function. If we plug them in: $\{\begin{array}{l}{y}_1={\alpha }_2(x_1{)}^2+{\alpha }_1{x}_1+{\alpha }_0\\ y_2={\alpha }_2(x_2{)}^2+{\alpha }_1{x}_2+{\alpha }_0\\ y_3={\alpha }_2(x_3{)}^2+{\alpha }_1{x}_3+{\alpha }_0\\ y_4={\alpha }_2(x_4{)}^2+{\alpha }_1{x}_4+{\alpha }_0\end{array}$ $⟺\underset{y}{\underbrace{\left(\begin{array}{c}{y}_1\\ y_2\\ y_3\\ y_4\end{array}\right)}}=\underset{A}{\underbrace{\left[\begin{array}{ccc}(x_1{)}^2& x_1& 1\\ (x_2{)}^2& x_2& 1\\ (x_3{)}^2& x_3& 1\\ (x_4{)}^2& x_4& 1\end{array}\right]}}\underset{\hat{\alpha }}{\underbrace{\left(\begin{array}{c}{\alpha }_2\\ {\alpha }_1\\ {\alpha }_0\end{array}\right)}}$
  • Minimizing now becomes reducing sum of squared differences from every coordinate of $A\hat{\alpha }$ (all our predictions) to the corres. coordinate of $y$ (all our expected results): ${\min }_{\hat{\alpha }\in {\mathbb{R}}^n}(A\hat{\alpha }-y{)}^T(A\hat{\alpha }-y)$ $⟺{\min }_{\hat{\alpha }\in {\mathbb{R}}^n}\Vert A\hat{\alpha }-y{\Vert }^2$ $⟺{\min }_{\hat{\alpha }\in {\mathbb{R}}^n}\Vert A\hat{\alpha }-y\Vert$ (norm is always positive)
  • $A\hat{\alpha }-y\cong A\hat{x}-b=e$ from projections. We therefore know how to minimize norm of $e$: find $e$ that’s orth. to the col. space. Hence, $\hat{\alpha }=(A^{T}A{)}^{-1}{A}^{T}y$.
• Orthogonal Matrices and Gram-Schmidt
  • Orthonormal columns: $Q^{T}Q=I$ b/c rows of $A^T$ are always orthogonal to cols of $A$ except if row idx = col idx, in which case we have $v^{T}v=\Vert v{\Vert }^2=1^2=1$
  • If square: called orthogonal matrix. $⟹Q$ has a right inverse (left inverse $\Rightarrow$ matrix injective: a vector $x$ first gets multiplied with $Q$, then with $Q^T$. If $Q$ reduced multiple values to the same value, $Q^T$ could not reverse $\Rightarrow$ matrix bijective if square) $⟹Q^T=Q^{-1}$ since $L=L(QR)=(LQ)R=IR=R$ ($L$ is left inverse, $R$ right) $⟹Q{Q}^T=I$
  • $Q$ orthogonal $⟺$ $Q$ norm preserving: $\Vert Qx\Vert =\Vert x\Vert$ and $(Qx{)}^T(Qy)=x^{T}y$
    • $\sqrt{(Qx{)}^T(Qx)}=\sqrt{x^T{Q}^{T}Qx}=\sqrt{x^{T}x}$
    • $(Qx{)}^T(Qy)=x^T{Q}^{T}Qy=x^{T}y$
  • Gram-Schmidt: $q_1=\frac{a_1}{\Vert a_1\Vert }$; $q_k^{\prime }=a_k-{\sum }_{j=1}^{k-1}{q}_j(q_j^T{a}_k)$; $q_k=\frac{q_k^{\prime }}{\Vert q_k^{\prime }\Vert }$
    • We project $a_k$ onto the already created subspace and then norm the error
    • The sum above is the same as subtracting $P\cdot a_k$, where $P$ is proj. matrix: $P=Q(Q^{T}Q{)}^{-1}{Q}^T=Q{Q}^T$ since $Q^{T}Q=I$ by definition. $Q{Q}^T\ne I$ b/c $Q$ is not yet square.
  • For orthonormal matrices: $Q^{T}Q\hat{x}=Q^{T}b$ $⟹\hat{x}=Q^{T}b$ is the least-squares solution to $Qx=b$
  • A matrix can be decomposed into $A=QR$
    • $Q$ has orthonormal columns (not necessarily orthogonal b/c it may not be square).
    • $R$ denotes how much each column of $Q$ contributes to a column of $A$. Since every column of $A$ is a linear combination of all the already created orthonormal columns + a new one in Gram-Schmidt, we get an upper triangular matrix.
      • If $A$ has linearly independent columns, then $R$ has values $\ne 0$ along the diagonal: each col. adds a new orthonormal vector to $Q$. It is therefore invertible. This is part of the def. in this class.
      • Otherwise, we add a column w/o pivot (we don’t add a new col to $Q$ b/c $pro{j}_C(a)=a$, so the error is the 0-vector). We get an upper triangular matrix with pivots set back.
    • Since $C(A)=C(Q)$, $P=Q{Q}^T$ is projection matrix.
    • $A^{T}A\hat{x}=A^{T}b$ $⟹R^{T}R\hat{x}=R^T{Q}^{T}b$ ($A^{T}A=(QR{)}^T(QR)=R^T{Q}^{T}QR=R^{T}R$) $⟹R\hat{x}=Q^{T}b$ ($R\in {\mathbb{R}}^{m\times n}$ and $\mathrm{rank}(R)=m$ $\Rightarrow R^T\in {\mathbb{R}}^{n\times m}$ has full col. rank $\Rightarrow$ $R^T$ has left inverse)
• Determinant Formula (https://youtu.be/Sv7VseMsOQc)
  • We can easily derive 3 axioms from volume:
    • $\det (I)=1$: a hypercube with edge length 1 has volume 1
    • Linearity is a direct result of volume:
      • A volume is spanned by multiple vectors. If you scale any one of the vectors by $\alpha$, your volume increases by $\alpha$. $⟹\det (\dots ,\alpha r_i,\dots )=\alpha \det (\dots ,r_i,\dots )$
      • A vector always determines two parallel edges in the case of a parallelogram and four parallel edges in the case of a 3d parallelepiped. If you split a vector into two, that equally bulges the shape in on one side and out at the other. Therefore, the volume stays the same. $⟹\det (\dots ,r_i+r_i^{\prime },\dots )=\det (\dots ,r_i,\dots )+\det (\dots ,r_i^{\prime },\dots )$
    • If a spanning vector is linearly dependent on the others, then the parallelepiped collapses into one dimension less $⟹$ volume of 0.
  • From these 3 axioms, it follows that the sign must switch if we swap two columns: $0=V(v+w,v+w,u)$ $=V(v,v+w,u)+V(w,v+w,u)$ $=V(v,v,u)+V(v,w,u)+V(w,v,u)+V(w,w,u)$ $=V(v,w,u)+V(w,v,u)$ (linear dependence) $⟹V(v,w,u)=-V(w,v,u)$
  • After using our linearity and linear dependence axioms multiple times, we are left with only $I$‘s permutations. By using sign flipping col. switching, we get to $\det (I)=1$. Hence: $\det (A)=\sum _{\sigma \in S_n}\mathrm{sgn}(\sigma )\prod _{i=1}^n{a}_{i,\sigma (i)}$
    • $S_n$: set of all possible permutation functions
  • Trick for sign of permutation: Draw two sets of dots from 1 to $n$. Connect input and output of permutation. $(-1{)}^{\text{\# intersections}}$ is sign.
• Properties of Determinants
  • $\det (A)=\det (A^T)$
    • $P^T=P$, where $P$ is the set of all permutation matrices.
    • Each permutation matrix is like a hole puncher.
    • If you turn both the page and the holes you punch, you still get the same holes.
  • $\det (AB)=\det (A)\cdot \det (B)$
    • Scale volume by A first, then by B
    • Follows from linearity: we can extract entries separately
  • $\det (A^{-1})=\frac{1}{\det (A)}$
    • $\det (A)=\det (A^{-1}AA)=\det (A^{-1})\cdot \det (A)\cdot \det (A)$, then divide by $\det (A)\cdot \det (A)$.
• Cofactors, Cramer’s rule and beyond
  • Cofactor: det of matrix = sum of product of row or col entries w/ cofactors $C_{ij}=(-1{)}^{i+j}\det (M_{ij})$. $M_{ij}$ is the minor obtained by deleting row $i$ and column $j$ from $A$.
    • Performs linearity on row or col: Split row or col into vectors with one entry and otherwise only zeros. Delete row and column b/c of lin dep.
    • Swapping that vector up to $i,j=0$, which is part of the diagonal, swaps the sign $i+j$ times.
    • Example $3\times 3$ matrix cofactor expansion along the first col: $\left|\begin{array}{ccc}{a}_{11}& a_{12}& a_{13}\\ a_{21}& a_{22}& a_{23}\\ a_{31}& a_{32}& a_{33}\end{array}\right|$ $=a_{11}\cdot \left|\begin{array}{cc}{a}_{22}& a_{23}\\ a_{32}& a_{33}\end{array}\right|-a_{21}\cdot \left|\begin{array}{cc}{a}_{12}& a_{13}\\ a_{32}& a_{33}\end{array}\right|+a_{31}\cdot \left|\begin{array}{cc}{a}_{12}& a_{13}\\ a_{22}& a_{23}\end{array}\right|$
  • $A^{-1}=\frac{1}{\det (A)}{C}^T$, where $C$ is the matrix with the co-factors of A as entries.
    • $A{C}^T={\sum }_{k=1}^n{a}_{ik}{C}_{jk}.$
    • Case 1: $i=j$
      • Then $(A{C}^T{)}_{ii}={\sum }_k{a}_{ik}{C}_{ik}$
      • This is exactly the cofactor expansion of $\det (A)$ along row $i$.
      • So $(A{C}^T{)}_{ii}=\det (A)$.
    • Case 2: $i\ne$ Then $(A{C}^T{)}_{ij}={\sum }_k{a}_{ik}{C}_{jk}$
      • This is like taking the determinant of a matrix where two rows are equal (row $i$ and row $j$ after replacing row $j$ with row $i$)
      • Determinant = 0 in this case.
    • $⟹A{C}^T=\det (A)I$
  • Efficient way to compute det: subtract and add rows until upper triangle form (similar to Gauss). If swapping rows: multiply final det by -1. Scaling not allowed.
    • Intuition: det measures volume of parallelepiped. Adding a multiple of one row to another just slides one face along another, which doesn’t change the volume ($\det A=\det A^T$, so rows can be seen as spanning vectors as well).
  • Cramer’s rule: $x_i=\frac{\det A_i}{\det A}$, where $x_i$ is $i$-th component of sol. vector for $Ax=b$ and $A_i$ has the $i$-th col replaced by $b$
    • $\det A_i$ $=\det (a_1,a_2,\dots ,b,\dots ,a_m)$ $=\det (a_1,a_2,\dots ,(a_1\cdot x_1+a_2\cdot x_2+\dots +a_i\cdot x_i+\dots +a_m\cdot x_m),\dots ,a_m)$ ($b$ lin. comb. of $A$‘s cols) $=x_i\det A$ (after applying linearity, all other dets = 0 b/c of linearly dep. cols)
• Eigenvalues and Eigenvectors
  • $Ax=\lambda x,x\ne 0$ $⟹Ax-\lambda x=0$ $⟹Ax-\lambda Ix=0$ $⟹(A-\lambda I)x=0$ $⟹\det (A-\lambda I)=0$ (because $x\ne 0⟹A-\lambda I$ must have nontrivial nullspace)
    • The pair $\lambda =0,x=0$ does not count. Only if $A$ is singular is $\lambda =0$ an eigenvalue b/c then $x\ne 0$ satisfies $Ax=0x$.
  • There are always as many (not necessarily unique) eigenvalues as dimensions $n$ b/c $\det (A-\lambda I)=0$ results in a polynomial with $n$ terms, which has $n$ (possibly complex) roots (fundamental theorem of algebra)
  • Characteristic polynomial: $(-1{)}^n\det (A-zI)$ b/c we want monic polynomial (leading coefficient $=1$)
    • Only diagonal contributes to leading coefficient (see proof for $\text{Tr}(A)={\sum }_i{\lambda }_i$). If we have an uneven $n$, then we have an uneven number of $-z$ in the diagonal $⟹-1$ as leading coefficient
    • Monic polynomial can always be factored into a series of positive factors b/c the $z$ after combining all must be pos.
• Properties of Eigenvalues and Eigenvectors
  • If $\lambda$ and $v$ eigenpair of $A$: ${\lambda }^k$ and $v$ eigenpair of $A^k$
    • If you repeat the same matrix operation $k$ times, evecs are scaled by $\lambda$ $k$ times.
  • If $\lambda$ and $v$ eigenpair of $A$: $\frac{1}{\lambda }$ and $v$ eigenpair of $A^{-1}$
    • If multiplying by $A$ scales $v$ by $\lambda$, then reversing $A$ should scale $v$ by $\frac{1}{\lambda }$
  • Eigenvalues ${\lambda }_1,\dots {\lambda }_k$ distinct $⟹$ corresponding evecs $v_1,\dots ,v_k$ lin. ind.
    • Assume $v_1,v_2,v_3$ are evecs of $A$ w/ distinct eigenvalues ${\lambda }_1,{\lambda }_2,{\lambda }_3$, and suppose $v_3$ is a linear combination of lin. ind. $v_1$ and $v_2$, i.e. $v_3=a{v}_1+b{v}_2$ for $a,b\ne 0$ $⟹$ $A{v}_3={\lambda }_3{v}_3$ $⟹$ $Aa{v}_1+Ab{v}_2={\lambda }_{3}a{v}_1+{\lambda }_{3}b{v}_2$ $⟹$ ${\lambda }_{1}a{v}_1+{\lambda }_{2}b{v}_2={\lambda }_{3}a{v}_1+{\lambda }_{3}b{v}_2$ $⟹$ $({\lambda }_1-{\lambda }_3)a{v}_1+({\lambda }_2-{\lambda }_3)b{v}_2=0$ $⟹$ $({\lambda }_1-{\lambda }_3)a{v}_1=0$ and $({\lambda }_2-{\lambda }_3)b{v}_2=0$ ($v_1,v_2$ lin. ind.) $⟹$ $a,v_1$ non-zero, so $({\lambda }_1-{\lambda }_3)=0$ $⟹{\lambda }_1={\lambda }_3$. Contradiction. Analogous for $v_2$.
    • Proof above generalizes for any num of vectors (can be written using sum notation)
    • Result: if $A\in {\mathbb{R}}^{k\times k}$, then we can create a basis of evecs
  • $(\lambda ,v)$ eigenpair $⟹$ $(\overline{\lambda },\overline{v})$ eigenpair
    • $\overline{Av}=\overline{\lambda v}$ $⟹\overline{A}\overline{v}=\overline{\lambda }\overline{v}$ $⟹A\overline{v}=\overline{\lambda }\overline{v}$ if $A\in {\mathbb{R}}^{n\times n}$
  • Eigenvalues for $A$ = eigenvalues for $A^T$
    • $\det (A-zI)=\det ((A-zI{)}^T)=\det (A^T-z{I}^T)=\det (A^T-zI)$
  • $\det A={\prod }_i{\lambda }_i$
    • $(-1{)}^n\det (A-zI)$ $=(z-{\lambda }_1)(z-{\lambda }_2)\cdots (z-{\lambda }_n)$ $=\text{[terms with z]}+(-1{)}^n{\prod }_{i=1}^n{\lambda }_i$
    • Set $z=0$. Then you get the claimed result.
  • $\text{Tr}(A)={\sum }_i{\lambda }_i$
    • Characteristic polynomial: $(z-{\lambda }_1)(z-{\lambda }_2)\cdots (z-{\lambda }_n)$
      • Coefficient of $z^{n-1}$ is sum of the eigenvalues since we pick every eigenvalue once and multiply it with the $z$ of all the $n-1$ other factors
    • We can calculate the characteristic polynomial by using the Leibnitz formula on $A-Iz$.
      • Results in a sum of products of matrix entries
      • Since we add these products, each product can only contribute to coefficients of powers of variables that it contains
      • Therefore: we are looking for product with a $z^{n-1}$. Since only the diagonal contains $z$, we need to pick $n-1$ elements from the diagonal to get the $z$ in. Picking $n-1$ elements forces the last one $⟹$ only the diagonal is relevant.
      • The diagonal: $(d_1-z)(d_2-z)\cdots (d_3-z)$, where $d_i$ is $A$‘s $i$-th diagonal entry
      • Coefficient of $z^{n-1}$ is sum of diagonal entries ($=\text{Tr}(A)$) b/c we pick $n-1$ $z$ and then must pick one of $A$‘s diagonal entries.
    • If diagonalizable: $\mathrm{Tr}(A)$ $=\mathrm{Tr}(S^{-1}\Lambda S)$ $=\mathrm{Tr}(\Lambda S{S}^{-1})$ $=\mathrm{Tr}(\Lambda )$ $={\sum }_i{\lambda }_i$
    • $\mathrm{Tr}(AB)=\mathrm{Tr}(BA)$ and $\mathrm{Tr}(ABC)=\mathrm{Tr}(BCA)=\mathrm{Tr}(CAB)$
      • $\mathrm{Tr}(AB)$ $={\sum }_j(AB{)}_{jj}$ $={\sum }_j{\sum }_i{A}_{ij}{B}_{ji}$ $={\sum }_j{\sum }_i{B}_{ji}{A}_{ij}$ $=\mathrm{Tr}(BA)$
      • $\mathrm{Tr}(A(BC))=\mathrm{Tr}((BC)A)$
  • $A^{T}A$ and $A{A}^T$ share non-zero eigenvalues
    • Since $\lambda \ne 0,u\ne 0$, $Au\ne 0$. Symmetric for $v,A^{T}v$.
    • $u$ evec of $A^{T}A$: $A{A}^T(Au)=A(A^{T}A)u=A(\lambda u)=\lambda (Au)$
    • $v$ evec of $A{A}^T$: $A^{T}A(A^{T}v)=A^T(A{A}^T)v=A^T(\lambda v)=\lambda (A^{T}v)$
• Diagonalization and Powers of A
  • $S:=$ the matrix with the evecs as cols. Then $AS=S\Lambda$, where $\Lambda$ has the eigenvalues corresponding to the evecs in $S$ on the diagonal $⟹A=S\Lambda S^{-1}$ and $\Lambda =S^{-1}AS$ if $S$ invertible
    • $\Lambda S$ would be wrong b/c you would then multiply each component of every evec with a different eigenvalue
  • To calculate power of $A$: $A=S{\Lambda }^k{S}^{-1}$ b/c the $S^{-1}$ and the $S$ cancel out
    • Can be used for closed formulas for recursions
• Spectral Theorem
  • Any symmetric matrix $A\in {\mathbb{R}}^{n\times n}$ has $n$ real eigenvalues and an orthonormal basis of ${\mathbb{R}}^n$ consisting of its evecs.
    • Induction proof in script
  • Symmetric matrices can be diagonalized as $A=V\Lambda V^T$ since $V$ can be made orthogonal
• Positive (Semi-)Definite Matrices
  • All eigenvalues of a symmetric matrix $>0$ (positive definite, PD) or $\ge 0$ (positive semi-definite, PSD)
  • Rayleigh-Quotient $R_A(x)=\frac{x^{T}Ax}{x^{T}x}$
    • Projects $Ax$ onto $x$, then norms by $\Vert x\Vert$
    • Measures how much $A$ scales $x$ in $x$‘s direction
  • ${\lambda }_{\min }\le R_A(x)\le {\lambda }_{\max }$
    • $R_A(x)=\frac{x^{T}Ax}{\Vert x{\Vert }^2}=\frac{x^{T}V\Lambda V^{T}x}{\Vert x{\Vert }^2}$ (evecs of sym. matrix can form orth. matrix)
    • Let $y=V^{T}x$, which is a vector. Then $R_A(x)$ $=\frac{y^T\Lambda y}{\Vert y{\Vert }^2}$ ($V$ is orth. and therefore norm preserving) $=\frac{{\sum }_i{y}_i{\lambda }_i{y}_i}{{\sum }_i{y}_i^2}$ $=\frac{{\sum }_i{\lambda }_i{y}_i^2}{{\sum }_i{y}_i^2}$
    • This is a positively weighted average of the eigenvalues ${\lambda }_i$, so ${\lambda }_{\min }\le R_A(x)\le {\lambda }_{\max }$
  • Matrix PD $⟺$ $\forall x{R}_A(x)>0$
    • Implies matrix invertible: if $Ax=0$ for $x\ne 0$, then $Ax=0x=\lambda x$, meaning $\lambda =0$ were an eigenvalue, contradicting PD.
  • Matrix PSD $⟺$ $\forall x{R}_A(x)\ge 0$
  • $A^{T}A$ and $A{A}^T$ are always positive semi-definite
    • $x^T(A^{T}A)x=(Ax{)}^{T}Ax=\Vert Ax{\Vert }^2\ge 0$ (the denominator of $R_A(x)$ is always $\ge 0$)
    • $x^T(A{A}^T)x=(A^{T}x{)}^T{A}^{T}x=\Vert A^{T}x{\Vert }^2\ge 0$
• Gram Matrices and Cholesky Decomposition
  • $M$ Gram matrix $⟺M=V^{T}V$ for some matrix $V$
  • $M$ PSD matrix $⟺$ $M$ Gram matrix with $M=C^{T}C$, where $C$ upper triangular (Cholesky Decomposition)
    • $M=V\Lambda V^T$ b/c $M$ PSD $⟹$ $M$ symmetric $⟹M=V{\Lambda }^{1/2}{\Lambda }^{1/2}{V}^T$ b/c eigenvalues non-negative $⟹M=\underset{V^T}{\underbrace{({\Lambda }^{1/2}{V}^T{)}^T}}\underset{V}{\underbrace{({\Lambda }^{1/2}{V}^T)}}$
    • $V=QR$ $⟹M=(QR{)}^{T}QR$ $⟹M=R^T{Q}^{T}QR$ $⟹M=R^{T}R$
• Singular Value Decomposition
  • We’re looking for orthogonal matrices $V$ and $U$ s.t. $AV=U\Sigma$, where $\Sigma$ is diagonal, with only positive elements along the diagonal (the “singular values”). $AV=U\Sigma$ $⟺A=U\Sigma V^T$ b/c $V^T=V^{-1}$ for orthogonal matrices
    • $U\in {\mathbb{R}}^{m\times m}$ b/c left most matrix in matrix mult. determines num rows (it telescopes)
    • $\Sigma \in {\mathbb{R}}^{m\times n}$ to match dim
    • $V^T\in {\mathbb{R}}^{n\times n}⟺V\in {\mathbb{R}}^{n\times n}$ b/c right most matrix determines num cols
  • To find $V$ and $U$:
    • $A^{T}A=(U\Sigma V^T{)}^{T}U\Sigma V^T$ $=V{\Sigma }^T{U}^{T}U\Sigma V^T$ $=V({\Sigma }^T\Sigma )V^T$
    • $A{A}^T=U\Sigma V^T(U\Sigma V^T{)}^T$ $=U\Sigma V^{T}V{\Sigma }^T{U}^T$ $=U(\Sigma {\Sigma }^T)U^T$
    • Since $A^{T}A$ and $A{A}^T$ are sym., they each have a full set of orthogonal evecs (spectral theorem) $⟹$ Above is their diagonalization, where ${\Sigma }^T\Sigma$ and $\Sigma {\Sigma }^T$ corresponds to $\Lambda$
    • Works b/c both $A{A}^T$ and $A^{T}A$ are PSD and have the same non-zero eigenvalues. $\Sigma$ is filled from the top left with the square roots of the shared eigenvalues of $A{A}^T$ and $A^{T}A$. By convention: descending order. Rest of matrix is filled with zeros.
      • $m>n$: $A^{T}A$ is larger than $A{A}^T$, so it has additional zero eigenvalues. Therefore, ${\Sigma }^T\Sigma$ is larger than $\Sigma {\Sigma }^T$. $\Sigma$ is wide.
      • $n>m$: Reverse. $\Sigma$ is tall.
  • Intuition: $V^T$ tells you how much the input it rotated, $\Sigma$ how much it is stretched, and $U$ how much the output is rotated. Since $V^T$ and $U$ are orth., they don’t stretch at all.
• Change of Basis
  • A vector is a series of numbers that each scale a basis vector. Therefore, the same vector looks differently in different bases.
  • $B_1$ and $B_2:=$ two bases
  • $M:=$ matrix w/ $B_1$‘s basis vectors as cols as expressed in $B_2$. Multiplying a vector in $B_2$ by $M$ therefore maps it to $B_1$.
  • $A_1:=$ matrix of lin. transformation in $B_1$. To apply it to a vector $x$ in $B_2$, we must first convert $x$ to $B_1$ ($Mx$), then apply $A$ ($AMx$) and then convert back to $B_2$ ($M^{-1}AMx$) $⟹A_2=M^{-1}AM$
    • $A_1,A_2$ called similar
  • Application: Image Compression
    • Represent entire image or parts of image as vector or matrix, where each coordinate or row has a grayscale/color value.
    • Change basis so that basis vectors capture larger parts of the image, for example all pixels black, half black/half white, and so on. We then discard the ones with low coefficients since they don’t contribute much.
    • Common choices:
      • Fourier matrix: You have a wave going across the entire vector, with different frequencies for each basis vector.
      • Wavelet matrix: You have one wave cycle somewhere in the column vector. The crests have a couple different widths and locations.
• Left and Right Inverses; Pseudoinverse
  • Goal: Always get the most relevant answer to $Ax=b$
  • Tall matrix, full col. rank ($r=n$)
    • Does not collapse information in $Ax$: Converts vectors $x$ into higher dimension vectorspace; full column rank $⟹$ the subspace that the vectors inhabit has the same dim as their original vectorspace, so the transformation is injective. Therefore, $A$ should have a left inverse.
    • $A^{T}A$ is an $n\times n$ square matrix. Since $\mathrm{rank}A=\mathrm{rank}{A}^{T}A$, $A^{T}A$ is full rank and therefore invertible.
      • $A^{+}=(A^{T}A{)}^{-1}{A}^T$ is left inverse of $A$
    • Same as projection: $Ax=b$ $⟹A^{T}A\hat{x}=A^{T}b$ $⟺\hat{x}=A^{+}b$
      • Intuition: The inverse must work for all points, not just ones on hyperspace formed by $Ax$. The inverse must therefore project along the nullspace onto the hyperspace.
  • Wide matrix, full row rank ($r=m$)
    • Does not collapse information in $x^{T}A$: Converts vectors $x^T$ into higher dimension vectorspace; full row rank $⟹$ the subspace that the vectors inhabit has the same dim as their original vectorspace, so the transformation is injective. Therefore, $A$ should have a right inverse.
    • $A{A}^T$ is an $m\times m$ square matrix. Since $\mathrm{rank}A=\mathrm{rank}A{A}^T$, $A{A}^T$ is full rank and therefore invertible.
      • $A^{+}=A^T(A{A}^T{)}^{-1}$ is right inverse of $A$
    • $x^{\ast }=A^{+}b$ is min norm solution to $Ax=b$
      • $A(x^{\ast }+n)=b$, where $n\in N(A)$ and $x^{\ast }\in C(A^T)$, b/c they’re orth. complements $⟺A{x}^{\ast }+An=b$ $⟺A{x}^{\ast }=b$
      • $x^{\ast }$ is min-norm solution b/c $\Vert x{\Vert }^2=\Vert x^{\ast }{\Vert }^2+\Vert n{\Vert }^2+2\cdot x^{T}n\ge \Vert x^{\ast }{\Vert }^2$ ($x^{T}n=0$)
      • $A^{T}c=x^{\ast }$ for some $c$ b/c $x^{\ast }\in C(A^T)$ $⟹A{A}^{T}c=b$ $⟹A^{T}c=A^{+}b$ ($A^{+}A{A}^T=A^T$) $⟹x^{\ast }=A^{+}b$
    • $A^{+}=((A^T{)}^{+}{)}^T$
      • $A^{+}$ is the same for a wide matrix as transposing it into a tall matrix, taking the pseudoinverse, and then transposing again.
      • $((A^T{)}^{+}{)}^T=((A^T{)}^T{A}^T{)}^{-1}(A^T{)}^T{)}^T=A^{+}$
  • For any matrix
    • Use CR-decomposition: $A=CR$ $⟹A^{+}=(CR{)}^{+}=R^{+}{C}^{+}$
    • $C$ is tall matrix w/ full col. rank. $R$ is wide matrix w/ full row rank
    • $R^{+}{C}^{+}$ $=R^T(R{R}^T{)}^{-1}(C^{T}C{)}^{-1}{C}^T$ $=R^T(C^{T}CR{R}^T{)}^{-1}{C}^T$ ($R{R}^T$ and $C^{T}C$ invertible $⟺$ both bijections) $=R^T(C^{T}A{R}^T{)}^{-1}{C}^T$
    • $\hat{x}=A^{+}b$ is least squares sol:
      • $\hat{x}$ least squares sol $⟺$ $\hat{x}$ satisfies normal equation
      • $A^{T}A\hat{x}$ $=(CR{)}^{T}CR\hat{x}$ $=(CR{)}^{T}CR(R^{+}{C}^{+}b)$ ($x=A^{+}b$) $=(CR{)}^{T}C{C}^{+}b$ ($R^{+}$ right inverse) $=(CR{)}^{T}C(C^{T}C{)}^{-1}{C}^{T}b$ (def. $C^{+}$) $=R^T{C}^{T}C(C^{T}C{)}^{-1}{C}^{T}b$ (def. transpose) $=R^T{C}^{T}b$ $=A^{T}b$
    • $\hat{x}=A^{+}b$ is min norm solution:
      • We know from wide matrices: $\hat{x}$ min norm $⟺\hat{x}\in R(A)⟺\hat{x}=A^{T}c$
      • $\hat{x}$ $=A^{+}b$ $=R^{+}{C}^{+}b$ $=R^T\underset{v\in {\mathbb{R}}^m}{\underbrace{(R{R}^T{)}^{-1}(C^{T}C{)}^{-1}{C}^{T}b}}$ $=R^{T}v$ $=A^{T}c$ for some $c$ ($A$ and $R$ have same row space)
• Properties of the Pseudoinverse
  • $A{A}^{+}A=A$ and $A^{+}A{A}^{+}=A^{+}$
    • $C\underset{I}{\underbrace{R{R}^{+}}}\underset{I}{\underbrace{C^{+}C}}R=CR$ ($R^{+}$ = right inverse of $R$ and $C^{+}$ = left inverse of $C$)
    • $R^{+}\underset{I}{\underbrace{C^{+}C}}\underset{I}{\underbrace{R{R}^{+}}}{C}^{+}=R^{+}{C}^{+}$
  • $(A^T{)}^{+}=(A^{+}{)}^T$.
    • $((CR{)}^T{)}^{+}=(R^T{C}^T{)}^{+}=(C^T{)}^{+}(R^T{)}^{+}=\dots =(C^{+}{R}^{+}{)}^T$