Linear Algebra for Machine Learning

Part I - Foundations

1.1 What is a Vector, Really?

In programming, a vector is usually treated as a simple 1D array of numbers. Whereas in linear algebra, a vector is a geometric object in space with both magnitude and direction (or equivalently, a point in space relative to an origin).

To describe that geometric arrow using numbers, we need a coordinate system, which is defined by a set of reference vectors called a basis. The basis vectors define the fundamental directions and step sizes of our grid, while the numbers inside our vector simply tell us how many steps to take along each basis vector.

For example, in the standard 2D Cartesian grid where our basis vectors are $\hat{i} = \begin{bmatrix} 1 \\ 0 \end{bmatrix}$ and $\hat{j} = \begin{bmatrix} 0 \\ 1 \end{bmatrix}$, writing a coordinate vector as $\mathbf{v} = \begin{bmatrix} 4 \\ 2 \end{bmatrix}$ is shorthand for:

$\mathbf{v} = 4\begin{bmatrix} 1 \\ 0 \end{bmatrix} + 2\begin{bmatrix} 0 \\ 1 \end{bmatrix}$

What happens if we switch to a new coordinate system where each unit step on the axes is twice as long i.e. $\mathbf{b}_1 = \begin{bmatrix} 2 \\ 0 \end{bmatrix}$ and $\mathbf{b}_2 = \begin{bmatrix} 0 \\ 2 \end{bmatrix}$ ?

The underlying geometric arrow in space does not change in direction or physical length at all. However, its coordinate representation changes to $\begin{bmatrix} 2 \\ 1 \end{bmatrix}$, because 1 step along our new axes covers 2 units of magnitude:

$\mathbf{v} = 2\begin{bmatrix} 2 \\ 0 \end{bmatrix} + 1\begin{bmatrix} 0 \\ 2 \end{bmatrix} = \begin{bmatrix} 4 \\ 2 \end{bmatrix}$

1.2 Scalars, Vectors, Matrices and Tensors

Before diving into operations, we should know the following terminology:

• Scalar ($x \in \mathbb{R}$): A single real number (like $x = 3.5$). It has magnitude but no direction ($0$-dimensional).

• Vector ($\mathbf{x} \in \mathbb{R}^n$): A 1D ordered collection of $n$ scalars, written by default as a column vector: $\mathbf{x} = \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{bmatrix}$

• Matrix ($A \in \mathbb{R}^{m \times n}$): A 2D rectangular grid of numbers with $m$ rows and $n$ columns. An individual entry at row $i$, column $j$ is written as $A_{ij}$ or $a_{ij}$.

Part II - Operations & Their Meaning

We can understand every vector and matrix operation through two complementary lenses: data accounting (algebraic) and movements in space (geometric).

2.1 Vector Addition, Subtraction and Scalar Multiplication

Vector Addition ($\mathbf{u} + \mathbf{v}$)

Algebraically, adding two vectors means adding their matching components. Imagine a 2D vector as a receipt tracking two quantities: $\begin{bmatrix} \text{apples} \\ \text{dollars spent} \end{bmatrix}$.

• On your first trip to a fruit stand, you buy 2 apples for $1: $\mathbf{u} = \begin{bmatrix} 2 \\ 1 \end{bmatrix}$.
• On a second trip to a wholesale stall, you buy 6 apples for $2: $\mathbf{v} = \begin{bmatrix} 6 \\ 2 \end{bmatrix}$.

To find your combined haul and total spend, you add apples to apples and dollars to dollars:

$\mathbf{u} + \mathbf{v} = \begin{bmatrix} 2 \\ 1 \end{bmatrix} + \begin{bmatrix} 6 \\ 2 \end{bmatrix} = \begin{bmatrix} 2 + 6 \\ 1 + 2 \end{bmatrix} = \begin{bmatrix} 8 \\ 3 \end{bmatrix}$

Geometrically, if we plot Apples on the horizontal axis and Dollars on the vertical axis, this is the tip-to-tail rule: start at the origin $(0,0)$, walk along arrow $\mathbf{u}$ to $(2,1)$, and then place the tail of arrow $\mathbf{v}$ at the arrowhead of $\mathbf{u}$. Drawing a straight line from the origin to the final arrowhead lands us at $(8,3)$.

Scalar Multiplication ($c\mathbf{u}$)

Multiplying a vector by a scalar $c \in \mathbb{R}$ scales every component proportionally.

Using our first receipt $\mathbf{u} = \begin{bmatrix} 2 \\ 1 \end{bmatrix}$ (2 apples for $1), scaling linearly means the rate stays constant:

