The Little Book of Linear Algebra

A concise, beginner-friendly introduction to the core ideas of linear algebra.

Source: the-litte-book-of/linear-algebra

Online:

Formats

Download PDF – print-ready version
Download EPUB – e-reader friendly
View LaTeX – Latex source

Chapter 1. Vectors

1.1 Scalars and Vectors

A scalar is a single numerical quantity, most often taken from the real numbers, denoted by $R$ . Scalars are the fundamental building blocks of arithmetic: they can be added, subtracted, multiplied, and, except in the case of zero, divided. In linear algebra, scalars play the role of coefficients, scaling factors, and entries of larger structures such as vectors and matrices. They provide the weights by which more complex objects are measured and combined. A vector is an ordered collection of scalars, arranged either in a row or a column. When the scalars are real
numbers, the vector is said to belong to real $n$ -dimensional space, written

R^{n} = {(x_{1}, x_{2}, \dots, x_{n}) ∣ x_{i} \in R} .

An element of $R^{n}$ is called a vector of dimension $n$ or an n-vector. The number $n$ is called the dimension of the vector space. Thus $R^{2}$ is the space of all ordered pairs of real numbers, $R^{3}$ the space of all ordered triples, and so on.

Example 1.1.1.

A 2-dimensional vector: $(3, - 1) \in R^{2}$ .
A 3-dimensional vector: $(2, 0, 5) \in R^{3}$ .
A 1-dimensional vector: $(7) \in R^{1}$ , which corresponds to the scalar $7$ itself.

Vectors are often written vertically in column form, which emphasizes their role in matrix multiplication:

v = [\begin{matrix} 2 \\ 0 \\ 5 \end{matrix}] \in R^{3} .

The vertical layout makes the structure clearer when we consider linear combinations or multiply matrices by vectors.

Geometric Interpretation

In $R^{2}$ , a vector $(x_{1}, x_{2})$ can be visualized as an arrow starting at the origin $(0, 0)$ and ending at the point $(x_{1}, x_{2})$ . Its length corresponds to the distance from the origin, and its orientation gives a direction in the plane. In $R^{3}$ , the same picture extends into three dimensions: a vector is an arrow from the origin to $(x_{1}, x_{2}, x_{3})$ . Beyond three dimensions, direct visualization is no longer possible, but the algebraic rules of vectors remain identical. Even though we cannot draw a vector in $R^{10}$ , it behaves under addition, scaling, and transformation exactly as a 2or 3-dimensional vector does. This abstract point of view is what allows linear algebra to apply to data science, physics, and machine learning, where data often lives in very high-dimensional spaces.

Thus a vector may be regarded in three complementary ways:

As a point in space, described by its coordinates.
As a displacement or arrow, described by a direction and a length.
As an abstract element of a vector space, whose properties follow algebraic rules independent of geometry.

Notation

Vectors are written in boldface lowercase letters: $v, w, x$ .
The i-th entry of a vector $v$ is written $v_{i}$ , where indices begin at 1.
The set of all n-dimensional vectors over $R$ is denoted $R^{n}$ .
Column vectors will be the default form unless otherwise stated.

Why begin here?

Scalars and vectors form the atoms of linear algebra. Every structure we will build-vector spaces, linear transformations, matrices, eigenvalues-relies on the basic notions of number and ordered collection of numbers. Once vectors are understood, we can define operations such as addition and scalar multiplication, then generalize to subspaces, bases, and coordinate systems. Eventually, this framework grows into the full theory of linear algebra, with powerful applications to geometry, computation, and data.

Exercises 1.1

Write three different vectors in $R^{2}$ and sketch them as arrows from the origin. Identify their coordinates explicitly.
Give an example of a vector in $R^{4}$ . Can you visualize it directly? Explain why high-dimensional visualization is challenging.
Let $v = (4, - 3, 2)$ . Write $v$ in column form and state $v_{1}, v_{2}, v_{3}$ .
In what sense is the set $R^{1}$ both a line and a vector space? Illustrate with examples.
Consider the vector $u = (1, 1, \dots, 1) \in R^{n}$ . What is special about this vector when $n$ is large? What might it represent in applications?

1.2 Vector Addition and Scalar Multiplication

Vectors in linear algebra are not static objects; their power comes from the operations we can perform on them. Two fundamental operations define the structure of vector spaces: addition and scalar multiplication. These operations satisfy simple but far-reaching rules that underpin the entire subject.

Vector Addition

Given two vectors of the same dimension, their sum is obtained by adding corresponding entries. Formally, if

u = (u_{1}, u_{2}, \dots, u_{n}), v = (v_{1}, v_{2}, \dots, v_{n}),

then their sum is

u + v = (u_{1} + v_{1}, u_{2} + v_{2}, \dots, u_{n} + v_{n}) .

Example 1.2.1.
Let $u = (2, - 1, 3)$ and $v = (4, 0, - 5)$ . Then

u + v = (2 + 4, - 1 + 0, 3 + (- 5)) = (6, - 1, - 2) .

Geometrically, vector addition corresponds to the parallelogram rule. If we draw both vectors as arrows from the origin, then placing the tail of one vector at the head of the other produces the sum. The diagonal of the parallelogram they form represents the resulting vector.

Scalar Multiplication

Multiplying a vector by a scalar stretches or shrinks the vector while preserving its direction, unless the scalar is negative, in which case the vector is also reversed. If $c \in R$ and

v = (v_{1}, v_{2}, \dots, v_{n}),

then

c v = (c v_{1}, c v_{2}, \dots, c v_{n}) .

Example 1.2.2.
Let $v = (3, - 2)$ and $c = - 2$ . Then

c v = - 2 (3, - 2) = (- 6, 4) .

This corresponds to flipping the vector through the origin and doubling its length.

Linear Combinations

The interaction of addition and scalar multiplication allows us to form linear combinations. A linear combination of vectors $v_{1}, v_{2}, \dots, v_{k}$ is any vector of the form

c_{1} v_{1} + c_{2} v_{2} + \dots + c_{k} v_{k}, c_{i} \in R .

Linear combinations are the mechanism by which we generate new vectors from existing ones. The span of a set of vectors-the collection of all their linear combinations-will later lead us to the idea of a subspace.

Example 1.2.3.
Let $v_{1} = (1, 0)$ and $v_{2} = (0, 1)$ . Then any vector $(a, b) \in R^{2}$ can be expressed as

a v_{1} + b v_{2} .

Thus $(1, 0)$ and $(0, 1)$ form the basic building blocks of the plane.

Notation

Addition: $u + v$ means component-wise addition.
Scalar multiplication: $c v$ scales each entry of $v$ by $c$ .
Linear combination: a sum of the form $c_{1} v_{1} + \dots + c_{k} v_{k}$ .

Why this matters

Vector addition and scalar multiplication are the defining operations of linear algebra. They give structure to vector spaces, allow us to describe geometric phenomena like translation and scaling, and provide the foundation for solving systems of equations. Everything that follows-basis, dimension, transformations-builds on these simple but profound rules.

Exercises 1.2

Compute $u + v$ where $u = (1, 2, 3)$ and $v = (4, - 1, 0)$ .
Find $3 v$ where $v = (- 2, 5)$ . Sketch both vectors to illustrate the scaling.
Show that $(5, 7)$ can be written as a linear combination of $(1, 0)$ and $(0, 1)$ .
Write $(4, 4)$ as a linear combination of $(1, 1)$ and $(1, - 1)$ .
Prove that if $u, v \in R^{n}$ ,
then $(c + d) (u + v) = c u + c v + d u + d v$ for
scalars $c, d \in R$ .

1.3 Dot Product, Norms, and Angles

The dot product is the fundamental operation that links algebra and geometry in vector spaces. It allows us to measure lengths, compute angles, and determine orthogonality. From this single definition flow the notions of norm and angle, which give geometry to abstract vector spaces.

The Dot Product

For two vectors in $R^{n}$ , the dot product (also called the inner product) is defined by

u \cdot v = u_{1} v_{1} + u_{2} v_{2} + \dots + u_{n} v_{n} .

Equivalently, in matrix notation:

u \cdot v = u^{T} v .

Example 1.3.1.
Let $u = (2, - 1, 3)$ and $v = (4, 0, - 2)$ . Then

u \cdot v = 2 \cdot 4 + (- 1) \cdot 0 + 3 \cdot (- 2) = 8 - 6 = 2.

The dot product outputs a single scalar, not another vector.

Norms (Length of a Vector)

The Euclidean norm of a vector is the square root of its dot product with itself:

∥ v ∥ = \sqrt{v \cdot v} = \sqrt{v_{1}^{2} + v_{2}^{2} + \dots + v_{n}^{2}} .

This generalizes the Pythagorean theorem to arbitrary dimensions.

Example 1.3.2.
For $v = (3, 4)$ ,

∥ v ∥ = \sqrt{3^{2} + 4^{2}} = \sqrt{25} = 5.

This is exactly the length of the vector as an arrow in the plane.

Angles Between Vectors

The dot product also encodes the angle between two vectors. For nonzero vectors $u, v$ ,

u \cdot v = ∥ u ∥ ∥ v ∥ \cos θ,

where $θ$ is the angle between them. Thus,

\cos θ = \frac{u \cdot v}{∥ u ∥ ∥ v ∥} .

Example 1.3.3.
Let $u = (1, 0)$ and $v = (0, 1)$ . Then

u \cdot v = 0, ∥ u ∥ = 1, ∥ v ∥ = 1.

Hence

\cos θ = \frac{0}{1 \cdot 1} = 0 \Rightarrow θ = \frac{π}{2} .

The vectors are perpendicular.

Orthogonality

Two vectors are said to be orthogonal if their dot product is zero:

u \cdot v = 0.

Orthogonality generalizes the idea of perpendicularity from geometry to higher dimensions.

Notation

Dot product: $u \cdot v$ .
Norm (length): $| v |$ .
Orthogonality: $u ⊥ v$ if $u \cdot v = 0$ .

Why this matters

The dot product turns vector spaces into geometric objects: vectors gain lengths, angles, and notions of perpendicularity. This foundation will later support the study of orthogonal projections, Gram–Schmidt orthogonalization, eigenvectors, and least squares problems.

Exercises 1.3

Compute $u \cdot v$ for $u = (1, 2, 3)$ , $v = (4, 5, 6)$ .
Find the norm of $v = (2, - 2, 1)$ .
Determine whether $u = (1, 1, 0)$ and $v = (1, - 1, 2)$ are orthogonal.
Let $u = (3, 4)$ , $v = (4, 3)$ . Compute the angle between them.
Prove that $| u + v |^{2} = | u |^{2} + | v |^{2} + 2 u \cdot v$ . This identity is the algebraic version of the Law of Cosines.

1.4 Orthogonality

Orthogonality captures the notion of perpendicularity in vector spaces. It is one of the most important geometric ideas in linear algebra, allowing us to decompose vectors, define projections, and construct special bases with elegant properties.

Definition

Two vectors $u, v \in R^{n}$ are said to be orthogonal if their dot product is zero:

u \cdot v = 0.

This condition ensures that the angle between them is $π / 2$ radians (90 degrees).

Example 1.4.1.
In $R^{2}$ , the vectors $(1, 2)$ and $(2, - 1)$ are orthogonal since

(1, 2) \cdot (2, - 1) = 1 \cdot 2 + 2 \cdot (- 1) = 0.

Orthogonal Sets

A collection of vectors is called orthogonal if every distinct pair of vectors in the set is orthogonal. If, in addition, each vector has norm 1, the set is called orthonormal.

Example 1.4.2.
In $R^{3}$ , the standard basis vectors

e_{1} = (1, 0, 0), e_{2} = (0, 1, 0), e_{3} = (0, 0, 1)

form an orthonormal set: each has length 1, and their dot products vanish when the indices differ.

Projections

Orthogonality makes possible the decomposition of a vector into two components: one parallel to another vector, and one orthogonal to it. Given a nonzero vector $u$ and any vector $v$ , the projection of $v$ onto $u$ is

{proj}_{u} (v) = \frac{u \cdot v}{u \cdot u} u .

The difference

v - {proj}_{u} (v)

is orthogonal to $u$ . Thus every vector can be decomposed uniquely into a parallel and perpendicular part with respect to another vector.

Example 1.4.3.
Let $u = (1, 0)$ , $v = (2, 3)$ . Then

{proj}_{u} (v) = \frac{(1, 0) \cdot (2, 3)}{(1, 0) \cdot (1, 0)} (1, 0) = \frac{2}{1} (1, 0) = (2, 0) .

Thus

v = (2, 3) = (2, 0) + (0, 3),

where $(2, 0)$ is parallel to $(1, 0)$ and $(0, 3)$ is orthogonal to it.

Orthogonal Decomposition

In general, if $u \neq 0$ and $v \in R^{n}$ , then

v = {proj}_{u} (v) + (v - {proj}_{u} (v)),

where the first term is parallel to $u$ and the second term is orthogonal. This decomposition underlies methods such as least squares approximation and the Gram–Schmidt process.

Notation

$u ⊥ v$ : vectors $u$ and $v$ are orthogonal.
An orthogonal set: vectors pairwise orthogonal.
An orthonormal set: pairwise orthogonal, each of norm 1.

Why this matters

Orthogonality gives structure to vector spaces. It provides a way to separate independent directions cleanly, simplify computations, and minimize errors in approximations. Many powerful algorithms in numerical linear algebra and data science (QR decomposition, least squares regression, PCA) rely on orthogonality.

Exercises 1.4

Verify that the vectors $(1, 2, 2)$ and $(2, 0, - 1)$ are orthogonal.
Find the projection of $(3, 4)$ onto $(1, 1)$ .
Show that any two distinct standard basis vectors in $R^{n}$ are orthogonal.
Decompose $(5, 2)$ into components parallel and orthogonal to $(2, 1)$ .
Prove that if $u, v$ are orthogonal and nonzero,
then $(u + v) \cdot (u - v) = 0$ .

Chapter 2. Matrices

2.1 Definition and Notation

Matrices are the central objects of linear algebra, providing a compact way to represent and manipulate linear transformations, systems of equations, and structured data. A matrix is a rectangular array of numbers arranged in rows and columns.

Formal Definition

An $m \times n$ matrix is an array with $m$ rows and $n$ columns, written

A = [\begin{matrix} a_{11} & a_{12} & \dots & a_{1 n} \\ a_{21} & a_{22} & \dots & a_{2 n} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ a_{m 1} & a_{m 2} & \dots & a_{m n} \end{matrix}] .

Each entry $a_{i j}$ is a scalar, located in the i-th row and j-th column. The size (or dimension) of the matrix is denoted by $m \times n$ .

If $m = n$ , the matrix is square.
If $m = 1$ , the matrix is a row vector.
If $n = 1$ , the matrix is a column vector.

Thus, vectors are simply special cases of matrices.

Examples

Example 2.1.1. A $2 \times 3$ matrix:

A = [\begin{matrix} 1 & - 2 & 4 \\ 0 & 3 & 5 \end{matrix}] .

Here, $a_{12} = - 2$ , $a_{23} = 5$ , and the matrix has 2 rows, 3 columns.

Example 2.1.2. A $3 \times 3$ square matrix:

B = [\begin{matrix} 2 & 0 & 1 \\ - 1 & 3 & 4 \\ 0 & 5 & - 2 \end{matrix}] .

This will later serve as the representation of a linear transformation on $R^{3}$ .

Indexing and Notation

Matrices are denoted by uppercase bold letters: $A, B, C$ .
Entries are written as $a_{i j}$ , with the row index first, column index second.
The set of all real $m \times n$ matrices is denoted $R^{m \times n}$ .

Thus, a matrix is a function $A : 1, \dots, m \times 1, \dots, n \to R$ , assigning a scalar to each row-column position.

Why this matters

Matrices generalize vectors and give us a language for describing linear operations systematically. They encode systems of equations, rotations, projections, and transformations of data. With matrices, algebra and geometry come together: a single compact object can represent both numerical data and functional rules.

Exercises 2.1

