Linear Algebra

Vector Spaces¶

Subspace¶

Definition: skip due to complication

That's say a vector space $V = Span {v_{1}, v_{2}, v_{3}}$ ,

then the subspace $H = Span {v_{1}, v_{2}}, Span {v_{2}, v_{3}}, \dots$

Thus it's intuitive that subspace $H$ have the property: ${0} \in H$

Null Space¶

Definition
for homogeneous equation

\begin{matrix} Ax = 0 \\ Nul A = {x | x \in R^{n} \cap Ax = 0} \end{matrix}

example

\begin{matrix} A = [\begin{matrix} 1 & - 3 & - 2 \\ - 5 & 9 & - 1 \end{matrix}] u = [\begin{matrix} 5 \\ 3 \\ - 2 \end{matrix}] \\ Au = [\begin{matrix} 1 & - 3 & - 2 \\ - 5 & 9 & - 1 \end{matrix}] [\begin{matrix} 5 \\ 3 \\ - 2 \end{matrix}] = [\begin{matrix} 0 \\ 0 \end{matrix}] \end{matrix}

Thus $u$ is in $Nul A$ .

Properties¶

$Nul A$ is namely the solution space of $x$
for the matrix $A_{m \times n}$ , $Nul A$ is a subspace of $ℝ^{n}$
since $Ax = 0$ , thus $x$ can be written as

\begin{matrix} x = [\begin{matrix} x_{1} \\ x_{2} \\ ⋮ \\ x_{n} \end{matrix}] \end{matrix}

so this property is intuitive.

Column Space¶

Definition: For an $m \times n$ matrix $A = [a_{1}, a_{2}, \dots, a_{n}]$

\begin{matrix} Col A = Span {a_{1}, a_{2}, \dots, a_{n}} \\ a_{i} \in ℝ^{m} \end{matrix}

or equivalently,

\begin{matrix} Col A = {Ax | x \in ℝ^{n}} \end{matrix}

Properties¶

$Col A$ is a subspace of $ℝ^{m}$
range of linear transform $Ax$
$rank A = dim (Col A)$
$rank A + dim (Nul A) = n$
this is quite intuitive since when we lost $1$ dimension in $Col A$ , we got $1$ dimension in solution space.
e.g. $3$ equations in $ℝ^{3}$ can yield an unique solution. However, $2$ equations can only yield a line (i.e. one dimension) at most.

Characteristic Equation¶

Eigenvector & Eigenvalue¶

Definition

\begin{matrix} Ax = λ x \\ ⇕ \\ (A - λ I) x = 0 \end{matrix}

$n \times n$ matrix $A$ , with the eigenvector $x$ and eigenvalue $λ$ .

note:

$0$ cannot be an eigenvector (since it is trivial and by definition)
0 can be an eigenvalue.

Orthogonality¶

Orthogonal Complements¶

A vector $x$ is in $W^{⊥}$ iff $x$ is orthogonal to every vector in $W$
$(Row A)^{⊥} = Nul A$
$(Col A)^{⊥} = Nul A^{T}$

Orthogonal Projection¶

Given a vector $y$ and a subspace $W$ in $ℝ^{n}$

\begin{aligned} y & = c_{1} u_{1} + c_{2} u_{2} + \dots + c_{n} u_{n} \\ = [\begin{array}{c} u_{1} & u_{2} & \dots & u_{n} \end{array}] [\begin{array}{c} c_{1} \\ c_{2} \\ ⋮ \\ c_{n} \end{array}] \end{aligned}

Let's say $W = Span {u_{1}, u_{2}, \dots, u_{p}}$ ( $p \leq n$ )

then the orthogonal projection of $y$ onto $W$ , $\hat{y}$ (aka ${proj}_{W} y$ )

\begin{matrix} \hat{y} = \frac{y \cdot u_{1}}{| | u_{1} | |^{2}} u_{1} + \frac{y \cdot u_{2}}{| | u_{2} | |^{2}} u_{2} + \dots + \frac{y \cdot u_{p}}{| | u_{p} | |^{2}} u_{p} \end{matrix}

assume ${u_{1}, u_{2}, \dots, u_{p}}$ is an orthonormal basic. we can thus further write

\begin{aligned} \hat{y} & = \frac{y \cdot u_{1}}{| | u_{1} | |^{2}} u_{1} + \frac{y \cdot u_{2}}{| | u_{2} | |^{2}} u_{2} + \dots + \frac{y \cdot u_{p}}{| | u_{p} | |^{2}} u_{p} \\ = (y \cdot u_{1}) u_{1} + (y \cdot u_{2}) u_{2} + (y \cdot u_{p}) u_{p} \\ = [\begin{array}{c} u_{1} & u_{2} & \dots & u_{p} \end{array}] [\begin{array}{c} y \cdot u_{1} \\ y \cdot u_{2} \\ ⋮ \\ y \cdot u_{p} \end{array}] \\ = [\begin{array}{c} u_{1} & u_{2} & \dots & u_{p} \end{array}] [\begin{array}{c} u_{1}^{T} \\ u_{2}^{T} \\ ⋮ \\ u_{p}^{T} \end{array}] y \\ = {UU}^{T} y \end{aligned}