• If I hand you $3 instead of $1 ($c = 3$), you get $3\begin{bmatrix} 2 \\ 1 \end{bmatrix} = \begin{bmatrix} 6 \\ 3 \end{bmatrix}$ (6 apples for $3).
• If I hand you $1.50 ($c = 1.5$), you get $1.5\begin{bmatrix} 2 \\ 1 \end{bmatrix} = \begin{bmatrix} 3 \\ 1.5 \end{bmatrix}$ (3 apples for $1.50).

Geometrically, scalar multiplication stretches or shrinks the vector along the exact same straight line passing through the origin:

• $\vert{}c\vert{} > 1$ stretches the arrow.
• $0 < \vert{}c\vert{} < 1$ shrinks the arrow.
• $c < 0$ flips the arrow's direction by $180^\circ$ (like returning the apples for a refund).

Vector Subtraction ($\mathbf{u} - \mathbf{v}$)

Subtraction is simply adding the opposite vector: $\mathbf{u} - \mathbf{v} = \mathbf{u} + (-1)\mathbf{v}$.

Geometrically, there are two ways to visualize $\mathbf{u} - \mathbf{v}$:

1. Flip and add tip-to-tail: Reverse the direction of $\mathbf{v}$ and attach its tail to the tip of $\mathbf{u}$.
2. Tip-to-tip displacement: Draw both $\mathbf{u}$ and $\mathbf{v}$ starting from the origin. The vector $\mathbf{u} - \mathbf{v}$ is the arrow starting at the tip of $\mathbf{v}$ and pointing straight to the tip of $\mathbf{u}$ (because $\mathbf{v} + (\mathbf{u} - \mathbf{v}) = \mathbf{u}$).

2.2 Modulus (Length) and the Dot Product

Modulus (Vector Length)

The modulus of a vector, written as $\|\mathbf{u}\|$ or $|\mathbf{u}|$, is the straight-line distance from the origin to the vector's tip. It captures pure magnitude and ignores direction.

By the Pythagorean theorem in $n$ dimensions:

Because each component is squared, negative signs vanish meaning $\mathbf{u}$ and $-\mathbf{u}$ have the exact same modulus.

The Dot Product ($\mathbf{u} \cdot \mathbf{v}$)

The dot product takes two vectors of the same dimension and collapses them into a single scalar.

Because lengths $\|\mathbf{u}\|$ and $\|\mathbf{v}\|$ are always positive, the sign of the dot product is controlled entirely by $\cos\theta$:

• $\mathbf{u} \cdot \mathbf{v} > 0$ ($\theta$ is less than $90^\circ$): They point in generally the same direction.
• $\mathbf{u} \cdot \mathbf{v} = 0$ ($\theta = 90^\circ$): The vectors are orthogonal (perpendicular).
• $\mathbf{u} \cdot \mathbf{v} < 0$ ($\theta$ is greater than $90^\circ$): They point in opposing directions.

2.3 Scalar and Vector Projections

Imagine shining a flashlight directly perpendicular to vector $\mathbf{a}$. Vector $\mathbf{b}$ will cast a shadow onto the line of $\mathbf{a}$. Finding that shadow is called projection.

1. Scalar Projection (Length of the Shadow)

From basic right-triangle trigonometry, if $\theta$ is the angle between $\mathbf{a}$ and $\mathbf{b}$, the signed length $s$ of the shadow of $\mathbf{b}$ along $\mathbf{a}$ is:

$s = \|\mathbf{b}\| \cos\theta$

Since we know $\mathbf{a} \cdot \mathbf{b} = \|\mathbf{a}\|\|\mathbf{b}\|\cos\theta$, we can substitute $\cos\theta = \frac{\mathbf{a} \cdot \mathbf{b}}{\|\mathbf{a}\|\|\mathbf{b}\|}$ to eliminate the angle $\theta$ completely:

$\text{comp}_{\mathbf{a}}(\mathbf{b}) = \|\mathbf{b}\| \left(\frac{\mathbf{a} \cdot \mathbf{b}}{\|\mathbf{a}\|\|\mathbf{b}\|}\right) = \frac{\mathbf{a} \cdot \mathbf{b}}{\|\mathbf{a}\|}$

2. Vector Projection (The Shadow as an Arrow)

The scalar projection gives us a number (how long the shadow is). To turn that length into an actual vector pointing in the direction of $\mathbf{a}$, we multiply the scalar length by the unit vector in the direction of $\mathbf{a}$ (which is $\hat{\mathbf{a}} = \frac{\mathbf{a}}{\|\mathbf{a}\|}$):

$\text{proj}_{\mathbf{a}}(\mathbf{b}) = \left(\frac{\mathbf{a} \cdot \mathbf{b}}{\|\mathbf{a}\|}\right) \frac{\mathbf{a}}{\|\mathbf{a}\|} = \left(\frac{\mathbf{a} \cdot \mathbf{b}}{\|\mathbf{a}\|^2}\right)\mathbf{a} = \left(\frac{\mathbf{a} \cdot \mathbf{b}}{\mathbf{a} \cdot \mathbf{a}}\right)\mathbf{a}$

