机器学习数学学习笔记：Chapter 2. Linear Algebra

Chapter 2. Linear Algebra

Resources

Gilbert Strang’s Linear Algebra course

Linear Algebra Series by 3Blue1Brown

Algebra

Construct a set of objects (symbols) and a set of rules to manipulate these objects.

Vector objects:

Geometric vectors

Polynomials

Audio signals are vectors

Elements of ${\mathbb{R}}^n$ are vectors

2.1 Systems of Linear Algebra

$a_{11}{X}_1+\cdot \cdot \cdot +a_{1n}{x}_n=b_1$
$a_{m1}{X}_1+\cdot \cdot \cdot +a_{mn}{x}_n=b_m$

where $a_{ij}\in \mathbb{R}$ and $b_i\in \mathbb{R}$

The above is the general form of a system of linear algebra. $(x_1,......,x_n)\in {\mathbb{R}}^n$ that satisfies above equations is a solution of the linear equation system

Every linear equation represents a line

The solution set is the intersection of these lines

$\left[\begin{array}{c}{a}_{11}\\ ⋮\\ a_{m1}\end{array}\right]x_1+\left[\begin{array}{c}{a}_{12}\\ ⋮\\ a_{m2}\end{array}\right]x_2+\cdots +\left[\begin{array}{c}{a}_{1n}\\ ⋮\\ a_{mn}\end{array}\right]x_n=\left[\begin{array}{c}{b}_1\\ ⋮\\ b_m\end{array}\right]$

$\left[\begin{array}{c}{a}_{11}\cdots a_{1n}\\ ⋮⋮\\ a_{m1}\cdots a_{mn}\end{array}\right]\left[\begin{array}{c}{x}_1\\ ⋮\\ x_n\end{array}\right]=\left[\begin{array}{c}{b}_1\\ ⋮\\ b_m\end{array}\right]$

2.2 Matrices

$A=\left[\begin{array}{c}{a}_{11}{a}_{12}\cdots a_{1n}\\ a_{21}{a}_{22}\cdots a_{2n}\\ ⋮⋮⋮\\ a_{m1}{a}_{m2}\cdots a_{mn}\end{array}\right],a_{ij}\in \mathbb{R}$

(1,n) - matrices = rows

(m,1) - matrices = columns

2.2.1 Addition and Multiplication

• Addition

  • plus each other

• Multiplication

  • $c_{ij}=\sum _{l=1}^n{a}_{ij}{b}_{ij},i=1,\cdots ,m,j=1,\cdots ,k$.

• For dimensions: M \cdot k \times k \cdot N = M \times N

2.2.2 Inverse and Transpose

• Inverse

  • $AB=I_n=BA$ B is called the inverse of A and denoted by $A^{-1}$
  • $A=\left[\begin{array}{c}{a}_{11}{a}_{12}\\ a_{21}{a}_{22}\end{array}\right]=>A^{-1}=\frac{1}{(a_{11}{a}_{22}-a_{12}{a}_{21})}\left[\begin{array}{c}{a}_{22}-a_{12}\\ -a_{21}{a}_{11}\end{array}\right]$

• Transpose

  • $A\in {\mathbb{R}}^{m\times n}andB\in {\mathbb{R}}^{n\times m}with{b}_{ij}=a_{ji}$ is called the transpose of $A.B=A^T$

• Important Properties

  • $A{A}^{-1}=I=A^{-1}A$
  • $(AB{)}^{-1}=B^{-1}{A}^{-1}$
  • $(A+B{)}^{-1}\ne A^{-1}+B^{-1}$
  • $(A^T{)}^T=A$
  • $(A+B{)}^T=A^T+B^T$
  • $(AB{)}^T=B^T{A}^T$

• Symmetric Matrix

  • $A^T=A$

2.2.3 Multiplication by Scalar

• $A\in {\mathbb{R}}^{m\times n}$ and $\lambda \in \mathbb{R}Then,\lambda A=K,K_{ij}=\lambda a_{ij}$

