1. Foundations and Prerequisites

Linear algebra is written in the language of sets and functions, uses scalars drawn from a field, and establishes its results through proof. This chapter builds that toolkit: the notation for collections and mappings, the number systems that serve as scalars (real, complex, and finite), and the proof techniques that appear in every later chapter. Gaps here tend to show up later as confusion about matrices and vector spaces, so the time spent on this chapter pays off throughout the guide.

<a id="11-sets-functions-and-notation"></a>

1.1 Sets, Functions, and Notation

This subchapter introduces the vocabulary used to describe collections of objects, the maps between them, and the compact notation used for sums and recursive arguments.

Set Notation and Operations

Why it matters. Linear algebra constantly talks about collections: "all solutions of a system", "all vectors in a plane", "all linear combinations of these vectors". Set notation lets us name and manipulate these collections precisely.

What a set is. A set is an unordered collection of distinct objects called elements. Think of a guest list: order does not matter, and listing a guest twice does not add a second guest. We write $x \in A$ for "$x$ is an element of $A$" and $x \notin A$ otherwise.

Two ways to describe a set:

• Roster notation lists the elements: $A = {1, 2, 3}$.
• Set-builder notation gives a membership rule: ${x \in \mathbb{R} : x > 0}$ reads "the set of real $x$ such that $x > 0$".

Standard sets used throughout this guide:

Symbol	Name	Example elements
$\mathbb{N}$	Natural numbers	$0, 1, 2, \dots$ (some authors start at 1)
$\mathbb{Z}$	Integers	$\dots, -1, 0, 1, \dots$
$\mathbb{Q}$	Rationals	$\tfrac{1}{2}, -\tfrac{7}{3}$
$\mathbb{R}$	Reals	$\sqrt{2}, \pi$
$\mathbb{C}$	Complex numbers	$3 + 4i$
$\varnothing$	Empty set	none

Relations between sets. $A \subseteq B$ ($A$ is a subset of $B$) means every element of $A$ is in $B$. Two sets are equal exactly when $A \subseteq B$ and $B \subseteq A$. This "double inclusion" is the standard way to prove two sets are equal, and it is how you will later prove that two subspaces coincide.

Operations. With $A = {1, 2, 3}$ and $B = {3, 4}$:

Operation	Notation	Definition	Result
Union	$A \cup B$	in $A$ or $B$ (or both)	${1, 2, 3, 4}$
Intersection	$A \cap B$	in both $A$ and $B$	${3}$
Difference	$A \setminus B$	in $A$ but not $B$	${1, 2}$
Complement	$A^c$	in the universe $U$ but not $A$	depends on $U$
Cartesian product	$A \times B$	ordered pairs $(a, b)$	6 pairs, e.g. $(1, 4)$

The Cartesian product matters most in this guide: $\mathbb{R}^n = \mathbb{R} \times \cdots \times \mathbb{R}$ ($n$ times) is the set of ordered $n$-tuples of reals, which is where vectors live.

  Universe U
  +-----------------------------------+
  |        A                 B        |
  |   +-----------+-----+--------+    |
  |   |   1   2   |  3  |   4    |    |
  |   +-----------+-----+--------+    |
  |    \_ A \ B _/ A ∩ B \_ B \ A_/   |
  +-----------------------------------+
     A ∪ B = {1, 2, 3, 4}: every region inside either set

De Morgan's laws relate complements to unions and intersections:

$$(A \cup B)^c = A^c \cap B^c, \qquad (A \cap B)^c = A^c \cup B^c.$$

Python's built-in set type mirrors these operations directly:

from itertools import product

A = {1, 2, 3}
B = {3, 4}

print(A | B)                      # union: {1, 2, 3, 4}
print(A & B)                      # intersection: {3}
print(A - B)                      # difference: {1, 2}
print(A <= {1, 2, 3, 4})          # subset test: True
print(set(product(A, B)))         # Cartesian product: 6 ordered pairs

# Set-builder notation {x in Z : -3 <= x <= 3, x^2 < 5} as a comprehension
S = {x for x in range(-3, 4) if x**2 < 5}
print(S)                          # {-2, -1, 0, 1, 2}

Key takeaways

• A set is unordered and has no duplicates; membership is the only thing that matters.
• Prove $A = B$ by showing $A \subseteq B$ and $B \subseteq A$.
• $\mathbb{R}^n$ is a Cartesian product, the set of ordered $n$-tuples of reals.
• De Morgan's laws turn complements of unions into intersections of complements, and the reverse.

🧪 Practice

1. Let $A = {x \in \mathbb{Z} : 0 \le x \le 6,\ x \text{ even}}$ and $B = {x \in \mathbb{Z} : 1 \le x \le 5}$. List $A \cup B$, $A \cap B$, $A \setminus B$, and $B \setminus A$.
2. Prove $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ using double inclusion.
3. Describe the set ${(x, y) \in \mathbb{R}^2 : x + y = 1} \cap {(x, y) \in \mathbb{R}^2 : x - y = 3}$ geometrically, then find its elements.
4. Interview: If $A$ has $m$ elements and $B$ has $n$ elements, how many elements does $A \times B$ have, and how many subsets does $A$ have? Hint: treat building each pair, or each subset, as a sequence of independent choices.

Functions, Domain, and Codomain

Why it matters. Linear algebra is largely the study of one kind of function: the linear map. Matrices are functions in disguise. Being precise about where a function's inputs come from and where its outputs land is essential for questions like "does $Ax = b$ have a solution?"

Definition. A function $f : A \to B$ assigns to every element $a \in A$ exactly one element $f(a) \in B$.

• $A$ is the domain (allowed inputs).
• $B$ is the codomain (the declared target set).
• The image or range $f(A) = {f(a) : a \in A}$ is the set of outputs actually produced. It is always a subset of the codomain, but it may be smaller.

Analogy. A vending machine: each button (input) dispenses exactly one item. The codomain is the catalog of everything the machine could stock. The range is what the buttons actually dispense. One button producing two items, or a button producing nothing, would break the "function" contract.

     Domain A                Codomain B
   +---------+             +-------------+
   |   a1  --+------------>|  b1         |
   |   a2  --+------------>|  b2         |     range f(A) = {b1, b2}
   |   a3  --+------------>|  (b2)       |     b3 is in B but never hit
   |         |             |  b3         |
   +---------+             +-------------+
   every input has exactly one arrow leaving it

Composition. Given $f : A \to B$ and $g : B \to C$, the composition $g \circ f : A \to C$ is $(g \circ f)(a) = g(f(a))$. Read it right to left: apply $f$ first. Composition is associative, $h \circ (g \circ f) = (h \circ g) \circ f$, but generally not commutative. This is exactly why matrix multiplication is associative but not commutative (Chapter 4).

Preimage. For $C \subseteq B$, the preimage $f^{-1}(C) = {a \in A : f(a) \in C}$ is defined for every function, invertible or not. The preimage of ${0}$ under a linear map is its kernel, a central object in Chapters 6 and 7.

Function equality. $f = g$ requires the same domain, the same codomain, and $f(a) = g(a)$ for all $a$.

A matrix defines a function between spaces of different dimensions:

import numpy as np

M = np.array([[1, 2],
              [0, 1],
              [1, 0]])          # 3x2 matrix

def T(x):
    """T : R^2 -> R^3, x |-> M x"""
    return M @ x

