Math 511: Linear Algebra
Formalism and Proof
Chapter One, Problem Set 1.P4 — Honors Option
Each section and exercise title is a link. At the end of each section there is a link back to this table.
- Introduction
- 1.P4.1 The Axioms of the Real Numbers
- 1.P4.2 What a Proof Is
- 1.P4.3 Linear Combinations and Span
- 1.P4.4 Solution Sets
- 1.P4.5 Matrix-Vector Algebra, Entry by Entry
- 1.P4.6 Where Completeness Will Matter
- 1.P4.7 Exercises
- Exercise 1 - Consequences of the Field Axioms
- Exercise 2 - A Gap in the Rational Numbers
- Exercise 3 - Two Limits
- Exercise 4 - Consistency and Span
- Exercise 5 - A Span Is Closed
- Exercise 6 - The Structure of a Solution Set
- Exercise 7 - Uniqueness and the Homogeneous System
- Exercise 8 - True or False
- Exercise 9 - Name the Axiom
- Exercise 10 - Complex Scalars
- Exercise 11 - Duplicated Features
- Exercise 12 - A Field Between the Rationals and the Reals
- copyleft
Introduction 
Writing Proofs in Linear Algebra¶
This is Problem Set 1.P4, the second of the two honors options for Chapter One. Where Problem Set 1.P3, Linear Systems with MATLAB, asked you to compute, this one asks you to prove. Nothing here requires a computer.
Everything you have done in Chapter One rests on properties of the real numbers that were never stated: that you may add equations, that you may multiply a row by a nonzero number and divide it back, that a pivot can be scaled to $1$. Section 1.P4.1 states those properties as axioms and adds the one axiom that separates the real numbers from the rational numbers. Sections 1.P4.3 through 1.P4.5 then prove, carefully, the facts about linear combinations, spans, and solution sets that Chapter One used informally.
A Note to the Student¶
A proof is not a longer explanation. It is an argument in which every step follows from a definition, an axiom, or a previously proved statement, and in which a reader who disagrees with you has nowhere to stand. Learning to write one is the point of this problem set.
The exercises in section 1.P4.7 are independent of one another and are labeled by topic. Your instructor will assign a subset. Write your solutions in complete sentences. A chain of equations with no words is not a proof, and neither is a correct calculation with the quantifiers left out. When a claim is false you must exhibit a counterexample; when it is true you must prove it for every case the statement covers, and no number of examples will do.
1.P4.1 The Axioms of the Real Numbers
What We Have Been Assuming¶
Every elementary row operation in Chapter One used arithmetic in $\mathbb{R}$ without comment. Adding a multiple of one row to another uses distributivity; scaling a row by a nonzero number and later undoing it uses multiplicative inverses; reordering terms in an equation uses commutativity. These properties are not theorems about the real numbers. They are the axioms that define them.
Definition¶
The Field Axioms
A field is a set $F$ with two operations, addition and multiplication, satisfying the following for all $a$, $b$, $c$ in $F$.
$$ \begin{array}{|l|l|l|} \hline & \textbf{Addition} & \textbf{Multiplication} \\ \hline \text{Associative} & (a+b)+c = a+(b+c) & (ab)c = a(bc) \\ \hline \text{Commutative} & a+b = b+a & ab = ba \\ \hline \text{Identity} & a + 0 = a & a\cdot 1 = a \\ \hline \text{Inverse} & a + (-a) = 0 & a\,a^{-1} = 1 \ \ \text{for } a \neq 0 \\ \hline \text{Distributive} & a(b+c) = ab + ac & (a+b)c = ac + bc \\ \hline \end{array} $$
with $0 \neq 1$. Both $\mathbb{R}$ and $\mathbb{C}$ are fields, and they are the only fields used in this course.
The set $\mathbb{Z}$ of integers satisfies every one of these axioms except the last one in the multiplication column: the integer $2$ has no integer multiplicative inverse. That single failure is why Gaussian elimination over the integers cannot always scale a pivot to $1$.
There exist fields with only finitely many elements, and you will meet the two-element field in coding theory, cryptography, and hashing if you work in those areas. We will not use them in this course.
Definition¶
The Order Axioms
The real numbers carry a relation $<$ such that for all $a$, $b$, $c$ in $\mathbb{R}$:
- exactly one of $a < b$, $a = b$, $b < a$ holds;
- if $a < b$ and $b < c$ then $a < c$;
- if $a < b$ then $a + c < b + c$;
- if $a < b$ and $0 < c$ then $ac < bc$.
A field with such a relation is an ordered field. Both $\mathbb{Q}$ and $\mathbb{R}$ are ordered fields.
The complex numbers form a field but not an ordered field. No relation $<$ on $\mathbb{C}$ satisfies these four axioms, because $i \neq 0$ forces $i^2 > 0$, and $i^2 = -1$. This is worth remembering: every statement about a complex quantity being positive, or smallest, or bounded, must be a statement about its modulus $|z|$, which is a real number. Later work with complex vectors depends on that distinction.
The Axiom That Separates $\mathbb{Q}$ from $\mathbb{R}$¶
The rational numbers satisfy every axiom stated so far. One more axiom is needed, and it is the reason the real numbers exist at all.
Definition¶
Bounds and the Completeness Axiom
Let $S \subseteq \mathbb{R}$ be nonempty. A number $M$ is an upper bound for $S$ if $x \leq M$ for every $x \in S$, and $S$ is bounded above if it has an upper bound. A number $L$ is a least upper bound, or supremum, of $S$ if $L$ is an upper bound for $S$ and $L \leq M$ for every upper bound $M$ of $S$.
Completeness Axiom. Every nonempty subset of $\mathbb{R}$ that is bounded above has a least upper bound in $\mathbb{R}$.
The rational numbers fail this axiom. The set
$$ S = \left\{\, x \in \mathbb{Q} \,:\, x > 0 \ \text{ and } \ x^2 < 2 \,\right\} $$
is nonempty and bounded above by $2$, yet no rational number is a least upper bound for it; Exercise 2 asks you to prove this. Informally, $\mathbb{Q}$ has a hole where $\sqrt{2}$ should be. The real numbers are what you get when every such hole is filled, and one consequence is that every real number is a limit of a sequence of rational numbers. The decimal expansion $1,\ 1.4,\ 1.41,\ 1.414,\ \ldots$ is exactly such a sequence, made of rational numbers, converging to a real number that is not rational.
Completeness is not a technicality you can postpone. Chapter Two computes powers $P^k$ of a Markov matrix and asks what happens as $k$ grows; that question has no meaning without limits, and limits have no theory without completeness.
Definition¶
Convergence of a Sequence of Real Numbers
A sequence $(a_n)$ of real numbers converges to $L \in \mathbb{R}$, written
$$ \lim_{n \to \infty} a_n = L $$
if for every $\varepsilon > 0$ there exists a positive integer $N$ such that
$$ |a_n - L| < \varepsilon \qquad \text{for every } n > N $$
A sequence that converges to no such $L$ diverges.
Read the definition in the order it is written. The adversary chooses $\varepsilon$ first, and $\varepsilon$ may be as small as they like. You must then produce an $N$, and your $N$ is allowed to depend on $\varepsilon$. This order is the whole content of the definition, and reversing it produces a statement that is both different and false.
Here is the pattern of an $\varepsilon$-$N$ proof. Start from the inequality you must establish, solve it for $n$ on scratch paper, then write the proof forward, beginning with the $N$ that your scratch work produced.
Claim. $\displaystyle \lim_{n \to \infty} \frac{1}{n} = 0$.
Proof. Let $\varepsilon > 0$ be given. By the Archimedean property of $\mathbb{R}$, which follows from completeness, there is a positive integer $N$ with $N > 1/\varepsilon$. Suppose $n > N$. Then $n > 1/\varepsilon$, and since $n$ and $\varepsilon$ are positive this gives $1/n < \varepsilon$. Therefore
$$ \left| \frac{1}{n} - 0 \right| = \frac{1}{n} < \varepsilon $$
Since $\varepsilon > 0$ was arbitrary, the sequence converges to $0$. $\blacksquare$
Notice what the proof does not do. It never chooses a particular $\varepsilon$, it never says the terms get close to $0$, and it never appeals to a picture. It exhibits an $N$ for an arbitrary $\varepsilon$, which is exactly what the definition demands.
Practice Exercise 1 - An Epsilon-N Proof¶
Prove directly from the definition that
$$ \lim_{n \to \infty} \frac{n+1}{n} = 1 $$
View Solution
Scratch work. We need $\left| \dfrac{n+1}{n} - 1 \right| < \varepsilon$. Simplify the quantity first:
$$ \left| \frac{n+1}{n} - 1 \right| = \left| \frac{n+1-n}{n} \right| = \frac{1}{n} $$
so the requirement is $1/n < \varepsilon$, which holds exactly when $n > 1/\varepsilon$. That tells us which $N$ to choose. Now write the proof forward.
Proof. Let $\varepsilon > 0$ be given. Choose a positive integer $N$ with $N > 1/\varepsilon$, which is possible by the Archimedean property. Let $n > N$. Then $n > 1/\varepsilon$, and since $n > 0$ and $\varepsilon > 0$ we may multiply both sides by $\varepsilon/n$ to obtain $\varepsilon > 1/n$. Hence
$$ \left| \frac{n+1}{n} - 1 \right| = \frac{1}{n} < \varepsilon $$
Since $\varepsilon > 0$ was arbitrary, $\lim_{n\to\infty} (n+1)/n = 1$. $\blacksquare$
The scratch work is not part of the proof and should not appear in your submission, but you should always do it. Every $\varepsilon$-$N$ proof is written backwards and read forwards.
1.P4.2 What a Proof Is
Quantifiers Come First¶
Before proving a claim you must know its logical shape, because the shape dictates what a proof and what a disproof look like.
Definition¶
Quantifiers
A universal statement asserts that a property holds for every object of some kind, written $\forall$. An existential statement asserts that at least one object has the property, written $\exists$.
$$ \begin{array}{|l|l|l|} \hline \textbf{Statement} & \textbf{To prove it} & \textbf{To disprove it} \\ \hline \forall x,\ P(x) & \text{argue for an arbitrary } x & \text{exhibit one } x \text{ with } P(x) \text{ false} \\ \hline \exists x,\ P(x) & \text{exhibit one such } x & \text{argue no } x \text{ can work} \\ \hline \end{array} $$
The negation of $\forall x,\ P(x)$ is $\exists x,\ \neg P(x)$, and the negation of $\exists x,\ P(x)$ is $\forall x,\ \neg P(x)$.
Mathematical writing hides quantifiers constantly. "A matrix with more columns than rows has a nonzero solution to $A\mathbf{x} = \mathbf{0}$" means: for every field $F$, for every $m$ and $n$ with $n > m$, and for every $m \times n$ matrix $A$ over $F$, there exists a nonzero $\mathbf{x}$ with $A\mathbf{x} = \mathbf{0}$. Two universals and an existential. Your proof must begin by taking an arbitrary such $A$ and must end by producing a specific $\mathbf{x}$.
Definition¶
Four Forms of Proof
Direct proof. To prove "if $P$ then $Q$", assume $P$ and derive $Q$ by definitions, axioms, and established results.
Counterexample. To disprove a universal statement, exhibit a single object for which it fails. One counterexample settles the matter permanently.
Double inclusion. To prove two sets are equal, prove $S \subseteq T$ and $T \subseteq S$. To prove $S \subseteq T$, take an arbitrary element of $S$ and show it lies in $T$.
Proof by cases. When the hypothesis splits into finitely many exhaustive situations, prove the conclusion in each. The cases must cover every possibility.
Evidence Is Not Proof¶
In Practice Exercise 4 of Problem Set 1.P3 you built random integer matrices with randi([0 9],6,6) and observed their behavior. That habit is valuable and it is not proof. Consider the claim
$$ \text{every } 6 \times 6 \text{ matrix whose entries are integers from } 0 \text{ to } 9 \text{ is nonsingular} $$
Generate ten thousand such matrices in MATLAB and every one of them will very likely be nonsingular. The evidence is overwhelming and the claim is false: the matrix of all zeros has integer entries from $0$ to $9$ and is singular, as does any such matrix with two equal rows. The claim is universal, so a single counterexample destroys it, and no quantity of random trials can establish it.
The reverse error is just as common. A claim that fails on a hundred random trials is false, and that observation is a disproof, provided you exhibit one failing case explicitly rather than reporting a failure rate.
Practice Exercise 2 - Evidence Is Not Proof¶
Consider the claim: for every $2 \times 2$ matrix $A$ all of whose entries are positive real numbers, the system $A\mathbf{x} = \mathbf{b}$ has a unique solution for every $\mathbf{b} \in \mathbb{R}^2$.
(a) Write the claim with its quantifiers made explicit.
(b) Decide whether the claim is true. Prove it or disprove it.
View Solution
(a) For every $A \in \mathbb{R}^{2\times 2}$ such that $a_{ij} > 0$ for all $i$ and $j$, and for every $\mathbf{b} \in \mathbb{R}^2$, there exists exactly one $\mathbf{x} \in \mathbb{R}^2$ with $A\mathbf{x} = \mathbf{b}$. The claim is universal in both $A$ and $\mathbf{b}$, so a single choice of $A$ and $\mathbf{b}$ for which it fails disproves it.
(b) The claim is false. Take
$$ A = \begin{bmatrix} 1 & 1 \\ 1 & 1 \end{bmatrix}, \qquad \mathbf{b} = \begin{bmatrix} 1 \\ 0 \end{bmatrix} $$
Every entry of $A$ is positive. If $A\mathbf{x} = \mathbf{b}$ then the first equation gives $x_1 + x_2 = 1$ and the second gives $x_1 + x_2 = 0$, so $1 = 0$, a contradiction. Hence no solution exists and the claim fails. $\blacksquare$
Note that a second counterexample is available with $\mathbf{b} = (1,1)^T$, where the system is consistent but has infinitely many solutions, so uniqueness fails as well. Either one suffices; there is no need to give both.
Observe also that positivity of the entries was a distraction. It is a hypothesis that sounds restrictive and controls nothing relevant, and recognizing that is part of reading a claim carefully.
1.P4.3 Linear Combinations and Span
Definitions Made Precise¶
Section 1.1.10 introduced linear combinations and span through pictures. Here are the same ideas stated so that they can be used in a proof. Throughout, $F$ denotes $\mathbb{R}$ or $\mathbb{C}$.
Definition¶
Linear Combination and Span
Let $\mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_k$ be vectors in $F^n$. A linear combination of these vectors is any vector of the form
$$ c_1\mathbf{v}_1 + c_2\mathbf{v}_2 + \cdots + c_k\mathbf{v}_k, \qquad c_1, \ldots, c_k \in F $$
The span of the vectors is the set of all such vectors,
$$ \operatorname{span}\{\mathbf{v}_1, \ldots, \mathbf{v}_k\} = \left\{\, c_1\mathbf{v}_1 + \cdots + c_k\mathbf{v}_k \,:\, c_1, \ldots, c_k \in F \,\right\} $$
The definition is a set built by a rule, so proving that a vector belongs to a span means exhibiting the scalars, and proving that a set is contained in a span means producing scalars for an arbitrary element of that set.
The first theorem of this problem set connects the definition to the computation you performed all through Chapter One. It is stated as a biconditional, so its proof has two halves, and each half is a direct proof.
Theorem 1¶
Consistency and Span
Let $A$ be an $m \times n$ matrix over $F$ with columns $\mathbf{a}_1, \ldots, \mathbf{a}_n$, and let $\mathbf{b} \in F^m$. Then the system $A\mathbf{x} = \mathbf{b}$ is consistent if and only if $\mathbf{b} \in \operatorname{span}\{\mathbf{a}_1, \ldots, \mathbf{a}_n\}$.
Proof. Recall from Section 1.2.1 that for any $\mathbf{x} = (x_1, \ldots, x_n)^T$ in $F^n$,
$$ A\mathbf{x} = x_1\mathbf{a}_1 + x_2\mathbf{a}_2 + \cdots + x_n\mathbf{a}_n $$
$(\Rightarrow)$ Suppose the system is consistent. Then there exists $\mathbf{x} \in F^n$ with $A\mathbf{x} = \mathbf{b}$. By the identity above, $\mathbf{b} = x_1\mathbf{a}_1 + \cdots + x_n\mathbf{a}_n$, which exhibits $\mathbf{b}$ as a linear combination of the columns with scalars $x_1, \ldots, x_n$. Hence $\mathbf{b}$ lies in the span.
$(\Leftarrow)$ Suppose $\mathbf{b} \in \operatorname{span}\{\mathbf{a}_1, \ldots, \mathbf{a}_n\}$. By definition there exist scalars $c_1, \ldots, c_n \in F$ with $\mathbf{b} = c_1\mathbf{a}_1 + \cdots + c_n\mathbf{a}_n$. Set $\mathbf{x} = (c_1, \ldots, c_n)^T$. Then $A\mathbf{x} = c_1\mathbf{a}_1 + \cdots + c_n\mathbf{a}_n = \mathbf{b}$, so the system has a solution and is consistent. $\blacksquare$
The two halves are mirror images: one direction converts a solution into scalars, the other converts scalars into a solution. That is not a coincidence but the content of the theorem, and it is why the column picture and the row-reduction procedure answer the same question.
Practice Exercise 3 - Closure of a Span¶
Let $W = \operatorname{span}\{\mathbf{v}_1, \ldots, \mathbf{v}_k\}$ in $F^n$. Prove that if $\mathbf{u} \in W$ and $\mathbf{w} \in W$ and $c \in F$, then $\mathbf{u} + \mathbf{w} \in W$ and $c\mathbf{u} \in W$.
View Solution
Proof. Let $\mathbf{u}, \mathbf{w} \in W$ and let $c \in F$ be arbitrary. By the definition of span there exist scalars $a_1, \ldots, a_k$ and $b_1, \ldots, b_k$ in $F$ with
$$ \mathbf{u} = a_1\mathbf{v}_1 + \cdots + a_k\mathbf{v}_k, \qquad \mathbf{w} = b_1\mathbf{v}_1 + \cdots + b_k\mathbf{v}_k $$
Adding and collecting the coefficient of each $\mathbf{v}_i$,
$$ \mathbf{u} + \mathbf{w} = (a_1 + b_1)\mathbf{v}_1 + \cdots + (a_k + b_k)\mathbf{v}_k $$
Each $a_i + b_i$ lies in $F$, because $F$ is closed under addition, so $\mathbf{u} + \mathbf{w}$ is a linear combination of $\mathbf{v}_1, \ldots, \mathbf{v}_k$ and therefore lies in $W$.
Similarly,
$$ c\mathbf{u} = c(a_1\mathbf{v}_1 + \cdots + a_k\mathbf{v}_k) = (ca_1)\mathbf{v}_1 + \cdots + (ca_k)\mathbf{v}_k $$
where the second equality uses distributivity and the associativity of multiplication in $F$. Each $ca_i$ lies in $F$, so $c\mathbf{u} \in W$. Since $\mathbf{u}$, $\mathbf{w}$, and $c$ were arbitrary, the claim holds. $\blacksquare$
The proof used two facts about $F$ and nothing else: that sums and products of scalars are again scalars, and that multiplication distributes over addition. Everything else is bookkeeping.
1.P4.4 Solution Sets
The Free Variables of Chapter One, Made Into Theorems¶
In Exercises 2, 6, 7, and 8 of Problem Set 1.P3 you computed reduced row echelon forms, read off free variables, and wrote solution sets in the form $\mathbf{w} + s\mathbf{z}_1 + t\mathbf{z}_2$. Every one of those computations relied on a structural fact that was demonstrated by example and never proved. Here it is proved.
Throughout, $A$ is an $m \times n$ matrix over $F$ and
$$ N(A) = \left\{\, \mathbf{z} \in F^n \,:\, A\mathbf{z} = \mathbf{0} \,\right\} $$
denotes the set of solutions of the homogeneous system.
Theorem 2¶
Homogeneous Solutions Are Closed
If $\mathbf{z}_1, \mathbf{z}_2 \in N(A)$ and $c_1, c_2 \in F$, then $c_1\mathbf{z}_1 + c_2\mathbf{z}_2 \in N(A)$. In particular $\mathbf{0} \in N(A)$.
Proof. Let $\mathbf{z}_1, \mathbf{z}_2 \in N(A)$ and $c_1, c_2 \in F$. Using the linearity of the matrix-vector product, proved as Theorem 5 in the next section,
$$ A(c_1\mathbf{z}_1 + c_2\mathbf{z}_2) = c_1(A\mathbf{z}_1) + c_2(A\mathbf{z}_2) = c_1\mathbf{0} + c_2\mathbf{0} = \mathbf{0} $$
so $c_1\mathbf{z}_1 + c_2\mathbf{z}_2 \in N(A)$. Taking $c_1 = c_2 = 0$ shows $\mathbf{0} \in N(A)$. $\blacksquare$
Theorem 3¶
Structure of a Solution Set
Suppose $A\mathbf{x} = \mathbf{b}$ is consistent and let $\mathbf{w}$ be any particular solution. Then the set of all solutions is
$$ S = \left\{\, \mathbf{w} + \mathbf{z} \,:\, \mathbf{z} \in N(A) \,\right\} $$
Proof. This is an equality of sets, so we prove two inclusions.
$(\supseteq)$ Let $\mathbf{z} \in N(A)$. Then
$$ A(\mathbf{w} + \mathbf{z}) = A\mathbf{w} + A\mathbf{z} = \mathbf{b} + \mathbf{0} = \mathbf{b} $$
so $\mathbf{w} + \mathbf{z}$ is a solution.
$(\subseteq)$ Let $\mathbf{x}$ be any solution, so $A\mathbf{x} = \mathbf{b}$. Put $\mathbf{z} = \mathbf{x} - \mathbf{w}$. Then
$$ A\mathbf{z} = A(\mathbf{x} - \mathbf{w}) = A\mathbf{x} - A\mathbf{w} = \mathbf{b} - \mathbf{b} = \mathbf{0} $$
so $\mathbf{z} \in N(A)$, and $\mathbf{x} = \mathbf{w} + \mathbf{z}$ has the required form.
Since each set contains the other, they are equal. $\blacksquare$
Notice that the theorem says nothing about which particular solution $\mathbf{w}$ you choose. Any solution works, and different choices produce the same set $S$ described differently. That is why two students who assign free variables differently can both be right.
Theorem 4¶
Uniqueness
For every $\mathbf{b} \in F^m$ the system $A\mathbf{x} = \mathbf{b}$ has at most one solution if and only if $N(A) = \{\mathbf{0}\}$.
The proof is Exercise 7. Together with Theorem 3, this is the precise version of the rule you have been using since Section 1.2.9: a free column produces a nonzero homogeneous solution, a nonzero homogeneous solution produces infinitely many solutions whenever any solution exists, and only a system with no free columns can have a unique solution.
Practice Exercise 4 - Reading a Solution Set¶
Let
$$ A = \begin{bmatrix} 1 & 2 & 3 \\ 2 & 4 & 6 \end{bmatrix}, \qquad \mathbf{b} = \begin{bmatrix} 6 \\ 12 \end{bmatrix} $$
(a) Verify that $\mathbf{w} = (1,\ 1,\ 1)^T$ is a solution.
(b) Exhibit two vectors in $N(A)$ that are not scalar multiples of one another, and prove that each lies in $N(A)$.
(c) Use Theorem 3 to describe the complete solution set, and verify that $(6,\ 0,\ 0)^T$ belongs to it by exhibiting the corresponding $\mathbf{z}$.
View Solution
(a) $A\mathbf{w} = (1 + 2 + 3,\ 2 + 4 + 6)^T = (6,\ 12)^T = \mathbf{b}$, so $\mathbf{w}$ is a solution.
(b) Take $\mathbf{z}_1 = (-2,\ 1,\ 0)^T$ and $\mathbf{z}_2 = (-3,\ 0,\ 1)^T$. Then
$$ A\mathbf{z}_1 = \begin{bmatrix} -2 + 2 + 0 \\ -4 + 4 + 0 \end{bmatrix} = \mathbf{0}, \qquad A\mathbf{z}_2 = \begin{bmatrix} -3 + 0 + 3 \\ -6 + 0 + 6 \end{bmatrix} = \mathbf{0} $$
so both lie in $N(A)$. Neither is a scalar multiple of the other, since the second entry of $\mathbf{z}_1$ is nonzero while that of $\mathbf{z}_2$ is zero, and the third entries behave oppositely.
(c) By Theorem 3 the solution set is $\{\mathbf{w} + \mathbf{z} : \mathbf{z} \in N(A)\}$, and since every element of $N(A)$ here has the form $s\mathbf{z}_1 + t\mathbf{z}_2$,
$$ S = \left\{\, \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix} + s\begin{bmatrix} -2 \\ \ \ 1 \\ \ \ 0 \end{bmatrix} + t\begin{bmatrix} -3 \\ \ \ 0 \\ \ \ 1 \end{bmatrix} \,:\, s, t \in \mathbb{R} \,\right\} $$
For $(6,0,0)^T$, take $\mathbf{z} = (6,0,0)^T - \mathbf{w} = (5,\ -1,\ -1)^T$. Then $A\mathbf{z} = (5 - 2 - 3,\ 10 - 4 - 6)^T = \mathbf{0}$, confirming $\mathbf{z} \in N(A)$, and indeed $\mathbf{z} = -\mathbf{z}_1 - \mathbf{z}_2$ with $s = t = -1$.
1.P4.5 Matrix-Vector Algebra, Entry by Entry
Proving What the Notation Suggests¶
Theorems 2 and 3 both used the rule $A(\mathbf{u} + \mathbf{v}) = A\mathbf{u} + A\mathbf{v}$. That rule is not an axiom and not a convention. It is a theorem about the definition of the matrix-vector product, and its proof is a computation with the $i$th entry in which every step is a field axiom.
Theorem 5¶
Linearity of the Matrix-Vector Product
Let $A$ be an $m \times n$ matrix over $F$, let $\mathbf{u}, \mathbf{v} \in F^n$, and let $c \in F$. Then
$$ A(\mathbf{u} + \mathbf{v}) = A\mathbf{u} + A\mathbf{v} \qquad \text{and} \qquad A(c\mathbf{u}) = c(A\mathbf{u}) $$
Proof. Two vectors in $F^m$ are equal exactly when their corresponding entries are equal, so it suffices to fix $i$ with $1 \leq i \leq m$ and compare $i$th entries. By the definition of the matrix-vector product, the $i$th entry of $A\mathbf{x}$ is $\sum_{j=1}^{n} a_{ij}x_j$.
$$ \begin{align*} \left[A(\mathbf{u} + \mathbf{v})\right]_i &= \sum_{j=1}^{n} a_{ij}(u_j + v_j) && \text{definition of the product and of } \mathbf{u}+\mathbf{v} \\ &= \sum_{j=1}^{n} \left( a_{ij}u_j + a_{ij}v_j \right) && \text{distributivity in } F \\ &= \sum_{j=1}^{n} a_{ij}u_j + \sum_{j=1}^{n} a_{ij}v_j && \text{associativity and commutativity of addition} \\ &= \left[A\mathbf{u}\right]_i + \left[A\mathbf{v}\right]_i && \text{definition of the product} \end{align*} $$
Since $i$ was arbitrary, the two vectors agree in every entry and are therefore equal. For the second identity,
$$ \begin{align*} \left[A(c\mathbf{u})\right]_i &= \sum_{j=1}^{n} a_{ij}(cu_j) && \text{definition of the product and of } c\mathbf{u} \\ &= \sum_{j=1}^{n} c\,(a_{ij}u_j) && \text{associativity and } \textbf{commutativity} \text{ of multiplication} \\ &= c \sum_{j=1}^{n} a_{ij}u_j && \text{distributivity} \\ &= c\left[A\mathbf{u}\right]_i && \text{definition of the product} \end{align*} $$
Again $i$ was arbitrary, so the identity holds. $\blacksquare$
The Step That Needs Commutativity¶
Every step of the first identity uses only distributivity and the arithmetic of addition. The second identity is different. Moving $c$ from the right of $a_{ij}$ to its left, in the line marked above, requires $a_{ij}c = c\,a_{ij}$, and that is the commutative law of multiplication.
For scalars in $\mathbb{R}$ or $\mathbb{C}$ this is automatic and easy to overlook. There is a fourth number system, the quaternions, in which multiplication is associative and every nonzero element has an inverse but multiplication is not commutative: $ij = k$ while $ji = -k$. Quaternions are how rotations are represented in robotics, aerospace attitude control, and computer graphics, so the question is not idle. Over such a system the identity $A(c\mathbf{u}) = c(A\mathbf{u})$ genuinely fails, and one must decide once and for all whether scalars multiply vectors from the left or from the right. We return to this at the end of the semester.
Practice Exercise 5 - Name the Axiom¶
Let $A$ be $m \times n$ over $F$, let $\mathbf{u} \in F^n$, and let $c, d \in F$. Prove that $A\big((c+d)\mathbf{u}\big) = c(A\mathbf{u}) + d(A\mathbf{u})$, naming the field axiom used at each step.
View Solution
Proof. Fix $i$ with $1 \leq i \leq m$ and compare $i$th entries.
$$ \begin{align*} \left[A\big((c+d)\mathbf{u}\big)\right]_i &= \sum_{j=1}^{n} a_{ij}\big((c+d)u_j\big) && \text{definition of the product} \\ &= \sum_{j=1}^{n} a_{ij}\big(cu_j + du_j\big) && \text{distributivity in } F \\ &= \sum_{j=1}^{n} \left( a_{ij}(cu_j) + a_{ij}(du_j) \right) && \text{distributivity in } F \\ &= \sum_{j=1}^{n} \left( c(a_{ij}u_j) + d(a_{ij}u_j) \right) && \text{associativity and commutativity of multiplication} \\ &= c\sum_{j=1}^{n} a_{ij}u_j + d\sum_{j=1}^{n} a_{ij}u_j && \text{distributivity, associativity and commutativity of addition} \\ &= c\left[A\mathbf{u}\right]_i + d\left[A\mathbf{u}\right]_i && \text{definition of the product} \end{align*} $$
Since $i$ was arbitrary the vectors are equal in every entry, hence equal. $\blacksquare$
An acceptable shorter proof cites Theorem 5 twice: $(c+d)\mathbf{u} = c\mathbf{u} + d\mathbf{u}$ entrywise, then $A(c\mathbf{u} + d\mathbf{u}) = A(c\mathbf{u}) + A(d\mathbf{u}) = c(A\mathbf{u}) + d(A\mathbf{u})$. Building on established results rather than returning to the axioms every time is not laziness; it is how mathematics is actually written. Return to the axioms when you are proving the foundational result, and cite it thereafter.
1.P4.6 Where Completeness Will Matter
Why the Completeness Axiom Was Stated¶
Nothing proved in 1.P4.3 through 1.P4.5 used completeness. Elimination, spans, and solution sets are finite algebra, and they work over any field. Completeness enters the moment a question involves infinitely many steps, and such questions arrive almost immediately.
Definition¶
Convergence of Sequences of Vectors and Matrices
A sequence $(\mathbf{x}^{(k)})$ of vectors in $\mathbb{R}^n$ converges entrywise to $\mathbf{x} \in \mathbb{R}^n$ if
$$ \lim_{k \to \infty} x^{(k)}_i = x_i \qquad \text{for each } i = 1, 2, \ldots, n $$
A sequence $(A^{(k)})$ of $m \times n$ matrices converges entrywise to $A$ if $\lim_{k\to\infty} a^{(k)}_{ij} = a_{ij}$ for every $i$ and $j$. Each of these is finitely many ordinary limits of real sequences, so each rests on the completeness axiom of 1.P4.1.
This definition is stated here and used in Chapter Two. Three places where it will matter:
Markov matrices. Chapter Two studies transition matrices and their powers $P^k$. The question "what is the long-run distribution" is the question of whether the sequence $(P^k)$ converges entrywise, and if so to what. The answer is a theorem, not an observation about a table of numbers, and it cannot even be stated without the definition above.
Little $\ell^2$. Convergence in $\mathbb{R}^n$ can be phrased through the quantity $\|\mathbf{x}\| = \sqrt{x_1^2 + \cdots + x_n^2}$. Allowing infinitely many entries with $\sum_{i=1}^{\infty} x_i^2$ finite gives the space $\ell^2$, where completeness is no longer a convenience but the property that makes the theory work at all.
Fourier convergence. Writing a signal as an infinite sum of sinusoids asks whether a sequence of finite approximations converges, and in what sense. You met the finite version of this question in Exercise 3 of Problem Set 1.P3, where a sampled signal was decomposed into finitely many known frequencies by solving a linear system. The infinite version is the same idea with a limit attached, and every result about it depends on the completeness of the underlying space.
The Line Between the Two Halves of the Course¶
Everything in Chapter One is finite: finitely many equations, finitely many unknowns, finitely many row operations. Such results hold over any field and require no analysis whatsoever.
The moment the course asks what happens in the long run, in the limit, or for an infinite sum, the algebra is no longer sufficient and the completeness of $\mathbb{R}$ is doing the work. Knowing which side of that line a theorem lives on is a large part of understanding the subject.
1.P4.7 Exercises
Choose Your Problems¶
The exercises below are independent of one another and are labeled by topic. Your instructor will tell you which to submit.
Write in complete sentences. Begin each proof by stating what is assumed and what is to be shown, and end it when the required statement has been established. When you use a theorem from this problem set, cite it by number. When a claim is false, exhibit an explicit counterexample and verify that it fails.
$$ \begin{array}{|l|l|} \hline \textbf{Exercise} & \textbf{Topic} \\ \hline \text{1. Consequences of the Field Axioms} & \text{Axioms of } \mathbb{R} \\ \hline \text{2. A Gap in the Rational Numbers} & \text{Completeness} \\ \hline \text{3. Two Limits} & \text{Epsilon-N Proofs} \\ \hline \text{4. Consistency and Span} & \text{Span, Biconditional Proof} \\ \hline \text{5. A Span Is Closed} & \text{Span, Double Inclusion} \\ \hline \text{6. The Structure of a Solution Set} & \text{Solution Sets} \\ \hline \text{7. Uniqueness and the Homogeneous System} & \text{Solution Sets} \\ \hline \text{8. True or False} & \text{Counterexamples} \\ \hline \text{9. Name the Axiom} & \text{Matrix Algebra} \\ \hline \text{10. Complex Scalars} & \text{The Field } \mathbb{C} \\ \hline \text{11. Duplicated Features} & \text{Applications} \\ \hline \text{12. A Field Between the Rationals and the Reals} & \text{Challenge} \\ \hline \end{array} $$
Exercise 1 - Consequences of the Field Axioms
Topic: Axioms of $\mathbb{R}$.
Prove each statement using only the field axioms of 1.P4.1. Do not use any property of the real numbers that you have not proved or been given as an axiom, and name the axiom at each step.
(a) The additive identity is unique: if $0'$ satisfies $a + 0' = a$ for every $a \in \mathbb{R}$, then $0' = 0$.
(b) For every $a \in \mathbb{R}$, $\ 0 \cdot a = 0$.
(c) For all $a, b \in \mathbb{R}$, if $ab = 0$ then $a = 0$ or $b = 0$. Identify precisely which axiom fails if this is attempted in a system without multiplicative inverses.
(d) For every $a \in \mathbb{R}$, $\ (-1)a = -a$, where $-a$ denotes the additive inverse of $a$.
Exercise 2 - A Gap in the Rational Numbers
Topic: Completeness.
Let $S = \{\, x \in \mathbb{Q} : x > 0 \text{ and } x^2 < 2 \,\}$. This exercise proves that $S$ has no least upper bound in $\mathbb{Q}$, so the rational numbers fail the completeness axiom. Throughout, you may use without proof that there is no rational number $p$ with $p^2 = 2$.
(a) Show that $S$ is nonempty and bounded above in $\mathbb{Q}$.
(b) For a positive rational $p$, define
$$ q = p - \frac{p^2 - 2}{p + 2} = \frac{2p + 2}{p + 2} $$
Verify that $q$ is rational and positive, and show that
$$ q^2 - 2 = \frac{2(p^2 - 2)}{(p+2)^2} $$
(c) Use part (b) to show that if $p \in S$ then $q \in S$ and $q > p$; and that if $p$ is a positive rational upper bound for $S$ with $p^2 > 2$, then $q$ is also an upper bound with $q < p$.
(d) Conclude that $S$ has no least upper bound in $\mathbb{Q}$. Explain in a sentence why this does not contradict the completeness axiom.
Exercise 3 - Two Limits
Topic: Epsilon-N Proofs.
Prove each limit directly from the definition in 1.P4.1. Show your scratch work separately from the proof, and make sure the proof itself reads forward.
(a) $\displaystyle \lim_{n \to \infty} \frac{3n+1}{n+2} = 3$
(b) $\displaystyle \lim_{n \to \infty} \frac{1}{2^n} = 0$. You may use without proof that $2^n > n$ for every positive integer $n$.
(c) Explain why the following is not a proof that $\lim_{n\to\infty} 1/n = 0$: "Take $\varepsilon = 0.001$. Then for $n > 1000$ we have $1/n < 0.001$, so the terms get arbitrarily close to $0$."
Exercise 4 - Consistency and Span
Topic: Span, Biconditional Proof.
This exercise asks you to reproduce and then extend Theorem 1. Let $A$ be $m \times n$ over $F$ with columns $\mathbf{a}_1, \ldots, \mathbf{a}_n$.
(a) State Theorem 1 with all quantifiers explicit, and explain why proving a biconditional requires two separate arguments.
(b) Prove the direction: if $A\mathbf{x} = \mathbf{b}$ is consistent then $\mathbf{b} \in \operatorname{span}\{\mathbf{a}_1, \ldots, \mathbf{a}_n\}$.
(c) Prove the converse.
(d) Use Theorem 1 to prove: if the columns of $A$ span all of $F^m$, then $A\mathbf{x} = \mathbf{b}$ is consistent for every $\mathbf{b} \in F^m$. Then state, without proof, what this says about the reduced row echelon form of $A$.
Exercise 5 - A Span Is Closed
Topic: Span, Double Inclusion.
Let $\mathbf{v}_1, \ldots, \mathbf{v}_k \in F^n$ and write $W = \operatorname{span}\{\mathbf{v}_1, \ldots, \mathbf{v}_k\}$. Call a subset $U \subseteq F^n$ closed if $\mathbf{u} + \mathbf{u}' \in U$ and $c\mathbf{u} \in U$ whenever $\mathbf{u}, \mathbf{u}' \in U$ and $c \in F$.
(a) Prove that $W$ is closed.
(b) Prove that $\mathbf{v}_j \in W$ for each $j$, and that $\mathbf{0} \in W$.
(c) Prove that if $U$ is closed and $\mathbf{v}_i \in U$ for every $i$, then $W \subseteq U$. Conclude that $W$ is the smallest closed set containing all the $\mathbf{v}_i$.
(d) Show by counterexample that the union of two closed sets need not be closed. Take $F = \mathbb{R}$ and $n = 2$.
Exercise 6 - The Structure of a Solution Set
Topic: Solution Sets.
Let $A$ be $m \times n$ over $F$ and $\mathbf{b} \in F^m$, and let $N(A) = \{\mathbf{z} \in F^n : A\mathbf{z} = \mathbf{0}\}$. You may use Theorem 5.
(a) Prove Theorem 2: $N(A)$ is closed under linear combinations, and $\mathbf{0} \in N(A)$.
(b) Prove Theorem 3 by double inclusion: if $\mathbf{w}$ is any particular solution of $A\mathbf{x} = \mathbf{b}$, then the solution set equals $\{\mathbf{w} + \mathbf{z} : \mathbf{z} \in N(A)\}$.
(c) Prove that the solution set of a consistent system $A\mathbf{x} = \mathbf{b}$ is closed under addition if and only if $\mathbf{b} = \mathbf{0}$.
(d) Give an explicit $2 \times 2$ example with $\mathbf{b} \neq \mathbf{0}$ showing that the sum of two solutions need not be a solution.
Exercise 7 - Uniqueness and the Homogeneous System
Topic: Solution Sets.
Let $A$ be $m \times n$ over $F$ and $\mathbf{b} \in F^m$.
(a) Prove Theorem 4: for every $\mathbf{b} \in F^m$ the system $A\mathbf{x} = \mathbf{b}$ has at most one solution if and only if $N(A) = \{\mathbf{0}\}$. Then explain why the quantifier over $\mathbf{b}$ cannot be dropped.
(b) Prove that if $n > m$, then $N(A) \neq \{\mathbf{0}\}$. You may use the fact from Chapter One that the reduced row echelon form of $A$ has at most one pivot per row.
(c) Combine (a) and (b) into a single statement about underdetermined systems, and explain in one sentence what it means for a data set with more features than observations.
Exercise 8 - True or False
Topic: Counterexamples.
For each statement, decide whether it is true or false. If true, give a proof. If false, give an explicit counterexample and verify that it fails. Throughout, $A$ is a real matrix and vectors have real entries.
(a) If $A\mathbf{x} = \mathbf{b}$ is consistent for some $\mathbf{b} \neq \mathbf{0}$, then it is consistent for every $\mathbf{b}$.
(b) If $A$ has more rows than columns, then $A\mathbf{x} = \mathbf{b}$ is inconsistent.
(c) If $A$ has more columns than rows, then $A\mathbf{x} = \mathbf{0}$ has a nonzero solution.
(d) The set $\{\mathbf{x} \in \mathbb{R}^3 : x_1 + x_2 + x_3 = 0\}$ is closed under addition and scalar multiplication.
(e) The set $\{\mathbf{x} \in \mathbb{R}^3 : x_1 x_2 = 0\}$ is closed under addition.
(f) If $\mathbf{z} \in N(A)$ and $\mathbf{z} \neq \mathbf{0}$, then $A\mathbf{x} = \mathbf{b}$ has infinitely many solutions.
Exercise 9 - Name the Axiom
Topic: Matrix Algebra.
In each part, prove the identity by comparing $i$th entries, and name the field axiom or definition used at every step. Let $A$ and $B$ be $m \times n$ over $F$, let $\mathbf{u}, \mathbf{v} \in F^n$, and let $c, d \in F$.
(a) $(A + B)\mathbf{u} = A\mathbf{u} + B\mathbf{u}$
(b) $c(d\mathbf{u}) = (cd)\mathbf{u}$
(c) In the proof of Theorem 5 the step $\sum a_{ij}(cu_j) = \sum c(a_{ij}u_j)$ used commutativity of multiplication. Show precisely where, by writing that single step with each factor's position tracked, and state what the identity $A(c\mathbf{u}) = c(A\mathbf{u})$ would become if scalars were required to multiply from the right and did not commute.
Exercise 10 - Complex Scalars
Topic: The Field $\mathbb{C}$.
For $\mathbf{z} \in \mathbb{C}^n$, write $\bar{z}$ for the complex conjugate of $z$ and $\mathbf{z}^H = \bar{\mathbf{z}}^T$ for the conjugate transpose, so that $\mathbf{z}^H\mathbf{w} = \sum_{i=1}^n \bar{z}_i w_i$. Recall $|z|^2 = z\bar{z}$ for $z \in \mathbb{C}$.
(a) Prove that $\mathbf{z}^H\mathbf{z}$ is a nonnegative real number for every $\mathbf{z} \in \mathbb{C}^n$, and that it equals $0$ if and only if $\mathbf{z} = \mathbf{0}$.
(b) Exhibit a nonzero $\mathbf{z} \in \mathbb{C}^2$ with $\mathbf{z}^T\mathbf{z} = 0$, and verify it.
(c) Explain why part (b) means that $\sqrt{\mathbf{z}^T\mathbf{z}}$ cannot serve as a measure of the size of a complex vector, and why the conjugate is not an arbitrary convention. Relate your answer to the fact from 1.P4.1 that $\mathbb{C}$ is not an ordered field.
Exercise 11 - Duplicated Features
Topic: Applications.
This exercise proves, as a theorem, the phenomenon you observed computationally in Exercise 2 of Problem Set 1.P3: a design matrix with a redundant feature cannot have identifiable coefficients. Let $X$ be an $m \times n$ real matrix with columns $\mathbf{x}_1, \ldots, \mathbf{x}_n$, and let $\mathbf{y} \in \mathbb{R}^m$.
(a) Suppose columns $j$ and $k$ of $X$ are equal, with $j \neq k$. Prove that $N(X) \neq \{\mathbf{0}\}$ by exhibiting a nonzero element.
(b) Conclude that if $X\boldsymbol{\beta} = \mathbf{y}$ has a solution, it has infinitely many, and that all of them give the same predictions $X\boldsymbol{\beta}$.
(c) Generalize: prove that if some column of $X$ is a linear combination of the others, the same conclusion holds. State the general principle in one sentence.
(d) State the converse of the principle in (c) and decide whether it is true. That is: if no column is a linear combination of the others, must the coefficients be unique when a solution exists?
Exercise 12 - A Field Between the Rationals and the Reals
Topic: Challenge.
Let $\mathbb{Q}(\sqrt{2}) = \{\, a + b\sqrt{2} \,:\, a, b \in \mathbb{Q} \,\}$, a subset of $\mathbb{R}$. You may use without proof that $\sqrt{2}$, $\sqrt{3}$, and $\sqrt{6}$ are irrational.
(a) Prove that $\mathbb{Q}(\sqrt{2})$ is closed under addition and multiplication.
(b) Prove that if $a$ and $b$ are rational and not both zero, then $a^2 - 2b^2 \neq 0$.
(c) Prove that every nonzero element of $\mathbb{Q}(\sqrt{2})$ has a multiplicative inverse in $\mathbb{Q}(\sqrt{2})$, and conclude that $\mathbb{Q}(\sqrt{2})$ is a field.
(d) Does $\mathbb{Q}(\sqrt{2})$ satisfy the completeness axiom? Justify your answer briefly.