Write a $3 \times 2$ matrix of your choice and identify its entries $a_{i j}$ .
Is every vector a matrix? Is every matrix a vector? Explain.
Which of the following are square
matrices: $A \in R^{4 \times 4}$ , $B \in R^{3 \times 5}$ , $C \in R^{1 \times 1}$ ?
Let $D = [\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}]$ . What kind of matrix is this?
Consider the matrix $E = [\begin{matrix} a & b \\ c & d \end{matrix}]$ . Express $e_{11}, e_{12}, e_{21}, e_{22}$
explicitly.

2.2 Matrix Addition and Multiplication

Once matrices are defined, the next step is to understand how they combine. Just as vectors gain meaning through addition and scalar multiplication, matrices become powerful through two operations: addition and multiplication.

Matrix Addition

Two matrices of the same size are added by adding corresponding entries. If

A = [a_{i j}] \in R^{m \times n}, B = [b_{i j}] \in R^{m \times n},

then

A + B = [a_{i j} + b_{i j}] \in R^{m \times n} .

Example 2.2.1.
Let

A = [\begin{matrix} 1 & 2 \\ 3 & 4 \end{matrix}], B = [\begin{matrix} - 1 & 0 \\ 5 & 2 \end{matrix}] .

Then

A + B = [\begin{matrix} 1 + (- 1) & 2 + 0 \\ 3 + 5 & 4 + 2 \end{matrix}] = [\begin{matrix} 0 & 2 \\ 8 & 6 \end{matrix}] .

Matrix addition is commutative ( $A + B = B + A$ ) and associative ( $(A + B) + C = A + (B + C)$ ). The zero matrix, with all entries 0, acts as the additive identity.

Scalar Multiplication

For a scalar $c \in R$ and a matrix $A = [[a_{i j}]$ , we define

c A = [c \cdot a_{i j}] .

This stretches or shrinks all entries of the matrix uniformly.

Example 2.2.2.
If

A = [\begin{matrix} 2 & - 1 \\ 0 & 3 \end{matrix}], c = - 2,

then

c A = [\begin{matrix} - 4 & 2 \\ 0 & - 6 \end{matrix}] .

Matrix Multiplication

The defining operation of matrices is multiplication. If

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

then their product is the $m \times p$ matrix

A B = C = [c_{i j}], c_{i j} = \sum_{k = 1}^{n} a_{i k} b_{k j} .

Thus, the entry in the $i$ -th row and $j$ -th column of $A B$ is the dot product of the $i$ -th row of $A$ with the $j$ -th column of $B$ .

Example 2.2.3.
Let

A = [\begin{matrix} 1 & 2 \\ 0 & 3 \end{matrix}], B = [\begin{matrix} 4 & - 1 \\ 2 & 5 \end{matrix}] .

Then

A B = [\begin{matrix} 1 \cdot 4 + 2 \cdot 2 & 1 \cdot (- 1) + 2 \cdot 5 \\ 0 \cdot 4 + 3 \cdot 2 & 0 \cdot (- 1) + 3 \cdot 5 \end{matrix}] = [\begin{matrix} 8 & 9 \\ 6 & 15 \end{matrix}] .

Notice that matrix multiplication is not commutative in general: $A B \neq B A$ . Sometimes $B A$ may not even be defined if dimensions do not align.

Geometric Meaning

Matrix multiplication corresponds to the composition of linear transformations. If $A$ transforms vectors in $R^{n}$ and $B$ transforms vectors in $R^{p}$ , then $A B$ represents applying $B$ first, then $A$ . This makes matrices the algebraic language of transformations.

Notation

Matrix sum: $A + B$ .
Scalar multiple: $c A$ .
Product: $A B$ , defined only when the number of columns of $A$ equals the number of rows of $B$ .

Why this matters

Matrix multiplication is the core mechanism of linear algebra: it encodes how transformations combine, how systems of equations are solved, and how data flows in modern algorithms. Addition and scalar multiplication make matrices into a vector space, while multiplication gives them an algebraic structure rich enough to model geometry, computation, and networks.

Exercises 2.2

Compute $A + B$ for

A = [\begin{matrix} 2 & 3 \\ - 1 & 0 \end{matrix}], B = [\begin{matrix} 4 & - 2 \\ 5 & 7 \end{matrix}] .

Find $3 A$ where

A = [\begin{matrix} 1 & - 4 \\ 2 & 6 \end{matrix}] .

Multiply

A = [\begin{matrix} 1 & 0 & 2 \\ - 1 & 3 & 1 \end{matrix}], B = [\begin{matrix} 2 & 1 \\ 0 & - 1 \\ 3 & 4 \end{matrix}] .

Verify with an explicit example that $A B \neq B A$ .
Prove that matrix multiplication is distributive: $A (B + C) = A B + A C$ .

2.3 Transpose and Inverse

Two special operations on matrices-the transpose and the inverse-give rise to deep algebraic and geometric properties. The transpose rearranges a matrix by flipping it across its main diagonal, while the inverse, when it exists, acts as the undo operation for matrix multiplication.

The Transpose

The transpose of an $m \times n$ matrix $A = [a_{i j}]$ is the $n \times m$ matrix $A^{T} = [a_{j i}]$ , obtained by swapping rows and columns.

Formally,

(A^{T})_{i j} = a_{j i} .

Example 2.3.1.
If

A = [\begin{matrix} 1 & 4 & - 2 \\ 0 & 3 & 5 \end{matrix}],

then

A^{T} = [\begin{matrix} 1 & 0 \\ 4 & 3 \\ - 2 & 5 \end{matrix}] .

Properties of the Transpose.

$(A^{T})^{T} = A$ .
$(A + B)^{T} = A^{T} + B^{T}$ .
$(c A)^{T} = c A^{T}$ , for scalar $c$ .
$(A B)^{T} = B^{T} A^{T}$ .

The last rule is crucial: the order reverses.

The Inverse

A square matrix $A \in R^{n \times n}$ is said to be invertible (or nonsingular) if there exists another matrix $A^{- 1}$ such that

A A^{- 1} = A^{- 1} A = I_{n},

where $I_{n}$ is the $n \times n$ identity matrix. In this case, $A^{- 1}$ is called the inverse of $A$ .

Not every matrix is invertible. A necessary condition is that $det (A) \neq 0$ , a fact that will be developed in Chapter

Example 2.3.2.
Let

A = [\begin{matrix} 1 & 2 \\ 3 & 4 \end{matrix}] .

Its determinant is $det (A) = (1) (4) - (2) (3) = - 2 \neq 0$ . The inverse is

A^{- 1} = \frac{1}{det (A)} [\begin{matrix} 4 & - 2 \\ - 3 & 1 \end{matrix}] = [\begin{matrix} - 2 & 1 \\ 1.5 & - 0.5 \end{matrix}] .

Verification:

A A^{- 1} = [\begin{matrix} 1 & 2 \\ 3 & 4 \end{matrix}] [\begin{matrix} - 2 & 1 \\ 1.5 & - 0.5 \end{matrix}] = [\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}] .

Geometric Meaning

The transpose corresponds to reflecting a linear transformation across the diagonal. For vectors, it switches between row and column forms.
The inverse, when it exists, corresponds to reversing a linear transformation. For example, if $A$ scales and rotates vectors, $A^{- 1}$ rescales and rotates them back.

Notation

Transpose: $A^{T}$ .
Inverse: $A^{- 1}$ , defined only for invertible square matrices.
Identity: $I_{n}$ , acts as the multiplicative identity.

Why this matters

The transpose allows us to define symmetric and orthogonal matrices, central to geometry and numerical methods. The inverse underlies the solution of linear systems, encoding the idea of undoing a transformation. Together, these operations set the stage for determinants, eigenvalues, and orthogonalization.

Exercises 2.3

Compute the transpose of

A = [\begin{matrix} 2 & - 1 & 3 \\ 0 & 4 & 5 \end{matrix}] .

Verify that $(A B)^{T} = B^{T} A^{T}$ for

A = [\begin{matrix} 1 & 2 \\ 0 & 1 \end{matrix}], B = [\begin{matrix} 3 & 4 \\ 5 & 6 \end{matrix}] .

Determine whether

C = [\begin{matrix} 2 & 1 \\ 4 & 2 \end{matrix}]

is invertible. If so, find $C^{- 1}$ .

Find the inverse of

D = [\begin{matrix} 0 & 1 \\ - 1 & 0 \end{matrix}],

and explain its geometric action on vectors in the plane.

Prove that if $A$ is invertible, then so is $A^{T}$ , and $(A^{T})^{- 1} = (A^{- 1})^{T}$ .

2.4 Special Matrices

Certain matrices occur so frequently in theory and applications that they are given special names. Recognizing their properties allows us to simplify computations and understand the structure of linear transformations more clearly.

The Identity Matrix

The identity matrix $I_{n}$ is the $n \times n$ matrix with ones on the diagonal and zeros elsewhere:

I_{n} = [\begin{matrix} 1 & 0 & \dots & 0 \\ 0 & 1 & \dots & 0 \\ ⋮ & ⋮ & ⋱ & ⋮ \\ 0 & 0 & \dots & 1 \end{matrix}] .

It acts as the multiplicative identity:

A I_{n} = I_{n} A = A, for all A \in R^{n \times n} .

Geometrically, $I_{n}$ represents the transformation that leaves every vector unchanged.

Diagonal Matrices

A diagonal matrix has all off-diagonal entries zero:

D = [\begin{matrix} d_{11} & 0 & \dots & 0 \\ 0 & d_{22} & \dots & 0 \\ ⋮ & ⋮ & ⋱ & ⋮ \\ 0 & 0 & \dots & d_{n n} \end{matrix}] .

Multiplication by a diagonal matrix scales each coordinate independently:

D x = (d_{11} x_{1}, d_{22} x_{2}, \dots, d_{n n} x_{n}) .

Example 2.4.1.
Let

D = [\begin{matrix} 2 & 0 & 0 \\ 0 & 3 & 0 \\ 0 & 0 & - 1 \end{matrix}], x = [\begin{matrix} 1 \\ 4 \\ - 2 \end{matrix}] .

Then

D x = [\begin{matrix} 2 \\ 12 \\ 2 \end{matrix}] .

Permutation Matrices

A permutation matrix is obtained by permuting the rows of the identity matrix. Multiplying a vector by a permutation matrix reorders its coordinates.

Example 2.4.2.
Let