def S(y):
    """S : R^3 -> R, y |-> sum of entries"""
    return y.sum()

x = np.array([1, 1])
print(T(x))                     # [3 1 1]  (lands in R^3)
print(S(T(x)))                  # 5        (S o T : R^2 -> R)
# T(S(x)) is meaningless: S expects a vector in R^3, and its output is not in R^2.

The range of T is a plane through the origin in $\mathbb{R}^3$ (all combinations of the two columns of M), not all of $\mathbb{R}^3$. Its codomain and range differ.

Key takeaways

• A function sends every domain element to exactly one codomain element.
• Range is a subset of the codomain; they need not be equal.
• Composition $g \circ f$ applies $f$ first and needs the output of $f$ to be a valid input of $g$.
• Preimages exist for every function; the preimage of ${0}$ under a linear map is its kernel.

🧪 Practice

1. For $f : \mathbb{R} \to \mathbb{R}$, $f(x) = x^2$, state the domain, codomain, and range. Is the range equal to the codomain?
2. Let $f(x) = 2x + 1$ and $g(x) = x^2$. Compute $g \circ f$ and $f \circ g$ and show they are different functions.
3. Let $T : \mathbb{R}^2 \to \mathbb{R}^2$, $T(x, y) = (x + y,\ 2x + 2y)$. Describe the range geometrically and find the preimage $T^{-1}({(0, 0)})$.
4. Interview: You have a map given by a $2 \times 3$ matrix and another given by a $3 \times 2$ matrix. Which compositions are defined, and what are their domains and codomains? Hint: write each map as "from $\mathbb{R}^? \to \mathbb{R}^?$" before composing.

Injective, Surjective, and Bijective Maps

Why it matters. Solving $Ax = b$ comes down to two questions about the map $x \mapsto Ax$: does a solution exist for every $b$ (surjectivity), and is it unique (injectivity)? These properties come up again in every chapter on matrices and linear maps.

Definitions. For $f : A \to B$:

• Injective (one-to-one): different inputs give different outputs. Formally, $f(a_1) = f(a_2) \implies a_1 = a_2$.
• Surjective (onto): every element of the codomain is hit. For every $b \in B$ there exists $a \in A$ with $f(a) = b$.
• Bijective: both injective and surjective. Exactly then $f$ has an inverse $f^{-1} : B \to A$ with $f^{-1} \circ f = \mathrm{id}_A$ and $f \circ f^{-1} = \mathrm{id}_B$.

Analogy. Seating guests (domain) in chairs (codomain). Injective: no two guests share a chair. Surjective: no chair is empty. Bijective: a perfect seating where both hold.

  Injective, not surjective   Surjective, not injective    Bijective
    A        B                  A        B                  A        B
   a1 ----> b1                 a1 ----> b1                 a1 ----> b1
   a2 ----> b2                 a2 ---/                     a2 ----> b2
            b3 (missed)        a3 ----> b2                 a3 ----> b3

Property	Question it answers	For $x \mapsto Ax$ (preview)
Injective	Is the solution unique, if one exists?	$Ax = 0$ has only $x = 0$
Surjective	Does a solution exist for every $b$?	Columns of $A$ span the codomain
Bijective	Exactly one solution for every $b$?	$A$ is square and invertible

Size constraints for finite sets. If $f : A \to B$ is injective then $\lvert A \rvert \le \lvert B \rvert$; if surjective then $\lvert A \rvert \ge \lvert B \rvert$. When $\lvert A \rvert = \lvert B \rvert$ is finite, injective and surjective are equivalent. The same pattern holds for linear maps between spaces of equal dimension, which is why a square matrix with a unique solution for one $b$ has one for every $b$.

Composition facts. Composites of injections are injective; composites of surjections are surjective; composites of bijections are bijective with $(g \circ f)^{-1} = f^{-1} \circ g^{-1}$ (note the reversed order, the same as $(AB)^{-1} = B^{-1}A^{-1}$).

def is_injective(f, domain):
    images = [f(x) for x in domain]
    return len(images) == len(set(images))       # no repeated outputs

def is_surjective(f, domain, codomain):
    return {f(x) for x in domain} == set(codomain)  # every target is hit

Z7 = range(7)
Z6 = range(6)

f = lambda x: (3 * x) % 7     # on {0,...,6}: outputs 0,3,6,2,5,1,4
g = lambda x: (2 * x) % 6     # on {0,...,5}: outputs 0,2,4,0,2,4

print(is_injective(f, Z7), is_surjective(f, Z7, Z7))   # True True   -> bijective
print(is_injective(g, Z6), is_surjective(g, Z6, Z6))   # False False -> neither

Key takeaways

• Injective means unique solutions; surjective means solutions always exist.
• A function has a two-sided inverse exactly when it is bijective.
• For finite sets of equal size, injective and surjective are equivalent; square matrices behave the same way.
• Inverting a composition reverses the order: $(g \circ f)^{-1} = f^{-1} \circ g^{-1}$.

🧪 Practice

1. Classify each as injective, surjective, both, or neither: $x \mapsto x^3$ on $\mathbb{R} \to \mathbb{R}$; $x \mapsto x^2$ on $\mathbb{R} \to \mathbb{R}$; $x \mapsto x^2$ on $\mathbb{R} \to [0, \infty)$; $x \mapsto x^2$ on $[0, \infty) \to [0, \infty)$.
2. Prove that the composition of two injective functions is injective.
3. Show $T : \mathbb{R}^2 \to \mathbb{R}^2$, $T(x, y) = (x + y,\ x - y)$ is bijective by finding an explicit inverse and checking both compositions.
4. Interview: Can a linear map $T : \mathbb{R}^5 \to \mathbb{R}^3$ be injective? Can it be surjective? Hint: injectivity means no information is lost; compare how many independent directions the domain has with how many the codomain can hold.

Summation and Index Notation

Why it matters. Dot products, matrix products, determinants, and traces are all defined by sums over indices. Fluency with $\Sigma$ notation lets you read and prove these formulas instead of guessing at them.

The notation.

$$\sum_{i=1}^{n} a_i = a_1 + a_2 + \cdots + a_n.$$

The index $i$ is a dummy variable: $\sum_{i=1}^n a_i = \sum_{k=1}^n a_k$. It has no meaning outside the sum.

Core rules (for finite sums):

Rule	Statement
Linearity	$\sum_i (c,a_i + b_i) = c \sum_i a_i + \sum_i b_i$
Constant term	$\sum_{i=1}^{n} c = n c$
Splitting	$\sum_{i=1}^{n} a_i = \sum_{i=1}^{m} a_i + \sum_{i=m+1}^{n} a_i$
Reindexing	$\sum_{i=1}^{n} a_i = \sum_{j=0}^{n-1} a_{j+1}$
Swapping order	$\sum_i \sum_j a_{ij} = \sum_j \sum_i a_{ij}$
Not a rule	$\sum_i a_i b_i \ne \left(\sum_i a_i\right)\left(\sum_i b_i\right)$ in general

Index notation in linear algebra. A vector $x \in \mathbb{R}^n$ has components $x_i$; a matrix $A$ has entries $a_{ij}$ (row $i$, column $j$).