Notice that the fraction $\frac{\mathbf{a} \cdot \mathbf{b}}{\mathbf{a} \cdot \mathbf{a}}$ is just a single scalar that scales vector $\mathbf{a}$.

2.4 Matrix Multiplication, Transpose, Identity and Inverses

Matrix Multiplication

Earlier, we dotted a quantity vector $\mathbf{q} = \begin{bmatrix} 4 & 3 \end{bmatrix}$ with a price vector $\mathbf{p} = \begin{bmatrix} 2 \\ 5 \end{bmatrix}$ to get a single bill.

Now suppose two people go shopping for apples and oranges, and they want to compare their total bills across two different stores (Store 1 and Store 2):

• Quantities Matrix ($Q$): Each row is a person's shopping list $\begin{bmatrix} \text{apples} & \text{oranges} \end{bmatrix}$. $$Q = \begin{bmatrix} 4 & 3 \\ 2 & 6 \end{bmatrix} \begin{matrix} \leftarrow \text{Person A} \\ \leftarrow \text{Person B} \end{matrix}$$
• Prices Matrix ($P$): Each column is a store's price list $\begin{bmatrix} \text{apple price} \\ \text{orange price} \end{bmatrix}$. $$P = \begin{bmatrix} 2 & 3 \\ 5 & 4 \end{bmatrix} \begin{matrix} \text{(Col 1: Store 1, Col 2: Store 2)} \end{matrix}$$

To find every person's bill at every store, we compute $QP$ by taking the dot product of each row of $Q$ with each column of $P$:

$QP = \begin{bmatrix} 4 & 3 \\ 2 & 6 \end{bmatrix} \begin{bmatrix} 2 & 3 \\ 5 & 4 \end{bmatrix} = \begin{bmatrix} (4\cdot 2 + 3\cdot 5) & (4\cdot 3 + 3\cdot 4) \\ (2\cdot 2 + 6\cdot 5) & (2\cdot 3 + 6\cdot 4) \end{bmatrix} = \begin{bmatrix} 23 & 24 \\ 34 & 30 \end{bmatrix}$

Transpose ($A^T$)

The transpose of a matrix $A$, written $A^T$, flips the matrix over its main diagonal - turning rows into columns and columns into rows: $(A^T)_{ij} = A_{ji}$.

• It also connects dot products to matrix multiplication: for column vectors $\mathbf{a}, \mathbf{b} \in \mathbb{R}^n$, turning $\mathbf{a}$ into a row vector $\mathbf{a}^T$ lets us write the dot product as $\mathbf{a} \cdot \mathbf{b} = \mathbf{a}^T \mathbf{b}$.
• Reversal rule: When transposing a product, the order reverses: $(AB)^T = B^T A^T$.

Identity Matrix ($I$) and Matrix Inverse ($A^{-1}$)

• Identity Matrix ($I_n$): A square $n \times n$ matrix with $1$s on the main diagonal and $0$s everywhere else. It acts like the number $1$ in multiplication: for any vector $\mathbf{x}$, $I\mathbf{x} = \mathbf{x}$ (it leaves space untouched). $I_2 = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}$
• Inverse Matrix ($A^{-1}$): If a matrix $A$ transforms vector $\mathbf{x}$ into $\mathbf{y}$ ($A\mathbf{x} = \mathbf{y}$), the inverse matrix $A^{-1}$ is the "undo button" that takes $\mathbf{y}$ back to $\mathbf{x}$: $$A^{-1}A = AA^{-1} = I$$ Not all matrices have an inverse! As we will see in Part IV, if a matrix squashes 2D space flat onto a 1D line, you cannot "un-squash" it uniquely.

Part III - Vector Spaces, Basis and Transformations

3.1 Linear Combinations and Span

Given a set of vectors $\{\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_k\}$, any expression where we scale each vector by a scalar and add them together is called a linear combination:

$\mathbf{w} = c_1\mathbf{v}_1 + c_2\mathbf{v}_2 + \dots + c_k\mathbf{v}_k$

The span of those vectors is the set of all possible vectors you can reach by trying every possible combination of scalars $c_1, \dots, c_k \in \mathbb{R}$:

• The span of a single non-zero vector in $\mathbb{R}^3$ is a straight line through the origin.
• The span of two non-collinear vectors in $\mathbb{R}^3$ is a flat 2D plane (a subspace) slicing through the origin.
• The span of three vectors that don't lie on the same plane fills the entire 3D space $\mathbb{R}^3$.

3.2 Linear Independence vs Dependence

