Linear Algebra Note

Euclidean Vector
Definition

Geometric object that has magnitude and direction

Elements of a Vector Space

Properties

Length

Vector

Real

Let $x \in R^{n}$ be an $n$ -dimensional vector, then the $L_{p}$ norm of the $x$ is defined as $∥ x ∥_{p} := (\sum_{i = 1}^{n} ∣ x_{i} ∣^{p})^{1/ p}$

Complex

Let $x \in C^{n}$ be an $n$ -dimensional complex vector, then the $L_{1}$ norm of the $x$ is defined as $∥ x ∥ = x^{†} x = \sum_{i = 1}^{n} \overset{x}{ˉ}_{i} x_{i}$
Link to original

Addition and Subtraction

for $x \in R^{n}, y \in R^{n}$ $x \pm y = [x_{1} \pm y_{2}, x_{2} \pm y_{2}, \dots, x_{n} \pm y_{n}]^{⊺}$

Distance

for $x \in R^{n}, y \in R^{n}$ $∣∣ x - y ∣∣ = ∣∣ y - x ∣∣ = \sum_{i = 1}^{n} (x_{i} - y_{i})^{2}$

Scalar Multiplication

for $x \in R^{n}$ $k x = [k x_{1}, k x_{2}, \dots, k x_{n}]^{⊺}$

Inner Product

Vector

Real

for $x, y \in R^{n}$ $⟨ x, y ⟩ = ∣∣ x ∣ \cdot ∣∣ y ∣∣ cos θ = \sum_{i = 1}^{n} x_{i} y_{i}$ where $∣∣ \cdot ∣∣$ is a Norm

Complex

for $x, y \in C^{n}$ $⟨ x, y ⟩ = x \overline{y} = \sum_{i = 1}^{n} x_{i} \overset{y}{ˉ}_{i}$
Link to original

Vector Product

Cross Product
Definition

$v \times w = ∣∣ v ∣∣∣∣ w ∣∣ sin (θ) n = (v_{2} w_{2} v_{3} w_{3}, - v_{1} w_{1} v_{3} w_{3}, v_{1} w_{1} v_{2} w_{2}) = [(v_{2} w_{3} - v_{3} w_{2}), (v_{3} w_{1} - v_{1} w_{3}), (v_{1} w_{2} - v_{2} w_{1})] = det i j k v_{1} v_{2} v_{3} w_{1} w_{2} w_{3}$ where the $v, w \in R^{3}$ , the $θ$ is the angle between $v$ and $w$ , and the $n$ is a unit vector perpendicular to the both $v$ and $w$ .

Facts

$u \times v = - (v \times u)$

$u \times (v + w) = (u \times v) + (u \times w)$ $u \times (v - w) = (u \times v) - (u \times w)$

$(u + v) \times w = (u \times w) + (v \times w)$

$k (u \times v) = (k u) \times v = u \times (k v)$

$u \times 0 = 0 \times u = 0$

$u \times u = 0$

Link to original
Link to original

Matrix
Definition

$A_{m \times n} = a_{11} ⋮ a_{m 1} \dots ⋱ \dots a_{1 n} ⋮ a_{mn}$

Operations

Addition, Subtraction

$A_{m \times n} \pm B_{m \times n} = a_{11} \pm b_{11} ⋮ a_{m 1} \pm b_{m 1} \dots ⋱ \dots a_{1 n} \pm b_{1 n} ⋮ a_{mn} \pm b_{mn}$

Scalar Multiplication

$k A_{m \times n} = k a_{11} ⋮ k a_{m 1} \dots ⋱ \dots k a_{1 n} ⋮ k a_{mn}$

Transpose

$A^{⊺}$ $a_{ij} \to ⊺ a_{ji}$ , $A_{m \times n} \to ⊤ A_{n \times m}$

Trace

Determinant

Matrix Multiplication

$A_{m \times p} \cdot B_{p \times n} = a_{11} ⋮ a_{m 1} \dots ⋱ \dots a_{1 p} ⋮ a_{m p} b_{11} ⋮ b_{p 1} \dots ⋱ \dots b_{1 n} ⋮ b_{p n} = a_{11} + b_{11} + \dots + a_{1 p} + b_{p 1} ⋮ a_{m 1} + b_{11} + \dots + a_{m p} + b_{p 1} \dots ⋱ \dots a_{11} + b_{1 n} + \dots + a_{1 p} + b_{p n} ⋮ a_{m 1} + b_{1 n} + \dots + a_{m p} + b_{p n}_{m \times n}$ $A_{i}^{⊺} \cdot B_{j} = \sum_{k = 1}^{p} a_{ik} \cdot b_{kj} = c_{ij}$ where $1 \leq i \leq m$ , $1 \leq j \leq n$

Vector-Matrix Multiplication

$A x = [A_{1}, A_{2}, \dots, A_{n}] [x_{1}, x_{2}, \dots, x_{n}]^{⊺} = x_{1} A_{1} + x_{2} A_{2} + \dots + x_{n} A_{n} = \sum_{k = 1}^{n} x_{k} A_{k}$
Link to original

Gauss Elimination
Definition

An algorithm for solving systems of linear equations. Transform a matrix to an upper triangular matrix using the elementary row operations.

Elementary Row Operations

Swapping two rows

Multiplying a row by a non-zero scalar

Adding a multiple of one row to another row

Examples

$1133111 1 - 1 5 ∣ ∣ ∣ 9135 \to r_{2} = r_{2} - r_{1} 100 3 - 2 2 1 - 2 2 ∣ ∣ ∣ 9 - 8 8 \to r_{3} = r_{3} + r_{2} 100 3 - 2 0 1 - 2 0 ∣ ∣ ∣ 9 - 8 0 \to r_{2} = - \frac{1}{2} r_{2} 100010 - 2 10 ∣ ∣ ∣ - 3 40$
Link to original

LU Decomposition
Definiiton

$A = E^{- 1} U = LU$ where $E$ is the lower triangular matrix of Gauss Elimination^[History of G.E] and $U$ is the result upper triangular matrix of Gauss Elimination^[Result of G.E].
Link to original

Cofactor
Definition

$C_{i, j} = (- 1)^{i + j} M_{i, j}$ where $M_{i, j}$ is the Minor.
Link to original

Adjugate Matrix
Definition

$adj (A) = C^{⊺}$ where $C$ is a Cofactor matrix

Facts

$A adj (A) = adj (A) A = det (A) I$

$adj (A) = det (A) A^{- 1}$

$A^{- 1} = det (A)^{- 1} adj (A)$

Link to original

Determinant
Definition

$det (A) = ∣ A ∣$

Computation

$2 \times 2$ matrix

$a c b d = a d - b c$

$n \times n$ matrix

Laplace Expansion
Definition

Let $C$ be a cofactor matrix of $A$

Along the $j$ th column gives

$det (A) = \sum_{i = 1}^{n} a_{ij} C_{ij} = \sum_{i = 1}^{n} a_{ij} (- 1)^{i + j} M_{i, j}$

Along the $i$ th row gives

$det (A) = \sum_{j = 1}^{n} a_{ij} C_{ij} = \sum_{j = 1}^{n} a_{ij} (- 1)^{i + j} M_{i, j}$
Link to original

Facts

$det A \neq = 0 \Leftrightarrow \exists A^{- 1}$ $det A = 0 \Leftrightarrow ∄ A^{- 1}$

The volume of box^[parallelepiped] $\in R^{n}$ is expressed by a determinant

$det (I) = 1$

$det (A)$ changes sign, when two rows are exchanged (permutated)

$det (A)$ depends on linearly on the 1st row.

$det (t A) = t^{n} det (A)$

$det (AB) = det (A) det (B)$

If two row or column vectors in $A$ are equal, then $det (A) = 0$

Gauss Elimination does not change $det (A)$

If a matrix $A$ has zero row or column vectors, then $det (A) = 0$

If a matrix $A$ is diagonal or triangular, then the determinant of $A$ is the product of diagonal elements $det (A) = \prod_{i = 1}^{n} a_{ii}$ where $a_{ii}$ is the $i, i$ element of the matrix $A$ .

$det (A^{- 1}) = det (A)^{- 1}$

$det (A^{⊺}) = det (A)$

$∣ A ∣ = \prod_{i = 1}^{n} λ_{i}$ The Determinant of the matrix is equal to the product of the eigenvalues of the matrix.

Link to original

$∣ I_{m} + A B ∣ = ∣ I_{n} + B A ∣$ where the dimensions of the matrices are $m \times n$ and $n \times m$ respectively.

$∣ A \pm u u^{⊺} ∣ = ∣ A ∣ (1 \pm u^{⊺} A^{- 1} u)$

Link to original

Cramer's Rule
Definition

The solution of a Linear System Equation. It expresses the solution in terms of the determinants.

For the system of linear equations $Ax = b$ , the elements of the column vector $x$ , $x_{i}$ are given by $x_{i} = \frac{det ( A _{i} )}{det ( A )}$ where $A_{i} = [a_{1}, a_{2}, \dots, a_{i - 1}, b, a_{i + 1}, \dots]$ is the matrix formed by replacing $i$ -th column of $A$ by the column vector $b$ .
Link to original