• Dot product: $x \cdot y = \sum_{i=1}^n x_i y_i$.
• Matrix-vector product: $(Ax)i = \sum{j=1}^{n} a_{ij} x_j$.
• Matrix product: $(AB){ij} = \sum{k=1}^{n} a_{ik} b_{kj}$. The summed index $k$ is "inner": it appears as the column of $A$ and the row of $B$.
• Trace: $\operatorname{tr}(A) = \sum_i a_{ii}$.

The Kronecker delta $\delta_{ij}$ equals $1$ if $i = j$ and $0$ otherwise. It is the entry formula of the identity matrix, $I_{ij} = \delta_{ij}$, and it "collapses" sums: $\sum_j \delta_{ij} x_j = x_i$.

Einstein summation convention (used in physics and Chapter 13): a repeated index is summed automatically, so $(AB){ij} = a{ik} b_{kj}$ with the $\Sigma$ omitted.

Each $\Sigma$ becomes a loop, and NumPy's einsum implements Einstein notation directly:

import numpy as np

A = np.array([[1, 2], [3, 4]])
B = np.array([[5, 6], [7, 8]])
n = 2

C = np.zeros((n, n), dtype=int)
for i in range(n):                 # free index i: row of the result
    for j in range(n):             # free index j: column of the result
        C[i, j] = sum(A[i, k] * B[k, j] for k in range(n))  # summed index k

assert np.array_equal(C, A @ B)

C2 = np.einsum('ik,kj->ij', A, B)  # repeated k is summed; i, j remain
tr = np.einsum('ii->', A)          # trace: sum of diagonal entries = 5
print(C2, tr)

Key takeaways

• Summation indices are dummy variables; free indices label the result's entries.
• $(AB){ij} = \sum_k a{ik} b_{kj}$: the summed index connects a column of $A$ to a row of $B$.
• The sum of products is not the product of sums.
• $\delta_{ij}$ represents the identity matrix and collapses any sum it appears in.

🧪 Practice

1. Evaluate $\sum_{i=1}^{4} (2i - 1)$ and $\sum_{i=1}^{3}\sum_{j=1}^{2} (i + j)$.
2. Show that $\sum_{i=1}^{n} \sum_{j=1}^{n} \delta_{ij}, x_i y_j = \sum_{i=1}^{n} x_i y_i$.
3. Write $\operatorname{tr}(AB)$ for $n \times n$ matrices as a double sum, and use it to prove $\operatorname{tr}(AB) = \operatorname{tr}(BA)$.
4. Interview: For $A$ of size $m \times n$, $B$ of size $n \times p$, and $C$ of size $p \times q$, how many scalar multiplications do $(AB)C$ and $A(BC)$ each require? Hint: each entry of a product is one inner sum; count entries times terms per sum.

Mathematical Induction

Why it matters. Many linear algebra statements hold "for all $n$": all $n \times n$ matrices, all sets of $n$ vectors, all powers $A^n$. Induction is the standard tool for proving such statements.

The idea. Picture an infinite row of dominoes. If you can show (1) the first domino falls, and (2) whenever domino $k$ falls it knocks over domino $k + 1$, then every domino falls.

To prove $P(n)$ for all integers $n \ge n_0$:

1. Base case: prove $P(n_0)$.
2. Inductive step: assume $P(k)$ for an arbitrary $k \ge n_0$ (the inductive hypothesis) and prove $P(k + 1)$.

Strong induction assumes $P(n_0), \dots, P(k)$ all hold when proving $P(k + 1)$. It is useful when the step depends on more than the immediately preceding case, for example when a matrix is split into smaller blocks.

Example 1 (classic). $\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$.

• Base: $n = 1$ gives $1 = \frac{1 \cdot 2}{2}$.
• Step: assume it for $k$. Then $\sum_{i=1}^{k+1} i = \frac{k(k+1)}{2} + (k + 1) = \frac{(k+1)(k+2)}{2}$.

Example 2 (matrix powers). For $A = \begin{pmatrix} 1 & 1 \ 0 & 1 \end{pmatrix}$, prove $A^n = \begin{pmatrix} 1 & n \ 0 & 1 \end{pmatrix}$ for $n \ge 1$.

• Base: $A^1 = A$, which matches the formula with $n = 1$.
• Step: assume $A^k = \begin{pmatrix} 1 & k \ 0 & 1 \end{pmatrix}$. Then $$A^{k+1} = A^k A = \begin{pmatrix} 1 & k \ 0 & 1 \end{pmatrix}\begin{pmatrix} 1 & 1 \ 0 & 1 \end{pmatrix} = \begin{pmatrix} 1 & k + 1 \ 0 & 1 \end{pmatrix}.$$

  P(1) true ──► P(2) true ──► P(3) true ──► ... ──► P(k) ──► P(k+1) ──► ...
  [base case]   [step k=1]    [step k=2]            [inductive step, general k]

Code can test a formula for many $n$, which is good for catching a wrong conjecture, but it never replaces the proof:

import numpy as np

A = np.array([[1, 1],
              [0, 1]])

for n in range(1, 21):
    predicted = np.array([[1, n],
                          [0, 1]])
    actual = np.linalg.matrix_power(A, n)
    assert np.array_equal(actual, predicted), f"fails at n={n}"

print("Formula holds for n = 1..20 (evidence, not a proof)")

Common pitfalls.

• Skipping the base case. The step alone can "prove" false statements, e.g. "$n = n + 1$" implies "$n + 1 = n + 2$".
• An inductive step that silently fails for small $k$. The famous "all horses are the same color" argument breaks exactly at $k = 1 \to 2$.
• Assuming $P(k + 1)$ while trying to prove it (circular reasoning).

Key takeaways

• Induction = base case + inductive step; both are required.
• Use strong induction when $P(k + 1)$ depends on several earlier cases.
• Matrix power formulas and statements about $n \times n$ matrices are natural induction targets.
• Numerical checks support a conjecture but do not prove it.

🧪 Practice

1. Prove $\sum_{i=1}^{n} (2i - 1) = n^2$ for all $n \ge 1$.
2. Prove that for $D = \begin{pmatrix} d_1 & 0 \ 0 & d_2 \end{pmatrix}$, $D^n = \begin{pmatrix} d_1^n & 0 \ 0 & d_2^n \end{pmatrix}$ for all $n \ge 1$.
3. Given that $(AB)^{-1} = B^{-1}A^{-1}$ for invertible $A, B$, prove by induction that $(A_1 A_2 \cdots A_n)^{-1} = A_n^{-1} \cdots A_2^{-1} A_1^{-1}$.
4. Interview: The "proof" that all horses are the same color removes one horse from a group of $k+1$, applies the hypothesis, then removes a different horse and applies it again. Where does it fail? Hint: check whether the two groups of $k$ horses overlap when $k + 1 = 2$.

<a id="12-number-systems-and-fields"></a>

1.2 Number Systems and Fields

The scalars that multiply vectors come from a number system. This subchapter surveys the real, complex, and finite number systems, then abstracts the rules they share into the definition of a field.

Real Numbers

Why it matters. $\mathbb{R}$ is the default scalar set for linear algebra. Lengths, angles, and least-squares fits all rely on properties that only the reals (among familiar systems) have.

The number hierarchy. Each system extends the previous one to fix a missing operation:

$$\mathbb{N} \subset \mathbb{Z} \subset \mathbb{Q} \subset \mathbb{R} \subset \mathbb{C}$$

