Linear Algebra

Linear Algebra is the study of Vector Spaces

Vectors and Vector Spaces

Vector Space

An Algebraic Structure containing Tensor elements called Vectors, over a Algebraic Field of Scalar values.

Vector Space Element

Note that Vectors need not be $n\times 1$. Any possible element of a vector space is by definition, a vector. This means that vector spaces really contain Tensors. 99% of the time when people are talking about vectors, they really mean “Coordinate Vector”, i.e. a vector that represents a location in Space. Whereas a vector represents a location in a Vector Space.

Link to original

Axioms

The Axioms neccessary to qualify as a Vector Space $V$ are

• Abelian Group under Addition
• Scalar Multiplication

Abelian Group under Addition Axioms

1. Closure: $\forall A,B\in V,A+B\in G$
2. Associativity: $\forall A,B,C\in V,(A+B)+C=A+(B+C)$
3. Identity: $\exists I\text{ s.t. }\forall A\in V,I+A=A+I=A$
4. Inverse: $\forall A\in V,A^{-1}\in V\text{ s.t. }A+A^{-1}=A^{-1}+A=I$
5. Commutativity: $\forall A,B\in V,A+B=B+A$ Scalar Multiplication Axioms
6. Closure: $\forall c\in \mathbb{R},A\in V,cV\in V$
7. Associativity: $\forall c,d\in \mathbb{R},A\in V,(cd)A=c(dA)$
8. Distributivity: $\forall c\in \mathbb{R},A,B\in V,c(A+B)=cA+cB$
9. Distributivity: $\forall c,d\in \mathbb{R},A\in V,(c+d)A=cA+dA$

Link to original

Vector

An element of a Vector Space, represented in that space either by a direction and magnitude, or by a list of Numbers, each describing the placement along a coordinate axis.

Circular transclusion detected: Mathematics/Algebra/LinearAlgebra/Vector-Space-Element

Operations

Addition

Add elementwise.

Subtraction

Subtract elementwise.

Scalar Multiplication

Multiply elementwise.

Magnitude

The magntiude calculates the distance from the tip of the vector to the origin.

$$||\vec{u}||=\sqrt{\vec{u}\cdot \vec{u}}=\sqrt{u_1^2+\cdots +u_n^2}$$

Dot Product

Dot Product

Measures the alignment of its operand vectors on a scale of 0 to 1

• $\vec{u}\cdot \vec{v}={\vec{u}}^T\vec{v}$
• $\vec{u}\cdot \vec{v}=\vec{v}\cdot \vec{u}$
• $(\vec{u}+\vec{v})\cdot \vec{w}=\vec{u}\cdot \vec{w}+\vec{v}\cdot \vec{w}$
• $(c\vec{u})\cdot \vec{v}=c(\vec{u}\cdot \vec{w})$
• $||c\vec{v}||=|c|||\vec{v}||$
• $\vec{u}\cdot \vec{u}\ge 0$
• $\vec{u}\cdot \vec{u}=||\vec{u}|{|}^2$
• $\vec{a}\cdot \vec{b}=|a||b|cos\theta$

Link to original

Cross Product

Cross Product

$$\vec{a}\times \vec{b}=\left(|a||b|\sin (\theta )\right)\vec{n}=\vec{c}$$

where $\vec{n}$ is the Unit Normal Vector of the Plane described by $\vec{a}$ and $\vec{b}$

Properties

$$\begin{array}{rl}\vec{a}\times \vec{b}& =-(\vec{b}\times \vec{a})\\ \vec{a}\times (\vec{b}+\vec{c})& =\vec{a}\times \vec{b}+\vec{a}\times \vec{c}\\ (\vec{a}+\vec{b})\times \vec{c}& =\vec{a}\times \vec{c}+\vec{b}\times \vec{c}\\ (C\vec{a})\times \vec{b}=\vec{a}\times (C\vec{b})& =C(\vec{a}\times \vec{b})\\ \vec{a}\times (\vec{b}\times \vec{c})& =\vec{b}\times (\vec{c}\times \vec{a})=\vec{c}\times (\vec{a}\times \vec{b})\end{array}$$

Magnitude

$$\underset{\text{Area}({▰}_{a,b})}{\underbrace{|\vec{a}\times \vec{b}|=|a||b|\sin (\theta )}}⟹\vec{a}\parallel \vec{b}⟺\vec{a}\times \vec{b}=\vec{0}$$Link to original

Link to original

Subspaces of ${\mathbb{R}}^n$

Subspace

A Vector Space’s version of a Subset, with some constraints.

While, a subspace does inherit the axioms of a Vector Space. Verifying a subset is a subspace is simpler; A Subset $H$ of ${\mathbb{R}}^n$ is a subspace if it is closed within scalar multiplication and vector addition:

$$\begin{array}{c}\text{For}c\in \mathbb{R},\vec{u},\vec{v}\in H\\ H\text{ is a subspace}\\ ⟺\\ c\vec{u}\in H\wedge \vec{u}+\vec{v}\in H\wedge \vec{0}\in H\end{array}$$

Properties

• $\text{span}H=H$, i.e. the Span of any subset is identical to itself

Four Fundamental Subspaces

For Matrix $A\in {\mathbb{R}}^{m\times n},r=\text{rank}A$

• The Subspaces are linked by the Fundamental Theorem of Linear Algebra
  • Rowspace
  • Nullspace of $A$
  • Columnspace
  • Nullspace of $A^T$, “Left Nullspace”
• Shows the relationship between the dimensions of the subspaces
  • $\dim \text{Col }A=r$
  • $\dim \text{Row }A=r$
  • $\dim \text{Nul }A=n-r$
  • $\dim \text{Nul }{A}^T=m-r$
• Shows the Morphisms between different subspaces of a matrix
  • Show existence of solutions:
    • $T(x):{\mathbb{R}}^n\to {\mathbb{R}}^m\equiv Ax$
    • $\exists x\in {\mathbb{R}}^n,Ax=b⟺b\in \text{Col }A$
• Shows the Orthogonality relationship between related subspaces of a matrix
  • $(\text{Row}A{)}^{\perp }=\text{Nul}A$
  • $(\text{Col}A{)}^{\perp }=\text{Nul}(A^T)$

Link to original

Columnspace

The Subspace defined by the Span of the columns of Matrix $A$