Suppose you are in 2D space with two vectors: $\mathbf{v}_1 = \begin{bmatrix} 1 \\ 0 \end{bmatrix}$ and $\mathbf{v}_2 = \begin{bmatrix} 0 \\ 1 \end{bmatrix}$. With these two arrows, you can already reach every single point in $\mathbb{R}^2$.

What if someone hands you a third vector $\mathbf{v}_3 = \begin{bmatrix} 3 \\ 2 \end{bmatrix}$? Does $\mathbf{v}_3$ allow you to reach any new territory? No, because you could already build $\mathbf{v}_3$ using $\mathbf{v}_1$ and $\mathbf{v}_2$:

$\mathbf{v}_3 = 3\mathbf{v}_1 + 2\mathbf{v}_2$

When one vector in a set can be written as a linear combination of the others, the set is linearly dependent. It contains redundant information.

Formally, a set of vectors $\{\mathbf{v}_1, \dots, \mathbf{v}_k\}$ is linearly independent if no vector in the set can be built from the others or equivalently, the only way to combine them to get the zero vector is to set every weight to zero:

$c_1\mathbf{v}_1 + c_2\mathbf{v}_2 + \dots + c_k\mathbf{v}_k = \mathbf{0} \iff c_1 = c_2 = \dots = c_k = 0$

3.3 Basis, Dimension and Matrices as Transformations

A basis of a vector space is a set of vectors that satisfies two strict conditions simultaneously:

1. They span the space (enough vectors to reach everywhere).
2. They are linearly independent (no redundant vectors).

The number of vectors in a basis is the dimension of the space.

Matrices as Linear Transformations

Why do we care so much about basis vectors? Because multiplying a matrix $A$ by a vector $\mathbf{x}$ is actually a change of basis / space transformation.

Consider multiplying a $2 \times 2$ matrix $A = \begin{bmatrix} a & b \\ c & d \end{bmatrix}$ by our standard basis vectors $\hat{i} = \begin{bmatrix} 1 \\ 0 \end{bmatrix}$ and $\hat{j} = \begin{bmatrix} 0 \\ 1 \end{bmatrix}$:

$A\hat{i} = \begin{bmatrix} a & b \\ c & d \end{bmatrix}\begin{bmatrix} 1 \\ 0 \end{bmatrix} = \begin{bmatrix} a \\ c \end{bmatrix} \quad (\text{Column 1 of } A)$

$A\hat{j} = \begin{bmatrix} a & b \\ c & d \end{bmatrix}\begin{bmatrix} 0 \\ 1 \end{bmatrix} = \begin{bmatrix} b \\ d \end{bmatrix} \quad (\text{Column 2 of } A)$

Consequently, for any vector $\mathbf{x} = \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = x_1\hat{i} + x_2\hat{j}$, multiplying $A\mathbf{x}$ just takes that exact same recipe ($x_1$ steps of the first column, plus $x_2$ steps of the second column) using the new landed basis vectors:

$A\mathbf{x} = x_1 \begin{bmatrix} a \\ c \end{bmatrix} + x_2 \begin{bmatrix} b \\ d \end{bmatrix}$

Common $2 \times 2$ geometric transformations include:

• Scaling by $k$ along $x$: $\begin{bmatrix} k & 0 \\ 0 & 1 \end{bmatrix}$
• Horizontal Shear: $\begin{bmatrix} 1 & k \\ 0 & 1 \end{bmatrix}$ ($\hat{i}$ stays put, $\hat{j}$ tilts to $\begin{bmatrix} k \\ 1 \end{bmatrix}$)
• Counterclockwise Rotation by angle $\theta$: $\begin{bmatrix} \cos\theta & -\sin\theta \\ \sin\theta & \cos\theta \end{bmatrix}$

3.4 Changing Basis ($B^{-1}$)

Suppose a friend uses a custom coordinate grid with basis vectors $\mathbf{b}_1 = \begin{bmatrix} 3 \\ 1 \end{bmatrix}$ and $\mathbf{b}_2 = \begin{bmatrix} 1 \\ 2 \end{bmatrix}$ (measured in our standard grid). We pack their basis vectors into the columns of a basis matrix $B$:

$B = \begin{bmatrix} 3 & 1 \\ 1 & 2 \end{bmatrix}$

1. From their grid to our standard grid: If a vector has coordinates $[\mathbf{v}]_B = \begin{bmatrix} 2 \\ 1 \end{bmatrix}$ in their grid, what is it in our standard grid? It's $2\mathbf{b}_1 + 1\mathbf{b}_2$, which is simply matrix multiplication by $B$:

2. From our standard grid to their grid: What if we have $\mathbf{v}_{\text{std}} = \begin{bmatrix} 7 \\ 4 \end{bmatrix}$ in standard coordinates and want to find its coordinates in their basis $B$? We multiply by the inverse $B^{-1}$ to run the translation backward:

3.5 Orthogonal Matrices & The Gram-Schmidt Process