Inverse Matrix
Definition

$A^{- 1}$ satisfies $A A^{- 1} = A^{- 1} A = I$ for given matrix $A$

Computation

2 x 2 matrix

$A^{- 1} = \frac{1}{∣ A ∣} [d - c - b a]$ where the matrix $A = [a c b d]$ , and $∣ A ∣$ is a Determinant of the matrix

Using Cofactor

$A adj (A) = AC^{⊺} = det (A) I$ where the matrix $C = C_{11} C_{21} ⋮ C_{n 1} C_{12} C_{22} ⋮ C_{n 2} \dots \dots ⋱ \dots C_{1 n} C_{2 n} ⋮ C_{nn}$ is the cofactor matrix, which is formed by all the cofactors of a given matrix $A$ . Then, by the definition of inverse matrix, $A^{- 1} = \frac{1}{det ( A )} C^{⊺}$
Link to original

Vector Space
Definition

$(V, F, +, \cdot)$ or $V$ is a vector space over $F$ .

A Module whose set of scalar is a Field. $(V, +)$ is an Abelian Group scalar multiplication $\cdot$ is a Monoid action of $(F, \cdot)$ on $V$ the scalar multiplication is distributive with both vector and scalar addition

Vector

Where we call the element of vector space $v \in V$ a Vector

Dimension

Dimension (Vector Space)
Definition

$dim (V)$ where $V$ is a Vector Space

The number of vectors in a basis for the Vector Space
Link to original

Conditions for Vector Space

Let $x, y \in V$

$x + y \in V$

$k x \in V$

$0 \in V$ where $o$ is the origin.

$\Rightarrow \sum_{i = 1}^{n} k_{i} x \in V$ (Linear Combination of Vectors)
Link to original

Linear Independence
Definition

Let $y_{1}, y_{2}, \dots, y_{n}$ be $n$ vectors or functions

Linearly independent

If $i = 1 \sum n k_{i} y_{i} = 0 \Rightarrow k_{1} = k_{2} = \dots = k_{n} = 0$ ,
then ${y_{i} ∣ i = 1, 2, \dots, n}$ is linearly independent.

$y_{n}$ can’t be expressed using the others

Linearly dependent

If $\exists k_{1}, k_{2}, \dots, k_{n}$ , not all zero, s.t. $i = 1 \sum n k_{i} y_{i} = 0$ ,
then ${y_{i} ∣ i = 1, 2, \dots, n}$ is linearly dependent.

Facts

Basis(solutions of the ODE) = linearly independent solutions

Mutually orthogonal $y_{i} ⊥ y_{j} (i \neq = j)$ vectors $y_{1}, y_{2}, \dots, y_{n}$ are linearly independent

Check of linear independence of a set of vectors

make a matrix using the given column vectors

apply Gauss Elimination to make an upper triangular or Echelon matrix

check the number of non-zero pivots

Link to original

Basis (Linear Algebra)
Definition

Basis

A linearly independent subset of Vector Space $V$ that spans $V$

Basis Vector

The elements of a basis

Facts

Basis vectors are not unique for a Vector Space

Basis vectors are changed by Gauss Elimination

Link to original

Dimension (Vector Space)
Definition

$dim (V)$ where $V$ is a Vector Space

The number of vectors in a basis for the Vector Space
Link to original

Linear Map
Definition

$f : V \to W$

A mapping between two vector spaces that preserves Additivity on a vector addition $(V, +)$ and Homogeneity on a scalar multiplication $(F, \cdot)$ on $V$

Additivity: $f (u + v) = f (u) + f (v)$

Homogeneity: $f (c u) = c f (u)$

Link to original

Fundamental Theorem of Linear Algebra
Definition

Let $L (V, W) := {L : V \to W}$ where $L$ is linear map and define a sum and scalar operation to the $L (V, W)$

$(L_{1} + L_{2}) (v) = L_{1} (v) + L_{2} (v)$

$(k L) (v) = k L (v)$

Where $L \in L (V, W)$ , $v \in V$ , $k \in F$ , and $M_{m \times n}$ is a set of $m \times n$ matrices on $F$

Let the functions $f, g$

$f : L (V, W) \to M_{m \times n} (F)$ $f (L) = [L]_{B_{W}}^{B_{V}} = M$

$g : M_{m \times n} (F) \to L (V, W)$ $g (M) = L_{M}$ where $L_{M}$ satisfies $[L_{M} (v)]_{B_{W}} = M [v]_{B_{V}}$

And terms

$[v]_{B_{V}} := (k_{1}, \dots, k_{n})^{⊺}$ for $v = (k_{1} v_{1} + \dots + k_{n} v_{n}) \in V$

$[L]_{B_{W}}^{B_{V}} := ([L (v_{1})]_{B_{W}}, \dots, [L (v_{n})]_{B_{W}})$

where $L (v) = (l_{1} w_{1} + \dots + l_{n} w_{n}) \in W$ , and $[L (v)]_{B_{W}} = (l_{1}, \dots, l_{n})^{⊺}$ is a column vector. and $B_{V}, B_{W}$ are the ordered basis of $V, W$ respectively

Then, $f, g$ both are Isomomorphism and the inverse maps of each other.

If $T : V \to W$ , then $\exists A$ s.t. $\forall v \in V : T (v) = A v$ Every Linear Map between finite-demensional vector spaces can be represented by a Matrix.

Proof

$f$ is a Linear Map

Proof of Additivity of $f$

$f (L_{1} + L_{2}) = f (L_{1}) + f (L_{2})$

$\forall i \in N^{+}, \forall L_{1}, L_{2} \in L (V, W) : (L_{1} + L_{2}) (v_{i}) = L_{1} (v_{i}) + L_{2} (v_{i})$ by the definition of $L (V, W)$ . So, $[(L_{1} + L_{2}) (v_{i})]_{B_{w}} = [L_{1} (v_{i}) + L_{2} (v_{i})]_{B_{w}} \Rightarrow [(L_{1} + L_{2}) (v_{i})]_{B_{w}} = [L_{1} (v_{i})]_{B_{W}} + [L_{2} (v_{i})]_{B_{W}}$ by the definition of $f (L)$ $\Leftrightarrow [(L_{1} + L_{2}) (v)]_{B_{W}} = [L_{1} (v)]_{B_{W}} + [L_{2} (v)]_{B_{W}}$ $∴ f (L_{1} + L_{2}) = f (L_{1}) + f (L_{2})$

Proof of Homogeneity of $f$

$f (k L) = k f (L)$

$\forall k \in F, \forall i \in N^{+}, L \in L (V, W) : (k L) (v_{i}) = k L (v_{i})$ by the definition of $L (V, W)$ . So, $[(k L) (v_{i})]_{B_{w}} = [k L (v_{i})]_{B_{w}} \Rightarrow [(k L) (v_{i})]_{B_{w}} = k [L (v_{i})]_{B_{w}}$ by the definition of $f (L)$ $\Leftrightarrow [(k L) (v)]_{B_{w}} = k [L (v)]_{B_{w}}$ $∴ f (k L) = k f (L)$

$f$ is a Isomomorphism

Proof of Monomorphism of $f$

$f (L_{1}) = f (L_{2}) \Rightarrow L_{1} = L_{2}$

$\forall i \in N^{+}, \forall L_{1}, L_{2} \in L (V, W) : f (L_{1}) = f (L_{2}) \Leftrightarrow [L_{1} (v_{i})]_{B_{W}} = [L_{2} (v_{i})]_{B_{W}} \Leftrightarrow L_{1} (v_{i}) = L_{1} (v_{i})$ Let ${v_{1}, \dots, v_{n}} = B_{V}$ , then $\forall v \in V : \exists k_{1}, \dots, k_{n} \in F$ s.t. $v = \sum_{i = 1}^{n} k_{i} v_{i}$ Since $L_{1} (v_{i}) = L_{1} (v_{i})$ , $\sum_{i = 1}^{n} k_{i} L_{1} (v_{i}) = \sum_{i = 1}^{n} k_{i} L_{2} (v_{i}) \Leftrightarrow \sum_{i = 1}^{n} L_{1} (k_{i} v_{i}) = \sum_{i = 1}^{n} L_{2} (k_{i} v_{i}) \Leftrightarrow L_{1} (\sum_{i = 1}^{n} k_{i} v_{i}) = L_{2} (\sum_{i = 1}^{n} k_{i} v_{i})$ by the definition of $L (V, W)$ . $∴ L_{1} (v) = L_{2} (v) \Leftrightarrow L_{1} = L = 2$

Proof of Epimorphism of $f$

$f (L) = M$

Let $\forall M \in M_{m \times n} (F) : [M]^{i} := i -th column of M$ , and $\forall i \in N^{+} : [L (v_{i})]_{B_{W}} := [M]^{i}$ Then, $[L (v_{i})]_{B_{W}}^{B_{V}} = M$ $∴ f (L) = M$

$g$ is a Linear Map

