0%

Notes for Algebra Basics

Selected notes from ROB 501 and ME 564.
$\{x_i\}^b_a$ denotes set $\{x_a, x_{a+1}, \ldots, x_b\}$

Algebraic Structures

Operation

  • Definition: an (binary, closed) operation $\ast$ on a set $S$ is a mapping of $S\times S\rightarrow S$
  • Commutative: $x\ast y=y\ast x,\;\forall x,y\in S$
  • Associative: $(x\ast y)\ast z=x\ast (y\ast z),\;\forall x,y,z\in S$

Group

  • Definition: a group is a pair $(\mathcal{S},\ast)$ with following axioms
    1. $\ast$ is associative on $\mathcal{S}$
    2. (Identity element) $\exists e\in \mathcal{S}\text{ s.t. }x\ast e=e\ast x=x,\;\forall x\in \mathcal{S}$
    3. (Inverse element) $\forall x\in \mathcal{S}, \exists x’ \in \mathcal{S}\text{ s.t. }x\ast x’=x’\ast x=e$
  • Abelian: a group is called abelian group if $\ast$ is also commutative

Ring

  • Definition: a ring is a triplet $(\mathcal{R},+,\ast)$ consisting of a set of scalars $\mathcal{R}$ and two operators + and $\ast$ with following axioms
    1. $(\mathcal{R},+)$ is an abelian group with identity denoted $0$
    2. $\forall a,b,c \in \mathcal{R}\text{ s.t. }a\ast(b\ast c) = (a\ast b)\ast c$
    3. $\exists 1\in\mathcal{R}, \forall a\in\mathcal{R}\text{ s.t. }a\cdot 1=a$
    4. $\ast$ is distributive over $+$

Field

  • Definition: a field $(\mathcal{F},+,\ast)$ is a ring where $(\mathcal{F}\backslash\{0\},\ast)$ is also an abelian group.

    Difference from ring to field is that $\ast$ need to be commutative and have a multiplicative inverse

Vector Space

  • Definition: a vector space (aka. linear space) is a triplet $(\mathcal{U},\oplus,\cdot)$ defined over a field $(\mathcal{F},+,\ast)$ with following axioms, where set $\mathcal{U}$ is called vectors, operator $\oplus$ is called vector addition and mapping $\cdot$ is called scalar multiplication:
    1. (Null vector) $(\mathcal{U},+)$ is an abelian group with identity element $\emptyset$
    2. Scalar multiplication is a mapping of $\mathcal{F}\times\mathcal{U}\rightarrow\mathcal{U}$
    3. $\alpha\cdot(x\oplus y) = \alpha\cdot x \oplus \alpha\cdot y,\;\forall x,y\in\mathcal{U};\alpha\in\mathcal{F}$
    4. $(\alpha+\beta)\cdot x = \alpha\cdot x\oplus\beta\cdot x,\;\forall x\in\mathcal{U};\alpha,\beta\in\mathcal{F}$
    5. $(\alpha\ast\beta)\cdot x=\alpha\cdot(\beta\cdot x),\;\forall x\in\mathcal{U};\alpha,\beta\in\mathcal{F}$
    6. $1_\mathcal{F}\cdot x=x$

    Usually we don’t distinguish vector addition $\oplus$ and addition of scalar $+$. Juxtaposition is also commonly used for both scalar multiplication $\cdot$ and multiplication of scalars $\ast$

  • Subspace: a subspace $\mathcal{V}$ of a linear space $\mathcal{U}$ over field $\mathcal{F}$ is a subset of $\mathcal{U}$ which is itself a linear space over $\mathcal{F}$ under same vector addition and scalar multiplication.