• Associativity

  • $(\lambda \psi )C=\lambda \psi (C),C\in {\mathbb{R}}^{m\times n}$
  • $\lambda (BC)=(\lambda B)C=B(\lambda C)=(BC)\lambda ,B\in {\mathbb{R}}^{m\times n},C\in {\mathbb{R}}^{n\times k}$
  • $(\lambda C{)}^T=C^T{\lambda }^T=C^T\lambda =\lambda C^{T}since\lambda ={\lambda }^{T}forall\lambda \in \mathbb{R}$

• Distributivity

  • $(\lambda +\psi )C=\lambda C+\psi C,C\in {\mathbb{R}}^{m\times n}$
  • $\lambda (B+C)=\lambda B+\psi C,B,C\in {\mathbb{R}}^{m\times n}$

2.3 Solving Systems of Linear Equations

2.3.1 Particular and General Solution

• The general approach we followed by three steps:

  1. Find a particular solution to $Ax=b$
  2. Find all solutions to $Ax=0$
  3. Combine the above steps to the general solution

• Gasussian Elimination

  • Transform system of linear equations into particular simple form. Only simple form can use above three steps

2.3.2 Elementary Transformation

• Keep the solution set the same, but transfor the equation system into a simple form (Equation = Row):

  • Exchange the two equations
  • Multiplication of equations with a constant
  • Addition of two equations

• Pivot

  • The leading coefiicient of a row (first nonzero number from the left) is called the pivot .

• REF- Row Echelon From

  • The variable corresponding to the pivots in the REF are called basic variable and the other variables are free variables.

• Gaussian Elimination

  • An algorithm that performs elementary transformation to bring a system of linear equations into reduced REF

• Reduced REF

  • $A=\left[\begin{array}{c}13003\\ 00109\\ 0001-4\end{array}\right]$

  • The pivot is the position of the first row the first column, the second row the third column and the third row the fourth column.

  • The key idea for find the solutions of $Ax=0$ is to look at the non-pivot columns ， which we will need to expree as a linear combination of the pivot columns.

  • Solutions:

    • $\left[\begin{array}{c}3-1000\end{array}\right]and\left[\begin{array}{c}309-4-1\end{array}\right]$

2.3.3 The Minus-1 Trick

• The columns of $\tilde{A}$ that contain the -1 pivots are solutions of the homogeneous equation system Ax = 0 ,These columns form a basis of the solution space of $Ax=0$ , which we call the kernel or null space

• Example

  • $A=\left[\begin{array}{c}13003\\ 00109\\ 0001-4\end{array}\right]$
  • augment this matrix to a 5\times 5 matrix by adding rows of the Minus -1 at the place where the pivots on the diagonal are missing.
  • Obtain: $A=\left[\begin{array}{c}13003\\ 0-1000\\ 00109\\ 0001-4\\ 0000-1\end{array}\right]$
  • Soltions: $\left[\begin{array}{c}3\\ -1\\ 0\\ 0\\ 0\end{array}\right]and\left[\begin{array}{c}3\\ 0\\ 9\\ -4\\ -1\end{array}\right]$

• Colculating the Inverse

  • The matrix is augmented by inserting a matrix of diagonal to 1 to the right. Then, use Gaussian Elimination to bring it into REF. Finally, the right side is the inverse of the matrix

  • $AX=I_n,X=A^{-1}$

  • Example:

    • Origin Matrix:
    • $\left[\begin{array}{c}1020\\ 1100\\ 1201\\ 1111\end{array}\right]$
    • Augmented:
    • $\left[\begin{array}{c}1020|1000\\ 1100|0100\\ 1201|0010\\ 1111|0001\end{array}\right]$
    • Gaussian Elimination
    • $\left[\begin{array}{c}1000|0-12-2\\ 0100|1-12-2\\ 0010|1-11-1\\ 0001|-10-12\end{array}\right]$
    • The Verse is $A^{-1}=\left[\begin{array}{c}0-12-2\\ 1-12-2\\ 1-11-1\\ -10-12\end{array}\right]$