Changing basis with $B^{-1}$ requires computing a matrix inverse, which is computationally expensive when dimensions get huge.

Is there a "dream basis" where we never have to compute a messy inverse? Yes: an orthonormal basis, where every basis vector $\mathbf{q}_i$ has unit length ($\Vert{}\mathbf{q}_i\Vert{} = 1$) and is mutually orthogonal (perpendicular) to every other basis vector ($\mathbf{q}_i \cdot \mathbf{q}_j = 0$ for $i \neq j$).

When we pack orthonormal basis vectors into the columns of a matrix $Q$, we get an orthogonal matrix. Look what happens when we multiply $Q^T Q$:

• Diagonal entries are $\mathbf{q}_i^T \mathbf{q}_i = \mathbf{q}_i \cdot \mathbf{q}_i = 1$.
• Off-diagonal entries are $\mathbf{q}_i^T \mathbf{q}_j = \mathbf{q}_i \cdot \mathbf{q}_j = 0$.

Therefore:

$Q^T Q = I \implies Q^{-1} = Q^T$

For an orthogonal matrix, inverting it is as effortless as taking its transpose! Geometrically, orthogonal matrices represent pure rigid rotations and reflections i.e. they preserve all vector lengths ($\Vert{}Q\mathbf{x}\Vert{} = \Vert{}\mathbf{x}\Vert{}$) and angles.

The Gram-Schmidt Process

If we are given a set of linearly independent vectors $\{\mathbf{v}_1, \mathbf{v}_2, \mathbf{v}_3\}$ that are tilted at awkward angles, the Gram-Schmidt process constructs a clean orthonormal basis $\{\mathbf{e}_1, \mathbf{e}_2, \mathbf{e}_3\}$ one vector at a time using projections:

1. First vector: Just normalize $\mathbf{v}_1$ to unit length: $\mathbf{u}_1 = \mathbf{v}_1, \quad \mathbf{e}_1 = \frac{\mathbf{u}_1}{\Vert{}\mathbf{u}_1\Vert{}}$
2. Second vector: Take $\mathbf{v}_2$ and subtract off its shadow (projection) onto $\mathbf{e}_1$. Whatever is left over is guaranteed to be strictly perpendicular to $\mathbf{e}_1$! Then normalize it: $\mathbf{u}_2 = \mathbf{v}_2 - (\mathbf{v}_2 \cdot \mathbf{e}_1)\mathbf{e}_1, \quad \mathbf{e}_2 = \frac{\mathbf{u}_2}{\Vert{}\mathbf{u}_2\Vert{}}$
3. Third vector: Take $\mathbf{v}_3$ and subtract off its shadows onto both $\mathbf{e}_1$ and $\mathbf{e}_2$, then normalize:

Part IV - Solving Linear Systems

4.1 Two Ways to Read $A\mathbf{x} = \mathbf{b}$

Consider a system of linear equations:

$\begin{aligned} 2x_1 + x_2 &= 5 \\ x_1 + 3x_2 &= 5 \end{aligned} \iff \begin{bmatrix} 2 & 1 \\ 1 & 3 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = \begin{bmatrix} 5 \\ 5 \end{bmatrix}$

We can interpret $A\mathbf{x} = \mathbf{b}$ in two ways:

1. The Row Picture (Intersecting Lines/Planes): Each row is the equation of a line (in 2D) or a plane (in 3D). Solving the system means finding the intersection point $(x_1, x_2)$ that satisfies all equations at once.
2. The Column Picture (Linear Combination of Columns): We are looking for the weights $x_1, x_2$ to combine the column vectors of $A$ to land on target $\mathbf{b}$:

Here, $x_1 = 2, x_2 = 1$ works!

4.2 Gaussian Elimination & Row Echelon Form

For larger systems, we solve $A\mathbf{x} = \mathbf{b}$ systematically using Gaussian Elimination. We write an augmented matrix $[A \mid \mathbf{b}]$ and apply valid row operations (swapping rows, scaling a row, or subtracting a multiple of one row from another) until the matrix is in Row Echelon Form (staircase of zeros below the diagonal).

Let's solve our $2 \times 2$ system step by step:

1. Subtract $\frac{1}{2} \times \text{Row 1}$ from $\text{Row 2}$ to eliminate the bottom-left entry: $\left[\begin{array}{cc|c} 2 & 1 & 5 \\ 0 & 2.5 & 2.5 \end{array}\right]$
2. Divide $\text{Row 2}$ by $2.5$ to get a leading $1$ (pivot): $\left[\begin{array}{cc|c} 2 & 1 & 5 \\ 0 & 1 & 1 \end{array}\right] \implies x_2 = 1$
3. Back-substitute $x_2 = 1$ into Row 1 ($2x_1 + 1 = 5 \implies x_1 = 2$).