Proof of Additivity of $g$

$g (M_{1} + M_{2}) = g (M_{1}) + g (M_{2})$

$\forall M_{1}, M_{2} \in M_{m \times n} (F), \forall v \in V : [L_{M_{1} + M_{2}} (v)]_{B_{W}} = (M_{1} + M_{2}) [v]_{B_{V}}$ by the definition of the operation $g (M)$ $(M_{1} + M_{2}) [v]_{B_{V}} = M_{1} [v]_{B_{V}} + M_{2} [v]_{B_{V}} = [L_{M_{1}} (v)]_{B_{W}} + [L_{M_{2}} (v)]_{B_{W}}$ by the definition of matrix operation $∴ g (M_{1} + M_{2}) = g (M_{1}) + g (M_{2})$

Proof of Homogeneity of $g$

$g (k M) = k g (M)$

$\forall k \in F, \forall M \in M_{m \times n} (F) : [L_{k M} (v)]_{B_{W}} = (k M) [v]_{B_{V}} = k M [v]_{B_{V}} = k [L_{M} (v)]_{B_{W}}$ $∴ g (k M) = k g (M)$

$g$ is a Isomomorphism

Proof of Monomorphism of $g$

$g (M_{1}) = g (M_{2}) \Rightarrow M_{1} = M_{2}$

$\forall M_{1}, M_{2} \in M_{m \times n} (F), \forall v \in V : g (M_{1}) = g (M_{2}) \Leftrightarrow [L_{M_{1}} (v)]_{B_{W}} = [L_{M_{2}} (v)]_{B_{W}} \Leftrightarrow M_{1} [v]_{B_{V}} = M_{2} [v]_{B_{V}} \Leftrightarrow [M_{1}]^{i} = [M_{2}]^{i} \Leftrightarrow M_{1} = M_{2}$ $∴ g (M_{1}) = g (M_{2}) \Rightarrow M_{1} = M_{2}$

Proof of Epimorphism of $g$

$∴ g (M) = L$

Let $\forall L \in L (V, W) : M := ([L (v_{1})]_{B_{W}}, \dots, [L (v_{n})]_{B_{W}})$ Then, $\forall i \in N^{+} : [L (v_{i})]_{B_{W}} := [M]^{i}$ by the definition $∴ g (M) = L_{M} = L$

$f, g$ are the inverse maps of each other.

$\forall L \in L (V, W), \forall v \in V : (g \circ f) (L) = g (f (L)) = g (M) = L_{M} = L \Rightarrow g f = I$

$\forall M \in M_{m \times n} (F) : (f \circ g) (M) = f (g (M)) = f (L_{M}) = f (L) = M \Rightarrow f g = I$
Link to original

Rank–Nullity Theorem
Definition

Linear Transformation

$dim (V) = dim (ker L) + dim (im L)$ where $V$ is a finite-dimensional Vector Space and $L : V \to W$ is a Linear Map

The dimension of vector space $V$ is equal to the sum of the dimension of kernel of $L$ and the dimension of image of $L$ .

Proof

We want to show that ${L (v_{k + 1}), \dots, L (v_{n})}$ is the basis of $im L$ , or $dim (V) = dim (im L)$

Let $B_{V} = {v_{1}, \dots, v_{n}}$ be the basis of Vector Space $V$ , and $B_{ker L} = {v_{1}, \dots, v_{k}}$ where $k \leq n$ be the basis of the $ker L \subset V$

Span

$\forall L (v) \in im L : v = c_{1} v_{1} + c_{2} v_{2} + \dots + c_{k} v_{k} + c_{k + 1} v_{k + 1} + \dots + c_{n} v_{n}$ Since $L (v_{1}) + L (v_{2}) + \dots + L (v_{k}) = 0$ by the definition of $B_{ker L}$ $L (v) = L (c_{k + 1} v_{k + 1} + \dots + c_{n} v_{n}) = c_{k + 1} L (v_{k + 1}) + \dots + c_{n} (v_{n}) \in im L$ $∴ span {L (v_{k + 1}), \dots, (v_{n})} = im L$

Linear Independence

Let $c_{k + 1} L (v_{k + 1}) + \dots + c_{n} L (v_{n}) = 0$ We can transform the equation $c_{k + 1} L (v_{k + 1}) + \dots + c_{n} L (v_{n}) = L (c_{k + 1} v_{k + 1} + \dots + c_{n} v_{n}) = 0$ by the Linearity of $L$ Then, $c_{k + 1} v_{k + 1} + \dots + c_{n} v_{n} \in ker L$

The expression can be expressed using only the basis vectors. So, $\exists c_{1}, \dots, c_{k}, (c_{1} v_{1} + \dots + c_{k} v_{k} = c_{k + 1} v_{k + 1} + \dots + c_{n} v_{n})$ $\Leftrightarrow c_{1} v_{1} + \dots + c_{k} v_{k} - c_{k + 1} v_{k + 1} - \dots - c_{n} v_{n} = 0$ by subtracting LHS - RHS

Since $B_{V} = {v_{1}, \dots, v_{n}}$ is a basis of the vector space, $c_{1} = c_{2} = \dots = c_{n} = 0$ $\Rightarrow c_{k + 1} + \dots + c_{n} = 0$ $∴ {L (v_{k + 1}), \dots, L (v_{n})}$ is linearly independent.

Since ${L (v_{k + 1}), \dots, L (v_{n})}$ satisfies Span and Linear Independence, is the basis of $im L$ $B_{im L} = {L (v_{k + 1}), L (v_{k + 2}), \dots, L (v_{n})}$

Matrices

$n = rank (M) + nullity (M)$ where $M \in M_{m \times n} (F)$

Proof

Let a matrix $A$ be the echelon form of the matrix $M$ , and $rank (M) = r \leq n$ Then, the number of pivots of $A$ is $r$ . Also the number of free variables of $M x = 0$ become $n - r$ $∴ nullity (M) = n - r \Rightarrow rank (M) + nullity (M) = n$

Visualization

$dim (Ker (A)) = 2, dim (Im (A)) = 1$
Link to original

Pigeonhole Principle
Definition

Let $A, B$ be sets and $∣ A ∣ = ∣ B ∣$ , and $f : A \to B$ . Then $f$ is Surjective $\Leftrightarrow$ $f$ is Injective $\Leftrightarrow$ $f$ is Bijective

Lemma

Let $L : V \to W$ be a linear map, and suppose that $dim (V) = dim (W)$ . Then $L$ is Epimorphism $\Leftrightarrow$ $L$ is Monomorphism $\Leftrightarrow$ $L$ is Isomomorphism

Proof

Epimorphism $\Rightarrow$ Monomorphism

Let $dim (V) = dim (W) = n$ If $L$ is Monomorphism $\Rightarrow dim (L (V)) = im (L) = n$ by the definition or Monomorphism $\Rightarrow dim (Ker L) = n - n = 0 \Leftrightarrow Ker L = {0 \in V}$ by the Dimension Theorem So, $\forall v_{1}, v_{2} \in V : L (v_{1}) = L (v_{2}) \Rightarrow L (v_{1}) - L (v_{2}) = 0 \Rightarrow L (v_{1} - v_{2}) = 0 \in W \Rightarrow v_{1} - v_{2} = 0$ by the $Ker L = {0}$ $∴ v_{1} = v_{2}$

Monomorphism $\Rightarrow$ Epimorphism

$dim (Ker L) = 0 \Rightarrow dim (L (V)) = n$ by the Dimension Theorem $L (V) \subset W$ and $dim (L (V)) = dim (W)$ $∴ L (V) = W = im L$

How to prove this statement? Let V be a vector space and W \subset V be given, If dim V = dim W, then V = W
Link to original

Rank Theorem
Definition

$col-rank (M) = row-rank (M)$

The Column Rank and the Row Rank are always equal

Proof

Let a matrix $A$ be the echelon form of the matrix $M$ . Then, $col-rank (M) = col-rank (A)$ and $row-rank (M) = row-rank (A)$ by the property of determinant

Since the number of columns or rows which containing pivots are the column or row rank of $A$ . $col-rank (A) = row-rank (A)$

$\therefore \text{col-rank}(\mathbf{M}) = \text{row-rank}(\mathbf{M})$$
Link to original

Null Space
Definition

$N (A) = ker (f) := {x \in V : f (x) = 0}$

The vector space of $x$ satisfying $Ax = 0$ for the matrix $A$

Facts

$x_{1} + x_{2} \in N (A) \to A (x_{1} + x_{2}) = 0$

$A (k x) = k A (x) = 0$

$A0 = 0$

$\exists A_{n \times n}^{- 1} \Leftrightarrow N (A) = {0}$

$∄ A^{- 1}$ and there exists infinitely many solutions, $\Rightarrow x = x_{n} + x_{p}$ where $x_{n} \in N (A)$

Link to original

Row Space
Definition

$C (A^{⊺}) = \sum_{i = 1}^{n} x_{i} a_{i}$

The span of the column vectors of the transposed matrix

Facts

Row Rank
Definition

$row-rank (A) = dim (C (A^{⊺}))$