Basis & Coordinate

  • Linear Independence: Let $\mathcal{V}$ be a vector space over $\mathcal{F}$ and let $X=\{x_i\}^n_1\subset \mathcal{V}$
    • X is linearly dependent if $\exists \alpha_1,\ldots,\alpha_n\in\mathcal{F}$ not all 0 s.t. $\sum^n_{i=1} \alpha_i x_i=0$.
    • X is linearly independent if $\sum^n_{i=1} \alpha_i x_i=0 \Rightarrow \alpha_1=\alpha_2=\ldots=\alpha_n=0$
  • Span: Given a set of vectors $V$, the set of linear combinations of vectors in $V$ is called the span of it, denoted $Span\{V\}$
  • Basis: A set of linearly independent vectors in a linear space $\mathcal{V}$ is a basis if every vector in $\mathcal{V}$ can be expressed as a unique linear combination of these vectors. (see below “Coordinate”)
    • Basis Expansion: Let $(X,\mathcal{F})$ be a vector space of dimension n. If $\{v_i\}^k_1,\;1\leqslant k< n$ is linearly independent, then $\exists \{v_i\}^n_{k+1}$ such that $\{v_i\}_1^n$ is a basis.
    • Reciprocal Basis: Given basis $\{v_i\}^n_1$, a set ${r_i}^1_n$ that satifies $\langle r_i,v_j \rangle=\delta_i(j)$ is a reciprocal basis. It can be generated by Gram-Schmidt Process and $\forall x\in\mathcal{X}, x=\sum^n_{i=1}\langle r_i,x\rangle v_i$.
  • Dimension: Cardinality of the basis is called the dimension of that vector space, which is equal to the maximum number of linearly independent vectors in the space. Denoted as $dim(\mathcal{V})$.
    • In an $n$-dimensional vector space, any set of $n$ linearly independent vectors is a basis.
  • Coordinate: For a vector $x$ in vector space $\mathcal{V}$, given a basis $\{e_1, \ldots, e_n\}$ we can write $x$ as $x=\sum^n_{i=1}\beta_i e_i=E\beta$ where $E=\begin{bmatrix}e_1&e_2&\ldots&e_n\end{bmatrix}$ and $\beta=\begin{bmatrix}\beta_1&\beta_2&\ldots&\beta_n\end{bmatrix}^\top$. Here $\beta$ is called the representation (or coordinate) of $x$ given the basis $E$.