2.4 Vectors Space

A set of elements and an operation defined on these elements that keeps some structure of the set intact.

2.4.1 Groups

• Consider a set $\mathcal{G}$ and an operation $\otimes :\mathcal{G}\times \mathcal{G}\to \mathcal{G}$ defined on $\mathcal{G}$. Then, $G:=(\mathcal{G},\otimes )$ is called a group if the following hold:

  • Closure of $\mathcal{G}$ under $\otimes :\forall x,y\in \mathcal{G}:(x\otimes y)\in \mathcal{G}$
  • Associativity: $\forall x,y,z\in \mathcal{G}:(x\otimes y)\otimes z=x\otimes (y\otimes z)$
  • Neutral element: $\exists e\in \mathcal{G}\forall x\in \mathcal{G}:x\otimes e=xande\otimes x=x$
  • Inverse element: $\forall x\in \mathcal{G}\exists y\in \mathcal{G}:x\otimes y=eandy\otimes x=e$ , where e is the neutral element.

• If additionally $\forall x,y\in \mathcal{G}:x\otimes y=y\otimes x,thenG=(\mathcal{G},\otimes )$ is an Abelian group (commutative)

• Examples:

  • $(\mathbb{Z},+)$ is an Abelian group
  • $({\mathbb{N}}_0,+)$ is not a group, because the inverse elements are missing.

2.4.2 Vector Spaces