(If we continue eliminating entries above the diagonal until the left side becomes the Identity matrix $I$, we get Reduced Row Echelon Form. Performing the exact same steps on $[A \mid I]$ until it becomes $[I \mid A^{-1}]$ is how we compute the inverse matrix $A^{-1}$)

4.3 Determinants, Rank and Existence of Solutions

What is the Determinant ($\det(A)$ or $\vert{}A\vert{}$)?

Geometrically, the determinant of a transformation matrix $A$ measures the factor by which the transformation scales area (in 2D) or volume (in 3D).

• Start with a $1 \times 1$ unit square formed by $\hat{i} = \begin{bmatrix} 1 \\ 0 \end{bmatrix}$ and $\hat{j} = \begin{bmatrix} 0 \\ 1 \end{bmatrix}$ (Area $= 1$).
• After transforming by $A = \begin{bmatrix} a & b \\ c & d \end{bmatrix}$, that unit square becomes a parallelogram spanned by $\begin{bmatrix} a \\ c \end{bmatrix}$ and $\begin{bmatrix} b \\ d \end{bmatrix}$, whose signed area is: $\det(A) = ad - bc$
• If $\det(A) < 0$, space was flipped inside-out (like a mirror reflection reversing the orientation of the axes).
• Crucial Case ($\det(A) = 0$): If the area of the transformed parallelogram is zero, it means the two columns of $A$ are collinear (linearly dependent)! The transformation has squashed 2D space flat onto a 1D line (or a single point). Once space is flattened, information is permanently lost i.e you cannot reverse the transformation. Such a matrix is called singular (non-invertible).

Rank and Solution Cases

The rank of a matrix is the number of linearly independent columns (or rows) which equals the number of non-zero pivot rows after Gaussian elimination. Geometrically, rank is the true dimension of the output space after transformation.

For an $n \times n$ system $A\mathbf{x} = \mathbf{b}$:

1. Full Rank ($\text{rank}(A) = n$, $\det(A) \neq 0$): The columns span the entire space. There is exactly one unique solution $\mathbf{x} = A^{-1}\mathbf{b}$ for every target $\mathbf{b}$.
2. Rank Deficient ($\text{rank}(A) < n$, $\det(A) = 0$): Space collapses onto a lower-dimensional subspace (like a plane collapsing into a line):
   • No solution (Inconsistent): Target $\mathbf{b}$ lies outside the collapsed line/plane that $A$ can reach.
   • Infinitely many solutions: Target $\mathbf{b}$ happens to lie on the collapsed line/plane, so an entire line or plane of input vectors all get squashed onto $\mathbf{b}$.

Part V - Eigenvalues and Eigenvectors

5.1 The Eigenvalue Equation & Geometric Meaning

When you apply a linear transformation matrix $A$ to space, almost every vector gets knocked off its original line of action changing both its direction and its length.

However, certain special vectors refuse to get knocked off their line. When $A$ multiplies one of these special vectors $\mathbf{v}$, the output $A\mathbf{v}$ points along the exact same line as $\mathbf{v}$ it only gets stretched, shrunk or flipped by a scalar factor $\lambda$:

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

• $\mathbf{v}$ (any non-zero vector satisfying this) is called an eigenvector ("characteristic vector").
• $\lambda$ is its corresponding eigenvalue (the scaling factor along that invariant direction).

Geometric Intuition:

• Pure Scaling along $x$ and $y$: The eigenvectors are simply the $x$-axis and $y$-axis themselves.
• Horizontal Shear $\begin{bmatrix} 1 & k \\ 0 & 1 \end{bmatrix}$: Every vector with a vertical component gets tilted sideways. Only vectors lying strictly along the horizontal $x$-axis stay on their own line ($\lambda = 1$).
• 3D Rotation: If you spin a globe in 3D space, almost every vector moves to a new direction except vectors lying along the axis of rotation, which stay completely fixed ($\lambda = 1$)!

5.2 Deriving the Characteristic Polynomial

How do we algebraically solve $A\mathbf{v} = \lambda\mathbf{v}$ when both $\lambda$ and $\mathbf{v}$ are unknown?

1. First, insert the identity matrix $I$ so we can subtract the right side from the left (since you cannot subtract a scalar $\lambda$ directly from a matrix $A$, we write $\lambda\mathbf{v} = \lambda I \mathbf{v}$): $A\mathbf{v} - \lambda I \mathbf{v} = \mathbf{0}$
2. Factor out $\mathbf{v}$: $(A - \lambda I)\mathbf{v} = \mathbf{0}$
3. Look closely at $(A - \lambda I)\mathbf{v} = \mathbf{0}$. Obviously, $\mathbf{v} = \mathbf{0}$ works, but the zero vector has no direction, so we ban $\mathbf{v} = \mathbf{0}$ by definition. For a matrix $(A - \lambda I)$ to squash a non-zero vector $\mathbf{v}$ onto the origin $\mathbf{0}$, that matrix must collapse space meaning it must be singular!
4. A matrix is singular if and only if its determinant is zero: $\det(A - \lambda I) = 0$