Norm & Inner product

  • Inner Product: an operator on two vectors that produces a scalar result (i.e. $\langle\cdot,\cdot\rangle:\mathcal{V}\rightarrow\mathbb{R}\;or\;\mathbb{C}$) with following axioms:
    1. (Symmetry) $\langle x,y \rangle=\overline{\langle y,x\rangle},\;\forall x,y\in\mathcal{V}$
    2. (Bilinearity) $\langle \alpha x+\beta y,z\rangle=\alpha\langle x,z\rangle+\beta\langle y,z\rangle,\;\forall x,y,z\in\mathcal{V};\alpha,\beta\in\mathbb{C}$
    3. (Pos. definiteness) $\langle x,x\rangle\geqslant 0,\;\forall x\in\mathcal{V}$ and $\langle x,x\rangle=0\Rightarrow x=0_\mathcal{V}$
  • Inner Product Space: A linear space with a defined inner product
  • Orthogonality:
    • Perpedicularity of vectors ($x\perp y$): $\langle x,y\rangle=0$
    • Perpedicularity of a vector to a set ($y\perp\mathcal{S},\mathcal{S}\subset\mathcal{V}$): $y\perp x,\;\forall x\in\mathcal{S}$
    • Orthogonal Set: set $\mathcal{S}\subset(\mathcal{U},\langle\cdot,\cdot\rangle)$ is orthogonal $\Leftrightarrow x\perp y,\;\forall x,y\in\mathcal{S},x\neq y$
    • Orthonormal Set: set $\mathcal{S}$ is orthonormal iff $\mathcal{S}$ is orthogonal and $\Vert x\Vert=1,\;\forall x\in\mathcal{S}$
    • Orthogonality of sets ($\mathcal{X}\perp\mathcal{Y}$): $\langle x,y\rangle=0,\;\forall x\in\mathcal{X};y\in\mathcal{Y}$
    • Orthogonal Complement: Let $(\mathcal{V},\langle\cdot,\cdot\rangle)$ be an inner product space and let $\mathcal{U}\subset\mathcal{V}$ be a subspace of $\mathcal{V}$, the orthogonal complement of $\mathcal{U}$ is $\mathcal{U}^\perp=\left\{v\in\mathcal{V}\middle|\langle v,u\rangle=0,\;\forall u\in\mathcal{U}\right\}$.
      • $\mathcal{U}^\perp\subset\mathcal{V}$ is a subspace
      • $\mathcal{V}=\mathcal{U}\overset{\perp}{\oplus}\mathcal{U}^\perp$ ($\oplus$: direct sum, $\overset{\perp}{\oplus}$: orthogonal sum)
  • Norm: A norm on a linear space $\mathcal{V}$ is mapping $\Vert\cdot\Vert:\;\mathcal{V}\rightarrow\mathbb{R}$ such that:
    1. (Positive definiteness) $\Vert x\Vert\geqslant 0\;\forall x\in \mathcal{V}$ and $\Vert x\Vert =0\Rightarrow x=0_\mathcal{V}$
    2. (Homogeneous) $\Vert \alpha x\Vert=|\alpha|\cdot\Vert x\Vert,\;\forall x\in\mathcal{V},\alpha\in\mathbb{R}$
    3. (Triangle inequality) $\Vert x+y\Vert\leqslant\Vert x\Vert+\Vert y\Vert$
  • Distance: Norm can be used to measure distance between two vectors. Meanwhile, distance from a vector to a (sub)space is defined as $d(x,\mathcal{S})=\inf_{y\in\mathcal{S}} d(x,y)=\inf_{y\in\mathcal{S}} \Vert x-y\Vert$
    • Projection Point: $x^* =\arg\min_{y\in\mathcal{S}}\Vert x-y\Vert$ is the projection point of $x$ on linear space $\mathcal{S}$.
    • Projection Theorem: $\exists !x^* \in\mathcal{S}$ s.t. $\Vert x-x^* \Vert=d(x,\mathcal{S})$ and we have $(x-x^*) \perp\mathcal{S}$
    • Orthogonal Projection: $P(x)=x^*:\mathcal{X}\rightarrow\mathcal{M}$ is called the orthogonal projection of $\mathcal{X}$ onto $\mathcal{M}$
  • Normed Space: A linear space with a defined norm $\Vert\cdot\Vert$, denoted $(\mathcal{V},\mathcal{F},\Vert\cdot\Vert)$

    A inner product space is always a normed space because we can define $\Vert x\Vert=\sqrt{\langle x,x\rangle}$

  • Common $\mathbb{R}^n$ Norms:
    • Euclidean norm (2-norm): $\Vert x\Vert_2=\left(\sum^n_{i=1}|x_i|^2\right)^{1/2}=\left\langle x,x\right\rangle^{1/2}=\left(x^\top x\right)^{1/2}$
    • $l_p$ norm (p-norm): $\Vert x\Vert_p=\left(\sum^n_{i=1}|x_i|^p\right)^{1/p}$
    • $l_1$ norm: $\Vert x\Vert_1=\sum^n_{i=1}|x_i|$
    • $l_\infty$ norm: $\Vert x\Vert_\infty=\max_{i}\{x_i\}$
  • Common matrix norms:

    Matrix norms are also called operator norms, can measure how much a linear operator “magnifies” what it operates on.

    • A general form induced from $\mathbb{R}^n$ norm: $$\Vert A\Vert=\sup_{x\neq 0}\frac{\Vert Ax\Vert}{\Vert x\Vert}=\sup_{\Vert x\Vert=1}\Vert Ax\Vert$$
    • $\Vert A\Vert_1=\max_j\left(\sum^n_{i=1}|a_{ij}|\right)$
    • $\Vert A\Vert_2=\left[ \max_{\Vert x\Vert=1}\left\{(Ax)^* (Ax)\right\}\right]^{1/2}=\left[ \lambda_{max}(A^ *A)\right]^{1/2}$ ($\lambda_{max}$: largest eigenvalue)
    • $\Vert A\Vert_\infty=\max_i\left(\sum^n_{j=1}|a_{ij}|\right)$
    • (Frobenius Norm) $\Vert A\Vert_F=\left[ \sum^m_{i=1}\sum^n_{j=1}\left|a_{ij}\right|^2\right]^{1/2}=\left[ tr(A^*A)\right]^{1/2}$
  • Useful inequations:
    • Cauchy-Schwarz: $|\langle x,y\rangle|\leqslant\left\langle x,x\right\rangle^{1/2}\cdot\left\langle y,y\right\rangle^{1/2}$
    • Triangle (aka. $\Delta$): $\Vert x+y\Vert\leqslant\Vert x\Vert+\Vert y\Vert$

      Lemma: $\Vert x-y\Vert \geqslant \left| \Vert x\Vert-\Vert y\Vert \right|$

    • Pythagorean: $x\perp y \Leftrightarrow \Vert x+y\Vert=\Vert x\Vert+\Vert y\Vert$