P = [\begin{matrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{matrix}] .

Then

P [\begin{matrix} a \\ b \\ c \end{matrix}] = [\begin{matrix} b \\ a \\ c \end{matrix}] .

Thus, $P$ swaps the first two coordinates.

Permutation matrices are always invertible; their inverses are simply their transposes.

Symmetric and Skew-Symmetric Matrices

A matrix is symmetric if

A^{T} = A,

and skew-symmetric if

A^{T} = - A .

Symmetric matrices appear in quadratic forms and optimization, while skew-symmetric matrices describe rotations and cross products in geometry.

Orthogonal Matrices

A square matrix $Q$ is orthogonal if

Q^{T} Q = Q Q^{T} = I .

Equivalently, the rows (and columns) of $Q$ form an orthonormal set. Orthogonal matrices preserve lengths and angles; they represent rotations and reflections.

Example 2.4.3.
The rotation matrix in the plane:

R (θ) = [\begin{matrix} \cos θ & - \sin θ \\ \sin θ & \cos θ \end{matrix}]

is orthogonal, since

R (θ)^{T} R (θ) = I_{2} .

Why this matters

Special matrices serve as the building blocks of linear algebra. Identity matrices define the neutral element, diagonal matrices simplify computations, permutation matrices reorder data, symmetric and orthogonal matrices describe fundamental geometric structures. Much of modern applied mathematics reduces complex problems to operations involving these simple forms.

Exercises 2.4

Show that the product of two diagonal matrices is diagonal, and compute an example.
Find the permutation matrix that cycles $(a, b, c)$ into $(b, c, a)$ .
Prove that every permutation matrix is invertible and its inverse is its transpose.
Verify that

Q = [\begin{matrix} 0 & 1 \\ - 1 & 0 \end{matrix}]

is orthogonal. What geometric transformation does it represent?
5. Determine whether

A = [\begin{matrix} 2 & 3 \\ 3 & 2 \end{matrix}], B = [\begin{matrix} 0 & 5 \\ - 5 & 0 \end{matrix}]

are symmetric, skew-symmetric, or neither.

Chapter 3. Systems of Linear Equations

3.1 Linear Systems and Solutions

One of the central motivations for linear algebra is solving systems of linear equations. These systems arise naturally in science, engineering, and data analysis whenever multiple constraints interact. Matrices provide a compact language for expressing and solving them.

Linear Systems

A linear system consists of equations where each unknown appears only to the first power and with no products between variables. A general system of $m$ equations in $n$ unknowns can be written as:

\begin{aligned} a_{11} x_{1} + a_{12} x_{2} + \dots + a_{1 n} x_{n} & = b_{1}, \\ a_{21} x_{1} + a_{22} x_{2} + \dots + a_{2 n} x_{n} & = b_{2}, \\ ⋮ \\ a_{m 1} x_{1} + a_{m 2} x_{2} + \dots + a_{m n} x_{n} & = b_{m} . \end{aligned}

Here the coefficients $a_{i j}$ and constants $b_{i}$ are scalars, and the unknowns are $x_{1}, x_{2}, \dots, x_{n}$ .

Matrix Form

The system can be expressed compactly as:

A x = b,

where

$A \in R^{m \times n}$ is the coefficient matrix $[a_{i j}]$ ,
$x \in R^{n}$ is the column vector of unknowns,
$b \in R^{m}$ is the column vector of constants.

This formulation turns the problem of solving equations into analyzing the action of a matrix.

Example 3.1.1.
The system

{\begin{cases} x + 2 y = 5, \\ 3 x - y = 4 \end{cases}

can be written as

[\begin{matrix} 1 & 2 \\ 3 & - 1 \end{matrix}] [\begin{matrix} x \\ y \end{matrix}] = [\begin{matrix} 5 \\ 4 \end{matrix}] .

Types of Solutions

A linear system may have:

No solution (inconsistent): The equations conflict.
Example:
${\begin{cases} x + y = 1 \\ x + y = 2 \end{cases}$
has no solution.
Exactly one solution (unique): The system’s equations intersect at a single point.
Example: The above system with coefficient matrix $
\begin{bmatrix} 1 & 2 \ 3 & -1 \end{bmatrix}
$ has a unique solution.
Infinitely many solutions: The equations describe overlapping constraints (e.g., multiple equations representing the
same line or plane).

The nature of the solution depends on the rank of $A$ and its relation to the augmented matrix $(A | b)$ , which
we will study later.

Geometric Interpretation

In $R^{2}$ , each linear equation represents a line. Solving a system means finding intersection points of
lines.
In $R^{3}$ , each equation represents a plane. A system may have no solution (parallel planes), one solution (a
unique intersection point), or infinitely many (a line of intersection).
In higher dimensions, the picture generalizes: solutions form intersections of hyperplanes.

Why this matters

Linear systems are the practical foundation of linear algebra. They appear in balancing chemical reactions, circuit analysis, least-squares regression, optimization, and computer graphics. Understanding how to represent and classify their solutions is the first step toward systematic solution methods like Gaussian elimination.

Exercises 3.1

Write the following system in matrix form:

{\begin{cases} 2 x + 3 y - z = 7, \\ x - y + 4 z = 1, \\ 3 x + 2 y + z = 5 \end{cases}

Determine whether the system

{\begin{cases} x + y = 1, \\ 2 x + 2 y = 2 \end{cases}

has no solution, one solution, or infinitely many solutions.

Geometrically interpret the system

{\begin{cases} x + y = 3, \\ x - y = 1 \end{cases}

in the plane.

Solve the system

{\begin{cases} 2 x + y = 1, \\ x - y = 4 \end{cases}

and check your solution.

In $R^{3}$ , describe the solution set of

{\begin{cases} x + y + z = 0, \\ 2 x + 2 y + 2 z = 0 \end{cases}

.
What geometric object does it represent?

3.2 Gaussian Elimination

To solve linear systems efficiently, we use Gaussian elimination: a systematic method of transforming a system into a simpler equivalent one whose solutions are easier to see. The method relies on elementary row operations that preserve the solution set.

Elementary Row Operations

On an augmented matrix $(A | b)$ , we are allowed three operations:

Row swapping: interchange two rows.
Row scaling: multiply a row by a nonzero scalar.
Row replacement: replace one row by itself plus a multiple of another row.

These operations correspond to re-expressing equations in different but equivalent forms.

Row Echelon Form

A matrix is in row echelon form (REF) if:

All nonzero rows are above any zero rows.
Each leading entry (the first nonzero number from the left in a row) is to the right of the leading entry in the row above.
All entries below a leading entry are zero.

Further, if each leading entry is 1 and is the only nonzero entry in its column, the matrix is in reduced row echelon
form (RREF).

Algorithm of Gaussian Elimination

Write the augmented matrix for the system.
Use row operations to create zeros below each pivot (the leading entry in a row).
Continue column by column until the matrix is in echelon form.
Solve by back substitution: starting from the last pivot equation and working upward.

If we continue to RREF, the solution can be read off directly.

Example

Example 3.2.1. Solve

{\begin{cases} x + 2 y - z = 3, \\ 2 x + y + z = 7, \\ 3 x - y + 2 z = 4. \end{cases}

Step 1. Augmented matrix

[\begin{array}{cccc} 1 & 2 & - 1 & 3 \\ 2 & 1 & 1 & 7 \\ 3 & - 1 & 2 & 4 \end{array}] .

Step 2. Eliminate below the first pivot

Subtract 2 times row 1 from row 2, and 3 times row 1 from row 3:

[\begin{array}{cccc} 1 & 2 & - 1 & 3 \\ 0 & - 3 & 3 & 1 \\ 0 & - 7 & 5 & - 5 \end{array}] .

Step 3. Pivot in column 2

Divide row 2 by -3:

[\begin{array}{cccc} 1 & 2 & - 1 & 3 \\ 0 & 1 & - 1 & - \frac{1}{3} \\ 0 & - 7 & 5 & - 5 \end{array}] .

Add 7 times row 2 to row 3:

[\begin{array}{cccc} 1 & 2 & - 1 & 3 \\ 0 & 1 & - 1 & - \frac{1}{3} \\ 0 & 0 & - 2 & - \frac{22}{3} \end{array}] .

Step 4. Pivot in column 3

Divide row 3 by -2:

[\begin{array}{cccc} 1 & 2 & - 1 & 3 \\ 0 & 1 & - 1 & - \frac{1}{3} \\ 0 & 0 & 1 & \frac{11}{3} \end{array}] .

Step 5. Back substitution

From the last row:

z = \frac{11}{3} .

Second row:

y - z = - \frac{1}{3} ⟹ y = - \frac{1}{3} + \frac{11}{3} = \frac{10}{3} .

First row:

x + 2 y - z = 3 ⟹ x + 2 \cdot \frac{10}{3} - \frac{11}{3} = 3.

x + \frac{20}{3} - \frac{11}{3} = 3 ⟹ x + 3 = 3 ⟹ x = 0.

Solution:

(x, y, z) = (0, \frac{10}{3}, \frac{11}{3}) .

Why this matters

Gaussian elimination is the foundation of computational linear algebra. It reduces complex systems to a form where
solutions are visible, and it forms the basis for algorithms used in numerical analysis, scientific computing, and
machine learning.

Exercises 3.2

Solve by Gaussian elimination:

{\begin{cases} x + y = 2, \\ 2 x - y = 0. \end{cases}

Reduce the following augmented matrix to REF:

[\begin{array}{cccc} 1 & 1 & 1 & 6 \\ 2 & - 1 & 3 & 14 \\ 1 & 4 & - 2 & - 2 \end{array}] .

Show that Gaussian elimination always produces either:
- a unique solution,
- infinitely many solutions, or
- a contradiction (no solution).
Use Gaussian elimination to find all solutions of

{\begin{cases} x + y + z = 0, \\ 2 x + y + z = 1. \end{cases}

Explain why pivoting (choosing the largest available pivot element) is useful in numerical computation.

3.3 Rank and Consistency

Gaussian elimination not only provides solutions but also reveals the structure of a linear system. Two key ideas are the rank of a matrix and the consistency of a system. Rank measures the amount of independent information in the equations, while consistency determines whether the system has at least one solution.

Rank of a Matrix

The rank of a matrix is the number of leading pivots in its row echelon form. Equivalently, it is the maximum number of linearly independent rows or columns.

Formally,

rank (A) = \dim (row space of A) = \dim (column space of A) .

The rank tells us the effective dimension of the space spanned by the rows (or columns).

Example 3.3.1.
For

A = [\begin{matrix} 1 & 2 & 3 \\ 2 & 4 & 6 \\ 3 & 6 & 9 \end{matrix}],

row reduction gives

[\begin{matrix} 1 & 2 & 3 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{matrix}] .

Thus, $rank (A) = 1$ , since all rows are multiples of the first.

Consistency of Linear Systems

Consider the system $A x = b$ .
The system is consistent (has at least one solution) if and only if

rank (A) = rank (A | b),

where $(A | b)$ is the augmented matrix.
If the ranks differ, the system is inconsistent.

If $rank (A) = rank (A | b) = n$ (number of unknowns), the system has a unique solution.
If $rank (A) = rank (A | b) < n$ , the system has infinitely many solutions.

Example

Example 3.3.2.
Consider

{\begin{cases} x + y + z = 1, \\ 2 x + 2 y + 2 z = 2, \\ x + y + z = 3. \end{cases}

The augmented matrix is

[\begin{array}{cccc} 1 & 1 & 1 & 1 \\ 2 & 2 & 2 & 2 \\ 1 & 1 & 1 & 3 \end{array}] .

Row reduction gives

[\begin{array}{cccc} 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 2 \end{array}] .

Here, $rank (A) = 1$ , but $rank (A | b) = 2$ . Since the ranks differ, the system is inconsistent: no solution exists.

Example with Infinite Solutions

Example 3.3.3.
For

{\begin{cases} x + y = 2, \\ 2 x + 2 y = 4, \end{cases}

the augmented matrix reduces to

[\begin{array}{ccc} 1 & 1 & 2 \\ 0 & 0 & 0 \end{array}] .

Here, $rank (A) = rank (A | b) = 1 < 2$ . Thus, infinitely many solutions exist, forming a line.

Why this matters

Rank is a measure of independence: it tells us how many truly distinct equations or directions are present. Consistency explains when equations align versus when they contradict. These concepts connect linear systems to vector spaces and prepare for the ideas of dimension, basis, and the Rank–Nullity Theorem.

Exercises 3.3

Compute the rank of

A = [\begin{matrix} 1 & 2 & 1 \\ 0 & 1 & - 1 \\ 2 & 5 & - 1 \end{matrix}] .

Determine whether the system

{\begin{cases} x + y + z = 1, \\ 2 x + 3 y + z = 2, \\ 3 x + 5 y + 2 z = 3 \end{cases}

is consistent.

Show that the rank of the identity matrix $I_{n}$ is $n$ .
Give an example of a system in $R^{3}$ with infinitely many solutions, and explain why it satisfies the rank
condition.
Prove that for any matrix $A \in R^{m \times n}$ ,
$
\text{rank}(A) \leq \min(m,n).
$

3.4 Homogeneous Systems

A homogeneous system is a linear system in which all constant terms are zero:

A x = 0,

where $A \in R^{m \times n}$ , and $0$ is the zero vector in $R^{m}$ .

The Trivial Solution

Every homogeneous system has at least one solution:

x = 0 .

This is called the trivial solution. The interesting question is whether nontrivial solutions (nonzero vectors) exist.

Existence of Nontrivial Solutions

Nontrivial solutions exist precisely when the number of unknowns exceeds the rank of the coefficient matrix:

rank (A) < n .

In this case, there are infinitely many solutions, forming a subspace of $R^{n}$ . The dimension of this solution space is

\dim (null (A)) = n - rank (A),

where null(A) is the set of all solutions to $A x = 0$ . This set is called the null space or kernel of $A$ .

Example

Example 3.4.1.
Consider

{\begin{cases} x + y + z = 0, \\ 2 x + y - z = 0. \end{cases}

The augmented matrix is

[\begin{array}{cccc} 1 & 1 & 1 & 0 \\ 2 & 1 & - 1 & 0 \end{array}] .

Row reduction:

[\begin{array}{cccc} 1 & 1 & 1 & 0 \\ 0 & - 1 & - 3 & 0 \end{array}] \to [\begin{array}{cccc} 1 & 1 & 1 & 0 \\ 0 & 1 & 3 & 0 \end{array}] .

So the system is equivalent to:

{\begin{cases} x + y + z = 0, \\ y + 3 z = 0. \end{cases}

From the second equation, $y = - 3 z$ . Substituting into the first:

x - 3 z + z = 0 ⟹ x = 2 z .

Thus solutions are:

(x, y, z) = z (2, - 3, 1), z \in R .

The null space is the line spanned by the vector $(2, - 3, 1)$ .

Geometric Interpretation

The solution set of a homogeneous system is always a subspace of $R^{n}$ .

If $rank (A) = n$ , the only solution is the zero vector.
If $rank (A) = n - 1$ , the solution set is a line through the origin.
If $rank (A) = n - 2$ , the solution set is a plane through the origin.

More generally, the null space has dimension $n - rank (A)$ , known as the nullity.

Why this matters

Homogeneous systems are central to understanding vector spaces, subspaces, and dimension. They lead directly to the concepts of kernel, null space, and linear dependence. In applications, homogeneous systems appear in equilibrium problems, eigenvalue equations, and computer graphics transformations.

Exercises 3.4

Solve the homogeneous system

{\begin{cases} x + 2 y - z = 0, \\ 2 x + 4 y - 2 z = 0. \end{cases}

What is the dimension of its solution space?

Find all solutions of

{\begin{cases} x - y + z = 0, \\ 2 x + y - z = 0. \end{cases}

Show that the solution set of any homogeneous system is a subspace of $R^{n}$ .
Suppose $A$ is a $3 \times 3$ matrix with $rank (A) = 2$ . What is the dimension of the null space of $A$ ?
For

A = [\begin{matrix} 1 & 2 & - 1 \\ 0 & 1 & 3 \end{matrix}],

compute a basis for the null space of $A$ .

Chapter 4. Vector Spaces

4.1 Definition of a Vector Space

Up to now we have studied vectors and matrices concretely in $R^{n}$ . The next step is to move beyond coordinates and define vector spaces in full generality. A vector space is an abstract setting where the familiar rules of addition and scalar multiplication hold, regardless of whether the elements are geometric vectors, polynomials, functions, or other objects.

Formal Definition

A vector space over the real numbers $R$ is a set $V$ equipped with two operations:

Vector addition: For any $u, v \in V$ , there is a vector $u + v \in V$ .
Scalar multiplication: For any scalar $c \in R$ and any $v \in V$ , there is a
vector $c v \in V$ .

These operations must satisfy the following axioms (for all $u, v, w \in V$ and all
scalars $a, b \in R$ ):

Commutativity of addition: $u + v = v + u$ .
Associativity of addition: $(u + v) + w = u + (v + w)$ .
Additive identity: There exists a zero vector $0 \in V$ such that $v + 0 = v$ .
Additive inverses: For each $v \in V$ , there exists $(- v \in V$ such
that $v + (- v) = 0$ .
Compatibility of scalar multiplication: $a (b v) = (a b) v$ .
Identity element of scalars: $1 \cdot v = v$ .
Distributivity over vector addition: $a (u + v) = a u + a v$ .
Distributivity over scalar addition: $(a + b) v = a v + b v$ .

If a set $V$ with operations satisfies all eight axioms, we call it a vector space.

Examples

Example 4.1.1. Standard Euclidean space
$R^{n}$ with ordinary addition and scalar multiplication is a vector space. This is the model case from which the axioms are abstracted.

Example 4.1.2. Polynomials
The set of all polynomials with real coefficients, denoted $R [x]$ , forms a vector space. Addition and scalar multiplication are defined term by term.

Example 4.1.3. Functions
The set of all real-valued functions on an interval, e.g. $f : [0, 1] \to R$ , forms a vector space, since functions can be added and scaled pointwise.

Non-Examples

Not every set with operations qualifies. For instance, the set of positive real numbers under usual addition is not a vector space, because additive inverses (negative numbers) are missing. The axioms must all hold.

Geometric Interpretation

In familiar cases like $R^{2}$ or $R^{3}$ , vector spaces provide the stage for geometry: vectors can be added, scaled, and combined to form lines, planes, and higher-dimensional structures. In abstract settings like function spaces, the same algebraic rules let us apply geometric intuition to infinite-dimensional problems.

Why this matters

The concept of vector space unifies seemingly different mathematical objects under a single framework. Whether dealing with forces in physics, signals in engineering, or data in machine learning, the common language of vector spaces allows us to use the same techniques everywhere.

Exercises 4.1

Verify that $R^{2}$ with standard addition and scalar multiplication satisfies all eight vector space axioms.
Show that the set of integers $Z$ with ordinary operations is not a vector space over $R$ . Which axiom fails?
Consider the set of all polynomials of degree at most 3. Show it forms a vector space over $R$ . What is its dimension?
Give an example of a vector space where the vectors are not geometric objects.
Prove that in any vector space, the zero vector is unique.

4.2 Subspaces

A subspace is a smaller vector space living inside a larger one. Just as lines and planes naturally sit inside three-dimensional space, subspaces generalize these ideas to higher dimensions and more abstract settings.

Definition

Let $V$ be a vector space. A subset $W \subseteq V$ is called a subspace of $V$ if:

$0 \in W$ (contains the zero vector),
For all $u, v \in W$ , the sum $u + v \in W$ (closed under addition),
For all scalars $c \in R$ and vectors $v \in W$ , the product $c v \in W$ (closed under
scalar multiplication).

If these hold, then $W$ is itself a vector space with the inherited operations.

Examples

Example 4.2.1. Line through the origin in $R^{2}$
The set

W = {(t, 2 t) ∣ t \in R}

is a subspace of $R^{2}$ . It contains the zero vector, is closed under addition, and is closed under scalar multiplication.

Example 4.2.2. The x–y plane in $R^{3}$
The set

W = {(x, y, 0) ∣ x, y \in R}

is a subspace of $R^{3}$ . It is the collection of all vectors lying in the plane through the origin parallel to the x–y plane.

Example 4.2.3. Null space of a matrix
For a matrix $A \in R^{m \times n}$ , the null space

{x \in R^{n} ∣ A x = 0}

is a subspace of $R^{n}$ . This subspace represents all solutions to the homogeneous system.

Non-Examples

Not every subset is a subspace.

The set $(x, y) \in R^{2} ∣ x \geq 0$ is not a subspace: it is not closed under scalar multiplication (a negative scalar breaks the condition).
Any line in $R^{2}$ that does not pass through the origin is not a subspace, because it does not contain $0$ .

Geometric Interpretation

Subspaces are the linear structures inside vector spaces.

In $R^{2}$ , the subspaces are: the zero vector, any line through the origin, or the entire plane.
In $R^{3}$ , the subspaces are: the zero vector, any line through the origin, any plane through the origin, or the entire space.
In higher dimensions, the same principle applies: subspaces are the flat linear pieces through the origin.

Why this matters

Subspaces capture the essential structure of linear problems. Column spaces, row spaces, and null spaces are all subspaces. Much of linear algebra consists of understanding how these subspaces intersect, span, and complement each other.

Exercises 4.2

Prove that the set $W = (x, 0) ∣ x \in R \subseteq R^{2}$ is a subspace.
Show that the line $(1 + t, 2 t) ∣ t \in R$ is not a subspace of $R^{2}$ . Which condition fails?
Determine whether the set of all vectors $(x, y, z) \in R^{3}$ satisfying $x + y + z = 0$ is a subspace.
For the matrix

A = [\begin{matrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{matrix}],

describe the null space of $A$ as a subspace of $R^{3}$ .
5. List all possible subspaces of $R^{2}$ .

4.3 Span, Basis, Dimension

The ideas of span, basis, and dimension provide the language for describing the size and structure of subspaces. Together, they tell us how a vector space is generated, how many building blocks it requires, and how those blocks can be chosen.

Span

Given a set of vectors $v_{1}, v_{2}, \dots, v_{k} \subseteq V$ , the span is the collection of all linear combinations:

span {v_{1}, \dots, v_{k}} = {c_{1} v_{1} + \dots + c_{k} v_{k} ∣ c_{i} \in R} .

The span is always a subspace of $V$ , namely the smallest subspace containing those vectors.

Example 4.3.1.
In $R^{2}$ , $ \text{span}{(1,0)} = {(x,0) \mid x \in \mathbb{R}},$ the x-axis.
Similarly, $span {(1, 0), (0, 1)} = R^{2} .$

Basis

A basis of a vector space $V$ is a set of vectors that:

Span $V$ .
Are linearly independent (no vector in the set is a linear combination of the others).

If either condition fails, the set is not a basis.

Example 4.3.2.
In $R^{3}$ , the standard unit vectors

e_{1} = (1, 0, 0), e_{2} = (0, 1, 0), e_{3} = (0, 0, 1)

form a basis. Every vector $(x, y, z)$ can be uniquely written as

x e_{1} + y e_{2} + z e_{3} .

Dimension

The dimension of a vector space $V$ , written $\dim (V)$ , is the number of vectors in any basis of $V$ . This number is
well-defined: all bases of a vector space have the same cardinality.

Examples 4.3.3.

$\dim (R^{2}) = 2$ , with basis $(1, 0), (0, 1)$ .
$\dim (R^{3}) = 3$ , with basis $(1, 0, 0), (0, 1, 0), (0, 0, 1)$ .
The set of polynomials of degree at most 3 has dimension 4, with basis $(1, x, x^{2}, x^{3})$ .

Geometric Interpretation

The span is like the reach of a set of vectors.
A basis is the minimal set of directions needed to reach everything in the space.
The dimension is the count of those independent directions.

Lines, planes, and higher-dimensional flats can all be described in terms of span, basis, and dimension.

Why this matters

These concepts classify vector spaces and subspaces in terms of size and structure. Many theorems in linear algebra-such as the Rank–Nullity Theorem-are consequences of understanding span, basis, and dimension. In practical terms, bases are how we encode data in coordinates, and dimension tells us how much freedom a system truly has.

Exercises 4.3

Show that $(1, 0, 0)$ , $(0, 1, 0)$ , $(1, 1, 0)$ span the $x y$ -plane in $R^{3}$ . Are they a basis?
Find a basis for the line ${(2 t, - 3 t, t) : t \in R}$ in $R^{3}$ .
Determine the dimension of the subspace of $R^{3}$ defined by $x + y + z = 0$ .
Prove that any two different bases of $R^{n}$ must contain exactly $n$ vectors.
Give a basis for the set of polynomials of degree $\leq 2$ . What is its dimension?

4.4 Coordinates

Once a basis for a vector space is chosen, every vector can be expressed uniquely as a linear combination of the basis vectors. The coefficients in this combination are called the coordinates of the vector relative to that basis. Coordinates allow us to move between the abstract world of vector spaces and the concrete world of numbers.

Coordinates Relative to a Basis

Let $V$ be a vector space, and let

B = {v_{1}, v_{2}, \dots, v_{n}}

be an ordered basis for $V$ . Every vector $u \in V$ can be written uniquely as

u = c_{1} v_{1} + c_{2} v * 2 + \dots + c_{n} v * n .

The scalars $(c_{1}, c_{2}, \dots, c_{n})$ are the coordinates of $u$ relative to $B$ , written

[u] * B = [\begin{matrix} c_{1} \\ c_{2} \\ ⋮ \\ c_{n} \end{matrix}] .

Example in $R^{2}$

Example 4.4.1.
Let the basis be

B = {(1, 1), (1, - 1)} .

To find the coordinates of $u = (3, 1)$ relative to $B$ , solve

(3, 1) = c_{1} (1, 1) + c_{2} (1, - 1) .

This gives the system

{\begin{cases} c_{1} + c_{2} = 3, \\ c_{1} - c_{2} = 1. \end{cases}

Adding: $2 c_{1} = 4 ⟹ c_{1} = 2$ . Then $c_{2} = 1$ .

So,

[u] * B = [\begin{matrix} 2 \\ 1 \end{matrix}] .

Standard Coordinates

In $R^{n}$ , the standard basis is

e_{1} = (1, 0, \dots, 0), e_{2} = (0, 1, 0, \dots, 0), \dots, e_{n} = (0, \dots, 0, 1) .

Relative to this basis, the coordinates of a vector are simply its entries. Thus, column vectors are coordinate representations by default.

Change of Basis

If $B = v_{1}, \dots, v_{n}$ is a basis of $R^{n}$ , the change of basis matrix is

P = [\begin{matrix} v_{1} & v * 2 & \dots & v * n \end{matrix}],

with basis vectors as columns. For any vector $u$ ,

u = P [u] * B, [u] * B = P^{- 1} u .

Thus, switching between bases reduces to matrix multiplication.

Geometric Interpretation

Coordinates are the address of a vector relative to a chosen set of directions. Different bases are like different coordinate systems: Cartesian, rotated, skewed, or scaled. The same vector may look very different numerically depending on the basis, but its geometric identity is unchanged.

Why this matters

Coordinates turn abstract vectors into concrete numerical data. Changing basis is the algebraic language for rotations of axes, diagonalization of matrices, and principal component analysis in data science. Mastery of coordinates is essential for moving fluidly between geometry, algebra, and computation.

Exercises 4.4

Express $(4, 2)$ in terms of the basis $(1, 1), (1, - 1)$ .
Find the coordinates of $(1, 2, 3)$ relative to the standard basis of $R^{3}$ .
If $B = {(2, 0), (0, 3)}$ , compute $[(4, 6)]_{B}$ .
Construct the change of basis matrix from the standard basis of $R^{2}$ to $B = {(1, 1), (1, - 1)}$ .
Prove that coordinate representation with respect to a basis is unique.

Chapter 5. Linear Transformations

5.1 Functions that Preserve Linearity

A central theme of linear algebra is understanding linear transformations: functions between vector spaces that preserve their algebraic structure. These transformations generalize the idea of matrix multiplication and capture the essence of linear behavior.

Definition

Let $V$ and $W$ be vector spaces over $R$ . A function

T : V \to W

is called a linear transformation (or linear map) if for all vectors $u, v \in V$ and all
scalars $c \in R$ :

Additivity:

T (u + v) = T (u) + T (v),

Homogeneity:

T (c u) = c T (u) .

If both conditions hold, then $T$ automatically respects linear combinations:

T (c_{1} v_{1} + \dots + c_{k} v_{k}) = c_{1} T (v_{1}) + \dots + c_{k} T (v * k) .

Examples

Example 5.1.1. Scaling in $R^{2}$ .
Let $T : R^{2} \to R^{2}$ be defined by

T (x, y) = (2 x, 2 y) .

This doubles the length of every vector, preserving direction. It is linear.

Example 5.1.2. Rotation.
Let $R_{θ} : R^{2} \to R^{2}$ be

R * θ (x, y) = (x \cos θ - y \sin θ, x \sin θ + y \cos θ) .

This rotates vectors by angle $θ$ . It satisfies additivity and homogeneity, hence is linear.

Example 5.1.3. Differentiation.
Let $D : R [x] \to R [x]$ be differentiation: $D (p (x)) = p^{'} (x)$ . Since derivatives respect addition and scalar multiples, differentiation is a linear transformation.

Non-Example

The map $S : R^{2} \to R^{2}$ defined by

S (x, y) = (x^{2}, y^{2})

is not linear, because $S (u + v) \neq S (u) + S (v)$ in general.

Geometric Interpretation

Linear transformations are exactly those that preserve the origin, lines through the origin, and proportions along those lines. They include familiar operations: scaling, rotations, reflections, shears, and projections. Nonlinear transformations bend or curve space, breaking these properties.

Why this matters

Linear transformations unify geometry, algebra, and computation. They explain how matrices act on vectors, how data can be rotated or projected, and how systems evolve under linear rules. Much of linear algebra is devoted to understanding these transformations, their representations, and their invariants.

Exercises 5.1

Verify that $T (x, y) = (3 x - y, 2 y)$ is a linear transformation on $R^{2}$ .
Show that $T (x, y) = (x + 1, y)$ is not linear. Which axiom fails?
Prove that if $T$ and $S$ are linear transformations, then so is $T + S$ .
Give an example of a linear transformation from $R^{3}$ to $R^{2}$ .
Let $T : R [x] \to R [x]$ be integration:

T (p (x)) = \int_{0}^{x} p (t) d t .

Prove that $T$ is a linear transformation.

5.2 Matrix Representation of Linear Maps

Every linear transformation between finite-dimensional vector spaces can be represented by a matrix. This correspondence is one of the central insights of linear algebra: it lets us use the tools of matrix arithmetic to study abstract
transformations.

From Linear Map to Matrix

Let $T : R^{n} \to R^{m}$ be a linear transformation. Choose the standard basis ${e_{1}, \dots, e_{n}}$ of $R^{n}$ , where $e_{i}$ has a 1 in the $i$ -th position and 0 elsewhere.

The action of $T$ on each basis vector determines the entire transformation:

T (e * j) = [\begin{matrix} a * 1 j \\ a_{2 j} \\ ⋮ \\ a_{m j} \end{matrix}] .

Placing these outputs as columns gives the matrix of $T$ :

[T] = A = [\begin{matrix} a_{11} & a_{12} & \dots & a_{1 n} \\ a_{21} & a_{22} & \dots & a_{2 n} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ a_{m 1} & a_{m 2} & \dots & a_{m n} \end{matrix}] .

Then for any vector $x \in R^{n}$ :

T (x) = A x .

Examples

Example 5.2.1. Scaling in $R^{2}$ .
Let $T (x, y) = (2 x, 3 y)$ . Then

T (e * 1) = (2, 0), T (e * 2) = (0, 3) .

So the matrix is

[T] = [\begin{matrix} 2 & 0 \\ 0 & 3 \end{matrix}] .

Example 5.2.2. Rotation in the plane.
The rotation transformation $R_{θ} (x, y) = (x \cos θ - y \sin θ, x \sin θ + y \cos θ)$ has matrix

[R * θ] = [\begin{matrix} \cos θ & - \sin θ \\ \sin θ & \cos θ \end{matrix}] .

Example 5.2.3. Projection onto the x-axis.
The map $P (x, y) = (x, 0)$ corresponds to

[P] = [\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix}] .

Change of Basis

Matrix representations depend on the chosen basis. If $B$ and $C$ are bases of $R^{n}$ and $R^{m}$ , then the matrix of $T : R^{n} \to R^{m}$ with respect to these bases is obtained by expressing $T (v_{j})$ in terms of $C$ for each $v_{j} \in B$ . Changing bases corresponds to conjugating the matrix by the appropriate change-of-basis matrices.

Geometric Interpretation

Matrices are not just convenient notation-they are linear maps once a basis is fixed. Every rotation, reflection, projection, shear, or scaling corresponds to multiplying by a specific matrix. Thus, studying linear transformations reduces to studying their matrices.

Why this matters

Matrix representations make linear transformations computable. They connect abstract definitions to explicit calculations, enabling algorithms for solving systems, finding eigenvalues, and performing decompositions. Applications from graphics to machine learning depend on this translation.

Exercises 5.2

Find the matrix representation of $T : R^{2} \to R^{2}$ , $T (x, y) = (x + y, x - y)$ .
Determine the matrix of the linear transformation $T : R^{3} \to R^{2}$ , $T (x, y, z) = (x + z, y - 2 z)$ .
What matrix represents reflection across the line $y = x$ in $R^{2}$ ?
Show that the matrix of the identity transformation on $R^{n}$ is $I_{n}$ .
For the differentiation map $D : R_{2} [x] \to R_{1} [x]$ , where $R_{k} [x]$ is the space of polynomials of degree at most $k$ , find the matrix of $D$ relative to the bases ${1, x, x^{2}}$ and ${1, x}$ .

5.3 Kernel and Image

To understand a linear transformation deeply, we must examine what it kills and what it produces. These ideas are captured by the kernel and the image, two fundamental subspaces associated with any linear map.

The Kernel

The kernel (or null space) of a linear transformation $T : V \to W$ is the set of all vectors in $V$ that map to the zero vector in $W$ :

\ker (T) = {v \in V ∣ T (v) = 0} .

The kernel is always a subspace of $V$ . It measures the degeneracy of the transformation-directions that collapse to nothing.

Example 5.3.1.
Let $T : R^{3} \to R^{2}$ be defined by

T (x, y, z) = (x + y, y + z) .

In matrix form,

[T] = [\begin{matrix} 1 & 1 & 0 \\ 0 & 1 & 1 \end{matrix}] .

To find the kernel, solve

[\begin{matrix} 1 & 1 & 0 \\ 0 & 1 & 1 \end{matrix}] [\begin{matrix} x \\ y \\ z \end{matrix}] = [\begin{matrix} 0 \\ 0 \end{matrix}] .

This gives the equations $x + y = 0$ , $y + z = 0$ . Hence $x = - y, z = - y$ . The kernel is

\ker (T) = {(- t, t, - t) ∣ t \in R},

a line in $R^{3}$ .

The Image

The image (or range) of a linear transformation $T : V \to W$ is the set of all outputs:

im (T) = {T (v) ∣ v \in V} \subseteq W .

Equivalently, it is the span of the columns of the representing matrix. The image is always a subspace of $W$ .

Example 5.3.2.
For the same transformation as above,

[T] = [\begin{matrix} 1 & 1 & 0 \\ 0 & 1 & 1 \end{matrix}],

the columns are $(1, 0)$ , $(1, 1)$ , and $(0, 1)$ . Since $(1, 1) = (1, 0) + (0, 1)$ , the image is

im (T) = span {(1, 0), (0, 1)} = R^{2} .

Dimension Formula (Rank–Nullity Theorem)

For a linear transformation $T : V \to W$ with $V$ finite-dimensional,

\dim (\ker (T)) + \dim (im (T)) = \dim (V) .

This fundamental result connects the lost directions (kernel) with the achieved directions (image).

Geometric Interpretation

The kernel describes how the transformation flattens space (e.g., projecting a 3D object onto a plane).
The image describes the target subspace reached by the transformation.
The rank–nullity theorem quantifies the tradeoff: the more dimensions collapse, the fewer remain in the image.

Why this matters

Kernel and image capture the essence of a linear map. They classify transformations, explain when systems have unique or infinite solutions, and form the backbone of important results like the Rank–Nullity Theorem, diagonalization, and spectral theory.

Exercises 5.3

Find the kernel and image of $T : R^{2} \to R^{2}$ , $T (x, y) = (x - y, x + y)$ .
Let $A = [\begin{matrix} 1 & 2 & 3 \\ 0 & 1 & 4 \end{matrix}]$ . Find bases for $\ker (A)$ and $im (A)$ .
For the projection map $P (x, y, z) = (x, y, 0)$ , describe the kernel and image.
Prove that $\ker (T)$ and $im (T)$ are always subspaces.
Verify the Rank–Nullity Theorem for the transformation in Example 5.3.1.

5.4 Change of Basis

Linear transformations can look very different depending on the coordinate system we use. The process of rewriting vectors and transformations relative to a new basis is called a change of basis. This concept lies at the heart of diagonalization, orthogonalization, and many computational techniques.

Coordinate Change

Suppose $V$ is an $n$ -dimensional vector space, and let $B = {v_{1}, \dots, v_{n}}$ be a basis. Every vector $x \in V$ has a coordinate vector $[x]_{B} \in R^{n}$ .

If $P$ is the change-of-basis matrix from $B$ to the standard basis, then

x = P [x] * B .

Equivalently,

[x]_{B} = P^{- 1} x .

Here, $P$ has the basis vectors of $B$ as its columns:

P = [\begin{matrix} v * 1 & v * 2 & \dots & v * n \end{matrix}] .

Transformation of Matrices

Let $T : V \to V$ be a linear transformation. Suppose its matrix in the standard basis is $A$ . In the basis $B$ , the representing matrix becomes

[T] * B = P^{- 1} A P .

Thus, changing basis corresponds to a similarity transformation of the matrix.

Example

Example 5.4.1.
Let $T : R^{2} \to R^{2}$ be given by

T (x, y) = (3 x + y, x + y) .

In the standard basis, its matrix is

A = [\begin{matrix} 3 & 1 \\ 1 & 1 \end{matrix}] .

Now consider the basis $B = {(1, 1), (1, - 1)}$ . The change-of-basis matrix is

P = [\begin{matrix} 1 & 1 \\ 1 & - 1 \end{matrix}] .

Then

[T] * B = P^{- 1} A P .

Computing gives

[T] * B = [\begin{matrix} 4 & 0 \\ 0 & 0 \end{matrix}] .

In this new basis, the transformation is diagonal: one direction is scaled by 4, the other collapsed to 0.

Geometric Interpretation

Change of basis is like rotating or skewing your coordinate grid. The underlying transformation does not change, but its description in numbers becomes simpler or more complicated depending on the basis. Finding a basis that simplifies a transformation (often a diagonal basis) is a key theme in linear algebra.

Why this matters

Change of basis connects the abstract notion of similarity to practical computation. It is the tool that allows us to diagonalize matrices, compute eigenvalues, and simplify complex transformations. In applications, it corresponds to choosing a more natural coordinate system-whether in geometry, physics, or machine learning.

Exercises 5.4

Let $A = [\begin{matrix} 2 & 1 \\ 0 & 2 \end{matrix}]$ . Compute its representation in the basis ${(1, 0), (1, 1)}$ .
Find the change-of-basis matrix from the standard basis of $R^{2}$ to ${(2, 1), (1, 1)}$ .
Prove that similar matrices (related by $P^{- 1} A P$ ) represent the same linear transformation under different bases.
Diagonalize the matrix $A = [\begin{matrix} 1 & 0 \\ 0 & - 1 \end{matrix}]$ in the basis ${(1, 1), (1, - 1)}$ .
In $R^{3}$ , let $B = {(1, 0, 0), (1, 1, 0), (1, 1, 1)}$ . Construct the change-of-basis matrix $P$ and compute $P^{- 1}$ .

Chapter 6. Determinants

6.1 Motivation and Geometric Meaning

Determinants are numerical values associated with square matrices. At first they may appear as a complicated formula, but their importance comes from what they measure: determinants encode scaling, orientation, and invertibility of linear transformations. They bridge algebra and geometry.

Determinants of $2 \times 2$ Matrices

For a $2 \times 2$ matrix

A = [\begin{matrix} a & b \\ c & d \end{matrix}],

the determinant is defined as

det (A) = a d - b c .

Geometric meaning: If $A$ represents a linear transformation of the plane, then $| det (A) |$ is the area scaling factor. For example, if $det (A) = 2$ , areas of shapes are doubled. If $det (A) = 0$ , the transformation collapses the plane to
a line: all area is lost.

Determinants of $3 \times 3$ Matrices

For

A = [\begin{matrix} a & b & c \\ d & e & f \\ g & h & i \end{matrix}],

the determinant can be computed as

det (A) = a (e i - f h) - b (d i - f g) + c (d h - e g) .

Geometric meaning: In $R^{3}$ , $| det (A) |$ is the volume scaling factor. If $det (A) < 0$ , orientation is reversed (a handedness flip), such as turning a right-handed coordinate system into a left-handed one.

General Case

For $A \in R^{n \times n}$ , the determinant is a scalar that measures how the linear transformation given by $A$ scales n-dimensional volume.

If $det (A) = 0$ : the transformation squashes space into a lower dimension, so $A$ is not invertible.
If $det (A) > 0$ : volume is scaled by $det (A)$ , orientation preserved.
If $det (A) < 0$ : volume is scaled by $| det (A) |$ , orientation reversed.

Visual Examples

Shear in $R^{2}$ :
$A = [\begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix}]$ .
Then $det (A) = 1$ . The transformation slants the unit square into a parallelogram but preserves area.
Projection in $R^{2}$ :
$A = [\begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix}]$ .
Then $det (A) = 0$ . The unit square collapses into a line segment: area vanishes.
Rotation in $R^{2}$ :
$R_{θ} = [\begin{matrix} \cos θ & - \sin θ \\ \sin θ & \cos θ \end{matrix}]$ .
Then $det (R_{θ}) = 1$ . Rotations preserve area and orientation.

Why this matters

The determinant is not just a formula-it is a measure of transformation. It tells us whether a matrix is invertible, how it distorts space, and whether it flips orientation. This geometric insight makes the determinant indispensable in analysis, geometry, and applied mathematics.

Exercises 6.1

Compute the determinant of $[\begin{matrix} 2 & 3 \\ 1 & 4 \end{matrix}]$ . What area scaling factor does it represent?
Find the determinant of the shear matrix $[\begin{matrix} 1 & 2 \\ 0 & 1 \end{matrix}]$ . What happens to the area of the unit square?
For the $3 \times 3$ matrix $[\begin{matrix} 1 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 3 \end{matrix}]$ , compute the determinant. How does it scale volume in $R^{3}$ ?
Show that any rotation matrix in $R^{2}$ has determinant $1$ .
Give an example of a $2 \times 2$ matrix with determinant $- 1$ . What geometric action does it represent?

6.2 Properties of Determinants

Beyond their geometric meaning, determinants satisfy a collection of algebraic rules that make them powerful tools in linear algebra. These properties allow us to compute efficiently, test invertibility, and understand how determinants behave under matrix operations.

Basic Properties

Let $A, B \in R^{n \times n}$ , and let $c \in R$ . Then:

Identity:

det (I_{n}) = 1.

Triangular matrices:
If $A$ is upper or lower triangular, then

det (A) = a_{11} a_{22} \dots a_{n n} .

Row/column swap:
Interchanging two rows (or columns) multiplies the determinant by $- 1$ .
Row/column scaling:
Multiplying a row (or column) by a scalar $c$ multiplies the determinant by $c$ .
Row/column addition:
Adding a multiple of one row to another does not change the determinant.
Transpose:

det (A^{T}) = det (A) .

Multiplicativity:

det (A B) = det (A) det (B) .

Invertibility:
$A$ is invertible if and only if $det (A) \neq 0$ .

Example Computations

Example 6.2.1.
For

A = [\begin{matrix} 2 & 0 & 0 \\ 1 & 3 & 0 \\ - 1 & 4 & 5 \end{matrix}],

$A$ is lower triangular, so

det (A) = 2 \cdot 3 \cdot 5 = 30.

Example 6.2.2.
Let

B = [\begin{matrix} 1 & 2 \\ 3 & 4 \end{matrix}], C = [\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}] .

Then

det (B) = 1 \cdot 4 - 2 \cdot 3 = - 2, det (C) = - 1.

Since $C B$ is obtained by swapping rows of $B$ ,

det (C B) = - det (B) = 2.

This matches the multiplicativity rule: $det (C B) = det (C) det (B) = (- 1) (- 2) = 2.$

Geometric Insights

Row swaps: flipping orientation of space.
Scaling a row: stretching space in one direction.
Row replacement: sliding hyperplanes without altering volume.
Multiplicativity: performing two transformations multiplies their scaling factors.

These properties make determinants both computationally manageable and geometrically interpretable.

Why this matters

Determinant properties connect computation with geometry and theory. They explain why Gaussian elimination works, why invertibility is equivalent to nonzero determinant, and why determinants naturally arise in areas like volume computation, eigenvalue theory, and differential equations.

Exercises 6.2

Compute the determinant of

A = [\begin{matrix} 1 & 2 & 3 \\ 0 & 1 & 4 \\ 0 & 0 & 2 \end{matrix}] .

Show that if two rows of a square matrix are identical, then its determinant is zero.
Verify $det (A^{T}) = det (A)$ for

A = [\begin{matrix} 2 & - 1 \\ 3 & 4 \end{matrix}] .

If $A$ is invertible, prove that

det (A^{- 1}) = \frac{1}{det (A)} .

Suppose $A$ is a $3 \times 3$ matrix with $det (A) = 5$ . What is $det (2 A)$ ?

6.3 Cofactor Expansion

While determinants of small matrices can be computed directly from formulas, larger matrices require a systematic method. The cofactor expansion (also known as Laplace expansion) provides a recursive way to compute determinants by breaking them into smaller ones.

Minors and Cofactors

For an $n \times n$ matrix $A = [a_{i j}]$ :

The minor $M_{i j}$ is the determinant of the $(n - 1) \times (n - 1)$ matrix obtained by deleting the $i$ -th row and $j$
-th column of $A$ .
The cofactor $C_{i j}$ is defined by

C_{i j} = (- 1)^{i + j} M_{i j} .

The sign factor $(- 1)^{i + j}$ alternates in a checkerboard pattern:

[\begin{matrix} - & - & + & - & \dots \\ - & + & - & + & \dots \\ - & - & + & - & \dots \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋱ \end{matrix}] .

Cofactor Expansion Formula

The determinant of $A$ can be computed by expanding along any row or any column:

det (A) = \sum_{j = 1}^{n} a_{i j} C_{i j} (expansion along row i),

det (A) = \sum_{i = 1}^{n} a_{i j} C_{i j} (expansion along column j) .

Example

Example 6.3.1.
Compute

A = [\begin{matrix} 1 & 2 & 3 \\ 0 & 4 & 5 \\ 1 & 0 & 6 \end{matrix}] .

Expand along the first row:

det (A) = 1 \cdot C_{11} + 2 \cdot C_{12} + 3 \cdot C_{13} .

For $C_{11}$ :
$M_{11} = det [\begin{matrix} 4 & 5 \\ 0 & 6 \end{matrix}] = 24$ , so $C_{11} = (+ 1) (24) = 24$ .
For $C_{12}$ :
$M_{12} = det [\begin{matrix} 0 & 5 \\ 1 & 6 \end{matrix}] = 0 - 5 = - 5$ , so $C_{12} = (- 1) (- 5) = 5$ .
For $C_{13}$ :
$M_{13} = det [\begin{matrix} 0 & 4 \\ 1 & 0 \end{matrix}] = 0 - 4 = - 4$ , so $C_{13} = (+ 1) (- 4) = - 4$ .

Thus,

det (A) = 1 (24) + 2 (5) + 3 (- 4) = 24 + 10 - 12 = 22.

Properties of Cofactor Expansion

Expansion along any row or column yields the same result.
The cofactor expansion provides a recursive definition of determinant: a determinant of size $n$ is expressed in terms of determinants of size $n - 1$ .
Cofactors are fundamental in constructing the adjugate matrix, which gives a formula for inverses:

A^{- 1} = \frac{1}{det (A)} adj (A), where adj (A) = [C_{j i}] .

Geometric Interpretation

Cofactor expansion breaks down the determinant into contributions from sub-volumes defined by fixing one row or column at a time. Each cofactor measures how that row/column influences the overall volume scaling.

Why this matters

Cofactor expansion generalizes the small-matrix formulas and provides a conceptual definition of determinants. While not the most efficient way to compute determinants for large matrices, it is essential for theory, proofs, and connections to adjugates, Cramer’s rule, and classical geometry.

Exercises 6.3

Compute the determinant of

[\begin{matrix} 2 & 0 & 1 \\ 3 & - 1 & 4 \\ 1 & 2 & 0 \end{matrix}]

by cofactor expansion along the first column.

Verify that expanding along the second row of Example 6.3.1 gives the same determinant.
Prove that expansion along any row gives the same value.
Show that if a row of a matrix is zero, then its determinant is zero.
Use cofactor expansion to prove that $det (A) = det (A^{T})$ .

6.4 Applications (Volume, Invertibility Test)

Determinants are not merely algebraic curiosities; they have concrete geometric and computational uses. Two of the most important applications are measuring volumes and testing invertibility of matrices.

Determinants as Volume Scalers

Given vectors $v_{1}, v_{2}, \dots, v_{n} \in R^{n}$ , arrange them as columns of a matrix:

A = [\begin{matrix} | & | & | \\ v_{1} & v_{2} & \dots & v_{n} \\ | & | & | \end{matrix}] .

Then $| det (A) |$ equals the volume of the parallelepiped spanned by these vectors.

In $R^{2}$ , $| det (A) |$ gives the area of the parallelogram spanned by $v_{1}, v_{2}$ .
In $R^{3}$ , $| det (A) |$ gives the volume of the parallelepiped spanned
by $v_{1}, v_{2}, v_{3}$ .
In higher dimensions, it generalizes to $n$ -dimensional volume (hypervolume).

Example 6.4.1.
Let

v_{1} = (1, 0, 0), v_{2} = (1, 1, 0), v_{3} = (1, 1, 1) .

Then

A = [\begin{matrix} 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{matrix}], det (A) = 1.

So the parallelepiped has volume $1$ , even though the vectors are not orthogonal.

Invertibility Test

A square matrix $A$ is invertible if and only if $det (A) \neq 0$ .

If $det (A) = 0$ : the transformation collapses space into a lower dimension (area/volume is zero). No inverse exists.
If $det (A) \neq 0$ : the transformation scales volume by $| det (A) |$ , and is reversible.

Example 6.4.2.
The matrix

B = [\begin{matrix} 2 & 4 \\ 1 & 2 \end{matrix}]

has determinant $det (B) = 2 \cdot 2 - 4 \cdot 1 = 0$ .
Thus, $B$ is not invertible. Geometrically, the two column vectors are collinear, spanning only a line in $R^{2}$ .

Cramer’s Rule

Determinants also provide an explicit formula for solving systems of linear equations when the matrix is invertible.
For $A x = b$ with $A \in R^{n \times n}$ :

x_{i} = \frac{det (A_{i})}{det (A)},

where $A_{i}$ is obtained by replacing the $i$ -th column of $A$ with $b$ .
While inefficient computationally, Cramer’s rule highlights the determinant’s role in solutions and uniqueness.

Orientation

The sign of $det (A)$ indicates whether a transformation preserves or reverses orientation. For example, a reflection in the plane has determinant $- 1$ , flipping handedness.

Why this matters

Determinants condense key information: they measure scaling, test invertibility, and track orientation. These insights are indispensable in geometry (areas and volumes), analysis (Jacobian determinants in calculus), and computation (solving systems and checking singularity).

Exercises 6.4

Compute the area of the parallelogram spanned by $(2, 1)$ and $(1, 3)$ .
Find the volume of the parallelepiped spanned by $(1, 0, 0), (1, 1, 0), (1, 1, 1)$ .
Determine whether the matrix $[\begin{matrix} 1 & 2 \\ 3 & 6 \end{matrix}]$ is invertible. Justify using determinants.
Use Cramer’s rule to solve

{\begin{cases} x + y = 3, \\ 2 x - y = 0. \end{cases}

Explain geometrically why a determinant of zero implies no inverse exists.

Chapter 7. Inner Product Spaces

7.1 Inner Products and Norms

To extend the geometric ideas of length, distance, and angle beyond $R^{2}$ and $R^{3}$ , we introduce inner products. Inner products provide a way of measuring similarity between vectors, while norms derived from them measure length. These concepts are the foundation of geometry inside vector spaces.

Inner Product

An inner product on a real vector space $V$ is a function

⟨ \cdot, \cdot ⟩ : V \times V \to R

that assigns to each pair of vectors $(u, v)$ a real number, subject to the following properties:

Symmetry:
$⟨ u, v ⟩ = ⟨ v, u ⟩ .$
Linearity in the first argument:
$⟨ a u + b w, v ⟩ = a ⟨ u, v ⟩ + b ⟨ w, v ⟩ .$
Positive-definiteness:
$⟨ v, v ⟩ \geq 0$ , and equality holds if and only if $v = 0$ .

The standard inner product on $R^{n}$ is the dot product:

⟨ u, v ⟩ = u_{1} v_{1} + u_{2} v_{2} + \dots + u_{n} v_{n} .

Norms

The norm of a vector is its length, defined in terms of the inner product:

∥ v ∥ = \sqrt{⟨ v, v ⟩} .

For the dot product in $R^{n}$ :

∥ (x_{1}, x_{2}, \dots, x_{n}) ∥ = \sqrt{x_{1}^{2} + x_{2}^{2} + \dots + x_{n}^{2}} .

Angles Between Vectors

The inner product allows us to define the angle $θ$ between two nonzero vectors $u, v$ by

\cos θ = \frac{⟨ u, v ⟩}{∥ u ∥ ∥ v ∥} .

Thus, two vectors are orthogonal if $⟨ u, v ⟩ = 0$ .

Examples

Example 7.1.1.
In $R^{2}$ , with $u = (1, 2)$ , $v = (3, 4)$ :

⟨ u, v ⟩ = 1 \cdot 3 + 2 \cdot 4 = 11.

∥ u ∥ = \sqrt{1^{2} + 2^{2}} = \sqrt{5}, ∥ v ∥ = \sqrt{3^{2} + 4^{2}} = 5.

So,

\cos θ = \frac{11}{\sqrt{5} \cdot 5} .

Example 7.1.2.
In the function space $C [0, 1]$ , the inner product

⟨ f, g ⟩ = \int_{0}^{1} f (x) g (x) d x

defines a length

∥ f ∥ = \sqrt{\int_{0}^{1} f (x)^{2} d x} .

This generalizes geometry to infinite-dimensional spaces.

Geometric Interpretation

Inner product: measures similarity between vectors.
Norm: length of a vector.
Angle: measure of alignment between two directions.

These concepts unify algebraic operations with geometric intuition.

Why this matters

Inner products and norms allow us to extend geometry into abstract vector spaces. They form the basis of orthogonality, projections, Fourier series, least squares approximation, and many applications in physics and machine learning.

Exercises 7.1

Compute $⟨ (2, - 1, 3), (1, 4, 0) ⟩$ . Then find the angle between them.
Show that $∥ (x, y) ∥ = \sqrt{x^{2} + y^{2}}$ satisfies the properties of a norm.
In $R^{3}$ , verify that $(1, 1, 0)$ and $(1, - 1, 0)$ are orthogonal.
In $C [0, 1]$ , compute $⟨ f, g ⟩$ for $f (x) = x$ , $g (x) = 1$ .
Prove the Cauchy–Schwarz inequality:

| ⟨ u, v ⟩ | \leq ∥ u ∥ ∥ v ∥ .

7.2 Orthogonal Projections

One of the most useful applications of inner products is the notion of orthogonal projection. Projection allows us to approximate a vector by another lying in a subspace, minimizing error in the sense of distance. This idea underpins geometry, statistics, and numerical analysis.

Projection onto a Line

Let $u \in R^{n}$ be a nonzero vector. The line spanned by $u$ is

L = {c u ∣ c \in R} .

Given a vector $v$ , the projection of $v$ onto $u$ is the vector in $L$ closest to $v$ . Geometrically, it is the shadow of $v$ on the line.

The formula is

proj * u (v) = \frac{⟨ v, u ⟩}{⟨ u, u ⟩} u .

The error vector $v - {proj}_{u} (v)$ is orthogonal to $u$ .

Example 7.2.1

Let $u = (1, 2)$ , $v = (3, 1)$ .

⟨ v, u ⟩ = 3 \cdot 1 + 1 \cdot 2 = 5, ⟨ u, u ⟩ = 1^{2} + 2^{2} = 5.

proj * u (v) = \frac{5}{5} (1, 2) = (1, 2) .

The error vector is $(3, 1) - (1, 2) = (2, - 1)$ , which is orthogonal to $(1, 2)$ .

Projection onto a Subspace

Suppose $W \subseteq R^{n}$ is a subspace with orthonormal basis ${w_{1}, \dots, w_{k}}$ . The projection of a vector $v$ onto $W$ is

{proj}_{W} (v) = ⟨ v, w_{1} ⟩ w_{1} + \dots + ⟨ v, w_{k} ⟩ w_{k} .

This is the unique vector in $W$ closest to $v$ . The difference $v - {proj}_{W} (v)$ is orthogonal to all of $W$ .

Least Squares Approximation

Orthogonal projection explains the method of least squares. To solve an overdetermined system $A x \approx b$ , we seek the $x$ that makes $A x$ the projection of $b$ onto the column space of $A$ . This gives the normal equations

A^{T} A x = A^{T} b .

Thus, least squares is just projection in disguise.

Geometric Interpretation

Projection finds the closest point in a subspace to a given vector.
It minimizes distance (error) in the sense of Euclidean norm.
Orthogonality ensures the error vector points directly away from the subspace.

Why this matters

Orthogonal projection is central in both pure and applied mathematics. It underlies the geometry of subspaces, the theory of Fourier series, regression in statistics, and approximation methods in numerical linear algebra. Whenever we fit data with a simpler model, projection is at work.

Exercises 7.2

Compute the projection of $(2, 3)$ onto the vector $(1, 1)$ .
Show that $v - {proj}_{u} (v)$ is orthogonal to $u$ .
Let $W = span {(1, 0, 0), (0, 1, 0)} \subseteq R^{3}$ . Find the projection of $(1, 2, 3)$ onto $W$ .
Explain why least squares fitting corresponds to projection onto the column space of $A$ .
Prove that projection onto a subspace $W$ is unique: there is exactly one closest vector in $W$ to a given $v$ .

7.3 Gram–Schmidt Process

The Gram–Schmidt process is a systematic way to turn any linearly independent set of vectors into an orthonormal basis. This is especially useful because orthonormal bases simplify computations: inner products become simple coordinate comparisons, and projections take clean forms.

The Idea

Given a linearly independent set of vectors ${v_{1}, v_{2}, \dots, v_{n}}$ in an inner product
space, we want to construct an orthonormal set ${u_{1}, u_{2}, \dots, u_{n}}$ that spans the same
subspace.

We proceed step by step:

Start with $v_{1}$ , normalize it to get $u_{1}$ .
Subtract from $v_{2}$ its projection onto $u_{1}$ , leaving a vector orthogonal to $u_{1}$ . Normalize to get $u_{2}$ .
For each $v_{k}$ , subtract projections onto all previously constructed $u_{1}, \dots, u_{k - 1}$ , then normalize.

The Algorithm

For $k = 1, 2, \dots, n$ :

w_{k} = v * k - \sum * {j = 1}^{k - 1} ⟨ v_{k}, u_{j} ⟩ u_{j},

u_{k} = \frac{w_{k}}{∥ w_{k} ∥} .

The result ${u_{1}, \dots, u_{n}}$ is an orthonormal basis of the span of the original vectors.

Example 7.3.1

Take $v_{1} = (1, 1, 0), v_{2} = (1, 0, 1), v_{3} = (0, 1, 1)$ in $R^{3}$ .

Normalize $v_{1}$ :

u_{1} = \frac{1}{\sqrt{2}} (1, 1, 0) .

Subtract projection of $v_{2}$ on $u_{1}$ :

w_{2} = v_{2} - ⟨ v_{2}, u_{1} ⟩ u_{1} .

⟨ v_{2}, u_{1} ⟩ = \frac{1}{\sqrt{2}} (1 \cdot 1 + 0 \cdot 1 + 1 \cdot 0) = \frac{1}{\sqrt{2}} .

w_{2} = (1, 0, 1) - \frac{1}{\sqrt{2}} \cdot \frac{1}{\sqrt{2}} (1, 1, 0) = (1, 0, 1) - \frac{1}{2} (1, 1, 0) = (\frac{1}{2}, - \frac{1}{2}, 1) .

Normalize:

u_{2} = \frac{1}{\sqrt{\frac{1}{4} + \frac{1}{4} + 1}} (\frac{1}{2}, - \frac{1}{2}, 1) = \frac{1}{\sqrt{\frac{3}{2}}} (\frac{1}{2}, - \frac{1}{2}, 1) .

Subtract projections from $v_{3}$ :

w_{3} = v_{3} - ⟨ v_{3}, u_{1} ⟩ u_{1} - ⟨ v_{3}, u_{2} ⟩ u_{2} .

After computing, normalize to obtain $u_{3}$ .

The result is an orthonormal basis of the span of ${v_{1}, v_{2}, v_{3}}$ .

Geometric Interpretation

Gram–Schmidt is like straightening out a set of vectors: you start with the original directions and adjust each new vector to be perpendicular to all previous ones. Then you scale to unit length. The process ensures orthogonality while preserving the span.

Why this matters

Orthonormal bases simplify inner products, projections, and computations in general. They make coordinate systems easier to work with and are crucial in numerical methods, QR decomposition, Fourier analysis, and statistics (orthogonal polynomials, principal component analysis).

Exercises 7.3

Apply Gram–Schmidt to $(1, 0), (1, 1)$ in $R^{2}$ .
Orthogonalize $(1, 1, 1), (1, 0, 1)$ in $R^{3}$ .
Prove that each step of Gram–Schmidt yields a vector orthogonal to all previous ones.
Show that Gram–Schmidt preserves the span of the original vectors.
Explain how Gram–Schmidt leads to the QR decomposition of a matrix.

7.4 Orthonormal Bases

An orthonormal basis is a basis of a vector space in which all vectors are both orthogonal to each other and have unit length. Such bases are the most convenient possible coordinate systems: computations involving inner products, projections, and norms become exceptionally simple.

Definition

A set of vectors ${u_{1}, u_{2}, \dots, u_{n}}$ in an inner product space $V$ is called an orthonormal basis if

$⟨ u_{i}, u_{j} ⟩ = 0$ whenever $i \neq j$ (orthogonality),
$∥ u_{i} ∥ = 1$ for all $i$ (normalization),
The set spans $V$ .

Examples

Example 7.4.1. In $R^{2}$ , the standard basis

e_{1} = (1, 0), e_{2} = (0, 1)

is orthonormal under the dot product.

Example 7.4.2. In $R^{3}$ , the standard basis

e_{1} = (1, 0, 0), e_{2} = (0, 1, 0), e * 3 = (0, 0, 1)

is orthonormal.

Example 7.4.3. Fourier basis on functions:

{1, \cos x, \sin x, \cos 2 x, \sin 2 x, \dots}

is an orthogonal set in the space of square-integrable functions on $[- π, π]$ with inner product

⟨ f, g ⟩ = \int * {- π}^{π} f (x) g (x) d x .

After normalization, it becomes an orthonormal basis.

Properties

Coordinate simplicity: If ${u_{1}, \dots, u_{n}}$ is an orthonormal basis of $V$ , then any vector $v \in V$ has coordinates

[v] = [\begin{matrix} ⟨ v, u_{1} ⟩ \\ ⋮ \\ ⟨ v, u_{n} ⟩ \end{matrix}] .

That is, coordinates are just inner products.

Parseval’s identity: For any $v \in V$ ,

∥ v ∥^{2} = \sum_{i = 1}^{n} | ⟨ v, u_{i} ⟩ |^{2} .

Projections: The orthogonal projection onto the span of ${u_{1}, \dots, u_{k}}$ is

proj (v) = \sum_{i = 1}^{k} ⟨ v, u_{i} ⟩ u_{i} .

Constructing Orthonormal Bases

Start with any linearly independent set, then apply the Gram–Schmidt process to obtain an orthonormal set spanning the same subspace.
In practice, orthonormal bases are often chosen for numerical stability and simplicity of computation.

Geometric Interpretation

An orthonormal basis is like a perfectly aligned and equally scaled coordinate system. Distances and angles are computed directly using coordinates without correction factors. They are the ideal rulers of linear algebra.

Why this matters

Orthonormal bases simplify every aspect of linear algebra: solving systems, computing projections, expanding functions, diagonalizing symmetric matrices, and working with Fourier series. In data science, principal component analysis produces orthonormal directions capturing maximum variance.

Exercises 7.4

Verify that $(1 / \sqrt{2}) (1, 1)$ and $(1 / \sqrt{2}) (1, - 1)$ form an orthonormal basis of $R^{2}$ .
Express $(3, 4)$ in terms of the orthonormal basis ${(1 / \sqrt{2}) (1, 1), (1 / \sqrt{2}) (1, - 1)}$ .
Prove Parseval’s identity for $R^{n}$ with the dot product.
Find an orthonormal basis for the plane $x + y + z = 0$ in $R^{3}$ .
Explain why orthonormal bases are numerically more stable than arbitrary bases in computations.

Chapter 8. Eigenvalues and eigenvectors

8.1 Definitions and Intuition

The concepts of eigenvalues and eigenvectors reveal the most fundamental behavior of linear transformations. They identify the special directions in which a transformation acts by simple stretching or compressing, without rotation or distortion.

Definition

Let $T : V \to V$ be a linear transformation on a vector space $V$ . A nonzero vector $v \in V$ is called an eigenvector of $T$ if

T (v) = λ v

for some scalar $λ \in R$ (or $C$ ). The scalar $λ$ is the eigenvalue corresponding to $v$ .

Equivalently, if $A$ is the matrix of $T$ , then eigenvalues and eigenvectors satisfy

A v = λ v .

Basic Examples

Example 8.1.1.
Let

A = [\begin{matrix} 2 & 0 \\ 0 & 3 \end{matrix}] .

Then

A (1, 0)^{T} = 2 (1, 0)^{T}, A (0, 1)^{T} = 3 (0, 1)^{T} .

So $(1, 0)$ is an eigenvector with eigenvalue $2$ , and $(0, 1)$ is an eigenvector with eigenvalue $3$ .

Example 8.1.2.
Rotation matrix in $R^{2}$ :

R_{θ} = [\begin{matrix} \cos θ & - \sin θ \\ \sin θ & \cos θ \end{matrix}] .

If $θ \neq 0, π$ , $R_{θ}$ has no real eigenvalues: every vector is rotated, not scaled. Over $C$ , however, it has eigenvalues $e^{i θ}, e^{- i θ}$ .

Algebraic Formulation

Eigenvalues arise from solving the characteristic equation:

det (A - λ I) = 0.

This polynomial in $λ$ is the characteristic polynomial. Its roots are the eigenvalues.

Geometric Intuition

Eigenvectors are directions that remain unchanged in orientation under a transformation; only their length is scaled.
Eigenvalues tell us the scaling factor along those directions.
If a matrix has many independent eigenvectors, it can often be simplified (diagonalized) by changing basis.

Applications in Geometry and Science

Stretching along principal axes of an ellipse (quadratic forms).
Stable directions of dynamical systems.
Principal components in statistics and machine learning.
Quantum mechanics, where observables correspond to operators with eigenvalues.

Why this matters

Eigenvalues and eigenvectors are a bridge between algebra and geometry. They provide a lens for understanding linear transformations in their simplest form. Nearly every application of linear algebra-differential equations, statistics, physics, computer science-relies on eigen-analysis.

Exercises 8.1

Find the eigenvalues and eigenvectors of
$[\begin{matrix} 4 & 0 \\ 0 & - 1 \end{matrix}]$ .
Show that every scalar multiple of an eigenvector is again an eigenvector for the same eigenvalue.
Verify that the rotation matrix $R_{θ}$ has no real eigenvalues unless $θ = 0$ or $π$ .
Compute the characteristic polynomial of
$[\begin{matrix} 1 & 2 \\ 2 & 1 \end{matrix}]$ .
Explain geometrically what eigenvectors and eigenvalues represent for the shear matrix
$[\begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix}]$ .

8.2 Diagonalization

A central goal in linear algebra is to simplify the action of a matrix by choosing a good basis. Diagonalization is the process of rewriting a matrix so that it acts by simple scaling along independent directions. This makes computations such as powers, exponentials, and solving differential equations far easier.

Definition

A square matrix $A \in R^{n \times n}$ is diagonalizable if there exists an invertible matrix $P$ such that

P^{- 1} A P = D,

where $D$ is a diagonal matrix.

The diagonal entries of $D$ are eigenvalues of $A$ , and the columns of $P$ are the corresponding eigenvectors.

When is a Matrix Diagonalizable?

A matrix is diagonalizable if it has $n$ linearly independent eigenvectors.
Equivalently, the sum of the dimensions of its eigenspaces equals $n$ .
Symmetric matrices (over $R$ ) are always diagonalizable, with an orthonormal basis of eigenvectors.

Example 8.2.1

Let

A = [\begin{matrix} 4 & 1 \\ 0 & 2 \end{matrix}] .

Characteristic polynomial:

det (A - λ I) = (4 - λ) (2 - λ) .

So eigenvalues are $λ_{1} = 4$ , $λ_{2} = 2$ .

Eigenvectors:

For $λ = 4$ , solve $(A - 4 I) v = 0$ :
$[\begin{matrix} 0 & 1 \\ 0 & - 2 \end{matrix}] v = 0$ , giving $v_{1} = (1, 0)$ .
For $λ = 2$ : $(A - 2 I) v = 0$ , giving $v_{2} = (1, - 2)$ .

Construct $P = [\begin{matrix} 1 & 1 \\ 0 & - 2 \end{matrix}]$ . Then

P^{- 1} A P = [\begin{matrix} 4 & 0 \\ 0 & 2 \end{matrix}] .

Thus, $A$ is diagonalizable.

Why Diagonalize?

Computing powers:
If $A = P D P^{- 1}$ , then

A^{k} = P D^{k} P^{- 1} .

Since $D$ is diagonal, $D^{k}$ is easy to compute.

Matrix exponentials:
$e^{A} = P e^{D} P^{- 1}$ , useful in solving differential equations.
Understanding geometry:
Diagonalization reveals the directions along which a transformation stretches or compresses space independently.

Non-Diagonalizable Example

Not all matrices can be diagonalized.

A = [\begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix}]

has only one eigenvalue $λ = 1$ , with eigenspace dimension 1. Since $n = 2$ but we only have 1 independent eigenvector, $A$ is not diagonalizable.

Geometric Interpretation

Diagonalization means we have found a basis of eigenvectors. In this basis, the matrix acts by simple scaling along each coordinate axis. It transforms complicated motion into independent 1D motions.

Why this matters

Diagonalization is a cornerstone of linear algebra. It simplifies computation, reveals structure, and is the starting point for the spectral theorem, Jordan form, and many applications in physics, engineering, and data science.

Exercises 8.2

Diagonalize

A = [\begin{matrix} 2 & 0 \\ 0 & 3 \end{matrix}] .

Determine whether

A = [\begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix}]

is diagonalizable. Why or why not?

Find $A^{5}$ for

A = [\begin{matrix} 4 & 1 \\ 0 & 2 \end{matrix}]

using diagonalization.

Show that any $n \times n$ matrix with $n$ distinct eigenvalues is diagonalizable.
Explain why real symmetric matrices are always diagonalizable.

8.3 Characteristic Polynomials

The key to finding eigenvalues is the characteristic polynomial of a matrix. This polynomial encodes the values of $λ$ for which the matrix $A - λ I$ fails to be invertible.

Definition

For an $n \times n$ matrix $A$ , the characteristic polynomial is

p_{A} (λ) = det (A - λ I) .

The roots of $p_{A} (λ)$ are the eigenvalues of $A$ .

Examples

Example 8.3.1.
Let

A = [\begin{matrix} 2 & 1 \\ 1 & 2 \end{matrix}] .

Then

p_{A} (λ) = det [\begin{matrix} 2 - λ & 1 \\ 1 & 2 - λ \end{matrix}] = (2 - λ)^{2} - 1 = λ^{2} - 4 λ + 3.

Thus eigenvalues are $λ = 1, 3$ .

Example 8.3.2.
For

A = [\begin{matrix} 0 & - 1 \\ 1 & 0 \end{matrix}]

(rotation by 90°),

p_{A} (λ) = det [\begin{matrix} - λ & - 1 \\ 1 & - λ \end{matrix}] = λ^{2} + 1.

Eigenvalues are $λ = \pm i$ . No real eigenvalues exist, consistent with pure rotation.

Example 8.3.3.
For a triangular matrix

A = [\begin{matrix} 2 & 1 & 0 \\ 0 & 3 & 5 \\ 0 & 0 & 4 \end{matrix}],

the determinant is simply the product of diagonal entries minus $λ$ :

p_{A} (λ) = (2 - λ) (3 - λ) (4 - λ) .

So eigenvalues are $2, 3, 4$ .

Properties

The characteristic polynomial of an $n \times n$ matrix has degree $n$ .
The sum of the eigenvalues (counted with multiplicity) equals the trace of $A$ :

tr (A) = λ_{1} + \dots + λ_{n} .

The product of the eigenvalues equals the determinant of $A$ :

det (A) = λ_{1} \dots λ_{n} .

Similar matrices have the same characteristic polynomial, hence the same eigenvalues.

Geometric Interpretation

The characteristic polynomial captures when $A - λ I$ collapses space: its determinant is zero precisely when the transformation $A - λ I$ is singular. Thus, eigenvalues mark the critical scaling where the matrix loses invertibility.

Why this matters

Characteristic polynomials provide the computational tool to extract eigenvalues. They connect matrix invariants (trace and determinant) with geometry, and form the foundation for diagonalization, spectral theorems, and stability analysis in dynamical systems.

Exercises 8.3

Compute the characteristic polynomial of

A = [\begin{matrix} 4 & 2 \\ 1 & 3 \end{matrix}] .

Verify that the sum of the eigenvalues of
$[\begin{matrix} 5 & 0 \\ 0 & - 2 \end{matrix}]$
equals its trace, and their product equals its determinant.
Show that for any triangular matrix, the eigenvalues are just the diagonal entries.
Prove that if $A$ and $B$ are similar matrices, then $p_{A} (λ) = p_{B} (λ)$ .
Compute the characteristic polynomial of
$[\begin{matrix} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{matrix}]$ .

8.4 Applications (Differential Equations, Markov Chains)

Eigenvalues and eigenvectors are not only central to the theory of linear algebra-they are indispensable tools across mathematics and applied science. Two classic applications are solving systems of differential equations and analyzing Markov chains.

Linear Differential Equations

Consider the system

\frac{d x}{d t} = A x,

where $A$ is an $n \times n$ matrix and $x (t)$ is a vector-valued function.

If $v$ is an eigenvector of $A$ with eigenvalue $λ$ , then the function

x (t) = e^{λ t} v

is a solution.

Eigenvalues determine the growth or decay rate:
- If $λ < 0$ , solutions decay (stable).
- If $λ > 0$ , solutions grow (unstable).
- If $λ$ is complex, oscillations occur.

By combining eigenvector solutions, we can solve general initial conditions.

Example 8.4.1.
Let

A = [\begin{matrix} 2 & 0 \\ 0 & - 1 \end{matrix}] .

Then eigenvalues are $2, - 1$ with eigenvectors $(1, 0)$ , $(0, 1)$ . Solutions are

x (t) = c_{1} e^{2 t} (1, 0) + c_{2} e^{- t} (0, 1) .

Thus one component grows exponentially, the other decays.

Markov Chains

A Markov chain is described by a stochastic matrix $P$ , where each column sums to 1 and entries are nonnegative. If $x_{k}$ represents the probability distribution after $k$ steps, then

x_{k + 1} = P x_{k} .

Iterating gives

x_{k} = P^{k} x_{0} .

Understanding long-term behavior reduces to analyzing powers of $P$ .

The eigenvalue $λ = 1$ always exists. Its eigenvector gives the steady-state distribution.
All other eigenvalues satisfy $| λ | \leq 1$ . Their influence decays as $k \to \infty$ .

Example 8.4.2.
Consider

P = [\begin{matrix} 0.9 & 0.5 \\ 0.1 & 0.5 \end{matrix}] .

Eigenvalues are $λ_{1} = 1$ , $λ_{2} = 0.4$ . The eigenvector for $λ = 1$ is proportional to $(5, 1)$ .
Normalizing gives the steady state

π = (\frac{5}{6}, \frac{1}{6}) .

Thus, regardless of the starting distribution, the chain converges to $π$ .

Geometric Interpretation

In differential equations, eigenvalues determine the time evolution: exponential growth, decay, or oscillation.
In Markov chains, eigenvalues determine the long-term equilibrium of stochastic processes.

Why this matters

Eigenvalue methods turn complex iterative or dynamical systems into tractable problems. In physics, engineering, and finance, they describe stability and resonance. In computer science and statistics, they power algorithms from Google’s PageRank to modern machine learning.

Exercises 8.4

Solve $\frac{d}{d t} x = [\begin{matrix} 3 & 0 \\ 0 & - 2 \end{matrix}] x$ .
Show that if $A$ has a complex eigenvalue $α \pm i β$ , then solutions
of $\frac{d}{d t} x = A x$ involve oscillations of frequency $β$ .
Find the steady-state distribution of

P = [\begin{matrix} 0.7 & 0.2 \\ 0.3 & 0.8 \end{matrix}] .

Prove that for any stochastic matrix $P$ , $1$ is always an eigenvalue.
Explain why all eigenvalues of a stochastic matrix satisfy $| λ | \leq 1$ .

Chapter 9. Quadratic Forms and Spectral Theorems

9.1 Quadratic Forms

A quadratic form is a polynomial of degree two in several variables, expressed neatly using matrices. Quadratic forms appear throughout mathematics: in optimization, geometry of conic sections, statistics (variance), and physics (energy functions).

Definition

Let $A$ be an $n \times n$ symmetric matrix and $x \in R^{n}$ . The quadratic form associated with $A$ is

Q (x) = x^{T} A x .

Expanded,

Q (x) = \sum_{i = 1}^{n} \sum_{j = 1}^{n} a_{i j} x_{i} x_{j} .

Because $A$ is symmetric ( $a_{i j} = a_{j i}$ ), the cross-terms can be grouped naturally.

Examples

Example 9.1.1.
For

A = [\begin{matrix} 2 & 1 \\ 1 & 3 \end{matrix}], x = [\begin{matrix} x \\ y \end{matrix}],

Q (x, y) = [\begin{matrix} x & y \end{matrix}] [\begin{matrix} 2 & 1 \\ 1 & 3 \end{matrix}] [\begin{matrix} x \\ y \end{matrix}] = 2 x^{2} + 2 x y + 3 y^{2} .

Example 9.1.2.
The quadratic form

Q (x, y) = x^{2} + y^{2}

corresponds to the matrix $A = I_{2}$ . It measures squared Euclidean distance from the origin.

Example 9.1.3.
The conic section equation

4 x^{2} + 2 x y + 5 y^{2} = 1

is described by the quadratic form $x^{T} A x = 1$ with

A = [\begin{matrix} 4 & 1 \\ 1 & 5 \end{matrix}] .

Diagonalization of Quadratic Forms

By choosing a new basis consisting of eigenvectors of $A$ , we can rewrite the quadratic form without cross terms.
If $A = P D P^{- 1}$ with $D$ diagonal, then

Q (x) = x^{T} A x = (P^{- 1} x)^{T} D (P^{- 1} x) .

Thus quadratic forms can always be expressed as a sum of weighted squares:

Q (y) = λ_{1} y_{1}^{2} + \dots + λ_{n} y_{n}^{2},

where $λ_{i}$ are the eigenvalues of $A$ .

Geometric Interpretation

Quadratic forms describe geometric shapes:

In 2D: ellipses, parabolas, hyperbolas.
In 3D: ellipsoids, paraboloids, hyperboloids.
In higher dimensions: generalizations of ellipsoids.

Diagonalization aligns the coordinate axes with the principal axes of the shape.

Why this matters

Quadratic forms unify geometry and algebra. They are central in optimization (minimizing energy functions), statistics (covariance matrices and variance), mechanics (kinetic energy), and numerical analysis. Understanding quadratic forms leads directly to the spectral theorem.

Exercises 9.1

Write the quadratic form $Q (x, y) = 3 x^{2} + 4 x y + y^{2}$ as $x^{T} A x$ for some symmetric matrix $A$ .
For $A = [\begin{matrix} 1 & 2 \\ 2 & 1 \end{matrix}]$ , compute $Q (x, y)$ explicitly.
Diagonalize the quadratic form $Q (x, y) = 2 x^{2} + 2 x y + 3 y^{2}$ .
Identify the conic section given by $Q (x, y) = x^{2} - y^{2}$ .
Show that if $A$ is symmetric, quadratic forms defined by $A$ and $A^{T}$ are identical.

9.2 Positive Definite Matrices

Quadratic forms are especially important when their associated matrices are positive definite, since these guarantee positivity of energy, distance, or variance. Positive definiteness is a cornerstone in optimization, numerical analysis, and statistics.

Definition

A symmetric matrix $A \in R^{n \times n}$ is called:

Positive definite if

x^{T} A x > 0 for all nonzero x \in R^{n} .

Positive semidefinite if

x^{T} A x \geq 0 for all x .

Similarly, negative definite (always < 0) and indefinite (can be both < 0 and > 0) matrices are defined.

Examples

Example 9.2.1.

A = [\begin{matrix} 2 & 0 \\ 0 & 3 \end{matrix}]

is positive definite, since

Q (x, y) = 2 x^{2} + 3 y^{2} > 0

for all $(x, y) \neq (0, 0)$ .

Example 9.2.2.

A = [\begin{matrix} 1 & 2 \\ 2 & 1 \end{matrix}]

has quadratic form

Q (x, y) = x^{2} + 4 x y + y^{2} .

This matrix is not positive definite, since $Q (1, - 1) = - 2 < 0$ .

Characterizations

For a symmetric matrix $A$ :

Eigenvalue test: $A$ is positive definite if and only if all eigenvalues of $A$ are positive.
Principal minors test (Sylvester’s criterion): $A$ is positive definite if and only if all leading principal minors ( determinants of top-left $k \times k$ submatrices) are positive.
Cholesky factorization: $A$ is positive definite if and only if it can be written as

A = R^{T} R,

where $R$ is an upper triangular matrix with positive diagonal entries.

Geometric Interpretation

Positive definite matrices correspond to quadratic forms that define ellipsoids centered at the origin.
Positive semidefinite matrices define flattened ellipsoids (possibly degenerate).
Indefinite matrices define hyperbolas or saddle-shaped surfaces.

Applications

Optimization: Hessians of convex functions are positive semidefinite; strict convexity corresponds to positive definite Hessians.
Statistics: Covariance matrices are positive semidefinite.
Numerical methods: Cholesky decomposition is widely used to solve systems with positive definite matrices efficiently.

Why this matters

Positive definiteness provides stability and guarantees in mathematics and computation. It ensures energy functions are bounded below, optimization problems have unique solutions, and statistical models are meaningful.

Exercises 9.2

Use Sylvester’s criterion to check whether

A = [\begin{matrix} 2 & - 1 \\ - 1 & 2 \end{matrix}]

is positive definite.

Determine whether

A = [\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}]

is positive definite, semidefinite, or indefinite.

Find the eigenvalues of

A = [\begin{matrix} 4 & 2 \\ 2 & 3 \end{matrix}],

and use them to classify definiteness.

Prove that all diagonal matrices with positive entries are positive definite.
Show that if $A$ is positive definite, then so is $P^{T} A P$ for any invertible matrix $P$ .

9.3 Spectral Theorem

The spectral theorem is one of the most powerful results in linear algebra. It states that symmetric matrices can always be diagonalized by an orthogonal basis of eigenvectors. This links algebra (eigenvalues), geometry (orthogonal directions), and applications (stability, optimization, statistics).

Statement of the Spectral Theorem

If $A \in R^{n \times n}$ is symmetric ( $A^{T} = A$ ), then:

All eigenvalues of $A$ are real.
There exists an orthonormal basis of $R^{n}$ consisting of eigenvectors of $A$ .
Thus, $A$ can be written as

A = Q Λ Q^{T},

where $Q$ is an orthogonal matrix ( $Q^{T} Q = I$ ) and $Λ$ is diagonal with eigenvalues of $A$ on the diagonal.

Consequences

Symmetric matrices are always diagonalizable, and the diagonalization is numerically stable.
Quadratic forms $x^{T} A x$ can be expressed in terms of eigenvalues and eigenvectors, showing ellipsoids aligned with eigen-directions.
Positive definiteness can be checked by confirming that all eigenvalues are positive.

Example 9.3.1

Let

A = [\begin{matrix} 2 & 1 \\ 1 & 2 \end{matrix}] .

Characteristic polynomial:

p (λ) = (2 - λ)^{2} - 1 = λ^{2} - 4 λ + 3.

Eigenvalues: $λ_{1} = 1, λ_{2} = 3$ .

Eigenvectors:

For $λ = 1$ : solve $(A - I) v = 0$ , giving $(1, - 1)$ .
For $λ = 3$ : solve $(A - 3 I) v = 0$ , giving $(1, 1)$ .

Normalize eigenvectors:

u_{1} = \frac{1}{\sqrt{2}} (1, - 1), u_{2} = \frac{1}{\sqrt{2}} (1, 1) .

Then

Q = [\begin{matrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \[6 p t] - \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \end{matrix}], Λ = [\begin{matrix} 1 & 0 \\ 0 & 3 \end{matrix}] .

A = Q Λ Q^{T} .

Geometric Interpretation

The spectral theorem says every symmetric matrix acts like independent scaling along orthogonal directions. In geometry, this corresponds to stretching space along perpendicular axes.

Ellipses, ellipsoids, and quadratic surfaces can be fully understood via eigenvalues and eigenvectors.
Orthogonality ensures directions remain perpendicular after transformation.

Applications

Optimization: The spectral theorem underlies classification of critical points via eigenvalues of the Hessian.
PCA (Principal Component Analysis): Data covariance matrices are symmetric, and PCA finds orthogonal directions of maximum variance.
Differential equations & physics: Symmetric operators correspond to measurable quantities with real eigenvalues (stability, energy).

Why this matters

The spectral theorem guarantees that symmetric matrices are as simple as possible: they can always be analyzed in terms of real, orthogonal eigenvectors. This provides both deep theoretical insight and powerful computational tools.

Exercises 9.3

Diagonalize

A = [\begin{matrix} 4 & 2 \\ 2 & 3 \end{matrix}]

using the spectral theorem.

Prove that all eigenvalues of a real symmetric matrix are real.
Show that eigenvectors corresponding to distinct eigenvalues of a symmetric matrix are orthogonal.
Explain geometrically how the spectral theorem describes ellipsoids defined by quadratic forms.
Apply the spectral theorem to the covariance matrix

Σ = [\begin{matrix} 2 & 1 \\ 1 & 2 \end{matrix}],

and interpret the eigenvectors as principal directions of variance.

9.4 Principal Component Analysis (PCA)

Principal Component Analysis (PCA) is a widely used technique in data science, machine learning, and statistics. At its core, PCA is an application of the spectral theorem to covariance matrices: it finds orthogonal directions (principal components) that capture the maximum variance in data.

The Idea

Given a dataset of vectors $x_{1}, x_{2}, \dots, x_{m} \in R^{n}$ :

Center the data by subtracting the mean vector $\bar{x}$ .
Form the covariance matrix

Σ = \frac{1}{m} \sum_{i = 1}^{m} (x_{i} - \bar{x}) (x_{i} - \bar{x})^{T} .

Apply the spectral theorem: $Σ = Q Λ Q^{T}$ .
- Columns of $Q$ are orthonormal eigenvectors (principal directions).
- Eigenvalues in $Λ$ measure variance explained by each direction.

The first principal component is the eigenvector corresponding to the largest eigenvalue; it is the direction of maximum variance.

Example 9.4.1

Suppose we have two-dimensional data points roughly aligned along the line $y = x$ . The covariance matrix is approximately

Σ = [\begin{matrix} 2 & 1.9 \\ 1.9 & 2 \end{matrix}] .

Eigenvalues are about $3.9$ and $0.1$ . The eigenvector for $λ = 3.9$ is approximately $(1, 1) / \sqrt{2}$ .

First principal component: the line $y = x$ .
Most variance lies along this direction.
Second component is nearly orthogonal ( $y = - x$ ), but variance there is tiny.

Thus PCA reduces the data to essentially one dimension.

Applications of PCA

Dimensionality reduction: Represent data with fewer features while retaining most variance.
Noise reduction: Small eigenvalues correspond to noise; discarding them filters data.
Visualization: Projecting high-dimensional data onto top 2 or 3 principal components reveals structure.
Compression: PCA is used in image and signal compression.

Connection to the Spectral Theorem

The covariance matrix $Σ$ is always symmetric and positive semidefinite. Hence by the spectral theorem, it has an orthonormal basis of eigenvectors and nonnegative real eigenvalues. PCA is nothing more than re-expressing data in this eigenbasis.

Why this matters

PCA demonstrates how abstract linear algebra directly powers modern applications. Eigenvalues and eigenvectors give a practical method for simplifying data, revealing patterns, and reducing complexity. It is one of the most important algorithms derived from the spectral theorem.

Exercises 9.4

Show that the covariance matrix is symmetric and positive semidefinite.
Compute the covariance matrix of the dataset $(1, 2), (2, 3), (3, 4)$ , and find its eigenvalues and eigenvectors.
Explain why the first principal component captures the maximum variance.
In image compression, explain how PCA can reduce storage by keeping only the top $k$ principal components.
Prove that the sum of the eigenvalues of the covariance matrix equals the total variance of the dataset.

Chapter 10. Linear Algebra in Practice

10.1 Computer Graphics (Rotations, Projections)

Linear algebra is the language of modern computer graphics. Every image rendered on a screen, every 3D model rotated or projected, is ultimately the result of applying matrices to vectors. Rotations, reflections, scalings, and projections are all linear transformations, making matrices the natural tool for manipulating geometry.

Rotations in 2D

A counterclockwise rotation by an angle $θ$ in the plane is represented by

R_{θ} = [\begin{matrix} \cos θ & - \sin θ \\ \sin θ & \cos θ \end{matrix}] .

For any vector $v \in R^{2}$ , the rotated vector is

v^{'} = R_{θ} v .

This preserves lengths and angles, since $R_{θ}$ is orthogonal with determinant $1$ .

Rotations in 3D

In three dimensions, rotations are represented by $3 \times 3$ orthogonal matrices with determinant $1$ . For example, a rotation about the $z$ -axis is

R_{z} (θ) = [\begin{matrix} \cos θ & - \sin θ & 0 \\ \sin θ & \cos θ & 0 \\ 0 & 0 & 1 \end{matrix}] .

Similar formulas exist for rotations about the $x$ - and $y$ -axes.
More general 3D rotations can be described by axis–angle representation or quaternions, but the underlying idea is still linear transformations represented by matrices.

Projections

To display 3D objects on a 2D screen, we use projections:

Orthogonal projection: drops the $z$ -coordinate, mapping $(x, y, z) \mapsto (x, y)$ .

P = [\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix}] .

Perspective projection: mimics the effect of a camera. A point $(x, y, z)$ projects to

(\frac{x}{z}, \frac{y}{z}),

capturing how distant objects appear smaller.

These operations are linear (orthogonal projection) or nearly linear (perspective projection becomes linear in homogeneous coordinates).

Homogeneous Coordinates

To unify translations and projections with linear transformations, computer graphics uses homogeneous coordinates. A 3D point $(x, y, z)$ is represented as a 4D vector $(x, y, z, 1)$ . Transformations are then $4 \times 4$ matrices, which can represent rotations, scalings, and translations in a single framework.

Example: Translation by $(a, b, c)$ :

T = [\begin{matrix} 1 & 0 & 0 & a \\ 0 & 1 & 0 & b \\ 0 & 0 & 1 & c \\ 0 & 0 & 0 & 1 \end{matrix}] .

Geometric Interpretation

Rotations preserve shape and size, only changing orientation.
Projections reduce dimension: from 3D world space to 2D screen space.
Homogeneous coordinates allow us to combine multiple transformations (rotation + translation + projection) into a single matrix multiplication.

Why this matters

Linear algebra enables all real-time graphics: video games, simulations, CAD software, and movie effects. By chaining simple matrix operations, complex transformations are applied efficiently to millions of points per second.

Exercises 10.1

Write the rotation matrix for a 90° counterclockwise rotation in $R^{2}$ . Apply it to $(1, 0)$ .
Rotate the point $(1, 1, 0)$ about the $z$ -axis by 180°.
Show that the determinant of any 2D or 3D rotation matrix is 1.
Derive the orthogonal projection matrix from $R^{3}$ to the $x y$ -plane.
Explain how homogeneous coordinates allow translations to be represented as matrix multiplications.

10.2 Data Science (Dimensionality Reduction, Least Squares)

Linear algebra provides the foundation for many data science techniques. Two of the most important are dimensionality reduction, where high-dimensional datasets are compressed while preserving essential information, and the least squares method, which underlies regression and model fitting.

Dimensionality Reduction

High-dimensional data often contains redundancy: many features are correlated, meaning the data essentially lies near a lower-dimensional subspace. Dimensionality reduction identifies these subspaces.

PCA (Principal Component Analysis):
As introduced earlier, PCA diagonalizes the covariance matrix of the data.
- Eigenvectors (principal components) define orthogonal directions of maximum variance.
- Eigenvalues measure how much variance lies along each direction.
- Keeping only the top $k$ components reduces data from $n$ -dimensional space to $k$ -dimensional space while
  retaining most variability.

Example 10.2.1. A dataset of 1000 images, each with 1024 pixels, may have most variance captured by just 50 eigenvectors of the covariance matrix. Projecting onto these components compresses the data while preserving essential features.

Least Squares

Often, we have more equations than unknowns-an overdetermined system:

A x \approx b, A \in R^{m \times n}, m > n .

An exact solution may not exist. Instead, we seek $x$ that minimizes the error

∥ A x - b ∥^{2} .

This leads to the normal equations:

A^{T} A x = A^{T} b .

The solution is the orthogonal projection of $b$ onto the column space of $A$ .

Example 10.2.2

Fit a line $y = m x + c$ to data points $(x_{i}, y_{i})$ .

Matrix form:

A = [\begin{matrix} x_{1} & 1 \\ x_{2} & 1 \\ ⋮ & ⋮ \\ x_{m} & 1 \end{matrix}], b = [\begin{matrix} y_{1} \\ y_{2} \\ ⋮ \\ y_{m} \end{matrix}], x = [\begin{matrix} m \\ c \end{matrix}] .

Solve $A^{T} A x = A^{T} b$ . This yields the best-fit line in the least squares sense.

Geometric Interpretation

Dimensionality reduction: Find the best subspace capturing most variance.
Least squares: Project the target vector onto the subspace spanned by predictors.

Both are projection problems, solved using inner products and orthogonality.

Why this matters

Dimensionality reduction makes large datasets tractable, filters noise, and reveals structure. Least squares fitting powers regression, statistics, and machine learning. Both rely directly on eigenvalues, eigenvectors, and projections-core tools of linear algebra.

Exercises 10.2

Explain why PCA reduces noise in datasets by discarding small eigenvalue components.
Compute the least squares solution to fitting a line through $(0, 0), (1, 1), (2, 2)$ .
Show that the least squares solution is unique if and only if $A^{T} A$ is invertible.
Prove that the least squares solution minimizes the squared error by projection arguments.
Apply PCA to the data points $(1, 0), (2, 1), (3, 2)$ and find the first principal component.

10.3 Networks and Markov Chains

Graphs and networks provide a natural setting where linear algebra comes to life. From modeling flows and connectivity to predicting long-term behavior, matrices translate network structure into algebraic form. Markov chains, already introduced in Section 8.4, are a central example of networks evolving over time.

Adjacency Matrices

A network (graph) with $n$ nodes can be represented by an adjacency matrix $A \in R^{n \times n}$ :

A_{i j} = {\begin{cases} 1 & if there is an edge from node i to node j \\ 0 & otherwise. \end{cases}

For weighted graphs, entries may be positive weights instead of $0 / 1$ .

The number of walks of length $k$ from node $i$ to node $j$ is given by the entry $(A^{k})_{i j}$ .
Powers of adjacency matrices thus encode connectivity over time.

Laplacian Matrices

Another important matrix is the graph Laplacian:

L = D - A,

where $D$ is the diagonal degree matrix ( $D_{i i} = degree (i)$ ).

$L$ is symmetric and positive semidefinite.
The smallest eigenvalue is always $0$ , with eigenvector $(1, 1, \dots, 1)$ .
The multiplicity of eigenvalue $0$ equals the number of connected components in the graph.

This connection between eigenvalues and connectivity forms the basis of spectral graph theory.

Markov Chains on Graphs

A Markov chain can be viewed as a random walk on a graph. If $P$ is the transition matrix where $P_{i j}$ is the probability of moving from node $i$ to node $j$ , then

x_{k + 1} = P x_{k}

describes the distribution of positions after $k$ steps.

The steady-state distribution is given by the eigenvector of $P$ with eigenvalue $1$ .
The speed of convergence depends on the gap between the largest eigenvalue (which is always $1$ ) and the second largest eigenvalue.

Example 10.3.1

Consider a simple 3-node cycle graph:

P = [\begin{matrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{matrix}] .

This Markov chain cycles deterministically among the nodes. Eigenvalues are the cube roots of unity: $1, e^{2 π i / 3}, e^{4 π i / 3}$ . The eigenvalue $1$ corresponds to the steady state, which is the uniform distribution $(1 / 3, 1 / 3, 1 / 3)$ .

Applications

Search engines: Google’s PageRank algorithm models the web as a Markov chain, where steady-state probabilities rank pages.
Network analysis: Eigenvalues of adjacency or Laplacian matrices reveal communities, bottlenecks, and robustness.
Epidemiology and information flow: Random walks model how diseases or ideas spread through networks.

Why this matters

Linear algebra transforms network problems into matrix problems. Eigenvalues and eigenvectors reveal connectivity, flow, stability, and long-term dynamics. Networks are everywhere-social media, biology, finance, and the internet-so these tools are indispensable.

Exercises 10.3

Write the adjacency matrix of a square graph with 4 nodes. Compute $A^{2}$ and interpret the entries.
Show that the Laplacian of a connected graph has exactly one zero eigenvalue.
Find the steady-state distribution of the Markov chain with

P = [\begin{matrix} 0.5 & 0.5 \\ 0.4 & 0.6 \end{matrix}] .

Explain how eigenvalues of the Laplacian can detect disconnected components of a graph.
Describe how PageRank modifies the transition matrix of the web graph to ensure a unique steady-state distribution.

10.4 Machine Learning Connections

Modern machine learning is built on linear algebra. From the representation of data as matrices to the optimization of large-scale models, nearly every step relies on concepts such as vector spaces, projections, eigenvalues, and matrix decompositions.

Data as Matrices

A dataset with $m$ examples and $n$ features is represented as a matrix $X \in R^{m \times n}$ :

X = [\begin{matrix} - & x_{1}^{T} & - \\ - & x_{2}^{T} & - \\ ⋮ \\ - & x_{m}^{T} & - \end{matrix}],

where each row $x_{i} \in R^{n}$ is a feature vector. Linear algebra provides tools to analyze, compress, and transform this data.

Linear Models

At the heart of machine learning are linear predictors:

\hat{y} = X w,

where $w$ is the weight vector. Training often involves solving a least squares problem or a regularized variant such as ridge regression:

min_{w} ∥ X w - y ∥^{2} + λ ∥ w ∥^{2} .

This is solved efficiently using matrix factorizations.

Singular Value Decomposition (SVD)

The SVD of a matrix $X$ is

X = U Σ V^{T},

where $U, V$ are orthogonal and $Σ$ is diagonal with nonnegative entries (singular values).

Singular values measure the importance of directions in feature space.
SVD is used for dimensionality reduction (low-rank approximations), topic modeling, and recommender systems.

Eigenvalues in Machine Learning

PCA (Principal Component Analysis): diagonalization of the covariance matrix identifies directions of maximal variance.
Spectral clustering: uses eigenvectors of the Laplacian to group data points into clusters.
Stability analysis: eigenvalues of Hessian matrices determine whether optimization converges to a minimum.

Neural Networks

Even deep learning, though nonlinear, uses linear algebra at its core:

Each layer is a matrix multiplication followed by a nonlinear activation.
Training requires computing gradients, which are expressed in terms of matrix calculus.
Backpropagation is essentially repeated applications of the chain rule with linear algebra.

Why this matters

Machine learning models often involve datasets with millions of features and parameters. Linear algebra provides the algorithms and abstractions that make training and inference possible. Without it, large-scale computation in AI would be intractable.

Exercises 10.4

Show that ridge regression leads to the normal equations

(X^{T} X + λ I) w = X^{T} y .

Explain how SVD can be used to compress an image represented as a matrix of pixel intensities.
For a covariance matrix $Σ$ , show why its eigenvalues represent variances along principal components.
Give an example of how eigenvectors of the Laplacian matrix can be used for clustering a small graph.
In a neural network with one hidden layer, write the forward pass in matrix form.