A dimension of the Row Space
Link to original
Link to original

Left Null Space
Definition

$N (A^{⊺})$ The vector space of $y$ satisfying $A^{⊺} y = 0$ for the matrix $A$
Link to original

Column Space
Definition

$C (A) = \sum_{i = 1}^{n} x_{i} A_{i}$ where $A = [A_{1}, A_{2}, \dots, A_{n}]$

The span of the column vectors of the matrix

Facts

$A x = b$ is solvable $\Leftrightarrow$ $b$ is in the $C (A)$

$\exists A_{n \times n}^{- 1} \Leftrightarrow C (A) = R^{n}$

non-singular $n \times n$ matrix: $C (A_{n \times n}) = R^{n}$

Column Rank
Definition

$dim (C (A)) = rank (A)$

A dimension of the Column Space
Link to original

$C (A) = C (A^{⊺} A)$

Link to original

Orthonormal Matrix
Definition

$Q^{⊺} Q = Q Q^{⊺} = I and Q^{⊺} = Q^{- 1}$ The matrix whose column and rows are orthonormal vectors.

Examples

Rotation Matrix

Permutation Matrix

Facts

Every orthonormal matrix is Unitary Matrix.

For a vector $y = x_{1} q_{1} + x_{2} q_{2} + \dots + x_{n} q_{n}$ , which can be expressed as a linear combination of column vectors of the orthonormal matrix $Q$ , we can easily find the coefficients $x_{i} = q_{i}^{⊺} y$ of the linear combination using the Inner product. $y = Qx \to Q^{⊺} y = I Q^{⊺} Q x \to Q^{⊺} y = x$

Link to original

Unitary Matrix
Definition

$U^{†} U = U U^{†} = I$ and $U^{†} = U^{- 1}$

Facts

$⟨ Ux, Uy ⟩ = ⟨ x, y ⟩$ Given two complex vectors $x, y$ , multiplication by $U$ preserves their Inner product.

$∣∣ x ∣∣ = ∣∣ Ux ∣∣$ Given a complex vector $x$ , multiplication by $U$ preserves its Norm.

$∣ λ_{i} ∣ = 1$ Every Eigenvalue of $U$ has unit length. Therefore, $∣ U ∣ = \pm 1$

Eigenvectors of $U$ are orthogonal

Proof For the Eigendecomposition $U x_{1} = λ_{1} x_{1}, U x_{2} = λ_{2} x_{2}$ where $λ_{1} \neq = λ_{2}$ , $x_{1}^{†} x_{2} = (U x_{1})^{†} (U x_{2}) = (λ_{1} x_{1})^{†} (λ_{2} x_{2}) = \overset{ˉ}{λ}_{1} λ_{2} x_{1}^{†} x_{2}$ . So, $(1 - \overset{ˉ}{λ}_{1} λ_{2}) x_{1}^{†} x_{2} = 0$ . Since $\overset{ˉ}{λ}_{1} λ_{2} = 1$ only where $λ_{1} = λ_{2}$ , by the assumption $x_{1}^{†} x_{2} = 0$ .

$tr (U^{⊺} A U) = tr (A)$ $∣ U^{⊺} A U ∣ = ∣ A ∣$

Link to original

Gram Schmidt Orthonormalization
Definition

Method for orthogonalizing a set of vectors.

Computation

Given $a_{1}, a_{2}, \dots, a_{n + 1} \in R^{n}$

$a_{1}$ : $A_{1} := a_{1}, q_{1} = \frac{A _{1}}{∣∣ A _{1} ∣∣}$

$a_{2}$ : $A_{2} := (a_{2} - (q_{1}^{⊺} a_{2}) q_{1}) ⊥ q_{1}, q_{2} = \frac{A _{2}}{∣∣ A _{2} ∣∣}$

$a_{3}$ : $A_{3} := (a_{3} - (q_{1}^{⊺} a_{3}) q_{1} - (q_{2}^{⊺} a_{3}) q_{2}) ⊥ q_{1}, q_{2}, q_{3} = \frac{A _{3}}{∣∣ A _{3} ∣∣}$

$a_{k}$ : $A_{k} := (a_{k} - \sum_{i = 1}^{k - 1} (q_{i}^{⊺} a_{k}) q_{i}) ⊥ q_{1}, q_{2}, \dots, q_{k - 1}, q_{k} = \frac{A _{k}}{∣∣ A _{k} ∣∣}$ Where $(q_{i}^{⊺} a_{k}) q_{i}$ means the projection of the vector $a_{k}$ onto the vector space of $A_{i}$ .

Therefore, it can be expressed using $proj_{A_{i}} (a_{k})$

$a_{1}$ : $A_{1} := a_{1}, q_{1} = \frac{A _{1}}{∣∣ A _{1} ∣∣}$

$a_{2}$ : $A_{2} := (a_{2} - proj_{A_{1}} (a_{2})) ⊥ q_{1}, q_{2} = \frac{A _{2}}{∣∣ A _{2} ∣∣}$

$a_{3}$ : $A_{3} := (a_{3} - proj_{A_{1}} (a_{3}) - proj_{A_{2}} (a_{3})) ⊥ q_{1}, q_{2}, q_{3} = \frac{A _{3}}{∣∣ A _{3} ∣∣}$

$a_{k}$ : $A_{k} := (a_{k} - \sum_{i = 1}^{k - 1} proj_{A_{i}} (a_{k})) ⊥ q_{1}, q_{2}, \dots, q_{k - 1}, q_{k} = \frac{A _{k}}{∣∣ A _{k} ∣∣}$

Link to original

QR Decomposition
Definition

$A = QR$ Decomposition of matrix $A$ into a product $A = QR$ of an orthonormal matrix $Q$ and an upper triangular matrix $R$ .

Computation

Using the Gram Schmidt Orthonormalization

QR decomposition can be computed by Gram Schmidt Orthonormalization. Where $Q = [q_{1}, \dots, q_{n}]$ is the matrix of orthonormal column vectors obtained by the orthonormalization and $R = q_{1}^{⊺} a_{1} 00 ⋮ 0 q_{1}^{⊺} a_{2} q_{2}^{⊺} a_{2} 0 ⋮ 0 q_{1}^{⊺} a_{3} q_{2}^{⊺} a_{3} q_{3}^{⊺} a_{3} ⋮ 0 \dots \dots \dots ⋱ \dots q_{1}^{⊺} a_{n} q_{2}^{⊺} a_{n} q_{3}^{⊺} a_{n} ⋮ q_{n}^{⊺} a_{n}$
Link to original

Symmetric Matrix
Definition

For real elements, $A^{⊺} = A$ $a_{ij} = a_{ji}$ A square matrix that is equal to its transpose.

Facts

Every real symmetric matrix is Hermitian Matrix

By Spectral Theorem, is Diagonalizable Matrix

Link to original

Hermitian Matrix
Definition

$A^{†} = A$ $a_{ij} = \overset{a}{ˉ}_{ji}$

A complex square matrix that is equal to its own Conjugate Transpose

Facts

$(A^{†})^{†} = A$ $(A \pm B)^{†} = A^{†} \pm B^{†}$ $(k A)^{†} = \overline{k} A^{†}$ $(AB)^{†} = B^{†} A^{†}$

The diagonal elements of the hermitian matrix should be real numbers.

Let $A^{†} = A$ be hermitian matrix Then, $x^{†} Ax \in R$

Proof $(x^{†} Ax)^{†} = x^{†} A^{†} x = x^{†} Ax$

Link to original

Definite Matrix
Kinds

Positive-Definite Matrix
Definition

$M ≻ 0 \Leftrightarrow \forall z \neq = 0, z^{⊺} M z > 0$

Matrix $M$ , in which $z^{⊺} M z$ is positive for every non-zero column vector $z$ is a positive-definite matrix

Facts

Let $M ≻ 0$ , then

$A^{- 1} ≻ 0$

$rank (C A C^{⊺}) = rank (C)$ where $C$ is a $p \times n$ matrix.

$rank (C) = p \Rightarrow CM C^{⊺} ≻ 0$

The diagonal elements of $M$ are positive.

For a Symmetric Matrix $B$ , $\exists t, M - tB ≻ 0$ for sufficiently small $∣ t ∣$

$\forall b, h : h \neq = 0 sup \frac{( h ^{⊺} b ) ^{2}}{h ^{⊺} M h} = b^{⊺} A^{- 1} b$

$\exists M^{1/2} ≻ 0 s.t. (M^{1/2})^{2} = M$

$M ≻ 0 \Leftrightarrow \exists R s.t. A = R R^{⊺}$ where $R$ is a non-singular matrix.

$M ≻ 0 \Leftrightarrow$ all the leading minor determinants of $M$ are positive.

$rank (X) = p \Rightarrow X^{⊺} X ≻ 0$

Link to original

Positive Semi-Definite Matrix
Definition

$M ⪰ 0 \Leftrightarrow \forall z \neq = 0, z^{⊺} M z \geq 0$