Set	Closed under	What is missing
$\mathbb{N}$	$+$, $\times$	subtraction ($2 - 5$)
$\mathbb{Z}$	$+$, $-$, $\times$	division ($1 / 2$)
$\mathbb{Q}$	$+$, $-$, $\times$, $\div$ (nonzero)	limits and some roots ($\sqrt{2}$)
$\mathbb{R}$	all of the above, plus limits	roots of $x^2 + 1 = 0$
$\mathbb{C}$	all of the above, every polynomial has a root	ordering ($i > 0$ is meaningless)

Two defining properties of $\mathbb{R}$.

1. Ordered field: there is a consistent notion of "positive", with $a < b$ compatible with $+$ and $\times$. This is what lets us say a length $\sqrt{x_1^2 + \cdots + x_n^2}$ is nonnegative.
2. Completeness: every nonempty set of reals that is bounded above has a least upper bound (supremum). Informally, the number line has no holes. $\mathbb{Q}$ fails this: ${q \in \mathbb{Q} : q^2 < 2}$ has no least rational upper bound.

  Q:  ---o---o--o-o-oo o  o---   dense, but has "holes" at sqrt(2), pi, e, ...
  R:  ------------------------   a continuum: no holes
                     ^
                  sqrt(2) is here in R, missing from Q

Completeness matters for linear algebra because norms, limits of iterative methods (Chapter 12), and eigenvalues of symmetric matrices all need actual real numbers to exist, not just rational approximations.

Floating-point numbers are not real numbers. Computers store a finite subset of $\mathbb{R}$ (IEEE 754 doubles, about 16 significant digits). Rounding errors make exact equality tests unreliable, which matters for every numerical algorithm in later chapters.

import math
from fractions import Fraction

print(0.1 + 0.2 == 0.3)                       # False: binary rounding error
print(0.1 + 0.2)                              # 0.30000000000000004
print(math.isclose(0.1 + 0.2, 0.3))           # True: compare with a tolerance

# Exact rational arithmetic when you need it (slow, but no rounding)
print(Fraction(1, 10) + Fraction(2, 10) == Fraction(3, 10))  # True

Key takeaways

• Each number system extends the previous one to support another operation.
• $\mathbb{R}$ is an ordered, complete field; order gives meaning to length, completeness guarantees limits exist.
• $\mathbb{Q}$ is closed under arithmetic but has holes such as $\sqrt{2}$.
• Floating point approximates $\mathbb{R}$; compare computed values with a tolerance, never with ==.

🧪 Practice

1. Which of $\mathbb{N}, \mathbb{Z}, \mathbb{Q}, \mathbb{R}$ are closed under subtraction? Under division by nonzero elements? Give a counterexample for each failure.
2. Show that the vector $(1, 1) \in \mathbb{Q}^2$ has a length that is not in $\mathbb{Q}$. What does this say about using $\mathbb{Q}$ as the scalar set for geometry?
3. Explain why testing np.linalg.det(A) == 0 is a poor way to decide whether a floating-point matrix is singular, and propose a better test.
4. Interview: Gaussian elimination on a matrix with rational entries only ever produces rational numbers. Why, then, is $\mathbb{Q}$ not enough for linear algebra as a whole? Hint: think about eigenvalues of $\begin{pmatrix} 0 & 2 \ 1 & 0 \end{pmatrix}$ and about lengths.

Complex Numbers and Arithmetic

Why it matters. The rotation matrix $\begin{pmatrix} 0 & -1 \ 1 & 0 \end{pmatrix}$ turns every nonzero vector by $90^\circ$, so no real vector keeps its direction, and it has no real eigenvalues. Over $\mathbb{C}$ every square matrix has eigenvalues. Complex numbers also underpin the Fourier transform and quantum mechanics.

Definition. A complex number is $z = a + bi$ with $a, b \in \mathbb{R}$ and $i^2 = -1$. Here $a = \operatorname{Re}(z)$ is the real part and $b = \operatorname{Im}(z)$ the imaginary part.

Arithmetic. Treat $i$ as a symbol and replace $i^2$ by $-1$:

Operation	Formula
Addition	$(a + bi) + (c + di) = (a + c) + (b + d)i$
Multiplication	$(a + bi)(c + di) = (ac - bd) + (ad + bc)i$
Division	$\dfrac{a + bi}{c + di} = \dfrac{(a + bi)(c - di)}{c^2 + d^2}$ (multiply top and bottom by $c - di$)

Fundamental Theorem of Algebra. Every polynomial of degree $n \ge 1$ with complex coefficients has exactly $n$ complex roots, counted with multiplicity. In other words, $\mathbb{C}$ is algebraically closed. As a consequence, every $n \times n$ matrix has $n$ complex eigenvalues (Chapter 8).

Geometric view: the complex plane. Plot $a + bi$ as the point $(a, b)$. Addition is vector addition. Multiplication is easier to see in polar form:

$$z = r(\cos\theta + i\sin\theta) = re^{i\theta}, \qquad r = \lvert z \rvert,\ \theta = \arg z.$$

$$(r_1 e^{i\theta_1})(r_2 e^{i\theta_2}) = r_1 r_2, e^{i(\theta_1 + \theta_2)}.$$

Multiplying multiplies lengths and adds angles. Multiplying by $i = e^{i\pi/2}$ rotates by $90^\circ$.

            Im
             |
           4 +         * z = 3 + 4i
             |       /
             |     /   r = |z| = 5
             |   /
             | /  theta ≈ 53.13°
   ----------+----------+------- Re
             0          3

Analogy. A complex number is a 2D vector with an extra superpower: a multiplication that scales and rotates. In fact $a + bi$ behaves exactly like the real matrix $\begin{pmatrix} a & -b \ b & a \end{pmatrix}$, a rotation combined with a scaling.

import cmath
import numpy as np

z = 3 + 4j          # Python uses j for the imaginary unit
w = 1 - 2j

print(z + w)        # (4+2j)
print(z * w)        # (11-2j): 3 - 6j + 4j - 8j^2 = 11 - 2j
print(z / w)        # (-1+2j)
print(cmath.polar(z))   # (5.0, 0.927...): modulus and angle in radians

# a + bi  <->  [[a, -b], [b, a]]: complex multiplication = matrix multiplication
def as_matrix(c):
    return np.array([[c.real, -c.imag],
                     [c.imag,  c.real]])

assert np.allclose(as_matrix(z) @ as_matrix(w), as_matrix(z * w))

# The 90-degree rotation matrix has no real eigenvalues, but has complex ones
R = np.array([[0, -1],
              [1,  0]])
print(np.linalg.eigvals(R))  # [0.+1.j 0.-1.j]

Key takeaways

• $z = a + bi$ with $i^2 = -1$; arithmetic follows ordinary algebra plus that rule.
• Every degree-$n$ polynomial has $n$ complex roots, so every square matrix has complex eigenvalues.
• In polar form, multiplication multiplies moduli and adds angles.
• $a + bi$ corresponds to the matrix $\begin{pmatrix} a & -b \ b & a \end{pmatrix}$.

🧪 Practice