Gramian

  • Gram-Schmidt Process: A method to find orthogonal basis $\{v_i\}^n_1$ given an ordinary basis $\{y_i\}^n_1$. It’s done by perform $v_k=y_k-\sum^{k-1}_{j=1}\frac{\langle y_k,v_j\rangle}{\langle v_j,v_j \rangle}\cdot v_j$ iteratively from 1 to $n$. To get an orthonormal basis, just normalize these vectors.
  • Gram Matrix: The Gram matrix generated from vectors $\{y_i\}_ 1^k$ is denoted $G(y_ 1,y_ 2,\ldots,y_ k)$. Its element $G_{ij}=\langle y_i,y_j\rangle$
    • Gram Determinant: $g(y_1,y_2,\ldots,y_n)=\det G$
    • Normal Equations: Given subspace $\mathcal{M}$ and its basis $\{y_i\}^n_1$, the projection point of $\forall x\in\mathcal{M}$ can be represented by $$x^*=\alpha y=\begin{bmatrix}\alpha_1&\alpha_2&\ldots&\alpha_n\end{bmatrix}\begin{bmatrix}y_1\\y_2\\ \vdots \\y_n\end{bmatrix},\;\beta=\begin{bmatrix}\langle x,y_1\rangle\\ \langle x,y_2\rangle\\ \vdots\\ \langle x,y_n\rangle\end{bmatrix} where\;G^\top\alpha=\beta$$

      For least-squares problem $Ax=b$, consider $\mathcal{M}$ to be the column space of $A$, then $G=A^\top A,\;\beta=A^\top b,\;G^\top\alpha=\beta\Rightarrow\alpha=(A^\top A)^{-1}A^\top b$. Similarly for weighted least-squares problem ($\Vert x\Vert=x^\top Mx$), let $G=A^\top MA, \beta=A^\top Mb$, we can get $\alpha=(A^\top MA)^{-1}A^\top Mb$

Linear Algebra