This equation, $\det(A - \lambda I) = 0$, is called the characteristic equation.

Worked Numerical Example

Let's find the eigenvalues and eigenvectors of:

$A = \begin{bmatrix} 4 & 1 \\ 2 & 3 \end{bmatrix}$

Step 1: Solve $\det(A - \lambda I) = 0$ for $\lambda$.

$A - \lambda I = \begin{bmatrix} 4 - \lambda & 1 \\ 2 & 3 - \lambda \end{bmatrix}$

$\det(A - \lambda I) = (4 - \lambda)(3 - \lambda) - (1)(2) = \lambda^2 - 7\lambda + 12 - 2 = \lambda^2 - 7\lambda + 10 = 0$

Factoring the quadratic:

$(\lambda - 5)(\lambda - 2) = 0 \implies \lambda_1 = 5, \quad \lambda_2 = 2$

Step 2: Substitute each $\lambda$ back into $(A - \lambda I)\mathbf{v} = \mathbf{0}$ to find the eigenvectors.

• For $\lambda_1 = 5$: $\begin{bmatrix} 4 - 5 & 1 \\ 2 & 3 - 5 \end{bmatrix}\begin{bmatrix} v_1 \\ v_2 \end{bmatrix} = \begin{bmatrix} -1 & 1 \\ 2 & -2 \end{bmatrix}\begin{bmatrix} v_1 \\ v_2 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \end{bmatrix}$ Both rows state that $-v_1 + v_2 = 0 \implies v_1 = v_2$. Picking $v_1 = 1$ gives our first eigenvector: $\mathbf{v}_1 = \begin{bmatrix} 1 \\ 1 \end{bmatrix}$ (Any non-zero multiple of $\begin{bmatrix} 1 \\ 1 \end{bmatrix}$ lies on the same line and is an equally valid eigenvector).

• For $\lambda_2 = 2$: $\begin{bmatrix} 4 - 2 & 1 \\ 2 & 3 - 2 \end{bmatrix}\begin{bmatrix} v_1 \\ v_2 \end{bmatrix} = \begin{bmatrix} 2 & 1 \\ 2 & 1 \end{bmatrix}\begin{bmatrix} v_1 \\ v_2 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \end{bmatrix}$ This states $2v_1 + v_2 = 0 \implies v_2 = -2v_1$. Picking $v_1 = 1$ gives our second eigenvector: $\mathbf{v}_2 = \begin{bmatrix} 1 \\ -2 \end{bmatrix}$

5.3 Diagonalization ($A = PDP^{-1}$) and Matrix Powers

Why are eigenvectors the crown jewel of this course? Because if an $n \times n$ matrix $A$ has $n$ linearly independent eigenvectors, we can use those eigenvectors as our new coordinate basis!

Let $P$ be the basis matrix whose columns are the eigenvectors $[\mathbf{v}_1 \mid \mathbf{v}_2]$, and let $D$ be the diagonal matrix containing the eigenvalues on the diagonal:

$P = \begin{bmatrix} 1 & 1 \\ 1 & -2 \end{bmatrix}, \quad D = \begin{bmatrix} 5 & 0 \\ 0 & 2 \end{bmatrix}$

In the eigenvector basis, the matrix $A$ doesn't rotate or shear anything it just scales along the axes by $\lambda_1$ and $\lambda_2$. Therefore, applying $A$ is equivalent to:

1. $P^{-1}$: Change coordinates from the standard basis into the eigenvector basis.
2. $D$: Scale each coordinate directly by $\lambda_i$.
3. $P$: Convert coordinates back from the eigenvector basis to the standard basis.

Written as an equation, this is Eigendecomposition (Diagonalization):

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

The Superpower: Computing $A^k$ Instantly

Suppose we need to apply transformation $A$ $100$ times ($A^{100}$) for example, simulating a system over $100$ time steps or running Google's PageRank web-surfer algorithm to steady state. Multiplying a dense matrix $100$ times is slow and messy, but in diagonalized form, the interior $P^{-1}P$ terms cancel out like dominoes:

$A^2 = (PDP^{-1})(PDP^{-1}) = PD(P^{-1}P)DP^{-1} = PD^2P^{-1}$

$A^k = P D^k P^{-1} = P \begin{bmatrix} \lambda_1^k & 0 \\ 0 & \lambda_2^k \end{bmatrix} P^{-1}$

Raising a diagonal matrix $D$ to the $k$-th power simply raises its individual diagonal numbers to the $k$-th power!