Matrix $M$ , in which $z^{⊺} M z$ is positive or zero for every non-zero column vector $z$ is a positive semi-definite matrix

Facts

Let $M ⪰ 0$ , then

$tr (A) \geq 0$

$rank (A) = r \Leftrightarrow \exists R_{n \times n}, rank (R) = r, A = R R^{⊺}$

$rank (A) = r \Rightarrow \exists S_{n \times r}, rank (s) = r, S^{⊺} A S = I_{r}$

$X^{⊺} A X = O \Rightarrow A X = O$ where $X$ is $n \times p$ matrix.

Link to original

Negative-Definite Matrix
Definition

$M ≺ 0 \Leftrightarrow \forall z \neq = 0, z^{⊺} M z < 0$

Matrix $M$ , in which $z^{⊺} M z$ is negative for every non-zero column vector $z$ is a negative-definite matrix
Link to original

Facts

Every positive (semi)-definite matrix is Hermitian Matrix

Positive (Semi)-definite and Symmetric Matrix

$M$ is positive definite $\Leftrightarrow$ all eigenvalues of $M$ are real and positive.

$M$ is positive semi definite $\Leftrightarrow$ all eigenvalues of $M$ are real and positive or zero.

where $M$ is Hermitian Matrix

Proof

$(\Leftarrow)$ A Hermitian Matrix $M$ is orthogonally diagonalizable as $PΛ P^{⊺}$ ¹ Therefore, $z^{⊺} Mz = z^{⊺} PΛ P^{⊺} z = x^{⊺} Λx = \sum_{i = 1}^{n} x_{i}^{2} λ_{i} > 0$

$(\Rightarrow)$ A Hermitian Matrix $M$ is orthogonally diagonalizable as $pΛ p^{⊺}$ ¹ where $p$ is one of the eigenvectors of $M$

The $M$ can be replaced by the corresponding eigenvalue $λ$ ^[By definition of Eigendecomposition] $pM p^{⊺} = p λ p^{⊺}$

Since matrix of eigenvectors $P$ is orthogonal¹, $p λ p^{⊺} = λ$ $p λ p^{⊺} > 0$ for every $p$ ^[By definition of positive definite matrix] Therefore, $pM p^{⊺} = p λ p^{⊺} = λ > 0$ holds. In other words, every eigenvalue is non-zero.

Footnotes

By Spectral Theorem ↩ ↩² ↩³

Link to original

Cholesky Decomposition
Definition

$A = L L^{†}$

Decomposition of a Positive-Definite Matrix into the product of lower triangular matrix and its Conjugate Transpose.

Computation

Let $A = a_{11} a_{21} a_{31} a_{12} a_{22} a_{22} a_{13} a_{23} a_{33}$ be Positive-Definite Matrix. Then, $A = L L^{⊺} = L_{11} L_{21} L_{31} 0 L_{22} L_{32} 00 L_{33} L_{11} 00 L_{21} L_{22} 0 L_{31} L_{32} L_{33} = L_{11}^{2} L_{21} L_{11} L_{31} L_{11} L_{21}^{2} + L_{22}^{2} L_{31} L_{21} + L_{32} L_{22} (symmetric) L_{31}^{2} + L_{32}^{2} + L_{33}^{2}$ By setting the first-row first-column entry $L_{11} = a_{11}$ , can find other entries using substitution. $L_{21} = a_{21} / L_{11}, L_{31} = a_{31} / L_{11}, L_{22} = a_{22} - L_{21}^{2}, L_{32} = (a_{32} = L_{31} L_{21}) / L_{22}, L_{33} = a_{33} - L_{31}^{2} - L_{32}^{2}$ By summarizing, $L_{ii} = a_{ii} - \sum_{k = 1}^{i - 1} L_{ik}^{2}$ , $L_{ij} = \frac{1}{L _{jj}} (a_{ij} - \sum_{k = 1}^{j - 1} L_{ik} L_{jk})$
Link to original

Eigendecomposition
Definition

$Av = λ v$ where $A$ is a $n \times n$ matrix and $v \neq = 0$

If $Av$ is a scalar multiple of non-zero vector $v$ , then $λ$ is the eigenvalue and $v$ is the eigenvector.

Characteristic Polynomial

$∣ A - λ I ∣ = 0$ The values $λ_{i}$ satisfying the characteristic polynomial, are the eigenvalues of the matrix $A$

Eigenspace

$E = {v : (A - λ I) v = 0}$

The set of all eigenvectors of $A$ corresponding to the same eigenvalue, together with the zero vector.

The Kernel of the matrix $(A - λ I)$

Eigenvector: non-zero vector in the eigenspace

Algebraic Multiplicity

$μ_{A} (λ_{i})$

Let $λ_{i}$ be an eigenvalue of an $n \times n$ matrix $A$ . The algebraic multiplicity $μ_{A} (λ_{i})$ of the eigenvalue is its multiplicity as a root of a Characteristic Polynomial, that is, the largest k such that $(λ - λ_{i})^{k}$

Geometric Multiplicity

$γ_{A} (λ_{i})$ Let $λ_{i}$ be an eigenvalue of an $n \times n$ matrix $A$ . The geometric multiplicity $γ_{A} (λ_{i})$ of the eigenvalue is the dimension of the Eigenspace associated with the eigenvalue.

Computation

Find the solution^[eigenvalues] of the Characteristic Polynomial.

Find the solution^[eigenvectors] of the Under-Constrained System $(A - λ_{i} I) v_{i} = 0$ using the found eigenvalue.

Facts

There exists at least one eigenvector corresponding to the eigenvalue $λ$

Eigenvectors corresponding to different eigenvalues are always linearly independent.

When $A$ is a normal or real Symmetric Matrix, the eigendecomposition is called Spectral Decomposition

$tr (A) = \sum_{i = 1}^{n} λ_{i}$ The Trace of the matrix is equal to the sum of the eigenvalues of the matrix.

Proof Since the matrix $A - λ I$ only has $λ$ term on diagonal, and the calculation of cofactor deletes a row and a column, the coefficient of $λ^{n - 1}$ of $det (A - λ I)$ is always $- (a_{11} + a_{22} + \dots + a_{nn})$ . Also, since $λ_{i}$ are the solution of the Characteristic Polynomial, the expression is factorized as $det (A - λ I) = (λ - λ_{1}) (λ - λ_{2}) \dots (λ - λ_{n})$ and the coefficient of $λ^{n - 1}$ become a $- (λ_{1} + λ_{2} + \dots + λ_{n})$ Therefore, $- (a_{11} + a_{22} + \dots + a_{nn}) = - (λ_{1} + λ_{2} + \dots + λ_{n})$ and $Trace (A) = \sum_{i = 1}^{n} λ_{i}$ .

$∣ A ∣ = \prod_{i = 1}^{n} λ_{i}$ The Determinant of the matrix is equal to the product of the eigenvalues of the matrix.

Not all matrices have $n$ linearly independent eigenvectors.

When $Av = λ v$ holds,

the eigenvalues of $A^{- 1}$ are $\frac{1}{λ}$ and the eigenvectors of the matrix $A^{- 1}$ are the same as $A$ .

the eigenvalues of $A^{k}$ is $λ^{k}$

the eigenvalues of $c A$ is $c λ$

the eigenvalues of $A + c I$ is $λ + c$

the eigenvalues of $(A + c I)^{- 1}$ is $1/ (λ + c)$

$1 \leq γ_{A} (λ_{i}) \leq μ_{A} (λ_{i}) \leq n$

An eigenvalue’s Geometric Multiplicity cannot exceed its Algebraic Multiplicity

$\exists P s.t. A = P D P^{- 1} \Leftrightarrow \forall λ_{i} : γ_{A} (λ_{i}) = μ_{A} (λ_{i})$

the matrix is diagonalizable $\Leftrightarrow$ the Geometric Multiplicity is equal to the Algebraic Multiplicity for all eigenvalues

Let $A$ be a symmetric matrix. Then, $A$ has $r$ eigenvalues equal to $1$ and the rest zero $\Leftrightarrow A^{2} = A, rank (A) = r$ .

Link to original

The non-zero eigenvalues of $A B$ are the same as those of $B A$ .

Link to original

Cayley–Hamilton theorem
Definition

Let the Characteristic Polynomial of $A$ be $f_{A} (λ) = det (A - λ I) = \sum_{i = 0}^{n} a_{i} λ^{i}$ Then, for the similar mapping $p_{A} (A) = \sum_{i = 0}^{n} a_{i} A^{i}$ , $p_{A} (A) = 0$ is satisfied

Proof

Let $B = adj (λ I - A)$ Then, $B (λ I - A) = det (λ I - A) I = \sum_{i = 0}^{n} a_{i} λ^{i} I$ by the property of adjucate matrix

Since each element of $B$ is $(n - 1)$ -order polynomial about $λ$ So we can express $B = λ^{n - 1} B_{n - 1} + λ^{n - 2} B_{n - 2} + \dots + λ^{1} B_{1} + B_{0}$