Thus, we can conclude that for an $n \times p$ matrix $U$ which consists of $W$ which is $p$ -dimension subspace of $ℝ^{n}$ , there is ${UU}^{T}$ that project $y \in ℝ^{n}$ onto $W$ .

\begin{matrix} {UU}^{T} y = {proj}_{W} y \end{matrix}

Diagonalization¶

Diagonal Matrix¶

$D$ is said to be a diagonal matrix if $D$ has the form

\begin{matrix} D = [\begin{matrix} a & 0 & 0 & \dots \\ 0 & b & 0 & \dots \\ 0 & 0 & c & \dots \\ ⋮ & ⋮ & ⋮ & ⋱ \end{matrix}] \end{matrix}

thus $D$ has the property

\begin{matrix} D^{n} = [\begin{matrix} a^{n} & 0 & 0 & \dots \\ 0 & b^{n} & 0 & \dots \\ 0 & 0 & c^{n} & \dots \\ ⋮ & ⋮ & ⋮ & ⋱ \end{matrix}] \end{matrix}

Diagonalization¶

Square matrix $A$ is said to be diagonalizable if

$A = {PDP}^{- 1}$
in which $D$ is diagonal matrix
$P$ is invertible matrix.

The Diagonalization Theorem¶

An $n \times n$ matrix $A$ is diagonalizable iff $A$ has $n$ eigenvectors and eigenvalues(may be multiple roots).

Easy Proof

Let's say an invertiable matrix $P_{n \times n}$ and diagnol matrix $D$

\begin{matrix} P = [v_{1}, v_{2}, \dots, v_{n}] D = [\begin{matrix} λ_{1} & 0 \\ 0 & λ_{2} \\ ⋱ \\ λ_{n} \end{matrix}] \\ AP = [{Av}_{1}, {Av}_{2}, \dots] \\ PD = [v_{1}, v_{2}, \dots, v_{n}] [\begin{matrix} λ_{1} & 0 \\ 0 & λ_{2} \\ ⋱ \\ λ_{n} \end{matrix}] = [λ_{1} v_{1}, λ_{2} v_{2}, \dots] \end{matrix}

by the definition of characteristic equation

\begin{matrix} AP = PD \\ ⟹ A = {PDP}^{- 1} \end{matrix}

Orthogonally Diagonalizable¶

Definition
A matrix is said to be orthogonally diagonalizable if

\begin{matrix} A = {PDP}^{T} = {PDP}^{- 1} \\ ⇕ \\ A^{T} = P^{TT} D^{T} P^{T} = {PDP}^{T} = A \end{matrix}

And iff $A$ is a symmetric matrix.

SVD¶

Singular Value Diagonalization

Singular Values¶

Let $A$ be an $m \times n$ matrix. Then

\begin{matrix} (A^{T} A)^{T} = A^{T} A^{TT} = A^{T} A \end{matrix}

Thus, $A^{T} A$ is symmetric and orthogonally diagonalizable.

Then, Let say ${v_{1}, v_{2}, \dots, v_{n}}$ be an orthonormal basic for $ℝ^{n}$ consisting of eigenvectors of $A^{T} A$

And also, say $λ_{1}, λ_{2}, \dots$ be the eigenvalues of $A^{T} A$
(make $λ_{1} \geq λ_{2} \geq \dots \geq λ_{n} \geq 0$ )

The singular values $σ_{i}$ of $A$ are

\begin{matrix} σ_{i} = \sqrt{λ_{i}} \end{matrix}

Thinking

collapse: none

Singular values are the "eigenvalues" of non-square matrix $A$ .

Properties¶

${{Av}_{1}, {Av}_{2}, \dots, {Av}_{n}}$ is an orthogonal set.
for any $i \neq j$ , $({Av}_{i})^{T} ({Av}_{j}) = v_{i} A^{T} {Av}_{j} = v_{i} λ_{j} v_{j} = 0$
${{Av}_{1}, {Av}_{2}, \dots, {Av}_{r}}$ is an orthogonal basic of $Col A$ . $⟺ rank A = dim Col A = r$
say $y = Ax$ in $Col A$ , then