1. Compute $(2 + 3i)(4 - i)$ and $\dfrac{2 + 3i}{4 - i}$ in the form $a + bi$.
2. Write $1 + i$ in polar form and use it to compute $(1 + i)^8$ without expanding.
3. Find all complex roots of $\lambda^2 - 2\lambda + 5 = 0$. Verify that this is the characteristic polynomial $\det(A - \lambda I)$ of $A = \begin{pmatrix} 1 & -2 \ 2 & 1 \end{pmatrix}$.
4. Interview: Why do the non-real eigenvalues of a real matrix always come in pairs $a \pm bi$? Hint: the characteristic polynomial has real coefficients; see what happens when you conjugate both sides of $p(\lambda) = 0$.

Complex Conjugate and Modulus

Why it matters. For a real number, $x^2 \ge 0$ measures size. For complex numbers this fails: $i^2 = -1$. The conjugate fixes it, since $z\bar{z}$ is always a nonnegative real. This is why the complex dot product (Chapter 9) and the conjugate transpose $A^*$ (Chapter 4) include conjugates.

Definitions. For $z = a + bi$:

• Conjugate: $\bar{z} = a - bi$. Geometrically, reflection across the real axis.
• Modulus: $\lvert z \rvert = \sqrt{a^2 + b^2}$, the distance from $0$ to $z$ in the complex plane.

         Im
          |      * z = a + bi
          |    /
          |  /
   -------+-------------- Re
          |  \
          |    \
          |      * z̄ = a - bi     (mirror image across the real axis)

Properties.

Property	Formula
Conjugation respects arithmetic	$\overline{z + w} = \bar{z} + \bar{w}$, $\ \overline{zw} = \bar{z},\bar{w}$
Double conjugate	$\bar{\bar{z}} = z$
Recovering parts	$z + \bar{z} = 2\operatorname{Re}(z)$, $\ z - \bar{z} = 2i\operatorname{Im}(z)$
Real test	$z \in \mathbb{R} \iff z = \bar{z}$
Size	$z\bar{z} = \lvert z \rvert^2 = a^2 + b^2 \ge 0$
Inverse	$z^{-1} = \bar{z} / \lvert z \rvert^2$ for $z \ne 0$
Multiplicativity	$\lvert zw \rvert = \lvert z \rvert,\lvert w \rvert$
Triangle inequality	$\lvert z + w \rvert \le \lvert z \rvert + \lvert w \rvert$

Preview: complex vectors. For $v = (1, i) \in \mathbb{C}^2$, the naive "sum of squares" gives $1^2 + i^2 = 0$, a nonzero vector with zero length. The fix is $\lVert v \rVert^2 = \sum_k \lvert v_k \rvert^2 = \sum_k \bar{v}_k v_k = 1 + 1 = 2$.

import numpy as np

v = np.array([1, 1j])

print(np.sum(v * v))          # 0j: naive squared "length" of a nonzero vector is 0
print(np.vdot(v, v))          # (2+0j): vdot conjugates its first argument
print(np.linalg.norm(v))      # 1.4142...: sqrt(2), uses |v_k|^2 internally

z = 3 - 4j
print(z.conjugate(), abs(z), z * z.conjugate())   # (3+4j) 5.0 (25+0j)
print(1 / z, z.conjugate() / abs(z)**2)           # equal: z^{-1} = conj(z) / |z|^2

Key takeaways

• The conjugate flips the sign of the imaginary part; geometrically it is a reflection.
• $z\bar{z} = \lvert z \rvert^2$ is always a nonnegative real, which makes it the right measure of size.
• Conjugation commutes with $+$ and $\times$; the modulus is multiplicative.
• Complex inner products and norms must conjugate one argument, or nonzero vectors can have zero length.

🧪 Practice

1. For $z = 3 - 4i$, compute $\bar{z}$, $\lvert z \rvert$, $z\bar{z}$, and $z^{-1}$.
2. Prove $\overline{zw} = \bar{z},\bar{w}$ directly by writing $z = a + bi$ and $w = c + di$.
3. Prove that $\lvert z \rvert = 1$ if and only if $\bar{z} = z^{-1}$, and describe the set of such $z$ geometrically.
4. Interview: Why must the complex inner product conjugate one of its arguments? Hint: compute the "length squared" of $(1, i)$ with and without conjugation, and ask which axiom of length fails.

Definition of a Field

Why it matters. Gaussian elimination, determinants, and most of linear algebra use only four operations: $+$, $-$, $\times$, $\div$. Any number system where these behave "as usual" supports the same theory. A field is the precise statement of "as usual", and it lets one theorem cover $\mathbb{Q}$, $\mathbb{R}$, $\mathbb{C}$, and finite fields at once.

Analogy. A field is like an interface in programming. $\mathbb{R}$, $\mathbb{C}$, and $\mathbb{Z}_p$ are implementations. Any algorithm written only against the interface (add, subtract, multiply, divide) works with every implementation.

Definition. A field is a set $F$ with two operations, $+$ and $\cdot$, satisfying for all $a, b, c \in F$:

Axiom	Addition	Multiplication
Closure	$a + b \in F$	$ab \in F$
Associativity	$(a + b) + c = a + (b + c)$	$(ab)c = a(bc)$
Commutativity	$a + b = b + a$	$ab = ba$
Identity	exists $0$ with $a + 0 = a$	exists $1 \ne 0$ with $a \cdot 1 = a$
Inverses	exists $-a$ with $a + (-a) = 0$	if $a \ne 0$, exists $a^{-1}$ with $aa^{-1} = 1$
Distributivity	$a(b + c) = ab + ac$

Examples and non-examples.

Structure	Field?	Reason
$\mathbb{Q}, \mathbb{R}, \mathbb{C}$	Yes	All axioms hold
$\mathbb{Z}_p$, $p$ prime	Yes	See next topic
$\mathbb{Z}$	No	$2$ has no multiplicative inverse in $\mathbb{Z}$
$\mathbb{N}$	No	No additive inverses
$\mathbb{Z}_6$	No	$2 \cdot 3 = 0$, so $2$ cannot have an inverse
$2 \times 2$ real matrices	No	Multiplication is not commutative; nonzero singular matrices have no inverse

Consequences of the axioms. These hold in every field and are proved using only the axioms:

• $a \cdot 0 = 0$. (Proof: $a \cdot 0 = a(0 + 0) = a \cdot 0 + a \cdot 0$; add $-(a \cdot 0)$ to both sides.)
• $(-1)a = -a$.
• No zero divisors: if $ab = 0$ then $a = 0$ or $b = 0$. (If $a \ne 0$, then $b = a^{-1}ab = a^{-1} \cdot 0 = 0$.)

A solver written only against field operations works for any field. Here, Cramer's rule for a $2 \times 2$ system runs unchanged over $\mathbb{Q}$ and over $\mathbb{Z}_7$:

from fractions import Fraction

class GF:
    """Element of the finite field Z_p (p prime)."""
    def __init__(self, value, p):
        self.p = p
        self.v = value % p
    def __add__(self, o): return GF(self.v + o.v, self.p)
    def __sub__(self, o): return GF(self.v - o.v, self.p)
    def __mul__(self, o): return GF(self.v * o.v, self.p)
    def __truediv__(self, o):
        if o.v == 0:
            raise ZeroDivisionError("0 has no inverse")
        return self * GF(pow(o.v, -1, self.p), self.p)  # modular inverse (Python 3.8+)
    def __repr__(self): return f"{self.v} (mod {self.p})"

def solve_2x2(a, b, c, d, e, f):
    """Solve a*x + b*y = e, c*x + d*y = f using only field operations."""
    det = a * d - b * c
    x = (e * d - b * f) / det
    y = (a * f - e * c) / det
    return x, y