Then, $B (λ I - A) = λ^{n} B_{n - 1} + λ^{n - 1} (B_{n - 2} - B_{n - 1} A) + \dots + λ (B_{0} - B_{1} A) - B_{0} A = \sum_{i = 0}^{n} a_{i} λ^{i} I$ by using the two above expansions $∴ B_{n - 1} = a_{n} I, (B_{n - 2} - B_{n - 1} A) = a_{n - 1} I, (B_{0} - B_{1} A) = a_{1} I, - B_{0} A = a_{0} I$

Therefore, $p_{A} (A) = B_{n - 1} A^{n} + (B_{n - 2} - B_{n - 1} A) A^{n - 1} + (B_{0} - B_{1} A) A + (- B_{0} A) I = 0 = \sum_{i = 0}^{n} a_{i} A^{i}$

Examples

For $A = (1324)$ $p (λ) = det (λ I_{2} - A) = det (λ - 1 - 3 - 2 λ - 4) = (λ - 1) (λ - 4) - (- 2) (- 3) = λ^{2} - 5 λ - 2$ $p (A) = A^{2} - 5 A - 2 I_{2} = (0000)$
Link to original

Square System
Definition

$A_{n \times n} x = b$

The number of unknowns(n) = the number of equations(n) has unique or no solution.
Link to original

Under-Constrained System
Definition

$A_{m \times n} x = b$ where $m < n$

The number of unknowns(n) > the number of equations(m) usually has infinitely many or no solutions.

Solution

Homogeneous Under-Constrained System

solving the homogeneous under-constrained linear system $Ax = 0$

Obtain $Rx = 0$ and identify pivot and free variables where $R$ is the reduced Echelon matrix.

Find Special solution

set a free variable = 1, and others = 0

solve $Rx = 0$ to find the pivot variables

Example

$Ax = 0 \Leftrightarrow 12 - 1 36 - 3 393274 u v w y = 000$

Find the reduced Echelon matrix $12 - 1 36 - 3 393274 \to Echelon matrix 100300330230 \to Reduced Echelon matrix 100300010 - 1 10$

$Rx = 0 \Leftrightarrow 100300010 - 1 10 u v w y = 000$ where $u, w$ are the pivot variables and $v, y$ are the free variables.