$$\begin{array}{c}\text{Col}A=\text{range}A\end{array}$$ $$\dim \text{Col}A=\text{\# pivots}=\text{rank}A$$

See Rank

Link to original

Rowspace

The Subspace defined by the Span of the rows of Matrix $A$

$$\text{Row}A$$Link to original

Nullspace

The Subspace defined by the Set of $\vec{x}$ that satisfy $A\vec{x}=\vec{0}$

$$\text{Nul}A=\{\vec{x}|A\vec{x}=\vec{0}\}$$ $$\dim \text{Nul}A=\text{\# free vars}=\text{Nullity}A$$

See Nullity

Link to original

Basis

A Set of Basis Vectors. A set of Linearly Indepedent Vectors whose Linear Combinations can represent any vector in that space.

Standard Basis Vectors in ${\mathbb{R}}^3$ are i, j, k, but you can use other vectors to span the same amount of space if you want.

• Let $\mathcal{B}\in H$
• $\mathcal{B}=\{\overrightarrow{b_1},...,\overrightarrow{b_n}\}$
• $\mathcal{B}$ is some basis for the subspace $H$

$$\begin{array}{c}\vec{x}\in H⟹\\ \text{coords of x relative to B are c1,...,cn}\vec{x}=c_1\overrightarrow{b_1}+...+c_n\overrightarrow{b_n}\\ \\ \wedge \\ \text{coord vector of }\vec{x}\text{ relative to }\mathcal{B}[\vec{x}{]}_{\mathcal{B}}=\left[\begin{array}{c}{c}_1\\ ...\\ c_n\end{array}\right]\end{array}$$

Dimension

The dimension of a Subspace $H$ is the Cardinality of its Basis $\mathcal{B}$

$$\dim H=|\mathcal{B}|$$

$\dim \{\vec{0}\}$

$$\dim \vec{0}=0$$

This is because a basis requires a Set of Linearly Indepedent Vectors, and $\vec{0}$ does not meet this requirement. Therefore, its only basis is $\varnothing$. The cardinality of the empty set is 0, therefore so is $\dim \vec{0}$

Examples

• dim ${\mathbb{R}}^n$
  • $n$
• dim(Nul A) is the number of
  • number of free vars of A
• dim(Col A) is the number of
  • number of pivots of A
• H = $\{(x_1....,x_n):x_1+...+x_n=0\}$
  • n variables, solve for $x_1$ ito everything else. → one pivot everything else free vars. Therefore $n-1$ free vars

Link to original

Basis Theorem

Any two bases for a Subspace have the same Dimension

Link to original

Link to original

Rank

$$\text{rank}A=\dim \text{Col}A=\text{\# pivots}$$

• the rank of a matrix A is the dimension of its Columnspace
• number of Pivots

Link to original

Nullity

$$\text{Nullity}A=\dim \text{Nul}A=\text{\# free vars}$$

• The nullity of a matrix is the dimension of its Nullspace
• The number of Free Variables

Link to original

Fundamental Theorem of Linear Algebra

$$\text{Rank}A+\text{Nullity}A=\#\text{cols}$$ $$\#\text{pivots}+\#\text{free vars}=\#\text{cols}$$Link to original

Invertibility Theorem

A is an $n\times n$, Square Matrix $⟺$ A is Invertible $⟺$ The columns of A are a Basis for ${\mathbb{R}}^n$ $⟺$ Col A = ${\mathbb{R}}^n$ $⟺$ rank A = dim Col A = n $⟺$ nullity A = dim Nul A = 0 $⟺$ Nul A = {$\vec{0}$}

Link to original

Determinant

Imagine the area of parallelogram created by the basis of a standard vector space, like ${\mathbb{R}}^2$. Now apply a linear transformation $A$ to that vector space. The new area of the new parallelogram has been scaled by a factor of the determinant. $S$ is the parallelopiped.

$$\text{area}(T(S))=|\det (A)|\cdot \text{area}(S)$$

You can also just think of it as the area of the parallelogram spanned by the columns of a matrix

${\mathbb{R}}^3$: parallelopiped and volume

(assume n by n matrix because we only know how to find determinants for square matrices)

You can also get the area of S by using the determinant of the matrix created by the vectors that span S, i.e. $|\vec{a}\times \vec{b}|=area(S)⟹|det([\vec{a}\vec{b}])|=area(S)$ because you are shifting the standard basis vectors into the vector space dictated by S

Determinant Laws

• det(A) = 0 $⟺$ A is singular
  • det(A) $\ne$ 0 $⟺$ A is invertible
• det(Triangular) = product of diagonals
• det A = det $A^T$
• det(AB) = det A · det B
• $det(A^{-1})=\frac{1}{det(A)}$
• $det(kA)=k^{n}det(A)$

Determinant Post Row Operations

if A square:

• if adding rows to rows on A to get B then $detA=detB$
• if swapping rows in A to get B then $-detA=detB$
• if scaling one row of A by k, then $k\cdot det(A)$ = $det(B)$ Exactly the same for columns

Link to original

Cofactor Expansion

Cofactor expansion is a method used to calculate the Determinant of an $n\times n$ matrix $A$. It works by reducing the determinant of the $n\times n$ matrix to a sum of determinants of $(n-1)\times (n-1)$ submatrices. It is a recursive definition.

$C_{ij}=(-1{)}^{i+j}\det (M_{ij})$ where $M_{ij}$ is the determinant of the submatrix of $A$ obtained by deleting the $i$-th row and $j$-th column

The $\pm$ signs for each term of the expansion are determined solely by the position $(i,j)$ and follow a checkerboard pattern, starting with $+$ in the top-left corner

$$\left[\begin{array}{cccc}+& -& +& \cdots \\ -& +& -& \cdots \\ +& -& +& \cdots \\ ⋮& ⋮& ⋮& \ddots \end{array}\right]$$

The determinant of a matrix $A$ can be calculated by cofactor expansion along any single row $i$ or any single column $j$.

Expansion Along Row $i$: $\det (A)=a_{i1}{C}_{i1}+a_{i2}{C}_{i2}+\cdots +a_{in}{C}_{in}$

Expansion Along Column $j$: $\det (A)=a_{1j}{C}_{1j}+a_{2j}{C}_{2j}+\cdots +a_{nj}{C}_{nj}$

Strategy: To simplify calculations, it is generally best to choose the row or column with the most zeros.

Link to original

Eigenstuff

Eigenvector

In Linear Algebra, an Eigenvector is a Coordinate Vector for which, applying the given Linear Transformation has the same effect as multiplying that vector by a scalar. In other words, vectors for which the Output Space of the given linear transformation is proportional to the Input Space.

• Let $A$ be a Square Matrix that represents a linear transformation.
• Let $\vec{v}$ be some Coordinate Vector that we need to solve for.
• Let $\lambda$ be some Scalar that we need to solve for.
• By solving the following equation, we find eigenstuff

$$A\vec{v}=\lambda \vec{v}$$

• Eigenvalues are nonzero scalar values $\lambda$ that solve the equation
• Eigenvectors are coordinate vectors $\vec{v}$ that solve the equation
• Eigenspaces are the spaces that extend from the eigenvectors (the spans of the eigenvectors)
• Each eigenvector has a corresponding eigenvalue, i.e. each eigenvector has a specific amount that the linear transformation scales it by
• The following GIF shows a linear transformation scaling 2D space. The red lines are the eigenspaces of the transformation. Any coordinate vector part of those spaces is an eigenvector.

Eigenvalue

$\lambda$ is an eigenvalue for the transformation

• $A\vec{v}=\lambda \vec{v}⟹\det (A-\lambda I)=0$
• Solve for $\lambda$ in $\det (A-\lambda I)=0$, which yields the Characteristic Equation for this system, e.g. in a 2D systems it is ${\lambda }^2-\text{tr}A\cdot \lambda +\det A=0$.

• $\lambda >0⟹A\vec{v},\vec{v}$ point same direction
• $\lambda <0⟹A\vec{v},\vec{v}$ point opposite direction
• $\lambda$ can be complex even if nothing else in the equation is
• Eigenvalues cannot be determined from the reduced version of a matrix ⭐
  • i.e. row reductions change the eigenvalues of a matrix
• The diagonal elements of a triangular matrix are its eigenvalues.
• A invertible iff 0 is not an eigenvalue of A.
• Stochastic matrices have an eigenvalue equal to 1.
• If ${\vec{v}}_1,{\vec{v}}_2,...,{\vec{v}}_k$ are eigenvectors that correspond to distinct eigenvalues, then ${\vec{v}}_1,{\vec{v}}_2,...,{\vec{v}}_k$ are linearly independent

Defective

An eigenvalue is defective if and only if it does not have a complete Set of Linearly Independent eigenvectors.
$\lambda =0⟹\text{ Defective}$ Due to $\mathrm{Im}\lambda$‘s contribution, $\mathrm{Re}\lambda =0/⟹\text{ Defective}$

Neutral Eigenvalue

$$\forall \lambda s.t.\mathrm{Re}\lambda =0$$

Eigenspace

• the span of the eigenvectors that correspond to a particular eigenvalue

• $Nul(A-\lambda I)$

Link to original

Characteristic Equation

$det(A-\lambda I)=0$ to get values for $\lambda$. Recall $det(T)=0$ means noninvertible. If a matrix isn’t invertible, then we won’t get trivial solutions when solving. Also the idea of reducing the dimension through the transformation is relevant; squishing the basis vectors all onto the same span where the area/volume is 0. Recall eigenvectors remain on the same span despite a linear transformation.

$\lambda$ is an eigenvalue of A $⟺$ $(A-\lambda I)$ is singular

trace of a Matrix $tr(M)$ is the sum of diagonal

Characteristic Polynomial

$det(A-\lambda I)$ n degree polynomial → n roots → maximum n eigenvalues (could be repeated)

Algebraic Multiplicity

Algebraic multiplicity of an eigenvalue is how many times an eigenvalue repeatedly occurs as the root of the characteristic polynomial.

Geometric Multiplicity

• Geometric multiplicity of an eigenvalue is the number of eigenvectors associated with an eigenvalue; $dim(Nul(A-\lambda I))$, which is saying how many eigenvector solutions does this eigenvalue have (recall $dim(B)$ is number of free vars in $B$)

Link to original

Similar

1. square matrices A,B are similar $⟺$ we can find P so that $A=PB{P}^{-1}$
2. A,B similar $⟹$ same Characteristic Polynomial $⟹$ same eigenvalues

Link to original

Systems of Linear Equations

Linear System

A system of Linear Equations.

Representation

There are several equivalent ways to represent a linear system.

A system of Equations

$$\begin{array}{rl}2x+3y& =7\\ x-y& =5\end{array}$$

An Augmented Matrix

$$\left[\begin{array}{ccc}2& 3& 7\\ 1& -1& 5\end{array}\right]$$

A Vector Equation

$$x\left[\begin{array}{c}2\\ 1\end{array}\right]+y\left[\begin{array}{c}3\\ -1\end{array}\right]=\left[\begin{array}{c}7\\ 5\end{array}\right]$$

A Matrix Equation

$$\left[\begin{array}{cc}2& 3\\ 1& -1\end{array}\right]\left[\begin{array}{c}x\\ y\end{array}\right]=\left[\begin{array}{c}7\\ 5\end{array}\right]$$Link to original

Linear Equation

$$a_1{x}_1+a_2{x}_2+...+a_n{x}_n=b$$

An Equation where in the above form where the the a’s are coefficients, x’s are variables, n is the dimension (number of variables), e.g. $2x_1+4x_2=4$ has two dimensions

Link to original

Row Reduction

Row Operation

Row Operation

1. Replacement/Addition
2. Interchange
3. Scaling Row operations can be used to solve systems of linear equations

Single row operations can be represented by an Elementary Matrix A system of equations written as an Augmented Matrix

Row operation example (these are augmented)

$$\left[\begin{array}{cccc}1& -2& 1& 0\\ 0& 2& -8& 8\\ 5& 0& -5& 0\end{array}\right]\left[\begin{array}{cccc}1& -2& 1& 0\\ 0& 2& -8& 8\\ 0& -10& 10& 10\end{array}\right]\left[\begin{array}{cccc}1& -2& 1& 0\\ 0& 2& -8& 8\\ 0& -10& 10& 10\end{array}\right]\left[\begin{array}{cccc}1& -2& 1& 0\\ 0& 2& -8& 8\\ 0& 0& 30& -30\end{array}\right]$$ $$\left[\begin{array}{cccc}1& -2& 1& 0\\ 0& 1& -4& 4\\ 0& 0& 1& -1\end{array}\right]\left[\begin{array}{cccc}1& -2& 1& 0\\ 0& 1& 0& 0\\ 0& 0& 1& -1\end{array}\right]\left[\begin{array}{cccc}1& 0& 0& 1\\ 0& 1& 0& 0\\ 0& 0& 1& -1\end{array}\right]$$Link to original

Consistent

A linear system is considered consistent if it has $>=1$ solution(s)

Theorem for Consistency

A linear system is consistent iff the last column of the augmented matrix does not have a pivot. This is the same as saying that the RREF of the augmented matrix does not have a row of the form $[0000...|1]$

Moreover, if a linear system is consistent, then it has 1. a unique solution iff there are no free variables. 2. infinitely many solutions that are parameterized by free variables

Row Equivalent

Row Equivalent

If two matrices are row equivalent they have the same solution set, meaning that they have a Bijection through Row Operations

Link to original

Echelon Form

Echelon Form

A rectangular matrix is in echelon form if

1. If there are any, all zero rows are at the bottom
2. The first non-zero entry (leading entry) of a row is to the right of any leading entries in the row above it
3. All elements below a leading entry are zero For reduced row echelon form
4. All leading entries, if any, are equal to 1.
5. Leading entries are the only nonzero entry in their respective column.

Pivot

• A Pivot in a matrix A is a location in A that corresponds to a leading 1 in the RREF of A
• A Pivot column is the column of the pivot

Free Variable

Free variables are the variables of the non-pivot columns

• Any choice of the free variables leads to a solution of the system
• If you have any free variables you do not have a unique solution]

Link to original

Link to original

Vector Equations

Vector Equation

An Equation comprised of Vectors, rather than Scalars.

For example, the vector equation of a Space Curve through ${\mathbb{R}}^3$

$$\begin{array}{c}\vec{r}(t)={\vec{r}}_0+t\vec{\mathbf{v}}\\ {\vec{r}}_0,\vec{\mathbf{v}}\in {\mathbb{R}}^{3}t\in \mathbb{R}\end{array}$$Link to original

Real Number

A Real Number is a Number that represents a continuous quantity.

• $\mathbb{R}$ is all real numbers
  • Contains $\mathbb{Q}$, the Set of Rational Numbers
• ${\mathbb{R}}^n$ is $n$ dimensions of $\mathbb{R}$
• ${\mathbb{R}}^{n\times m}$ is $n$ rows and $m$ columns

Link to original

Linear Combination

Let $c_i\in \mathbb{R}\wedge {\vec{v}}_i\in {\mathbb{R}}^{>=1}$ $c_1{\vec{v}}_1+...c_n{\vec{v}}_n=\vec{B}$ is a linear combination of the $v$ vectors, with weights of the $c$‘s

Link to original

Span

• The Set of all Linear Combinations of the $v$‘s in called the span of the $v$‘s
• e.g.

$$\text{span}(\left[\begin{array}{c}1\\ 0\end{array}\right],\left[\begin{array}{c}0\\ 1\end{array}\right])={\mathbb{R}}^2$$

• any 2 vectors in ${\mathbb{R}}^2$ that are not scalar multiplies of each other span ${\mathbb{R}}^2$ Q: Is $\vec{b}\in SPAN({\vec{a}}_1,{\vec{a}}_2)$

$$\vec{b}=\left[\begin{array}{c}7\\ 4\\ 3\end{array}\right],{\vec{a}}_1=\left[\begin{array}{c}1\\ -2\\ -5\end{array}\right],{\vec{a}}_2=\left[\begin{array}{c}2\\ 5\\ 6\end{array}\right]$$Link to original

$$\left[\begin{array}{ccc}2& 3& 7\\ 1& -1& 5\end{array}\right]\left[\begin{array}{ccc}5& 0& 22\\ 1& -1& 5\end{array}\right]\left[\begin{array}{ccc}1& 0& 22/5\\ 0& 1& 22/5-5\end{array}\right]$$

Homogenous

When an Equation has a “trivial” solution $0$ or $\vec{0}$

Homogenous System

Homogenous System

$\vec{A}\vec{x}=\vec{0}$ Homogenous systems always have a trivial $\vec{0}$ solution, so naturally we would like to know if there are nontrivial, perhaps infinite solutions, namely if there is a free variable and a column with no pivots

Link to original

Homogenous Differential Equation

Homogeneous Differential Equation

A Linear Differential Equation satisfied by $y=0$.

Link to original

Link to original

Linear Independence

Linear Independence

The only solution to $A\vec{x}=\vec{0}$ is the trivial $\vec{0}$ $⟺$ Linearly Independent

Geometric Interpretation

If two vectors are linearly independent, the are not colinear If 3, then not coplanal If 4, not cospacial

Linear Dependence

• Any of the vectors in the set are a linear combination of the others
• If there is a free variable, so there are infinite solutions to the homogenous equation
• If the columns of A are in ${\mathbb{R}}^n$, and there are $n$ basis vectors in ${\mathbb{R}}^n$ (which is always true), then if the amount of columns in A exceeds the amount of basis vectors that exist in that dimension, it means that there are free variables, which indicates linear dependence
• If one or more of the columns of A is $\vec{0}$
• Iff $\det A=0⟺A\text{ is Singular}$

Link to original

Intro to Linear Transformations

Linear Transformation

A Linear transformation is a Transformation where $T:{\mathbb{R}}^n\to {\mathbb{R}}^m,T(\vec{v})=A\vec{v}$

• where $A\in R^{m\times n}$
• Domain of T is ${\mathbb{R}}^n$ (where we start)
• Codomain or target of T is ${\mathbb{R}}^m$
• The vector $T(\vec{x})$ is the image of $\vec{x}$ under T
• The set of all possible images is called the range
• image $\in$ range $\in$ codomain
• When the domain and codomain are both $\mathbb{R}$, you can represent them as a Cartesian Graph in ${\mathbb{R}}^2$, as in a mapping of $\mathbb{R}\to \mathbb{R}$
  • If y is the codomain and x is the domain, the range is the range, the domain is all the images of f(x)
• Addition Rule
  • T(u + v) = T(u) + T(v)
• Multiplication Rule
  • T(c$\vec{v}$) = cT(v)
• Prove a transformation is linear by proving the addition and multiplication rules.
• “Principle of Superposition”
  • If we know $T(e_1)$, …, $T(e_n)$ then we know every T(v)

1-1

Injective

If there is at most one location in the Codomain for every location in the Domain

Link to original

• 1-1 $⟺$ every column of T is a pivot column
• 1-1 iff standard matrix has pivot in every column

Onto

Surjective

If there is a location in the Codomain for every location in the Domain

Link to original

• TLDR: Onto $⟺$ every row of T is a pivot row
• onto iff the standard matrix has a pivot in every row
• The matrix A has columns which span ${\mathbb{R}}^m$.
• The matrix A has all pivotal rows.

Bijective

Bijective

If there is exactly one location in the Codomain for every location in the Domain for the Transformation

Link to original

• Needs square matrix

Matrix Multiplication is a Linear Transformation

$$A=\left[\begin{array}{cc}1& 1\\ 0& 1\\ 1& 1\end{array}\right],\vec{u}=\left[\begin{array}{c}3\\ 4\end{array}\right],\vec{b}=\left[\begin{array}{c}7\\ 5\\ 7\end{array}\right]$$ $$T:{\mathbb{R}}^2\to {\mathbb{R}}^3$$

Compute $T(\vec{u})$

$$A\vec{u}=\left[\begin{array}{cc}1& 1\\ 0& 1\\ 1& 1\end{array}\right]\left[\begin{array}{c}3\\ 4\end{array}\right]=\left[\begin{array}{c}7\\ 4\\ 7\end{array}\right]$$

Calculate $\vec{v}\in {\mathbb{R}}^2$ so that $T(\vec{v})=\vec{b}$

$$A\vec{v}=\vec{b}$$ $$\left[\begin{array}{ccc}1& 1& 7\\ 0& 1& 5\\ 1& 1& 7\end{array}\right]\left[\begin{array}{ccc}1& 0& 2\\ 0& 1& 5\\ 1& 1& 7\end{array}\right]\left[\begin{array}{ccc}1& 0& 2\\ 0& 1& 5\\ 0& 1& 5\end{array}\right]\left[\begin{array}{ccc}1& 0& 2\\ 0& 1& 5\\ 0& 0& 0\end{array}\right]\left[\begin{array}{ccc}1& 0& 2\\ 0& 1& 5\end{array}\right]$$ $$\vec{v}=\left[\begin{array}{c}2\\ 5\end{array}\right]$$

Give a $\vec{c}\in {\mathbb{R}}^3|\neg \exists \vec{v}|T(\vec{v})=\vec{c}$ $\vee$ Give a $\vec{c}$ that is not in the range of $T$ $\vee$ Give a $\vec{c}$ that is not in the span of the columns of $A$ (Same question for all)

Range of $T$ is a bunch of images of the following form:

$$A\vec{v}=\left[\begin{array}{c}{v}_1+v_2\\ v_2\\ v_1+v_2\end{array}\right]$$

For $\vec{c}$ to not be in the range of $T$, it cannot be in the above form, e.g. it can be

$$\left[\begin{array}{c}1\\ 2\\ 3\end{array}\right]$$Link to original

Matrix of Linear Transformations

The standard (basis) vectors

Circular transclusion detected: Mathematics/Algebra/LinearAlgebra/Basis

Basis Vector

A Vector that an element of a Basis for a Vector Space, which is a Set of Linearly Indepedent whose Linear Combinations can represent any vector in that space.

Standard Basis Vector

Standard basis vectors in ${\mathbb{R}}^n$ that have a one entry for each dimension, and zeros for the rest,

• e.g. for ${\mathbb{R}}^3$: $\overrightarrow{e_1},\overrightarrow{e_2},\overrightarrow{e_3}=\hat{i},\hat{j},\hat{k}$
• You could choose any basis for ${\mathbb{R}}^n$ so long as it is linearly independent, but the standard basis for a dimension is the most convienient one

Link to original

Standard Matrix

A standard matrix $A$ is a Matrix that represents a Linear Transformation, where the transformation can be expressed as $T(\vec{x})=A\vec{x}$. It is found by applying the transformation to the Standard Basis Vectorss and using the results as the columns of the matrix $A$

Theorem

Let $T:{\mathbb{R}}^n\to {\mathbb{R}}^m$ be a Linear Transformation. Then there is a unique Matrix $A$ such that $T(\vec{x})=A\vec{x},\vec{x}\in {\mathbb{R}}^n$ In fact, $A$ is a $m\times n$ and its $j^{th}$ column is a vector $T(\overrightarrow{e_j})$ $A=[T(\overrightarrow{e_1}),T(\overrightarrow{e_2}),...T(\overrightarrow{e_n})]$

Example

$$T(\overrightarrow{e_1})=\left[\begin{array}{c}5\\ -7\\ 2\end{array}\right],T(\overrightarrow{e_2})=\left[\begin{array}{c}-3\\ -8\\ 0\end{array}\right]$$ $$A=\left[\begin{array}{cc}T(\overrightarrow{e_1})& T(\overrightarrow{e_2})\end{array}\right]=\left[\begin{array}{cc}5& -3\\ -7& -8\\ 2& 0\end{array}\right]$$

Find standard matrix A for T(x) = 3$\vec{x}$ for x in ${\mathbb{R}}^2$ $A\in {\mathbb{R}}^2$

$$A=\left[\begin{array}{cc}T(\overrightarrow{e_1})& T(\overrightarrow{e_2})\end{array}\right]=\left[\begin{array}{cc}\left[\begin{array}{c}3\\ 0\end{array}\right]& \left[\begin{array}{c}0\\ 3\end{array}\right]\end{array}\right]=\left[\begin{array}{cc}3& 0\\ 0& 3\end{array}\right]$$Link to original

Zero Matrix

A Matrix full of zeroes.

• Multiplying any matrix by the zero matrix yields a zero matrix, though not neccessarily the same zero matrix
• The Zero Vector is a special case

Link to original

Identity Matrix

A Matrix full of zeroes, except for ones on the diagonal.

• Called the Identity matrix, because it follows the Multiplicative Identity Property
• It is denoted as $I$ or $I_n$ to indicate $I_n\in {\mathbb{R}}^{n\times n}$, but $n$ is usually obvious based on context

$$\begin{array}{rl}{I}_1& =\left[\begin{array}{c}1\end{array}\right]\\ I_2& =\left[\begin{array}{cc}1& 0\\ 0& 1\end{array}\right]\\ I_3& =\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right]\\ & ⋮\\ I_n& =\left[\begin{array}{ccccc}1& 0& 0& \cdots & 0\\ 0& 1& 0& \cdots & 0\\ 0& 0& 1& \cdots & 0\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ 0& 0& 0& \cdots & 1\end{array}\right].\end{array}$$Link to original

Circular transclusion detected: Mathematics/Algebra/LinearAlgebra/Zero-Matrix

Circular transclusion detected: Mathematics/Algebra/LinearAlgebra/Identity-Matrix

Matrix

A matrix is a rectangular array of Numbers

Operations

Matrix Addition

• Add elementwise
• Operand matrices must have the same dimensions

Matrix Multiplication

Let $A\in {\mathbb{R}}^{m\times n},B\in {\mathbb{R}}^{n\times p}$

• Then, the $(i,j)$ entry of $AB$ is $\text{A.row}(i)\cdot \text{B.col}(j)$, where we are performing many Dot Products to calculate the matrix product
• Then $AB\in {\mathbb{R}}^{m\times p}$

Multiplication Properties

• $AB\not\equiv BA$
• $AB=AC/⟹B=C$
• $AB=0/⟹A=0\vee B=0$
• $AB=[A{b}_{1}A{b}_2]$

Transpose

$$A=\left[\begin{array}{cc}a& b\\ c& d\\ e& f\end{array}\right],A^T=\left[\begin{array}{ccc}a& b& c\\ d& e& f\end{array}\right]$$

Transpose Properties

• $(A^T{)}^T=A$
• $(A+B{)}^T+A^T+B^T$
• $(sA{)}^T=s(A^T)$
• $(AB{)}^T=B^T{A}^T$

Inverse

• Row reduce $(A|I_n)$ until you get $I_n$ for A
• Keep track of the Elementary Matrix for each Row Operation
• The product of all of the elementary matrices is the inverse of $A$, by definition

$$\begin{array}{c}(E_n{E}_{n-1}...E_1)A=I_n\\ ⟹\\ (E_n{E}_{n-1}...E_1)=A^{-1}\end{array}$$

• $A$ may not be invertible. In this case, you won’t be able to row reduce it to the Identity Matrix

Invertible

You cannot always take the inverse of a matrix. Whether or not it is possible is called Invertibility. See also Invertible Matrix Theorem, Invertibility Theorem.

Invertibility Definition: $A\in {\mathbb{R}}^{n\times n}$ is invertible if $\exists C\in {\mathbb{R}}^{n\times n}s.t.AC=CA=I_n$

• A is invertible $⟹$ A is square
• A is invertible $⟺$ it is row equivalent to the identity
• Linearly dependent $⟺$ Singular

• Mnemonic: After the trial, Johnny Depp was Single

• Linearly independent $⟺$ Invertible

• This is just the inverse of the above
• $A\in {\mathbb{R}}^{n\times n}$ is invertible $⟺\forall \vec{b}\exists !\vec{x}(A\vec{x}=\vec{b})$
  • Basically means that A is Bijective
• $\det (A)\ne 0⟺$ invertible

Inverse Properties

• $(A^{-1}{)}^{-1}=A$
• $(AB{)}^{-1}=B^{-1}{A}^{-1}$
• $(A^T{)}^{-1}=(A^{-1}{)}^T$
• $\det A=\frac{1}{\det A^{-1}}$

$2\times 2$ Inverse Shortcut

$$\text{Let }A=\left[\begin{array}{cc}a& b\\ c& d\end{array}\right]$$ $$\text{then }{A}^{-1}={\left[\begin{array}{cc}a& b\\ c& d\end{array}\right]}^{-1}=\frac{1}{det(A)}\left[\begin{array}{cc}d& -b\\ -c& a\end{array}\right]$$Link to original

Elementary Matrix

An elementary matrix, $E$, is one that differs by $I_n$ by one Row Operation.

Link to original

Singular Matrix

A Matrix that is not Invertible

Link to original

Block Matrix

A Matrix that you write as a matrix of matrices

When doing multiplication with a block matrix, make sure the “receiving” matrix’s entries go first, to respect the lack of commutativity in matrix multiplication. See Multiplication

Link to original

LU Decomposition

If A is an $m\times n$ Matrix that can be row reduced to Echelon Form without row exchanges, then

$$A=LU$$

• where $L\in {\mathbb{R}}^{m\times m}$ is a composition of elementary matrices such that it is a Lower Triangular Matrix where all of its diagonal entries are 1
• $U$ is an Echelon Form of $A$

The Process

Suppose A can be row reduced to echelon form U without interchanging rows, i.e.

$$\begin{array}{rlr}{E}_p...E_{0}A& =U& \\ A& =(E_p...E_0{)}^{-1}UA& =LU\end{array}$$

You can construct $L$ by finding each $E$ and multiplying them all together. Alternatively you can construct $L$ such that the sequence of row operations that convert $A$ to $U$ would convert $L$ to $I$

Link to original

Markov chains

Probability Vector

Some Vector $\vec{x}$ with nonnegative elements that sum to 1

Link to original

Stochastic Matrix

A stochastic matrix is a Square Matrix $P$ whose columns are Probability Vectors.

|det(P)| ⇐ 1, only volume contracting or preserving

Theorem as $k\to \infty$

$${\vec{x}}_{k+1}=P{\vec{x}}_k;k=0,1,2,...$$

If $P$ is a regular stochastic matrix, then $P$ has a unique steady-state vector $\vec{q}$, and $\overrightarrow{x_{k+1}}=P\overrightarrow{x_k}$ converges to $\vec{q}$ as $k\to \infty$; $(P^k\overrightarrow{x_0}{⟶}_{k\to \infty }\vec{q})$ where $P\vec{q}=\vec{q}$

Regular

• Stochastic matrix is regular if there $\exists (k\ge 1)P^k$ strictly has positive entries
• Regular $⟺$ unique steady state vectors
• Irregular $⟺$ $0\le n\ne 1$ steady state vectors

Link to original

Markov Chain

A Markov chain is a sequence of Probability Vectors, and a Stochastic Matrix P , such that:

$$\begin{array}{c}{P}^k\overrightarrow{x_0}={\vec{x}}_k\\ {\vec{x}}_{k+1}=P{\vec{x}}_k\\ k\in {\mathbb{N}}_0\end{array}$$Link to original

Diagonalization

Diagonalization

Diagonal Matrix

A matrix is diagonal if the only non-zero elements, if any, are on the main diagonal.

• If $A$ is diagonal, then $A^k$ is very easy to compute because you simply exponentiate every diagonal element by $k$

Diagonal matrices cannot have $\lambda =0$

Strang

Consider a matrix $A$ with some eigenvalues and eigenvectors. $A\overrightarrow{v_0}={\lambda }_0\overrightarrow{v_0}$ … $A\overrightarrow{v_n}={\lambda }_n\overrightarrow{v_n}$

$$\begin{array}{c}A[\overrightarrow{v_0},...,\overrightarrow{v_n}]=[{\lambda }_0\overrightarrow{v_0},...,{\lambda }_n\overrightarrow{v_n}]\\ A[\overrightarrow{v_0},...,\overrightarrow{v_n}]=[\overrightarrow{v_0},...,\overrightarrow{v_n}]\left[\begin{array}{ccc}{\lambda }_0& & \\ & ...& \\ & & {\lambda }_n\end{array}\right]\\ A=[\overrightarrow{v_0},...,\overrightarrow{v_n}]\left[\begin{array}{ccc}{\lambda }_0& & \\ & ...& \\ & & {\lambda }_n\end{array}\right][\overrightarrow{v_0},...,\overrightarrow{v_n}{]}^{-1}\end{array}$$

Diagonalizable

Orthogonal Diagonalization

Link to original

Diagonalizable

$A\in {\mathbb{R}}^{n\times n}\wedge A=PD{P}^{-1}⟹A$ is diagonalizable, where $D$ is a diagonal matrix

$A$ is diagonalizable $⟺$ $A$ has $n$ linearly independent eigenvectors. i.e.

$$\begin{gathered} A=PD{P}^{-1} \\ ⟺ \\ A=[\overrightarrow{v_1},...,\overrightarrow{v_n}]\left[\begin{array}{ccc}{\lambda }_1& & \\ & ...& \\ & & {\lambda }_n\end{array}\right][\overrightarrow{v_1},...,\overrightarrow{v_n}{]}^{-1} \end{gathered}$$

where $\vec{v}$ vectors are linearly independent eigenvectors, and ${\lambda }_1,...,{\lambda }_n$ are the corresponding eigenvalues, in order.

Distinct Eigenvalues

If $A\in {\mathbb{R}}^{n\times n}$ and has $n$ distinct eigenvalues, then $A$ is diagonalizable

Non-distinct Eigenvalues

You check that the sum of the geometric multiplicities is equal to the size of the matrix. e.g. for

$$\left[\begin{array}{ccc}1& & -1\\ & 2& \\ & & 1\end{array}\right]$$

Find the eigenvalues:

$$\left|\begin{array}{ccc}1-\lambda & & -1\\ & 2-\lambda & \\ & & 1-\lambda \end{array}\right|=(1-\lambda {)}^2(2-\lambda )=0$$ $$\therefore \lambda =1,1,2$$

We know that geomult ⇐ algmult. Therefore $\lambda =2$ has 1 distinct eigenvector. This means $\lambda =1$ has to have 2 distinct eigenvectors to form a basis, so if it doesn’t then the matrix is not diagonalizable.

$$A-I=\left[\begin{array}{ccc}0& & -1\\ & 1& \\ & & 0\end{array}\right]$$

There is only one free columns here. Therefore, the dimension of the Nullspace is one, not two, which means the matrix is not diagonalizable.

Basis of Eigenvectors

$$\begin{array}{c}\text{Express the vector x0=}\left[\begin{array}{c}4\\ 5\end{array}\right]\text{ as a linear combination of the vectors }\\ {\vec{v}}_1=\left[\begin{array}{c}1\\ 1\end{array}\right]\text{ and }\overrightarrow{v_2}=\left[\begin{array}{c}1\\ -1\end{array}\right]\text{ and find the coordinates of }\overrightarrow{x_0}\text{ in the basis}\\ \mathcal{B}=\{\overrightarrow{v_1},\overrightarrow{v_2}\}\\ \\ [\overrightarrow{x_0}{]}_{\mathcal{B}}=?[\overrightarrow{x_0}{]}_{\mathcal{B}}=\left[\begin{array}{c}4.5\\ -0.5\end{array}\right]\\ \\ \sim \\ \\ \text{Let }P=[\overrightarrow{v_1}\overrightarrow{v_2}],D=\left[\begin{array}{cc}1& 0\\ 0& -1\end{array}\right]\\ \\ [A^k{\vec{x}}_0{]}_{\mathcal{B}}=?\text{where }A=PD{P}^{-1},k\in {\mathbb{Z}}^{+}\\ \\ A^k=P{D}^k{P}^{-1}=[\overrightarrow{v_1}\overrightarrow{v_2}]\left[\begin{array}{cc}{1}^k& \\ & (-1{)}^k\end{array}\right][\overrightarrow{v_1}\overrightarrow{v_2}{]}^{-1}\\ [A^k{\vec{x}}_0{]}_{\mathcal{B}}=?\end{array}$$

Misc.

$$\begin{array}{c}\text{Let d(x) be "x is diagonalizable"}\\ \text{Let i(x) be "x is invertible"}\\ d(A)\wedge i(A)⟺d(A^{-1})\wedge i(A^{-1})\end{array}$$Link to original

Complex Eigenvalues

Complex Number

The Complex Numbers are a Number Set denoted by $\mathbb{C}$ that extends the Real Numbers via the Imaginary Unit $i=\sqrt{-1}$

• $\mathbb{C}$ is a Vector Space Isomorphism of ${\mathbb{R}}^2$
• Like ${\mathbb{R}}^2$, the complex numbers can be represented within the Cartesian Plane.
• $\mathbb{C}$ is a closed Algebraic Field

Complex numbers are of the form

$$a+bi$$

• where $a,b\in \mathbb{R}$
• where $i$ is the Imaginary Unit

Euler's Formula

$$z=|z|e^{i\varphi }=|z|(\cos (\varphi )+i\sin (\varphi ))$$ $$z_1{z}_2=(|z_1|e^{i{\varphi }_1})(|z_2|e^{i{\varphi }_2})=(|z_1||z_2|e^{i({\varphi }_1+{\varphi }_2)})$$

• Consequence of Euler’s Identity
• Suppose $z_1$ has an angle ${\varphi }_1$ and $z_2$ has ${\varphi }_2$
• The product $z_1{z}_2$ has angle ${\varphi }_1+{\varphi }_2$, and modulus $|z_1||z_2|$

Link to original

Operations

Binary

Addition

Like adding Vectors in ${\mathbb{R}}^2$

$$\begin{array}{rl}{z}_1+z_2& =\\ (a+bi)+(c+di)& =\\ (a+c)+(b+d)i& \end{array}$$

Subtraction

Like subtracting Vectors in ${\mathbb{R}}^2$

$$\begin{array}{rl}{z}_1-z_2& =\\ (a+bi)-(c+di)& =\\ (a-c)+(b-d)i& \end{array}$$

Multiplication

$$z_1\cdot z_2=(a+bi)\cdot (c+di)=ac-bd+(ad+bc)i$$

Division

$$\frac{z_1}{z_2}=\frac{z_1\overline{z_2}}{|z_2{|}^2}=\frac{(a+bi)(c-di)}{c^2+d^2}=\frac{ac+bd+(bc-ad)i}{c^2+d^2}$$

Unary

Real Component Function

Imaginary Component Function

Argument

$$z=|z|e^{i\varphi }⟹\text{arg}z=\varphi$$

Complex Conjugate

$$\overline{a+bi}=(a+bi{)}^{\ast }=a-bi$$ $$\overline{(z_1+z_2)}=\overline{z_1}+\overline{z_2}$$ $$\overline{(z_1{z}_2)}=\overline{z_1}\overline{z_2}$$ $$\overline{A\vec{z}}=A\overline{\vec{z}}$$

$\text{Im}(z\overline{z})=0$ $z\overline{z}=|z{|}^2$ Reflects across the Real axis.

Magnitude

Also called “Modulus”

$$|a+bi|=\sqrt{a^2+b^2}=\sqrt{(a+bi)(a-bi)}$$

The magnitude is the $r$ in the figure.

Link to original

Circular transclusion detected: Mathematics/SetTheory/Complex-Number

Complex Eigenvalues

Complex Eigenstuff

Complex roots coming in complex conjugate pairs implies that complex Eigenvalues and their Eigenvectors come in complex conjugate pairs. This is because eigenvalues are the solutions to the Characteristic Equation, which is a Polynomial equation.

Link to original

Example

4 of the eigenvalues of a 7 x 7 matrix are -2, 4 + i, -4 - i, and i

• Because there are 3 nonconjugate complex pairs, we know that the remaining eigenvalues are the conjugates of the given complex values
• What is the characteristic polynomial?
• $p(\lambda )=(\lambda +2)(\lambda -(4+i))(\lambda -(-4-i))(\lambda -i)(\lambda -(4-i))(\lambda -(-4+i))(\lambda +i)$

Example

The matrix that rotates vectors by $\frac{\pi }{4}$ radians about the origin and then scales vectors by $\sqrt{2}$ is:

$$\left[\begin{array}{cc}1& -1\\ 1& 1\end{array}\right]$$

What are the eigenvalues of $A$? Find an eigenvector for each eigenvalue

$det(A-\lambda I)=(1-\lambda {)}^2={\lambda }^2-2\lambda +2$ $\lambda =\frac{2\pm \sqrt{4-8}}{2}=\frac{2\pm 2i}{2}=1\pm i$ ${\lambda }^{+}$:

$$\begin{array}{c}A-{\lambda }^{+}I\\ \left[\begin{array}{cc}1-(1+i)& -1\\ 1& 1-(1+i)\end{array}\right]\\ \left[\begin{array}{cc}-i& -1\\ 1& -i\end{array}\right]\\ \left[\begin{array}{cc}1& -i\\ -i& -1\end{array}\right]\\ \left[\begin{array}{cc}1& -i\\ 0& 0\end{array}\right]\to \overrightarrow{v_{+}}=\left[\begin{array}{c}i\\ 1\end{array}\right]\end{array}$$

${\lambda }^{-}$:

$$\begin{array}{c}""""""\to \overrightarrow{v_{-}}=\left[\begin{array}{c}-i\\ 1\end{array}\right]\end{array}$$

Could reason the eigenvalue for ${\lambda }^{-}$ by the fact that eigenvalues and their eigenvectors come in complex conjugate pairs.

Orthogonal Sets

Orthogonal

Perpendicular.

• $\vec{a}$ and $\vec{b}$ are orthogonal if $\vec{a}\cdot \vec{b}=0$

• $||\vec{u}+\vec{w}|{|}^2=||\vec{u}|{|}^2+||\vec{w}|{|}^2\vee \vec{u}\cdot \vec{w}=0⟹\text{Orthogonal}$
• If $W$ is a subspace of ${\mathbb{R}}^n$ and $\vec{z}\in {\mathbb{R}}^n$, $\vec{z}$ is orthogonal to $W$ if it is orthogonal to every vector in $W$
• The set of all vectors orthogonal to a subspace is a itself a subspace, called the Orthogonal Complement of $W$, $W^{\perp }$, W perp
  • $W^{\perp }=\{\vec{z}\in {\mathbb{R}}^n\mid \forall (\vec{w}\in W)\vec{z}\cdot \vec{w}=0\}$
• $dim(RowA)=dim(ColA)$
• $(RowA{)}^{\perp }=NulA$
• $(ColA{)}^{\perp }=Nul(A^T)$

$\vec{x}\in Nul(A)⟺$

• $A\vec{x}=\vec{0}$
• $\vec{x}$ is orthogonal to each row of $A$
• $RowA$ is orthogonal complement to $NulA$
• $dim(RowA)+dim(NulA)=$ number of columns

$\vec{a}\cdot \vec{b}=0\wedge \vec{a}\ne \vec{0},\vec{b}\ne 0⟺\vec{a}\perp \vec{b}⟺a\text{ and }b\text{ are Orthogonal}$

Link to original

Orthogonal Set

A Set of Vectors are an orthogonal set of vectors if every pair in the set is Orthogonal to every other vector in the set.

Linear Independence for Orthogonal Sets

If there is an orthogonal set of vectors $O$, then

$$||c_1\cdot {\vec{u}}_1+\cdots +c_n\cdot {\vec{u}}_n|{|}^2=c_1^2\cdot ||{\vec{u}}_1|{|}^2+\cdots +c_n^2\cdot ||{\vec{u}}_n|{|}^2$$

$\vec{0}\notin O⟹O$ is Linearly Indepedent

Expansion in Orthogonal Basis

If $O$ is the Basis for Subspace $W$ in ${\mathbb{R}}^n$ and $O$ is an orthogonal basis, then for any vector $\vec{w}\in W$

$$\vec{w}=c_1{\vec{u}}_1+\cdots +c_n{\vec{u}}_n$$ $$c_i=\frac{\vec{w}\cdot {\vec{u}}_i}{{\vec{u}}_i\cdot {\vec{u}}_i}$$Link to original

Orthogonal Projection

$${\text{proj}}_{\vec{u}}\vec{v}=\left(\vec{v}\cdot \hat{u}\right)\hat{u}=\frac{\vec{v}\cdot \vec{u}}{||\vec{u}||}\frac{\vec{u}}{||\vec{u}||}=\frac{\vec{v}\cdot \vec{u}}{\vec{u}\cdot \vec{u}}\vec{u}$$ $$\vec{w}=\vec{v}-{\text{proj}}_{\vec{u}}\vec{v}\vec{v}=\vec{w}+{\text{proj}}_{\vec{u}}\vec{v}||\vec{v}|{|}^2=||\vec{w}|{|}^2+||{\text{proj}}_{\vec{u}}\vec{v}|{|}^2$$Link to original

Orthogonal Decomposition

I proceed to define the orthogonal decomposition for some vector $y$, where $y\in {\mathbb{R}}^n$, where $W$ is a subspace of ${\mathbb{R}}^n$, where $W^{\perp }$ is the Orthogonal Complement of $W$, where $\hat{y}$ is the orthogonal projection of $\vec{y}$ onto $W$, and $\vec{z}$ is a vector orthogonal to $\hat{y}$. This is a Vector Decomposition.

$$y=(\hat{y}\in W)+(\vec{z}\in W^{\perp })$$

• Every $y\in {\mathbb{R}}^n$ has a unique sum in the form above, so long as $W$ is a subspace of ${\mathbb{R}}^n$
• $dim(W)+dim(W^{\perp })=n$

Concerning $\hat{y}$

If $\overrightarrow{u_1},\cdots ,\overrightarrow{u_p}$ is an Orthogonal Basis for $W$, then $\hat{y}$, the orthogonal projection of $\vec{y}$ onto $W$ is given by:

$$\begin{array}{c}\hat{y}=pro{j}_W\vec{y}=pro{j}_{\overrightarrow{u_1}}\vec{y}+\cdots +pro{j}_{\overrightarrow{u_p}}\vec{y}=pro{j}_W\vec{y}\end{array}$$

See Best Approximation, but in essence $\hat{y}$ is the closest vector in $W$ to $\vec{y}$

Examples:

HW 6.3 Q1 HW 6.3 Q5 HW 6.3 Q6

Link to original

Best Approximation

$W$ is a subspace of ${\mathbb{R}}^n$, $\vec{y}\in {\mathbb{R}}^n$, $\hat{y}=pro{j}_W\vec{y}$ $⟹$

$$\forall \vec{w}\ne \hat{y}\in W||\vec{y}-\hat{y}||<||\vec{y}-\vec{w}||$$

In other words, $\hat{y}$ is closest vector in $W$ to $\vec{y}$ See Orthogonal Decomposition, especially for the visual interpretation of this.

Link to original

Gram-Schmidt Process

Let $X$ be a set of vectors that form a basis for subspace $W$ of ${\mathbb{R}}^n$, Let $V$ be a set of vectors that form an Orthogonal Basis for $W$ The Gram-Schmidt process defines how $V$ can be derived from $X$ It depends on Orthogonal Decomposition

If $X=\{\overrightarrow{x_1},\cdots \overrightarrow{x_p}\}$, iteratively define vectors in $V=\{\overrightarrow{v_1},\cdots ,{\vec{v}}_p\}$ $\overrightarrow{v_1}=\overrightarrow{x_1}$ $\overrightarrow{v_2}=\overrightarrow{x_2}-pro{j}_{\overrightarrow{v_1}}\overrightarrow{x_2}$ $\overrightarrow{v_3}=\overrightarrow{x_3}-pro{j}_{\overrightarrow{v_1}}\overrightarrow{x_3}-pro{j}_{\overrightarrow{v_2}}\overrightarrow{x_3}$ $\cdots$ ${\vec{v}}_p=\overrightarrow{x_p}-pro{j}_{{\vec{v}}_1}\overrightarrow{x_p}-\cdots -pro{j}_{{\vec{v}}_{p-1}}{\vec{x}}_p$

$${\vec{v}}_p=\overrightarrow{x_p}-\sum _{i=1}^{p-1}{\text{proj}}_{{\vec{v}}_i}{\vec{x}}_p$$

Examples

HW 6.4 Q1 HW 6.4 Q2

Link to original

QR Decomposition

For any $m\times n$ matrix $A$, with Linearly Indepedent columns:

$$A=QR$$

Q is

• m x n
• its columns are an orthonormal basis for Col A R is
• n x n
• upper triangular
• positive diagonal
• $||{\vec{r}}_j||=||{\vec{a}}_j||$ where $\vec{r}$ and $\vec{a}$ are columns of R and A

Link to original

Least Squares

Given

Given many data points, construct a matrix equation in the form of a linear equation (this matrix equation will be overdetermined). The matrix equation below is $A\vec{x}=\vec{b}$ This equation is linear but it doesn’t have to be, just adjust accordingly to represent the equations as a matrix equation.

$$\left[\begin{array}{cc}1& x_0\\ 1& x_1\\ 1& x_2\\ 1& x_3\\ 1& x_4\\ 1& x_5\end{array}\right]\left[\begin{array}{c}b\\ m\end{array}\right]=\left[\begin{array}{c}{y}_0\\ y_1\\ y_2\\ y_3\\ y_4\\ y_5\end{array}\right]$$

Goal

Using Best Approximation, find a vector in subspace $ColA$ closest to $\vec{b}$

$ColA$ is a subspace of ${\mathbb{R}}^n$, $\vec{b}\in {\mathbb{R}}^n$ $\forall \vec{x},\vec{a}=A\vec{x}$, i.e. $\vec{a}\in ColA$ $\hat{b}=A\hat{x}=pro{j}_{ColA}\vec{b}$ Note: Can only use Orthogonal Decomposition for $\hat{b}$ when the columns of A form an orthogonal basis, by definition $⟹$

$$\begin{array}{c}\forall \vec{a}\in ColA,\vec{a}\ne \hat{b}||\vec{b}-\hat{b}||<||\vec{b}-\vec{a}||\\ \forall A\vec{x}\in ColA,A\vec{x}\ne A\hat{x}||\vec{b}-A\hat{x}||<||\vec{b}-A\vec{x}||\end{array}$$

In other words, $\hat{b}=A\hat{x}=pro{j}_{cola}\vec{b}$ is closest vector in $ColA$ to $\vec{b}$ Note: $\hat{x}$ is a unique vector, a special $\vec{x}$ that minimizes the above equation. Note: If the columns of $A$ are orthogonal, then you can just use the scalar projection of $\vec{b}$ onto each column of $A$.

Normal Equations

The least squares solutions to $A\vec{x}=\vec{b}$ corresponds to the solution to

$$A^{T}A\vec{x}=A^T\vec{b}$$

• Turns the $A\vec{x}=\vec{b}$ equation from above and transforms it into a square matrix equation

Derivation

• $(ColA{)}^{\perp }=Null(A^T)$
• $\hat{x}$ is the Least Squares Solution to $A\vec{x}=\vec{b}$ $⟺b-A\hat{x}\perp ColA$
• $\vec{b}-A\hat{x}\perp ColA⟹\vec{b}-A\hat{x}\in (ColA{)}^{\perp }$
• $\vec{b}-A\hat{x}\in (ColA{)}^{\perp }⟹\vec{b}-A\hat{x}\in Nul{A}^T$
• $\vec{b}-A\hat{x}\in Nul{A}^T⟺A^T(\vec{b}-A\hat{x})=0$
• $A^T(b-A\hat{x})=0$
• $A^{T}b-A^{T}A\hat{x}=0$
• $A^{T}A\hat{x}=A^T\vec{b}$

Normal Equation Usage

• Use when non-square matrix
  • Over/Under determined
• Regression

Theorem (Unique Solutions for Least Squares)

If A is m x n

• Ax = b has a unique least squares solution for each b in Rm
• Cols of A are linearly independent
• The matrix A^T A is invertible If the above hold, the unique least square solution is

$$\hat{x}=(A^{T}A{)}^{-1}{A}^T\vec{b}$$

If the above conditions are not true, there may be infinitely many solutions, or some other nonunique amount of solutions, in which case you should consider $[A^{T}A{A}^T\vec{b}]$ instead.

Note: $A^{T}A$ plays the role of the “length squared” of the matrix A

Theorem (Least Squares and QR)

$$\begin{array}{c}A\in {\mathbb{R}}^{m\times n}=QR\\ ⟹\\ \text{Least Squares Solution }\hat{x}=R^{-1}{Q}^T\vec{b}\end{array}$$

Examples

$$\begin{array}{c}A=\left[\begin{array}{cc}4& 0\\ 0& 2\\ 1& 1\end{array}\right],\vec{b}=\left[\begin{array}{c}2\\ 0\\ 11\end{array}\right]\\ \\ A^{T}A=\left[\begin{array}{cc}17& 1\\ 1& 8\end{array}\right]\\ A^T\vec{b}=\left[\begin{array}{c}19\\ 11\end{array}\right]\\ \text{Now setup the Normal Equations:}\\ A^{T}A\vec{x}=A^T\vec{b}\\ \left[\begin{array}{cc}17& 1\\ 1& 8\end{array}\right]\vec{x}=\left[\begin{array}{c}19\\ 11\end{array}\right]\\ \vec{x}={\left[\begin{array}{cc}17& 1\\ 1& 8\end{array}\right]}^{-1}\left[\begin{array}{c}19\\ 11\end{array}\right]\\ \hat{x}=\left[\begin{array}{c}1\\ 2\end{array}\right]\end{array}$$

Hampton Explanation for Least Squares

Let $A\in {\mathbb{R}}^{m\times n}$. $\hat{x}$ is the unique, minimizing solution to the equation $A\vec{x}=\vec{b}$ such that

$$\forall \vec{x}\in {\mathbb{R}}^n||\vec{b}-A\hat{x}||\le ||\vec{b}-A\vec{x}||$$

• Essentially, minimize $\vec{b}-A\hat{x}$
  • $||\vec{b}-\hat{b}||$ is the minimal distance between the different solutions
• $\forall x\in {\mathbb{R}}^n,A\vec{x}\in ColA,\vec{b}{=}^{?}ColA$
• Goal: Find $\hat{x}$ s.t. $A\hat{x}\in ColA$ is closest to $\vec{b}$
• $\hat{x}$ in this context just denotes the special/unique $x$ that minimizes the distances between $\vec{b}$ and $A\hat{x}$ b is closer to Axhat than to Ax for all other x in Col A
• If b in Col A, then xhat is…
• Seek $\hat{x}$ so that $A\hat{x}$ is as close to $\vec{b}$ as possible, i.e. $\hat{x}$ should solve Axhat = bhat
  • $\hat{b}=A\hat{x}=pro{j}_{Col(A)}\vec{b}$

Link to original

Google Page Rank

Stochastic Matrix

Link to original

Symmetric Matrix

Definition

Matrix A is symmetric if A^T = A

The eigenspaces of a symmetric matrix are orthogonal

Link to original

Spectral Decomposition

https://www.youtube.com/watch?v=mhy-ZKSARxI

Symmetric

Recall: If P is an orthogonal n × n matrix, then P −1 = P T , which implies A = PDP^T is diagonalizable and symmetric.

Spectral Thm

An n × n symmetric matrix A has the following properties.

1. All eigenvalues of A are real.
2. The dimenison of each eigenspace is full, that it’s dimension is equal to it’s algebraic multiplicity.
3. The eigenspaces are mutually orthogonal.
4. A can be diagonalized: A = PDP^T , where D is diagonal and P is orthogonal.

Spectal Decomp

Link to original

Orthogonal Diagonalization

Like Diagonalization, but you perform it on an orthogonal matrix, which makes the process easier as follows:

$$S=PD{P}^T$$

Where $P^{-1}=P^T$, i.e. $P$ is orthogonal It is otherwise the same as performing diagonalization on an arbitrary matrix

Link to original

Quadratic Form

Change of variable

Positive Definite Positive Semidefinite Negative Definite Negative Semidefinite

Link to original

Constrained Optimization

Q: When $x^T\cdot u=0$ for the first greatest eigenvalue, and the remaining ones were -2, and 0, the next maximum was -2 instead of 0?

Link to original

Singular Value Decomposition

https://www.youtube.com/watch?v=vSczTbgc8Rc

Applications

• If A is a invertible square matrix then the condition number is the largest singular value divided by the smallest singular value
  • Condition number describes the sensitivity of a solution to Ax = b to errors in A
  • A problem with a low condition number is said to be well-conditioned, while a problem with a high condition number is said to be ill-conditioned
  • Describe difficulty in computing inverse
  • Chaos: small change in input results in massive change in output
• Can use SVD to talk about rkA, ColA, RowA, NulA, $(ColA{)}^{\perp }$, etc.

  • rkA = rk$\Sigma$

  • ColA = U columns through dim A
    • bc $A\vec{v}\propto \vec{u}$
  • Col A perp = U columns after dim A
    • by def
  • Nul A = V columns that correspond to the free columns of U

Process

$A=U\Sigma V^T$ $U$ and $V$ are square, guaranteed.

1. Singular values: $\sqrt{\text{eigenvalues of }{A}^{T}A}$
2. Construct $\Sigma$ using the singular values. $\Sigma$ has the same shape as $A$, with a diagonal matrix of the singular values in the top left corner
3. V = matrix of eigenvectors of $A^{T}A$
4. Compute an orthonormal basis for Col A: use $A\overrightarrow{v_i}={\sigma }_i\overrightarrow{u_i}$ for dim $V$
5. Afterwhich, extend and fill up the remaining orthonormal basis
   1. Option A: Rawdog it$-$think about it, so to speak
   2. Option B: Gram-Schmidt Process
   3. Option C: Use $NulA{A}^T$
6. Construct the columns of $U$ with the $\overrightarrow{u_i}$ vectors
7. Note: for U you can also get it via the V process but with $A{A}^T$, for eigenvalue 0, find eigenvector
8. V and U are orthogonal btw, and they have dimensions of $A^{T}A$ and $A{A}^T$

$$A=\sum _{s=1}^r{\sigma }_s{\vec{u}}_s{\vec{v}}_s^T$$

where ${\vec{u}}_s$, ${\vec{v}}_s$ are the $s^{\text{th}}$ columns of $U$ and $V$

Link to original