# 2x + y = 1,  x + 3y = 1
print(solve_2x2(*map(Fraction, [2, 1, 1, 3, 1, 1])))       # (Fraction(2, 5), Fraction(1, 5)) over Q
print(solve_2x2(*[GF(k, 7) for k in [2, 1, 1, 3, 1, 1]]))  # (6, 3) over Z_7
# Check over Z_7: 2*6 + 3 = 15 = 1 (mod 7), and 6 + 3*3 = 15 = 1 (mod 7)

Note that $2/5$ in $\mathbb{Q}$ corresponds to $6$ in $\mathbb{Z}_7$, because $5 \cdot 6 = 30 \equiv 2 \pmod 7$.

Key takeaways

• A field is a set where $+, -, \times, \div$ (by nonzero) obey the familiar rules.
• Linear algebra theorems proved from the field axioms hold for $\mathbb{Q}$, $\mathbb{R}$, $\mathbb{C}$, and $\mathbb{Z}_p$ alike.
• Fields have no zero divisors: $ab = 0$ forces $a = 0$ or $b = 0$.
• $\mathbb{Z}$, $\mathbb{Z}_6$, and matrix sets fail to be fields for different reasons.

🧪 Practice

1. Decide which are fields, and name a failing axiom for each that is not: $\mathbb{Q}$; $\mathbb{Z}$; ${0, 1}$ with arithmetic mod 2; $\mathbb{Z}_8$; the set of $2 \times 2$ real diagonal matrices.
2. Using only the field axioms, prove that $(-1) \cdot a = -a$ for every $a$ in a field.
3. Prove that if $ab = 0$ in a field then $a = 0$ or $b = 0$, and use this to show $\mathbb{Z}_6$ is not a field.
4. Interview: Why do we require the scalars of a vector space to form a field rather than allowing a ring such as $\mathbb{Z}$? Hint: run Gaussian elimination on $2x = 1$ over $\mathbb{Z}$ and find the step that breaks.

Finite Fields and Modular Arithmetic

Why it matters. Linear algebra over finite fields underpins error-correcting codes (QR codes, storage systems), cryptography (AES works in a field with 256 elements), and computer algebra. It also shows that linear algebra is not just about real geometry.

Modular arithmetic. Think of a clock: after 12 comes 1 again. For an integer $n \ge 2$,

$$a \equiv b \pmod{n} \iff n \text{ divides } a - b.$$

$\mathbb{Z}_n = {0, 1, \dots, n - 1}$ with addition and multiplication followed by "take the remainder mod $n$".

When is $\mathbb{Z}_n$ a field? Exactly when $n$ is prime. An element $a$ has a multiplicative inverse mod $n$ if and only if $\gcd(a, n) = 1$. If $n$ is prime, every nonzero $a$ qualifies. If $n = rs$ is composite, then $r \cdot s \equiv 0$ is a zero divisor, which no field can contain.

Compare the multiplication tables of $\mathbb{Z}_5$ and $\mathbb{Z}_6$ (nonzero rows):

$\times$ in $\mathbb{Z}_5$	1	2	3	4
1	1	2	3	4
2	2	4	1	3
3	3	1	4	2
4	4	3	2	1

$\times$ in $\mathbb{Z}_6$	1	2	3	4	5
1	1	2	3	4	5
2	2	4	0	2	4
3	3	0	3	0	3
4	4	2	0	4	2
5	5	4	3	2	1

In $\mathbb{Z}_5$, every row contains a $1$, so every nonzero element has an inverse (e.g. $2^{-1} = 3$). In $\mathbb{Z}_6$, the rows for 2, 3, and 4 contain zeros and no $1$: those elements have no inverse.

Computing inverses. The extended Euclidean algorithm finds $x, y$ with $ax + ny = \gcd(a, n)$. When the gcd is $1$, reducing gives $ax \equiv 1 \pmod n$, so $x$ is $a^{-1}$. For prime $p$, Fermat's little theorem gives the alternative $a^{-1} \equiv a^{p-2} \pmod p$.

The binary field $\mathbb{F}_2 = \mathbb{Z}_2$. Addition is XOR, multiplication is AND. Since $1 + 1 = 0$, every vector over $\mathbb{F}_2$ is its own negative: $v + v = 0$.

Beyond $\mathbb{Z}_p$. Finite fields exist for every prime power order $p^k$, written $\mathbb{F}{p^k}$ or $GF(p^k)$. For $k > 1$ they are not $\mathbb{Z}{p^k}$ (which has zero divisors); they are built from polynomials instead.

from itertools import product