Linear Operator

  • Definition: a linear operator $\mathcal{A}$ (aka. linear transformation, linear mapping) is a function $f: V\rightarrow U$ that operate on a linear space $(V,\mathcal{F})$ to produce elements in another linear space $(U,\mathcal{F})$ and obey $$\mathcal{A}(\alpha_1 x_1+\alpha_2 x_2) = \alpha_1\mathcal{A}(x_1) + \alpha_2\mathcal{A}(x_2),\;\forall x_1,x_2\in V;\alpha_1, \alpha_2\in\mathcal{F}$$

  • Range (Space): $\mathcal{R}(\mathcal{A})=\left\{u\in U\middle|\mathcal{A}(v)=u,\;\forall v\in V\right\}$

  • Null Space (aka. kernel): $\mathcal{N}(\mathcal{A})=\left\{v\in V\middle|\mathcal{A}(v)=\emptyset_U\right\}$

  • Matrix Representation: Given bases for both $V$ and $U$ (respectively $\{v_i\}^n_1$ and $\{u_j\}^m_1$), matrix representation $A$ satisfies $\mathcal{A}(v_i)=\sum^m_{j=0}A_{ji}u_j$ so that $\beta=A\alpha$ where $\alpha$ and $\beta$ is the representation of a vector under $\{v_i\}$ and $\{u_j\}$ respectively.

    • $P$ and $Q$ are change of basis matrices, $A=Q^{-1}\tilde{A}P,\;\tilde{A}=QAP^{-1}$
    • The i-th column of $A$ is the coordinates of $\mathcal{A}(v_i)$ represented by the basis $\{u_j\}$, similarly i-th column of $\tilde{A}$ is $\mathcal{A}(\tilde{v}_i)$ represented in $\{\tilde{u}_j\}$
    • The i-th column of $P$ is the coordinates of $v_i$ represented by the basis $\{\tilde{v}\}$, similarly i-th column of $Q$ is $u_j$ represented in $\{\tilde{u}\}$
  • Matrix Similarity ($A\sim B$): Two (square) matrix representations ($A,B$) of the same linear operator are called similar (or conjugate) and they satisfies $\exists P$ s.t. $B=PAP^{-1}$.

    From now on we don’t distinguish between linear operator $\mathcal{A}$ and its matrix representation where choice of basis doesn’t matter.

  • Rank: $rank(A)=\rho(A)\equiv dim(\mathcal{R}(A))$

  • Nullity: $null(A)=\nu(A)\equiv dim(\mathcal{N}(A))$

    • $\rho(A)+\nu(A)=n$ ($n$ is the dimensionality of domain space)
  • Adjoint: The adjoint of the linear map $\mathcal{A}: \mathcal{V}\rightarrow\mathcal{W}$ is the linear map $\mathcal{A}^*: \mathcal{W}\rightarrow\mathcal{V}$ such that $\langle y,\mathcal{A}(x)\rangle_\mathcal{W}=\langle \mathcal{A}^ *(y),x\rangle_\mathcal{V}$

    For its matrix representation, adjoint of $A$ is $A^ *$, which is $A^\top$ for real numbers.

    Properties of $\mathcal{A}^ *$ is similar to matrix $A^ *$

    • $\mathcal{U}=\mathcal{R}(A)\overset{\perp}{\oplus}\mathcal{N}(A^ *),\;\mathcal{V}=\mathcal{R}(A^ *)\overset{\perp}{\oplus}\mathcal{N}(A)$
    • $\mathcal{N}(A^* )=\mathcal{N}(AA^* )\subseteq\mathcal{U},\;\mathcal{R}(A)=\mathcal{R}(AA^*)\subseteq\mathcal{U}$
  • Self-adjoint: $\mathcal{A}$ is self-adjoint iff $\mathcal{A}^*=\mathcal{A}$.

    • For self-adjoint $\mathcal{A}$, if $\mathcal{V}=\mathbb{C}^{n\times n}$ then $A$ is hermitian; if $\mathcal{V}=\mathbb{R}^{n\times n}$ then $A$ is symmetric.
    • Self-adjoint matrices have real eigenvalues and orthogonal eigenvectors
    • Skew symmetric: $A^*=-A$

      For quadratic form $x^\top Ax=x^\top(\frac{A+A^\top}{2}+\frac{A-A^\top}{2})x$, since $A-A^\top$ is skew symmetric, scalar $x^\top (A-A^\top) x=-x^\top (A-A^\top)x$, so the skew-symmetric part is zero. Therefore for quadratic form $x^\top Ax$ we can always assume $A$ is symmetric.

  • Definiteness: (for symmetric matrix $P$)

    • Positive definite ($P\succ 0$): $\forall x\in\mathbb{R}^n\neq 0,\; x^\top Px>0 \Leftrightarrow$ all eigenvalues of $P$ are positive.
    • Semi-positive definite ($P\succcurlyeq 0$): $x^\top Px\geqslant 0 \Leftrightarrow$ all eigenvalues of $P$ are non-negative.
    • Negative definite ($P\prec 0$): $x^\top Px < 0 \Leftrightarrow$ all eigenvalues of $P$ are negative.
  • Orthogonal Matrix: $Q$ is orthogonal iff $Q^\top Q=I$, iff columns of $Q$ are orthonormal.

    • If $A\in\mathbb{R}^{n\times b}$ is symmetric, then $\exists$ orthogonal $Q$ s.t. $Q^\top AQ=\Lambda=diag(\lambda_1,\ldots,\lambda_n)$
  • Orthogonal Projection: Given linear space $\mathcal{X}$ and subspace $\mathcal{M}$, $P(x)=x^*:\mathcal{X}\rightarrow\mathcal{M}$ ($x^ *$ is the projection point) is called orthogonal projection. If $\{v_i\}$ is a orthonormal basis of \mathcal{M}, then $P(x)=\sum_i \langle x,v_i\rangle v_i$

SVD and Linear Equations