(Note: When a matrix $A$ is symmetric ($A = A^T$), its eigenvectors are guaranteed to be mutually orthogonal, meaning our eigenvector basis matrix becomes an orthogonal matrix $Q$ where $Q^{-1} = Q^T$, giving $A = QDQ^T$ known as the Spectral Theorem).

5.4 Verifying Everything in Python (NumPy)

Here is a brief, self-contained script verifying our projections, Gram-Schmidt orthogonalization and eigendecomposition from the examples above:

import numpy as np

np.set_printoptions(precision=4, suppress=True)

A = np.array([[4.0, 1.0],
              [2.0, 3.0]])

eigenvalues, P = np.linalg.eig(A)

# Sort descending so the order matches the hand calculation (5, then 2)
order = np.argsort(eigenvalues)[::-1]
eigenvalues, P = eigenvalues[order], P[:, order]

D = np.diag(eigenvalues)
P_inv = np.linalg.inv(P)

print("Eigenvalues:", eigenvalues)  # [5. 2.]
print("A = P D P^-1 holds:", np.allclose(A, P @ D @ P_inv))

# Trace / determinant sanity check
print("Sum of eigenvalues == trace:", np.isclose(eigenvalues.sum(), np.trace(A)))
print("Product of eigenvalues == det:", np.isclose(eigenvalues.prod(), np.linalg.det(A)))

# Compare with hand-computed eigenvectors [1, 1] and [1, -2].
# NumPy normalises to unit length (and may flip sign), so compare directions only.
P_hand = np.array([[1.0, 1.0],
                   [1.0, -2.0]])
for i in range(2):
    v = P_hand[:, i]
    is_eigvec = np.allclose(A @ v, eigenvalues[i] * v)
    same_dir = np.allclose(np.abs(v / np.linalg.norm(v)), np.abs(P[:, i]))
    print(f"Hand eigenvector {v}: A v = lambda v -> {is_eigvec}, same direction as NumPy's -> {same_dir}")

# Fast matrix powers: A^k = P D^k P^-1
k = 5
A_direct = np.linalg.matrix_power(A, k)
A_eigen = P @ np.diag(eigenvalues**k) @ P_inv
print(f"\nDirect A^{k}:\n{A_direct}")
print(f"Eigen-based A^{k}:\n{A_eigen}")
print("Match:", np.allclose(A_direct, A_eigen))

# Special cases
print("\n--- Special cases ---")

# Uniform scaling: every vector is an eigenvector
S = 2 * np.eye(2)
vals, vecs = np.linalg.eig(S)
print("Uniform scaling 2I -> eigenvalues:", vals)  # [2. 2.]

# 90-degree rotation: no real eigenvectors (complex eigenvalues)
R = np.array([[0.0, -1.0],
              [1.0,  0.0]])
vals, _ = np.linalg.eig(R)
print("Rotation 90° -> eigenvalues:", vals)  # [0.+1.j 0.-1.j]

# Shear: repeated eigenvalue, only one eigenvector direction
Sh = np.array([[1.0, 1.0],
               [0.0, 1.0]])
vals, vecs = np.linalg.eig(Sh)
print("Shear -> eigenvalues:", vals)  # [1. 1.]
print("Shear -> eigenvector matrix:\n", vecs)
print("|det(P)| ≈ 0 (columns are parallel, so NOT diagonalizable):",
      abs(np.linalg.det(vecs)) < 1e-10)

# PageRank via the power method
print("\n--- PageRank ---")

# 4 pages A, B, C, D. Column j = where page j sends its "vote".
# A -> B, C, D | B -> C, D | C -> A | D -> A, C
L = np.array([
    [0,   0,   1, 1/2],
    [1/3, 0,   0, 0  ],
    [1/3, 1/2, 0, 1/2],
    [1/3, 1/2, 0, 0  ],
])
print("Columns sum to 1:", np.allclose(L.sum(axis=0), 1))

n = L.shape[0]

# Power method: start with equal rank, repeatedly apply L
r = np.ones(n) / n
for _ in range(100):
    r_next = L @ r
    if np.linalg.norm(r_next - r) < 1e-10:
        break
    r = r_next
print("Power method ranks:", r)

# Same answer as the eigenvector with eigenvalue 1 (normalised to sum to 1)
vals, vecs = np.linalg.eig(L)
idx = np.argmin(np.abs(vals - 1))
r_eig = np.real(vecs[:, idx])
r_eig = r_eig / r_eig.sum()
print("Eigenvector (lambda=1):", r_eig)
print("Match:", np.allclose(r, r_eig, atol=1e-6))

# With damping factor d = 0.85
d = 0.85
M = d * L + (1 - d) / n * np.ones((n, n))
r = np.ones(n) / n
for _ in range(100):
    r = M @ r
print("With damping (d=0.85):", r)