def egcd(a, b):
    """Return (g, x, y) with a*x + b*y = g = gcd(a, b)."""
    if b == 0:
        return a, 1, 0
    g, x1, y1 = egcd(b, a % b)
    return g, y1, x1 - (a // b) * y1

def mod_inverse(a, n):
    g, x, _ = egcd(a % n, n)
    if g != 1:
        raise ValueError(f"{a} has no inverse mod {n} (gcd = {g})")
    return x % n

print(mod_inverse(3, 7))     # 5, since 3 * 5 = 15 = 2*7 + 1
print(pow(3, 7 - 2, 7))      # 5, Fermat: 3^(p-2) mod p

# A linear system over F_2:  x + y = 1,  y + z = 1,  x + y + z = 0
# A finite field has finitely many candidates, so brute force works for tiny systems
solutions = [(x, y, z) for x, y, z in product([0, 1], repeat=3)
             if (x + y) % 2 == 1
             and (y + z) % 2 == 1
             and (x + y + z) % 2 == 0]
print(solutions)             # [(1, 0, 1)]

Key takeaways

• $\mathbb{Z}_n$ is a field if and only if $n$ is prime.
• $a$ is invertible mod $n$ exactly when $\gcd(a, n) = 1$; the extended Euclidean algorithm computes the inverse.
• In $\mathbb{F}_2$, addition is XOR and $v + v = 0$ for every vector.
• Finite fields of order $p^k$ exist but are not $\mathbb{Z}_{p^k}$ when $k > 1$.

🧪 Practice

1. Write the addition and multiplication tables of $\mathbb{Z}_3$ and list the inverse of every nonzero element.
2. Compute $7^{-1} \bmod 11$ with the extended Euclidean algorithm, then confirm it with Fermat's little theorem.
3. Solve $2x + 3y = 1,\ x + 4y = 2$ over $\mathbb{R}$ and then over $\mathbb{F}_5$. Explain why the outcomes differ.
4. Interview: Why is $\mathbb{Z}_n$ a field exactly when $n$ is prime? Hint: prove both directions: relate invertibility of $a$ to $\gcd(a, n)$ for one, and exhibit a zero divisor when $n = rs$ for the other.

<a id="13-proof-techniques-in-linear-algebra"></a>

1.3 Proof Techniques in Linear Algebra

Linear algebra is a theorem-driven subject. This subchapter presents the standard proof patterns, each shown on a statement that reappears later in the guide.

Direct Proof and Contrapositive

Why it matters. Most theorems have the form "if $P$ then $Q$" ($P \implies Q$). A direct proof is the default approach; the contrapositive is the most common alternative when the direct route stalls.

Direct proof. Assume $P$, then reason step by step until you reach $Q$. In linear algebra the key move is usually to unpack definitions: write out what each term means in symbols, and the proof often follows mechanically.

Example. If $u$ and $v$ are solutions of $Ax = 0$, then so is $u + v$.

Proof. By assumption $Au = 0$ and $Av = 0$. By distributivity of matrix multiplication, $A(u + v) = Au + Av = 0 + 0 = 0$. $\blacksquare$

Example. If $Ax = b$ has two distinct solutions $x_1 \ne x_2$, then $Ax = 0$ has a nonzero solution.

Proof. Let $h = x_1 - x_2 \ne 0$. Then $Ah = Ax_1 - Ax_2 = b - b = 0$. $\blacksquare$

Contrapositive. The statement $P \implies Q$ is logically equivalent to $\neg Q \implies \neg P$. Prove the second when it is easier. Do not confuse it with the converse $Q \implies P$, which is a different statement and may be false.

$P$	$Q$	$P \implies Q$	$\neg Q \implies \neg P$ (contrapositive)	$Q \implies P$ (converse)
T	T	T	T	T
T	F	F	F	T
F	T	T	T	F
F	F	T	T	T

The first two result columns always agree; the converse differs in the third row.

Example. "If $n^2$ is even, then $n$ is even." Directly, "$n^2 = 2k$" gives no easy handle on $n$. The contrapositive "if $n$ is odd, then $n^2$ is odd" is immediate: $(2m + 1)^2 = 2(2m^2 + 2m) + 1$.

Linear algebra example. "If a set of vectors is linearly independent, then every subset is linearly independent" is the contrapositive of "if a subset is dependent, the whole set is dependent", and the second version has a one-line proof (pad the dependence relation with zero coefficients).

The truth table can be checked mechanically:

from itertools import product

def implies(p, q):
    return (not p) or q      # P -> Q is false only when P is true and Q is false

print(f"{'P':<6}{'Q':<6}{'P->Q':<7}{'~Q->~P':<8}{'Q->P'}")
for P, Q in product([True, False], repeat=2):
    print(f"{P!s:<6}{Q!s:<6}{implies(P, Q)!s:<7}"
          f"{implies(not Q, not P)!s:<8}{implies(Q, P)!s}")

Key takeaways

• Direct proof: assume the hypothesis, unpack definitions, compute to the conclusion.
• $P \implies Q$ and $\neg Q \implies \neg P$ are equivalent; the converse $Q \implies P$ is not.
• Use the contrapositive when "not $Q$" gives you something concrete to compute with.
• Many linear algebra proofs are short once every definition is written in symbols.

🧪 Practice

1. Prove directly: if $Au = 0$ and $Av = 0$, then $A(cu + dv) = 0$ for all scalars $c, d$.
2. State the converse and the contrapositive of "if a square matrix $A$ is invertible, then $Ax = 0$ has only the trivial solution." Which of the two is automatically true once the original is?
3. Prove by contrapositive: if $x + y$ is irrational, then $x$ is irrational or $y$ is irrational.
4. Interview: How do you decide between a direct proof and a contrapositive? Hint: compare what each assumption hands you. "$x \ne y$" is hard to compute with, while "$x = y$" can be substituted.

Proof by Contradiction

Why it matters. Some claims, such as irrationality, nonexistence, and uniqueness, give you no object to compute with directly. Contradiction supplies one: assume the claim is false and use that assumption as a tool.

The method. To prove $Q$ (possibly under hypothesis $P$), assume $P$ and $\neg Q$, then derive something impossible: a statement and its negation, or a violation of a known fact. Since the logic was valid, the assumption $\neg Q$ must be wrong.

Analogy. A detective rules out a suspect by assuming they are guilty and showing that this would require them to be in two cities at once.

Claim:  P implies Q.
Proof:  Assume P holds and, for contradiction, that Q is false.
          ... valid deductions ...
        This yields both R and not-R (an impossibility).
        Therefore the assumption "Q is false" fails, so Q holds.   ∎

Example 1. $\sqrt{2}$ is irrational.

Proof. Suppose $\sqrt{2} = a/b$ with integers $a, b$, $b \ne 0$, in lowest terms. Then $a^2 = 2b^2$, so $a^2$ is even, hence $a$ is even (previous topic): $a = 2k$. Then $4k^2 = 2b^2$, so $b^2 = 2k^2$ and $b$ is even. Both $a$ and $b$ are even, contradicting lowest terms. $\blacksquare$

Example 2. If $A$ is invertible, then $Ax = 0$ has only the solution $x = 0$.

Proof. Suppose some $x \ne 0$ satisfies $Ax = 0$. Multiply by $A^{-1}$: $x = A^{-1}Ax = A^{-1}0 = 0$, contradicting $x \ne 0$. $\blacksquare$

Contradiction vs. contrapositive.

Aspect	Contrapositive	Contradiction
Assumes	$\neg Q$	$P$ and $\neg Q$
Target	exactly $\neg P$	any impossibility
Flexibility	narrower	broader
Readability	usually cleaner	can hide a direct argument

Pitfall. If your "contradiction" is that $\neg Q$ led to $\neg P$, you have actually written a contrapositive proof; present it that way. Reserve contradiction for cases where the impossibility is genuinely elsewhere.

Key takeaways

• Assume the negation of what you want, then derive an impossibility.
• It suits irrationality, nonexistence, and "only the trivial solution" claims.
• If the contradiction is just $\neg P$, rewrite the argument as a contrapositive.
• Always state clearly which assumption is being contradicted.

🧪 Practice

1. Prove that $\sqrt{3}$ is irrational.
2. Prove: if $c$ is a scalar and $v$ a vector with $cv = 0$ and $v \ne 0$, then $c = 0$.
3. Prove that a system of linear equations over $\mathbb{R}$ cannot have exactly two solutions.
4. Interview: Prove that a $2 \times 2$ matrix with a row of zeros has no inverse. Hint: assume $AB = I$ and look at the row of $AB$ that corresponds to the zero row of $A$.

If and Only If Statements

Why it matters. Linear algebra is full of equivalences. The Invertible Matrix Theorem alone lists more than a dozen conditions that are all equivalent for a square matrix. Knowing how to prove "if and only if" efficiently, and how to use it, is essential.

Meaning. $P \iff Q$ ("$P$ if and only if $Q$", often written "iff") means both $P \implies Q$ and $Q \implies P$. A proof needs both directions, conventionally labeled ($\Rightarrow$) and ($\Leftarrow$).

Phrase	Logical form	Meaning
$Q$ is necessary for $P$	$P \implies Q$	$P$ cannot hold without $Q$
$Q$ is sufficient for $P$	$Q \implies P$	$Q$ alone guarantees $P$
$Q$ is necessary and sufficient for $P$	$P \iff Q$	they are interchangeable

Example. For $A = \begin{pmatrix} a & b \ c & d \end{pmatrix}$: $A$ is invertible $\iff ad - bc \ne 0$.

Proof.

($\Leftarrow$) If $ad - bc \ne 0$, the matrix $B = \frac{1}{ad - bc}\begin{pmatrix} d & -b \ -c & a \end{pmatrix}$ satisfies $AB = BA = I$ by direct multiplication.

($\Rightarrow$) Contrapositive: suppose $ad - bc = 0$; we show $A$ is not invertible. Take $x = (d, -c)$; then $Ax = (ad - bc,\ cd - dc) = (0, 0)$. If $x = 0$, take $x = (b, -a)$ instead; then $Ax = (ab - ba,\ cb - da) = (0, 0)$. If both are zero, $A$ is the zero matrix and any nonzero $x$ works. In every case $Ax = 0$ has a nonzero solution, so $A$ is not invertible by Example 2 of the previous topic. $\blacksquare$

Proving several statements equivalent. To show (a), (b), (c), (d) are all equivalent, you need not prove all twelve implications. A cycle suffices:

   (a) A is invertible  ────────►  (b) Ax = 0 has only x = 0
          ▲                                  │
          │                                  ▼
   (d) det A ≠ 0  ◄──────────────  (c) A has n pivot positions

Each statement reaches every other by following arrows, so four implications establish all equivalences. (The individual arrows are proved in Chapters 3 to 5.)

Common errors.

• Proving $P \implies Q$ twice under different names and never proving $Q \implies P$.
• Using the statement being proved inside one of its own directions (circularity).

A random test is a quick sanity check that both directions agree, but it is not a proof:

import numpy as np

rng = np.random.default_rng(0)
for _ in range(10_000):
    a, b, c, d = rng.integers(-3, 4, size=4)
    A = np.array([[a, b], [c, d]])
    det_nonzero = (a * d - b * c) != 0
    invertible = np.linalg.matrix_rank(A) == 2   # full rank <=> invertible
    assert det_nonzero == invertible             # both directions agree on every sample
print("No disagreement found (evidence, not proof)")

Key takeaways

• "Iff" requires proving two implications; label them ($\Rightarrow$) and ($\Leftarrow$).
• "Necessary" is the forward direction, "sufficient" is the backward one.
• Each direction may use a different technique (direct, contrapositive, contradiction).
• A cycle of $k$ implications proves $k$ statements equivalent.

🧪 Practice

1. Prove that an integer $n$ is even if and only if $n^2$ is even.
2. Let $f : A \to B$ where $A$ and $B$ are finite sets with the same number of elements. Prove that $f$ is injective if and only if $f$ is surjective.
3. Prove that for elements $a, b$ of a field, $ab = 0$ if and only if $a = 0$ or $b = 0$.
4. Interview: To prove that $k$ statements are all equivalent, what is the minimum number of implications you must establish, and why? Hint: model statements as nodes and implications as directed edges; every node must be able to reach every other.

Counterexamples and Existence Proofs

Why it matters. Matrix algebra breaks several rules of ordinary arithmetic, and the fastest way to see this is through counterexamples. Many theorems also assert that something exists, such as an eigenvalue or a basis, and you need to know what kind of argument establishes that.

Disproving with counterexamples. A universal claim "for all $x$, $P(x)$" is false as soon as one $x$ fails it, because

$$\neg\big(\forall x,\ P(x)\big) \equiv \exists x,\ \neg P(x), \qquad \neg\big(\exists x,\ P(x)\big) \equiv \forall x,\ \neg P(x).$$

Statement	Negation
For all $A$, $AB = BA$	There exists $A$ with $AB \ne BA$
There exists $x \ne 0$ with $Ax = 0$	For all $x \ne 0$, $Ax \ne 0$
For every $b$ there exists $x$ with $Ax = b$	There exists $b$ such that for all $x$, $Ax \ne b$

Example. Claim: $AB = BA$ for all $2 \times 2$ matrices. Take

$$A = \begin{pmatrix} 0 & 1 \ 0 & 0 \end{pmatrix}, \quad B = \begin{pmatrix} 1 & 0 \ 0 & 0 \end{pmatrix}: \qquad AB = \begin{pmatrix} 0 & 0 \ 0 & 0 \end{pmatrix}, \quad BA = \begin{pmatrix} 0 & 1 \ 0 & 0 \end{pmatrix}.$$

The same pair also disproves "if $AB = 0$ then $A = 0$ or $B = 0$": matrices, unlike fields, have zero divisors.

A toolkit of small matrices. Most false matrix claims fail on one of these:

Matrix type	Example	Useful for breaking
Zero / identity	$0$, $I$	claims about edge cases, $\det(A + B)$
Nilpotent	$\begin{pmatrix} 0 & 1 \ 0 & 0 \end{pmatrix}$	"$A^2 = 0 \implies A = 0$"
Projection	$\begin{pmatrix} 1 & 0 \ 0 & 0 \end{pmatrix}$	"$A^2 = A \implies A \in {0, I}$", cancellation laws
Rotation	$\begin{pmatrix} 0 & -1 \ 1 & 0 \end{pmatrix}$	"every real matrix has a real eigenvalue"
Non-diagonalizable	$\begin{pmatrix} 1 & 1 \ 0 & 1 \end{pmatrix}$	"every matrix is diagonalizable"

Existence proofs.

• Constructive: exhibit the object. To show $Ax = 0$ has a nonzero solution for $A = \begin{pmatrix} 1 & 2 \ 2 & 4 \end{pmatrix}$, give $x = (2, -1)$ and check.
• Non-constructive: show the object must exist without producing it. Every $n \times n$ complex matrix has an eigenvalue because its characteristic polynomial has a root (Fundamental Theorem of Algebra), even though no general formula exists for $n \ge 5$.
• Uniqueness: assume two objects $x$ and $x'$ both satisfy the property and prove $x = x'$. For example, if $AB = BA = I$ and $AC = CA = I$, then $B = BI = B(AC) = (BA)C = C$.

"There exists a unique $x$" requires both an existence and a uniqueness argument.

A random search is an effective way to find counterexamples to a conjecture before trying to prove it:

import numpy as np

rng = np.random.default_rng(1)

def find_counterexample(claim, trials=1000):
    """Search small random integer 2x2 matrices for a pair violating the claim."""
    for _ in range(trials):
        A = rng.integers(-2, 3, size=(2, 2))
        B = rng.integers(-2, 3, size=(2, 2))
        if not claim(A, B):
            return A, B
    return None                       # no counterexample found: NOT a proof

# Conjecture: (A + B)^2 = A^2 + 2AB + B^2  (true for numbers, false for matrices)
binomial = lambda A, B: np.array_equal((A + B) @ (A + B),
                                       A @ A + 2 * (A @ B) + B @ B)
print(find_counterexample(binomial))
# Any returned pair has AB != BA, since (A + B)^2 = A^2 + AB + BA + B^2

Key takeaways

• One counterexample disproves a universal claim; negating a statement swaps "for all" and "there exists".
• Try zero, identity, nilpotent, projection, and rotation matrices first.
• Existence proofs may be constructive or non-constructive; uniqueness is a separate argument.
• Failing to find a counterexample by search is evidence, never a proof.

🧪 Practice

1. Disprove: for $2 \times 2$ matrices, if $AB = AC$ and $A \ne 0$, then $B = C$.
2. Disprove: $\det(A + B) = \det A + \det B$ for all $2 \times 2$ real matrices.
3. Show that for every invertible $A$ and every vector $b$, the system $Ax = b$ has exactly one solution: prove existence by constructing $x$, and uniqueness by assuming two solutions.
4. Interview: True or false: if $A^2 = A$, then $A = 0$ or $A = I$. Justify your answer. Hint: think geometrically about a map that, applied twice, does the same as applied once, such as flattening the plane onto a line.

<a id="2-vectors-in-euclidean-space"></a>