\begin{matrix} \begin{aligned} x & = c_{1} v_{1} + c_{2} v_{2} + \dots + c_{r} v_{r} + \dots + c_{n} v_{n} \\ = c_{1}^{'} v_{1} + c_{2}^{'} v_{2} + \dots + c_{r}^{'} v_{r} \end{aligned} \\ ⇓ \\ \begin{aligned} y & = Ax \\ = c_{1}^{'} {Av}_{1} + c_{2}^{'} {Av}_{2} + \dots + c_{r}^{'} {Av}_{r} \end{aligned} \end{matrix}

Singular Value Decomposition¶

$m \times n$ "diagonal" matrix

\begin{matrix} Σ_{m \times n} = [\begin{matrix} D_{r \times r} & 0_{r \times (n - r)} \\ 0_{(m - r) \times r} & 0_{(m - r) \times (n - r)} \end{matrix}] \end{matrix}

e.g. $A_{2 \times 3}$ with $r = 2$

\begin{matrix} Σ = [\begin{matrix} σ_{1} & 0 & 0 \\ 0 & σ_{2} & 0 \end{matrix}] \end{matrix}

singular value decomposition

\begin{matrix} A_{m \times n} = U_{m \times m} Σ_{m \times n} {V_{n \times n}}^{T} \end{matrix}

Left singular vectors of $A$ : The columns of $U$
Right singular vectors of $A$ : The columns of $V$

Easy Proof

First following the property 2. of singular value, we can obtain an orthonormal basic ${u_{1}, u_{2}, \dots, u_{r}}$ by

\begin{matrix} u_{i} = \frac{{Av}_{i}}{| | {Av}_{i} | |} = \frac{{Av}_{i}}{σ_{i}} \end{matrix}

then

\begin{matrix} \begin{aligned} U Σ & = [\begin{array}{c} u_{1} & u_{2} & \dots & u_{m} \end{array}] {[\begin{array}{c} σ_{1} & 0 & \dots \\ 0 & σ_{2} & \dots \\ ⋱ \end{array}]}_{m \times n} \\ = [\begin{array}{c} σ_{1} u_{1} & σ_{2} u_{2} & \dots & σ_{r} u_{r} & 0 & \dots & 0 \end{array}] \\ AV & = [\begin{array}{c} {Av}_{1} & {Av}_{2} & \dots & {Av}_{n} \end{array}] \\ = [\begin{array}{c} σ_{1} u_{1} & σ_{2} u_{2} & \dots & σ_{r} u_{r} & 0 & \dots & 0 \end{array}] \end{aligned} \\ ⟹ U Σ = AV ⟹ U Σ V^{T} = A \end{matrix}

Least-Squares Solution¶

Target
for $m \times n$ matrix $A$

\begin{matrix} A = [\begin{matrix} a_{1} & a_{2} & \dots & a_{n} \end{matrix}] \\ Ax = b \end{matrix}

say $b$ is a linear combination of columns of $A$ for solution $x$ .

Most of times we cannot find the perfect solution. Thus, we try to find the Least-Squares solution $\hat{x}$ .

Find

\begin{matrix} \hat{x} = \underset{\hat{x}}{\arg min} {| | b - A \hat{x} | |}^{2} \end{matrix}

First, let define

\begin{matrix} p = A \hat{x} \in Col A \end{matrix}

We know that the least-square root happens at $(b - p)$ orthogonal to $p$ .

Thus say the projection matrix $P$ s.t.

P b = p

Back to the condition $(b - p) \cdot p = 0$ . That is

\begin{aligned} p & \in Col A \\ (a) & (b - p) & \in (Col A)^{⊥} = Nul A^{T} \end{aligned}

from the definition of null space and equation $a$ , we have

\begin{matrix} A^{T} (b - p) = 0 \\ ⟹ A^{T} (b - A \hat{x}) = 0 \\ ⟹ A^{T} A \hat{x} = A^{T} b \\ ⟹ \hat{x} = (A^{T} A)^{- 1} A^{T} b \end{matrix}

Besides, we now further have

\begin{matrix} (b) & p = A \hat{x} = A (A^{T} A)^{- 1} A^{T} b \\ P = A (A^{T} A)^{- 1} A^{T} \end{matrix}

Pseudoinverse Aspect¶

\begin{matrix} A \hat{x} = b \\ ⟹ \hat{x} = A^{†} b \\ (c) & ⟹ p = A \hat{x} = {AA}^{†} b \end{matrix}

compare equation $b$ and $c$

\begin{aligned} p & = A \hat{x} = {AA}^{†} b \\ = (U_{r} D V_{r}^{T}) (V_{r} D^{- 1} U_{r}^{T}) b \\ = U_{r} U_{r}^{T} b \end{aligned}

by theorem of Orthogonal Projection, we know that

\begin{matrix} P = {AA}^{†} = U_{r} U_{r}^{T} \end{matrix}