SVD Decomposition is useful in various fields and teached by a lot of courses, its complete version is formulated as $$A=U\Sigma V^*, \Sigma=\begin{bmatrix}\mathbf{\sigma}&\mathbf{0}\\ \mathbf{0}&\mathbf{0}\end{bmatrix}, \mathbf{\sigma}=\begin{bmatrix}\sqrt{\lambda_1}&&&\\ &\sqrt{\lambda_2}&&\\ &&\ddots&\\ &&&\sqrt{\lambda_r}\end{bmatrix},V=\begin{bmatrix}V_1&V_2\end{bmatrix},U=\begin{bmatrix}U_1&U_2\end{bmatrix}$$
where

  • $\sigma_i$ are called sigular values, $\lambda_i$ are eigenvalues of $A^* A$
  • Columns of $V_1$ span $\mathcal{R}(A^ *A)=\mathcal{R}(A^ *)$, columns of $V_2$ span $\mathcal{N}(A^ *A)=\mathcal{N}(A)$
  • Columns of $U_1=AV_1\sigma^{-1}$ span $\mathcal{R}(A)$, columns of $U_2$ span $\mathcal{N}(A^*)$

SVD can be derived by doing eigenvalue decomposition on $A^* A$

With SVD introduced, we can efficiently solve general linear equation $Ax=b$ as $x=x_r+x_n$ where $x_r\in\mathcal{R}(A^\top)$ and $x_n\in\mathcal{N}(A)$.

$Ax=b$tall $A$ ($m>n$)fat $A$ ($m< n$)
Overdetermined,
Least Squares,
use Normal Equations
Underdetermined,
Quadratic Programming,
use Lagrange Multiplies
I.$b\in\mathcal{R}(A)$
1.$\mathcal{N}(A)={0}$$x$ exist & is unique$x=(A^\top A)^{-1}A^\top b=A^+b$$x=A^\top(AA^\top)^{-1}b=A^+b$
2.$\mathcal{N}(A)\neq{0}$$x$ exist & not unique$x_r=(A^\top A)^{-1}A^\top b=A^+b$$x_r=A^\top(AA^\top)^{-1}b=A^+b$
II.$b\notin\mathcal{R}(A)$
1.$\mathcal{N}(A)={0}$$x$ not exists, $x_r$ exist & is unique$x_r=(A^\top A)^{-1}A^\top b=A^+b$$x_r=A^\top(AA^\top)^{-1}b=A^+b$
2.$\mathcal{N}(A)\neq{0}$$x$ not exists, $x_r$ not exist$(A^\top A)^{-1}$ invertible$(AA^\top)^{-1}$ invertible
  • $A^+=(A^\top A)^{-1}A^\top$ is left pseudo-inverse, $A^+=A^\top (AA^\top)^{-1}$ is right pseudo-inverse.
  • $A^+$ can be unified by the name Moore-Penrose Inverse and calculated using SVD by $A^+=V\Sigma^+ U^\top$ where $\Sigma^+$ take inverse of non-zeros.

Miscellaneous

Selected theorems and lemmas useful in Linear Algebra. For more matrix properties see my post about Matrix Algebra

  • Matrix Square Root: $N^\top N=P$, then $N$ is the square root of $P$

    Square root is not unique. Cholesky decomposition is often used as square root.

  • Schur Complement: Given matrices $A_{n\times n}, B_{n\times m}, C_{m\times m}$, the matrix $M=\begin{bmatrix}A&B\\ B^\top&C\end{bmatrix}$ is symmetric. Then the following are equivalent (TFAE)
    1. $M\succ 0$
    2. $A\succ 0$ and $C-B^\top A^{-1}B\succ 0$ (LHS called Schur complement of $A$ in $M$)
    3. $C\succ 0$ and $A-B C^{-1}B^\top\succ 0$ (LHS called Schur complement of $C$ in $M$)
  • Matrix Inverse Lemma: $(A+BCD)^{-1}=A^{-1}-A^{-1}B\left(C^{-1}+DA^{-1}B\right)^{-1}DA$
  • Properties of $A^\top A$
    • $A^\top A \succeq 0$ and $A^\top A \succ 0 \Leftrightarrow A$ has full rank.
    • $A^\top A$ and $AA^\top$ have same non-zero eigenvalues, but different eigenvectors.
    • If $v$ is eigenvector of $A^\top A$ about $\lambda$, then $Av$ is eigenvector of $AA^\top$ about $\lambda$.
    • If $v$ is eigenvector of $AA^\top$ about $\lambda$, then $A^\top v$ is eigenvector of $A^\top A$ about $\lambda$.
    • $tr(A^\top A)=tr(AA^\top)=\sum_i\sum_j\left|A_{ij}\right|^2$
    • $det(A)=\prod_i\lambda_i, tr(A)=\sum_i\lambda_i$