• A real-valued vector space $V=(V,+,\cdot )$ is a set \mathcal{V} with two operations: $$\begin{gathered} +:\mathcal{V}\times \mathcal{V}\to \mathcal{V} \\ \cdot :\mathbb{R}\times \mathcal{V}\to \mathcal{V} \end{gathered}$$
• where 1. $(\mathcal{V},+)$ is an Abelian group.
• 2, Distributivity: $$\begin{gathered} 1.\forall \lambda \in \mathbb{R},x,y\in \mathcal{V}:\lambda \cdot (x+y)=\lambda \cdot x+\lambda \cdot y \\ 2.\forall \lambda ,\psi \in \mathbb{R},x\in \mathcal{V}:(\lambda +\psi )\cdot x=\lambda \cdot x+\psi \cdot x \end{gathered}$$
• 3. Associativity (outer operation): $\forall \lambda ,\psi \in \mathbb{R},x\in \mathcal{V}:\lambda \cdot (\psi \cdot x)=(\lambda \psi )\cdot x$
• 4. Neutral element with repsect to the outer operation: $\forall x\in \mathcal{V}:1\cdot x=x$
• The element $x\in \mathcal{V}$ are called vectors.
• The neutral element of $(\mathcal{V},+)$ is the zero vector $0=[0,\cdots ,0{]}^T$, the inner operation + is called vector addition.
• The $\lambda \in \mathbb{R}$ are called scalars. the outer operation · is a multiplication by scalars.
• A “vector multiplication” $ab,a,b\in {\mathbb{R}}^n$ is not defined.
• Defined multiplication: $a{b}^T\in {\mathbb{R}}^{n\times n}$ (outer product), $a^{T}b\in \mathbb{R}$ (inner/scalar/dot product

2.3.4 Vector Subspaces

• Let $V=(V,+,\cdot )$ be a vector space and $\mathcal{U}\subseteq \mathcal{V},\mathcal{U}\ne \varnothing$ . Then $U=(\mathcal{U},+,\cdot )$ is called vector subspace of $V$ (or linear subspace) if $U$ is a vector space with the vector space operations + and · restricted to $\mathcal{U}\times \mathcal{U}and\mathbb{R}\times \mathcal{U}$ . We write $U\subseteq V$ to denote a subspace $U$ of $V$
• Every subspsce $U\subseteq ({\mathbb{R}}^n,+,\cdot )$ is the solution space of a homogeneous system of linear equations $Ax=0$ for $x\in {\mathbb{R}}^n$

2.5 Linear Independence

Linear Combination

• Consider a vector space $V$ and a finite number of vectors $x_1,\cdots ,x_k\in V$. Then, every $v\in V$ of the form$v={\lambda }_1{x}_1+\cdots +{\lambda }_k{x}_k={\sum }_{i=1}^k{\lambda }_i{x}_i\in V$ with ${\lambda }_1,\cdots ,{\lambda }_k\in \mathbb{R}$ is a linear combination of the vectors $x_1,\cdots ,x_k$.

Linear (In)dependence

• Let us consider a vector space $V$ with $k\in \mathbb{N}and{x}_1,\cdots ,x_k\in V$. If there is a non-trivial linear combination, such that $0={\sum }_{i=1}^k{\lambda }_i{x}_i$ with at least one ${\lambda }_i\ne 0$. The vectors $x_1,\cdots ,x_k$ are linear dependent. If only the trivial solution exists, i.e., ${\lambda }_1=\cdots ={\lambda }_k=0$ the vectors $x_1,\cdots ,x_k$ are linear independent.

either independent or dependent. No third option.

The v e c t o r { x 1 , ⋯   , x k : x i ≠ 0 , i = 1 , ⋯ k } , k ⩾ 2 vector \{x_1,\cdots,x_k : x_i \neq 0, i = 1,\cdots k\}, k \geqslant 2 vector{x1​,⋯,xk​:xi​​=0,i=1,⋯k},k⩾2 linearly dependent if and oly if at least one of them is a linear combination of the others. In particular, if one vector is a multiple of another vector then the set is linearly dependent.

determine by Gaussian Elimination in REF.

• All column vectors are linearly independent if and only if all columns are pivot columns. If there is at least one non-pivot column, the columns are dependent.

2.6 Basis and Rank

2.6.1 Generating Set and Basis

• Generating Set ans Span

  • Consider a vector space $V=(\mathcal{V},+,\cdot )$ and set of vectors A = { x 1 , ⋯   , x k } ⊆ V \mathcal{A} = \{ x_1,\cdots,x_k\} \subseteq \mathcal{V} A={x1​,⋯,xk​}⊆V. If every vector $v\in \mathcal{V}$ can be expressed as a linear combination of $x_1,\cdots ,x_k,\mathcal{A}$ is called a generating set of V$. The set of all linear combination of vectors in $\mathcal{A}$ is called the span of $\mathcal{A}$. If $\mathcal{A}$ spans the vector space $V$, we write $V=span[\mathcal{A}]$ or $V=span\left[x_1,\cdots ,x_k\right]$.
  • Generating sets are sets of vectors that span vector (sub)spaces.

• Basis

  • There exists no smaller set that spans $V$. Every linearly independent generating set of $V$ is minimal and is called a basis of $V$.

• In ${\mathbb{R}}^3$, the canonical/standard basis is B = { [ 1 0 0 ] , [ 0 1 0 ] , [ 0 0 1 ] } \\ \mathcal{B} = \{ \left[ \begin{matrix} 1 \\ 0 \\0 \end{matrix} \right] , \left[ \begin{matrix} 0 \\ 1 \\0 \end{matrix} \right] , \left[ \begin{matrix} 0 \\ 0 \\1 \end{matrix} \right] \} B={⎣⎡​100​⎦⎤​,⎣⎡​010​⎦⎤​,⎣⎡​001​⎦⎤​}

• Determining a Basis

  • REF: $\left[\begin{array}{c}123-1\\ 012-2\\ 0001\\ 0000\\ 0000\end{array}\right]$
  • The pivot columns indicate which set of vectors is linearly independent, see from REF that $x_1,x_2,x_3,x_4$ are linearly independent. because ${\lambda }_1{x}_1+{\lambda }_2{x}_2+{\lambda }_4{x}_4=0$ can only be solved with ${\lambda }_1={\lambda }_2={\lambda }_4=0$. Therefore, { x 1 , x 2 , x 3 , x 4 } \{x_1,x_2,x_3,x_4\} {x1​,x2​,x3​,x4​} is a basis of $U$.

2.6.2 Rank

• The number of linearly independent columns of a matrix $A\in {\mathbb{R}}^{m\times n}$ equals the number of linearly independent row and is called the rank of $A$ and is denoted by $rk(A)$

• Important properties

  • $rk(A)=rk(A^T)$
  • The columns of $A\in {\mathbb{R}}^{m\times n}$ span a subspace $U\subseteq {\mathbb{R}}^m$ with $dim(U)=rk(A)$ . We call this subspace the image or range. $A$ basis of $U$ can be found by applying Gaussian Elimination to $A$ to identify the pivot columns.
  • The Rows of $A\in {\mathbb{R}}^{m\times n}$ span a subspace $W\subseteq {\mathbb{R}}^{n}withdim(W)=rk(A)$ . A basis of $W$ can be found by applying Gaussian Elimination to $A^T$
  • $A=\in {\mathbb{R}}^{n\times n}$ it holds that $A$ is regular (invertible) if and only if $rk(A)=n$.
  • $Ax=b$ can be solved if and only if $rk(A)=rk(A|b)$. The A|b denotes the augmented system.
  • $Ax=0$ possessed dimension $n-rk(A)$ . We call this subspace the kernel or the null space.
  • When rank equals the largest possible rank for a matrix of the same dimensions that means the matrix has full rank.This mean that the rank of a full-rank matrix is the lesser of the number of rows and columns.
  • If it does not have full rank, the matrix is said to be rank deficient.

2.7 Linear Mappings - Linear Transformation

Definition: For vector spaces V,W, a mapping $\Phi :V\to W$ is called a linear mapping.(or vector space homomorphism/ linear transformation) if $\forall x,y\in V\forall \lambda ,\psi \in \mathbb{R}:\Phi (\lambda x+\psi y)=\lambda \Phi (x)+\psi \Phi (y)$.

$\Phi :\mathcal{V}\to \mathcal{W}\mathcal{V},\mathcal{W}$ can be arbitrary sets. Then $\Phi$ is called

• Injective if $\forall x,y\in \mathcal{V}:\Phi (x)=\Phi (y)\Rightarrow x=y$
• Surjective if $\Phi (\mathcal{V})=\mathcal{W}$
• Bijective if it is injective and surjective.

Finite-dimensional vector spaces $V$ and $W$ are isomorphic if and only if $dim(V)=dim(W)$.

2.7.1 Matrix Representation of Linear Mapping

• $A_{\Phi }=\left[a_1,a_2,a_3\right]=\left[\begin{array}{c}120\\ -113\\ 371\\ -124\end{array}\right]$ where the $a_j,j=1,2,3$ are the coordinate vectors of $\Phi (b_j)$ with respect to $C$.
• Basis Vectors

2.7.2 Basis Change

• Equivalence

  • Two matrices $A,\tilde{A}\in {\mathbb{R}}^{m\times n}areequivalentifthereexistregularmatricesS\in {\mathbb{R}}^{n\times n}$ and $T\in {\mathbb{R}}^{m\times m}$ , such that $\tilde{A}=T^{-1}AS$

• Similarity

  • Two matrices $A,\tilde{A}\in {\mathbb{R}}^{n\times n}$ are similarity if there exist regular matrices $S\in {\mathbb{R}}^{n\times n}$ with $\tilde{A}=S^{-1}AS$

• Transformation formular: $$\begin{gathered} \tilde{A}=T^{-1}{A}_{\Phi }S \\ {A}_{\Phi }:B\to C,{\tilde{A}}_{\Phi }:\tilde{B}\to \tilde{C},S:\tilde{B}\to B,T:\tilde{C}\to Cand{T}^{-1}:C\to \tilde{C} \\ \tilde{B}\to \tilde{C}=\tilde{B}\to B\to C\to \tilde{C} \end{gathered}$$

2.7.3 Image and Kernel

• For $\Phi :V\to W$, we defined the kernel/null space k e r ( Φ ) : = Φ − 1 ( 0 W ) = { v ∈ V : Φ ( v ) = 0 W } \\ ker(\Phi) := \Phi^{-1}(0_W) = \{v \in V : \Phi(v) = 0_W\} ker(Φ):=Φ−1(0W​)={v∈V:Φ(v)=0W​} and the image/range I m ( Φ ) : = Φ ( V ) = { w ∈ W ∣ ∃ v ∈ V : Φ ( v ) = w } \\ Im(\Phi) := \Phi(V) = \{w\in W | \exist v\in V : \Phi(v) = w\} Im(Φ):=Φ(V)={w∈W∣∃v∈V:Φ(v)=w} we call $V$ and $W$ also the domain and codomain of $\Phi$, respectively.

• $rk(A)=dim(Im(\Phi ))$

• $\left[\begin{array}{c}1001\\ 01-\frac{1}{2}-\frac{1}{2}\end{array}\right]$ This matrix is in REF, and we can use the Minus-1 Trick to compute a basis of the kernel. Alternatively, we can express the non-pivot columns(3,4) as linear combinations of the pivot columns(1,2). The third column $a_3$ is equivalent to $-\frac{1}{2}$ times the second column $a_2$ . Therefor, $0=a_3+\frac{1}{2}{a}_2$. In the same way, we see that $a_4=a_1-\frac{1}{2}{a}_2$ and, therefore, $0=a_1-\frac{1}{2}{a}_2-a_4$. Overall, this gives us the kernel (null space) is $ker(\Phi )=span[\left[\begin{array}{c}0\\ \frac{1}{2}\\ 1\\ 0\end{array}\right],\left[\begin{array}{c}-1\\ \frac{1}{2}\\ 0\\ 1\end{array}\right]]$

• Rank-Nullity Theorem

  • For vector spaces $V,W$ and a linear mapping $\Phi :V\to W$ it holds that $dim(ker(\Phi ))+dim(Im(\Phi ))=dim(V)$
  • Fundamental theorem of linear mappings
  • If $dim(Im(\Phi ))<dim(V)$, then $ker(\Phi )$ is non-trivial, i.e., the kernel contains more than $0_v$ and $dim(ker(\Phi ))>1$
  • If $A_{\Phi }$ is the transformation matrix of $\Phi$ with respect to an ordered basis and $dim(Im(\Phi ))<dim(V)$, then the system of linear equations $A_{\Phi }x=0$ has infinitely many solutions.
  • If $dim(V)=dim(W)$, then the $\Phi$ is bijective(includ: injective and surjective). since $Im(\Phi )\subseteq W$.

2.8 Affine Spaces

Resemble linear mapping

Affine Subspace

• Let $V$ be a vector space, $x_0\in V$ and $U\subseteq V$ a subspace. The the subset L = x 0 + U : = { x 0 + u : u ∈ U }      = { v ∈ V ∣   ∃ u ∈ U : v = x 0 + u } ⊆ V \\ L = x_0 + U := \{x_0 + u : u \in U\} \\ \ \ \ \ = \{v\in V | \ \exist u\in U : v=x_0 + u\} \subseteq V L=x0​+U:={x0​+u:u∈U}    ={v∈V∣ ∃u∈U:v=x0​+u}⊆V is called affine subspace or linear manifold of $V$. $U$ is called direction or direction space, and $x_0$ is called support point.
• If $x_0\notin U$, an affine subspace is not a linear subspace(vector subspace) of $V$.
• Are points, lines, and planes in ${\mathbb{R}}^3$, which do not (necessarily) go through the origin.

Affine Mappings

• For two vector spaces $V,W$ , a linear mapping $\Phi :V\to W$, and $a\in W$, the mapping $$\begin{gathered} \varphi :V\to W \\ x\mapsto a+\Phi (x) \end{gathered}$$ is an affine mapping from $V$ to $W$ . The vector a is called the translation vector of $\varphi$.
• Affine mappings keep the geometric structure invariant. They also preserve the dimension and parallelism.