Set a free variable $v = 1$ and others $y = 0$ and find the pivot variables $100300010 - 1 10 u 1 w 0 = 000 \Rightarrow {u + 3 = 0 w = 0 \Rightarrow u = - 3 \Rightarrow u v w y = - 3 100$

Set a free variable $y = 0$ and others $v = 0$ and find the pivot variables $100300010 - 1 10 u 0 w 1 = 000 \Rightarrow {u - 1 = 0 w + 1 = 0 \Rightarrow u = 1 \Rightarrow w = - 1 \Rightarrow u v w y = 10 - 1 1$

Now, the solutions^[null space] are all linear combinations of special solution $x = a - 3 100 + b 10 - 1 1$

Non-Homogeneous Under-Constrained System

solving the non-homogeneous under-constrained linear system $Ax = b \neq = 0$

Find the special solution for $Ax = 0$ and find a particular solution from $d$ obtained by Gauss Elimination $Rx = d$ where $R$ is the reduced Echelon matrix

Sum the special solution and particular solution

Example

$Ax = b \Leftrightarrow 222 45 - 3 675462 u v w y = 435$

Find the reduced Echelon matrix $222 45 - 3 675462 ∣ ∣ ∣ 435 \to Echelon matrix 2004106164212 ∣ ∣ ∣ 4 - 1 - 6 \to Reduced Echelon matrix 100010001 - 4 02 ∣ ∣ ∣ 50 - 1$ where $100010001 - 4 02$ is the $R$ and $50 - 1$ is the $d$

Find the special solution $a 40 - 2 0$ using the method of homogeneous equation

Find the particular solution $50 - 1 0$ using $d$

Now, the solution of $Ax = b$ are the sum of all linear combination of special solution and a particular solution $x = a 40 - 2 0 + 50 - 1 0$

Link to original

Over-Constrained System
Definition

$A_{m \times n} x = b$ where $m > n$

The number of unknowns (n) < the number of equations (m) no solution for equality

Solutions

Non-Homogeneous Over-Constrained System

solve the non-homogeneous over-constrained linear system $Ax = b$

The error term $(Ax - b)$ of projection is orthogonal to the column space of $A$ , $C (A)$ . $(Ax - b) ⊥ C (A)$ Therefore, $A^{⊺} (Ax - b) = 0 \Rightarrow A^{⊺} Ax = A^{⊺} b \Rightarrow \hat{x} = (A^{⊺} A)^{- 1} A^{⊺} b$ . Now, $A \hat{x} = A (A^{⊺} A)^{- 1} A^{⊺} b$ is the least square solution and $A (A^{⊺} A)^{- 1} A^{⊺}$ become a projection matrix onto the column space of $A$ , $C (A)$ .

Homogeneous Over-Constrained System

solve the homogeneous over-constrained linear system $Ax = 0$

Let the Eigendecomposition of $A^{⊺} A$ be $(A^{⊺} A) v = λ A$ where $λ$ is the eigenvalue and $v$ is the corresponding eigenvector. Then, we can change the expression into $v^{⊺} A^{⊺} Av = v^{⊺} λ v = λ v^{⊺} v = λ ∣∣ v ∣∣$ by multiplying $v^{⊺}$ to the both left side So, $∣∣ Av ∣ ∣^{2} = λ ∣∣ v ∣∣ \Rightarrow λ = \frac{∣∣ Av ∣ ∣ ^{2}}{∣∣ v ∣ ∣ ^{2}} \in R \geq 0$ holds by the property of the real-valued gram matrix Since over-constrained system doesn’t have the solution for equality, $v \neq = 0 \Rightarrow λ ∣∣ v ∣∣ = ∣∣ Av ∣ ∣^{2} \neq = 0$ . Therefore, the eigenvalue of over-constrained system is positive and real $λ = \frac{∣∣ Av ∣ ∣ ^{2}}{∣∣ v ∣ ∣ ^{2}} \in R > 0$ .

Since there is not exist the exact solution $x$ for the $Ax = 0$ , the $x argmin ∣∣ Av ∣ ∣^{2}$ is the best solution for the over-constrained system. By the above expansion $∣∣ Av ∣ ∣^{2} = λ ∣∣ v ∣ ∣^{2}$ . So we can change the expression into $x min ∣∣ Av ∣ ∣^{2} = v min λ ∣∣ v ∣ ∣^{2}$ Therefore, $x argmin λ ∣∣ x ∣ ∣^{2}$ subject $∣∣ x ∣∣ = 1$ is the eigenvector with the minimum eigenvalue of $A^{⊺} A$ .

Facts

$Ax$ is the linear combination of column vectors in $A$ . So $Ax \in C (A)$ . Also, since $Ax \neq = b$ , $b \in / C (A)$ . Thus, $x min ∣∣ Ax - b ∣ ∣^{2}$ is the best solution. This is the projection of $b$ onto the subspace of $A$ .

If $b$ is in $C (A)$ , then $Ax = b$ There exists a solution satisfying all equality

If $b$ is perpendicular to the every column vectors in $A$ , $C (A)$ , then $A^{⊺} b = 0$ . In other words, $b$ become the Left Null Space of $A$ .

If $A$ is square( $n \times n$ ) and invertible, then $C (A)$ = $R^{n}$ , $b \in C (A)$ , and $Pb = b$

If $(A^{⊺} A)$ is non-invertable^[singular], then solve the Under-Constrained System $A^{⊺} Ax = A^{⊺} b \Rightarrow Bx = c$

Link to original

Polynomial Interpolation
Definition

The interpolation of a given bivariate data set by the polynomial of lowest possible degree that passes through the points of the dataset.

Examples

Find the cubic polynomial $f (x) = a_{0} + a_{1} x + a_{2} x^{2} + a_{3} x^{3}$ passes through the four points $(1, 3), (2, - 2), (3, - 5), (4, 0)$ .

Set the system equation for the polynomial $1111 x_{1} x_{2} x_{3} x_{4} x_{1}^{2} x_{2}^{2} x_{3}^{2} x_{4}^{2} x_{1}^{3} x_{2}^{3} x_{3}^{3} x_{4}^{3} = a_{0} a_{1} a_{2} a_{3} = y_{1} y_{2} y_{3} y_{4}$ substitute the given points to the system equation and make the augmented matrix $1111123414916182764 3 - 2 - 5 0$ solve the system of equation using the gauss elimination $1111123414916182764 3 - 2 - 5 0 \to reduced form 1000010000100001 43 - 5 1$ Then, $a_{0} = 4, a_{1} = 3, a_{2} = - 5, a_{3} = 1$ . $∴ f (x) = 4 + 3 x - 5 x^{2} + x^{3}$

Facts

Interpolation theorem

For any $n + 1$ bivariate data points $(x_{0}, y_{0}), \dots, (x_{n}, y_{n}) \in R^{2}$ , where no two $x_{i}$ are the same, there exists a unique polynomial $p (x)$ of degree at most $n$ that interpolates these points. $p (x_{0}) = y_{0}, \dots, p (x_{n}) - y_{n}$

Link to original

Diagonalizable Matrix
Definition

$A = PΛ P^{- 1}$ For square matrix $A$ , There exist invertible matrix $P$ that satisfies $P^{- 1} AP = D$ where $D$ is Diagonal Matrix

Orthogonally Diagonalizable Matrix

$A = PΛ P^{⊺}$ For square matrix $A$ , There exist orthogonal matrix $P$ that satisfies $P^{⊺} AP = D$ where $D$ is Diagonal Matrix

Unitary Diagonalizable Matrix

$A = UΛ U^{†}$ For square matrix $A$ , There exist Unitary Matrix $U$ that satisfies $U^{†} AU = D$ where $D$ is Diagonal Matrix

Diagonalization

$A = PΛ P^{- 1}$

Let $P$ be a matrix of eigenvectors of $A$ and $Λ = diag (λ_{1}, λ_{2}, \dots)$ be a Diagonal Matrix which has eigenvalues of $A$ . Then, by formula of Eigendecomposition $AP = PΛ$ If $P$ is full rank matrix, then $P$ is invertible. So, $P^{- 1} AP = Λ$ holds.

Facts

$A$ is diagonalizable $\Leftrightarrow$ $A$ has $n$ linearly independent eigenvectors

The matrix $P$ is not unique.

The order of $p_{i}$ and $λ_{i}$ in $S$ and $Λ$ should be the same.

Not all matrices are diagonalizable^[Since the property of eigen decomposition]

$A^{k} v = λ^{k} v \Rightarrow A^{k} = P Λ^{k} P^{- 1}$

the matrix is diagonalizable $\Leftrightarrow$ If the Geometric Multiplicity is equal to the Algebraic Multiplicity for all eigenvalues

Unitary Diagonalizable Matrix $\Leftrightarrow$ Normal Matrix

Spectral Theorem

Diagonalized matrix is similar to the original matrix.

Link to original

Matrix Similarity
Definition

$\exists P s.t. A = PB P^{- 1} \Leftrightarrow A \sim B$

Two matrices $A$ and $B$ are similar if there exists $P$

Similar matrices represent the same linear map under two different bases, with $P$ being the change of basis matrix.

Facts

Similarity invariant

Similar matrices share all properties of their shared underlying operator

Rank of Matrix

Determinant

Invertibility

Nullity

Characteristic Polynomial

Eigenvalue

Algebraic Multiplicity

Geometric Multiplicity

Trace

Link to original

Spectral Theorem
Definition

$A = A^{†} \Leftrightarrow A = Q Λ Q^{†}$ where $Q$ is a Unitary Matrix, and $Λ = diag (λ_{1}, λ_{2}, \dots, λ_{n})$

A matrix $A$ is a Hermitian Matrix if and only if $A$ is Unitary Diagonalizable Matrix.

Facts

Every Hermitian Matrix is diagonalizable, and has real-valued Eigenvalues and orthonormal eigenvector matrix.

For the Hermitian Matrix $A^{†} = A$ , the every eigenvalue is real.

Proof For the eigendecomposition $Ax = λ x$ , $x^{†} Ax = x^{†} λ x = λ x^{†} x = λ ∣∣ x ∣∣ \Rightarrow λ = \frac{x ^{†} Ax}{∣∣ x ∣∣}$ . Since $A$ is hermitian, $x^{†} Ax \in R$ and norm is always real. Therefore, every eigenvalue is real.

For the Hermitian Matrix $A^{†} = A$ , the eigenvectors from different eigenvalues are orthogonal.

Proof Let the eigendecomposition $A x_{1} = λ_{1} x_{1}, A x_{2} = λ_{2} x_{2}$ where $λ_{1} \neq = λ_{2}, x_{1} \neq = x_{2}$ . By the property of hermitian matrix, $(A x_{1})^{†} x_{2} = x_{1}^{†} A^{†} x_{2} = x_{1}^{†} λ_{2} x_{2} = λ_{2} x_{1}^{†} x_{2}$ and $(A x_{1})^{†} x_{2} = (λ_{1} x_{1})^{†} x_{2} = \overset{ˉ}{λ}_{1} x_{1}^{†} x_{2} = λ_{1} x_{1}^{†} x_{2}$ So, $λ_{2} x_{1}^{†} x_{2} = λ_{1} x_{1}^{†} x_{2} \Rightarrow (λ_{1} - λ_{2}) x_{1}^{†} x_{2} = 0$ . Since $λ_{1} \neq = λ_{2}$ , $x_{1}^{†} x_{2} = 0$ . Therefore, $x_{1}^{†}, x_{2}$ are orthogonal.

Link to original

Singular Value Decomposition
Definition

$A_{n \times m} = U_{n \times n} D_{n \times m} (V_{m \times m})^{⊺} = \sum_{i = 1}^{m i n (n, m)} d_{i} U_{i} V_{i}^{⊺}$ An arbitrary matrix $A_{n \times m}$ can be decomposed to $UD V^{⊺}$ .

For $n \geq m$ $A_{n \times m} = U_{n \times m} D_{m \times m} (V_{m \times m})^{⊺}$ where $U^{⊺} U = I_{m}$ and $V^{⊺} V = V V^{⊺} = I_{m}$ and $D$ is Diagonal Matrix

For $n \leq m$ $A_{n \times m} = U_{n \times n} D_{n \times n} (V_{m \times n})^{⊺}$ where $U^{⊺} U = U U^{⊺} = I_{n}$ and $V^{⊺} V = I_{n}$ and $D$ is Diagonal Matrix

Calculation

For matrix $A_{m \times n} = UD V^{⊺}$

$V_{n \times n}$ is the matrix of orthonormal eigenvectors of $A^{⊺} A$ $U_{m \times m}$ is the matrix of orthonormal eigenvectors of $A A^{⊺}$ $D_{m \times n}$ is the Diagonal Matrix made of the square roots of the non-zero eigenvalues of $A^{⊺} A$ and $A A^{⊺}$ sorted in descending order.

If the eigendecomposition is $A^{⊺} Ax = λ x$ , then the eigenvalues $λ \geq 0$ and the eigenvectors $x \in C (A^{⊺})$ are orthonormal by Spectral Theorem. If the $rank (A) = r \leq n$ , then $λ_{1} ⪈ λ_{2} ⪈ \dots \geq λ_{r}, λ_{r + 1} = \dots λ_{n} = 0$ . Where $σ_{i} = λ_{i}_{i = 1, 2, \dots, r}$ are called the singular values.

Now, the Orthonormal Matrix $V = [V_{1}, V_{2}]$ is calculated using the singular values. Where $V_{1} = [v_{1}, v_{2}, \dots, v_{r}]$ is the Orthonormal Matrix of eigenvectors corresponding to the non-zero eigenvalues and $V_{2} = [v_{r + 1}, v_{r + 2}, \dots, v_{n}]$ is the Orthonormal Matrix of eigenvectors corresponding to zero eigenvalues where each $v_{r} + i \in N (A^{⊺} A) = N (A)$ , and $D_{m \times n} = diag (σ_{1}, σ_{2}, \dots, σ_{r}, 0, \dots, 0)$ is a rectangular Diagonal Matrix.

Since $V$ is an orthonormal matrix and $D$ is a Diagonal Matrix, $AV = UD \Rightarrow A [v_{1}, v_{2}, \dots, v_{n}] = [u_{1}, u_{2}, \dots, u_{m}] D \Rightarrow A v_{i} = σ_{i} u_{i} \Rightarrow u_{i} = \frac{1}{σ _{i}} A v_{i}$ . Now, the Orthonormal Matrix $U = [U_{1}, U_{2}]$ is calculated using the linear system $\frac{1}{σ _{i}} A v_{i}$ and the null space of $A$ , $N (A)$ Where $U_{1} = [u_{1}, u_{2}, \dots, u_{r}]$ is the Orthonormal Matrix of the vectors $u_{{1, 2, \dots, r}} \in C (A)$ obtained from the system equation $\frac{1}{σ _{i}} A v_{i}$ And $U_{2} = [u_{r + 1}, u_{r + 2}, \dots, u_{m}]$ is the Orthonormal Matrix of the vectors $u_{{r + 1, r + 2, \dots, m}} \in N (A^{⊺})$ . which is corresponding to zero eigenvalues

The Orthonormal Matrix $U = [u_{1}, u_{2}, \dots, u_{m}]$ can also be formed by the eigenvectors of $A A^{⊺}$ similarly to calculating of $V$ .

Facts

$U, V$ are the Unitary Matrix

Let $A$ be a real symmetric Positive Semi-Definite Matrix Then, the Eigendecomposition(Spectral Decomposition) of $A$ and the singular value decomposition of $A$ are equal.

$A = PΛ P^{⊺} = UD V^{⊺}$ where $P = U = V$ and $Λ = D$ are non-negative and the shape of the every matrix is $n \times n$

Visualization

every matrix can be decomposed as a

$V^{⊺}$ : rotation and reflection

$D$ : scaling

$U$ : rotation and reflection

Link to original

Sherman–Morrison Formula
Definition

Suppose $A \in R^{n \times n}$ is an invertible matrix an d $v, u \in R^{n}$ . Then, $A + u v^{⊺}$ is invertible $\Leftrightarrow 1 + v^{⊺} A^{- 1} u \neq = 0$ . In this case, $(A + u v^{⊺})^{- 1} = A^{- 1} - \frac{A ^{- 1} u v ^{⊺} A ^{- 1}}{1 + v ^{⊺} A ^{- 1} u}$

Proof

Multiplying $(A + u v^{⊺})$ to the RHS gives $(A^{- 1} - \frac{A ^{- 1} u v ^{⊺} A ^{- 1}}{1 + v ^{⊺} A ^{- 1} u}) (A + u v^{⊺}) = I + A^{- 1} u v^{⊺} - \frac{A ^{- 1} u v ^{⊺} A ^{- 1} ( A + u v ^{⊺} )}{1 + v ^{⊺} A ^{- 1} u} (1)$

Since $v^{⊺} A^{- 1} u$ is a scalar, The numerator of the last term can be expressed as $A^{- 1} u v^{⊺} A^{- 1} (A + u v^{⊺}) = A^{- 1} u v^{⊺} + (v^{⊺} A^{- 1} u) A^{- 1} u v^{⊺} = (1 + v^{⊺} A^{- 1} u) A^{- 1} u v^{⊺}$

So, $(1) = I + A^{- 1} u v^{⊺} - \frac{( 1 + v ^{⊺} A ^{- 1} u ) A ^{- 1} u v ^{⊺}}{1 + v ^{⊺} A ^{- 1} u} = (1) = I + A^{- 1} u v^{⊺} - A^{- 1} u v^{⊺} = I$ $∴ (A + u v^{⊺})^{- 1} = A^{- 1} - \frac{A ^{- 1} u v ^{⊺} A ^{- 1}}{1 + v ^{⊺} A ^{- 1} u}$

Examples

Updating Fitted Least Square Estimator

Sherman–Morrison formula can be used for updating fitted Least Square estimator

Let $\hat{x} = (A^{⊺} A)^{- 1} A^{⊺} b$ be the least square estimator of $Ax = b$ and the matrices with a new data be $A_{a} = [A a^{⊺}]$ and $b_{a} = [b b]$ Then, $\hat{x}_{new} = (A_{a}^{⊺} A_{a})^{- 1} A_{a}^{⊺} b_{a} = ([A^{⊺} a] [A a^{⊺}])^{- 1} [A^{⊺} a] [b b] = (A^{⊺} A + a a^{⊺})^{- 1} (A^{⊺} b + b a)$

Let $P := (A^{⊺} A)^{- 1}$ for convenience Then, $P_{a} := (A^{⊺} A + a a^{⊺})^{- 1} = P - \frac{Pa a ^{⊺} P}{1 + a ^{⊺} Pa} = (A^{⊺} A)^{- 1} - \frac{( A ^{⊺} A ) ^{- 1} a a ^{⊺} ( A ^{⊺} A ) ^{- 1}}{1 + a ^{⊺} ( A ^{⊺} A ) ^{- 1} a}$ by Sherman-Morrison formula

So, $\hat{x}_{new} = (A^{⊺} A + a a^{⊺})^{- 1} (A^{⊺} b + b a) = (A^{⊺} A)^{- 1} A^{⊺} b - \frac{Pa a ^{⊺} P}{1 + a ^{⊺} Pa} A^{⊺} b + b P_{a} a = \hat{x} - \frac{Pa}{1 + a ^{⊺} Pa} a^{⊺} \hat{x} + b P_{a} a$ where $P_{a} a = Pa - \frac{Pa a ^{⊺} Pa}{1 + a ^{⊺} Pa} = \frac{Pa + Pa a ^{⊺} Pa - Pa a ^{⊺} Pa}{1 + a ^{⊺} Pa} = \frac{Pa}{1 + a ^{⊺} Pa}$ by expansion $∴ \hat{x}_{new} = \hat{x} - P_{a} a a^{⊺} \hat{x} + b P_{a} a = \hat{x} + P_{a} a (b - a^{⊺} \hat{x})$

So, $\hat{x}_{new}$ can be obtained without additional inverse matrix calculation.

Facts

Sherman–Morrison formula is a special case of the Woodbury Formula
Link to original

Matrix Inversion Lemma
Definition

$(A + UCV)^{- 1} = A^{- 1} - A^{- 1} U (C^{- 1} + V A^{- 1} U)^{- 1} V A^{- 1}$ where the size of matrices are $A$ is $n \times n$ , $C$ is $k \times k$ , and $V$ is $k \times n$ and $A, C, (C^{- 1} + V A^{- 1} U)$ should be invertible.

The inverse of a rank-k correction of some matrix can be computed by doing a rank-k correction to the inverse of the original matrix

Proof

Start by the matrix $[A V U C]$

The $L D U$ decomposition of the original matrix become $[A V U C] = [I V A^{- 1} 0 I] [A 0 0 C - V A^{- 1} U] [I 0 A^{- 1} U I]$ Inverting both sides gives^[Diagonalizable Matrix] $[A V U C]^{- 1} = [I 0 A^{- 1} U I]^{- 1} [A 0 0 C - V A^{- 1} U]^{- 1} [I V A^{- 1} 0 I]^{- 1} = [I 0 - A^{- 1} U I] [A^{- 1} 0 0 (C - V A^{- 1} U)^{- 1}] [I - V A^{- 1} 0 I] = [A^{- 1} + A^{- 1} U (C - V A^{- 1} U)^{- 1} V A^{- 1} - (C - V A^{- 1} U)^{- 1} V A^{- 1} - A^{- 1} U (C - V A^{- 1} U)^{- 1} (C - V A^{- 1} U)^{- 1}] (1)$

The $U D L$ decomposition of the original matrix become $[A V U C] = [I 0 U C^{- 1} I] [A - U C^{- 1} V 0 0 C] [I C^{- 1} V 0 I]$ Again inverting both sides, $[A V U C]^{- 1} = [I C^{- 1} V 0 I]^{- 1} [A - U C^{- 1} V 0 0 C]^{- 1} [I 0 U C^{- 1} I]^{- 1} = [I - C^{- 1} V 0 I] [(A - U C^{- 1} V)^{- 1} 0 0 C^{- 1}] [I 0 - U C^{- 1} I] = [(A - U C^{- 1} V)^{- 1} - C^{- 1} V (A - U C^{- 1} V)^{- 1} - (A - U C^{- 1} V)^{- 1} U C^{- 1} C^{- 1} + C^{- 1} V (A - U C^{- 1} V)^{- 1} U C^{- 1}] (2)$

The first-row first-column entry of RHS of (1) and (2) above gives the Woodbury formula $(A - U C^{- 1} V)^{- 1} = A^{- 1} + A^{- 1} U (C - V A^{- 1} U)^{- 1} V A^{- 1}$
Link to original

My Knowledge Base

Explorer

Linear Algebra Note

Euclidean Vector

Definition

Properties

Length

Vector

Real

Complex

Addition and Subtraction

Distance

Scalar Multiplication

Inner Product

Vector

Real

Complex

Vector Product

Cross Product

Definition

Facts

Matrix

Definition

Operations

Addition, Subtraction

Scalar Multiplication

Transpose

Matrix Multiplication

Vector-Matrix Multiplication

Gauss Elimination

Definition

Elementary Row Operations

Examples

LU Decomposition

Definiiton

Cofactor

Definition

Adjugate Matrix

Definition

Facts

Determinant

Definition

Computation

2×2 matrix

n×n matrix

Laplace Expansion

Definition

Along the jth column gives

Along the ith row gives

Facts

Cramer's Rule

Definition

Inverse Matrix

Definition

Computation

2 x 2 matrix

Using Cofactor

Vector Space

Definition

Vector

Dimension

Dimension (Vector Space)

Definition

Conditions for Vector Space

Linear Independence

Definition

Linearly independent

Linearly dependent

Facts

Check of linear independence of a set of vectors

Basis (Linear Algebra)

Definition

Basis

Basis Vector

Facts

Dimension (Vector Space)

Definition

Linear Map

Definition

Fundamental Theorem of Linear Algebra

$2 \times 2$ matrix

$n \times n$ matrix

Along the $j$ th column gives

Along the $i$ th row gives

$f$ is a Linear Map

Proof of Additivity of $f$

Proof of Homogeneity of $f$

$f$ is a Isomomorphism

Proof of Monomorphism of $f$

Proof of Epimorphism of $f$

$g$ is a Linear Map

Proof of Additivity of $g$

$g (M_{1} + M_{2}) = g (M_{1}) + g (M_{2})$

Proof of Homogeneity of $g$

$g$ is a Isomomorphism

Proof of Monomorphism of $g$

Proof of Epimorphism of $g$

$f, g$ are the inverse maps of each other.

Epimorphism $\Rightarrow$ Monomorphism

Monomorphism $\Rightarrow$ Epimorphism