Real Analysis

Set theory

$\text{~}S$ stands for complement of set $S$ in following contents. These concepts are discussed under normed space $(\mathcal{X}, \Vert\cdot\Vert)$

  • Open Ball: Let $x_0\in\mathcal{X}$ and let $a\in\mathbb{R}, a>0$, then the open ball of radius $a$ about $x_0$ is $B_a(x_0)=\left\{x\in\mathcal{X}\middle| \Vert x-x_0\Vert < a\right\}$
    • Given subset $S\subset \mathcal{X}$, $d(x,S)=0\Leftrightarrow \forall\epsilon >0, B_\epsilon(x)\cap S\neq\emptyset$
    • Given subset $S\subset \mathcal{X}$, $d(x,S)>0\Leftrightarrow \exists\epsilon >0, B_\epsilon(x)\cap S=\emptyset$
  • Interior Point: Given subset $S\subset\mathcal{X}$, $x\in S$ is an interior point of $S$ iff $\exists\epsilon >0, B_\epsilon(x)\subset S$
    • Interior: $\mathring{S}=\{x\in \mathcal{X}|x\text{ is an interior point of }S\}=\{x\in\mathcal{X}|d(x,\text{~}S)>0\}$
  • Open Set: $S$ is open if $\mathring{S}=S$
  • Closure Point: Given subset $S\subset\mathcal{X}$, $x\in S$ is a closure point of $S$ iff $\forall\epsilon >0, B_\epsilon(x)\cap S\neq\emptyset$.
    • Closure: $\bar{S}=\{x\in\mathcal{X}|x\text{ is a closure point of }S\}=\{x\in\mathcal{X}|d(x,S)=0\}$

      Note that $\partial\mathcal{X}=\emptyset$

  • Closed Set: $S$ is closed if $\bar{S}=S$

    $S$ is open $\Leftrightarrow$ $\text{~}S$ is closed, $S$ is closed $\Leftrightarrow$ $\text{~}S$ is open. Set being both open and closed is called clopen(e.g. the whole set $\mathcal{X}$), empty set is clopen by convention.

  • Set Boundary: $\partial S=\bar{S}\cap\overline{\text{~}S}=\bar{S}\backslash\mathring{S}$

Sequences

  • Sequence($\{x_n\}$): a set of vectors indexed by the counting numbers
    • Subsequence: Let $1\leqslant n_1< n_2<\ldots$ be an infinite set of increasing integers, then $\{x_{n_i}\}$ is a subsequence of $\{x_n\}$
  • Convergence($\{x_n\}\rightarrow x\in\mathcal{X}$): $\forall \epsilon>0,\exists N(\epsilon)<\infty\text{ s.t. }\forall n\geqslant N, \Vert x_n-x\Vert <\epsilon$
    • If $x_n \rightarrow x$ and $x_n \rightarrow y$, then $x=y$
    • If $x_n \rightarrow x_0$ and $\{x_{n_i}\}$ is a subsequence of $\{x_n\}$, then $\{x_{n_i}\} \rightarrow x_0$
    • Cauchy Convergence (necessary condition for convergence): $\{x_n\}$ is cauchy if $\forall \epsilon>0,\exists N(\epsilon)<\infty$ s.t. $\forall n,m\geqslant N, \Vert x_n-x_m\Vert <\epsilon$
    • If $\mathcal{X}$ is finite dimensional, $\{x_n\}$ is cauchy $\Rightarrow$ $\{x_n\}$ has a limit in $\mathcal{X}$
  • Limit Point: Given subset $S\subset\mathcal{X}$, $x$ is a limit point of $S$ if $\exists \{x_n\}$ s.t. $\forall n\geqslant 1, x_n\in S$ and $x_n\rightarrow x$
    • $x$ is a limit point of $S$ iff $x\in\bar{S}$
    • $S$ is closed iff $S$ contains its limit points
  • Complete Space: a normed space is complete if every Cauchy sequence has a limit. A complete normed space $(\mathcal{X}, \Vert\cdot\Vert)$ is called a Banach space.
    • $S\subset \mathcal{X}$ is complete if every Cauchy sequence with elements from $S$ has a limit in $S$
    • $S\subset \mathcal{X}$ is complete $\Rightarrow S$ is closed
    • $\mathcal{X}$ is complete and $S\subset\mathcal{X} \Rightarrow S$ is complete
    • All finite dimensional subspaces of $X$ are complete
  • Completion of Normed Space: $\mathcal{Y}=\bar{\mathcal{X}}=\mathcal{X}+\{$all limit points of Cauchy sequences in $\mathcal{X}\}$

    E.g. $C[a,b]$ contains continuous functions over $[a,b]$. $(C[a,b], \Vert\cdot\Vert_1)$ is not complete, $(C[a,b], \Vert\cdot\Vert_\infty)$ is complete. Completion of $(C[a,b], \Vert\cdot\Vert_1)$ requires Lebesque integration.

  • Contraction Mapping: Let $S\subset\mathcal{X}$ be a subset and $T:S\rightarrow S$ is a contraction mapping if $\exists 0\leqslant c\leqslant 1$ such that, $\forall x,y \in S, \Vert T(x)-T(y)\Vert\leqslant c\Vert x-y\Vert$
    • Fixed Point: $x^* \in\mathcal{X}$ is a fixed point of $T$ if $T(x^ *)=x^ *$
    • Contraction Mapping Theorem(不动点定理): If $T:S\rightarrow S$ is a contraction mapping in a complete subset $S$, then $\exists! x^ *\in\mathcal{X}\text{ s.t. }T(x^ *)=x^ *$. Moreover, $\forall x_0\in S$, the sequence $x_{k+1}=T(x_k),k\geqslant 0$ is Cauchy and converges to $x^ *$.

      E.g. Newton Method: $x_{k+1}=x_k-\epsilon\left[\frac{\partial h}{\partial x}(x_k)\right]^{-1}\left(h(x_k)-y\right)$

Continuity and Compactness

  • Continuous: Let $(\mathcal{X},\Vert\cdot\Vert_\mathcal{X})$ and $(\mathcal{Y},\Vert\cdot\Vert_\mathcal{Y})$ be two normed spaces. A function $f:\mathcal{X}\rightarrow\mathcal{Y}$ is continuous at $x_0\in\mathcal{X}$ if $\forall\epsilon >0,\exists \delta(\epsilon,x_0)>0\text{ s.t. }\Vert x-x_0\Vert_\mathcal{X}<\delta \Rightarrow\Vert f(x)-f(x_0)\Vert_\mathcal{Y} <\epsilon$
    • $f$ is continuous on $S\subset\mathcal{X}$ if $f$ is continuous at $\forall x_0\in S$
    • If $f$ in continuous at $x_0$ and $\{x_n\}$ is a sequence s.t. $x_n\rightarrow x_0$, then the sequence $\{f(x_n)\}$ in $\mathcal{Y}$ converges to $f(x_0)$
    • If $f$ is discontinuous at $x_0$, then $\exists \{x_n\}\in\mathcal{X}$ s.t. $x_n\rightarrow x_0$ but $f(x_n)\nrightarrow f(x_0)$
  • Compact: $S\subset\mathcal{X}$ is (sequentially) compact if every sequence in $S$ has a convergent subsequence with limit in $S$
  • Bounded: $S\subset\mathcal{S}$ is bounded if $\exists r<\infty$ such that $S\subset B_r(0)$
    • $S$ is compact $\Rightarrow$ $S$ is closed and bounded
    • Bolzano-Weierstrass Theorem: In a finite-dimensional normed space, $C$ is closed and bounded $\Leftrightarrow$ for $C$ is compact
  • Weierstrass Theorem: If $C\subset\mathcal{X}$ is a compact subset and $f:C\rightarrow\mathbb{R}$ is continuous at each point of $C$, then $f$ achieves its extreme values, i.e. $\exists \bar{x}\in C\text{ s.t. }f(\bar{x})=\sup_{x\in C} f(x)$ and $\exists \underline{x}\in C\text{ s.t. }f(\underline{x})=\inf_{x\in C} f(x)$
    • $f:C\rightarrow\mathbb{R}$ continuous and $C$ compact $\Rightarrow$ $\sup_{x\in C}f(x)<\infty$
Treat me some coffee XD