Theorems and definitions — MATA22 reference
This page collects every formal definition, lemma, theorem, and proposition introduced in Lectures 1–9, organized by topic. It is a reference, not a replacement for the lectures: proofs are omitted or sketched, and the “why” behind each result lives in the lecture notes.
Results that were stated but not fully proved in lecture are marked (proof in lecture), (proof sketched), or (proof omitted) as appropriate.
Lecture index: L1 · L2 · L3 · L4 · L5 · L6 · L7 · L8 · L9
1. Vector spaces
Definition — Real vector space (L3)
A real vector space is a set
equipped with two operations, satisfying the following eight axioms for all
and :
Axiom (A1) (A2) (A3) such that for all (A4) with (S1) (S2) (D1) (D2) Elements of
are vectors; elements of acting on are scalars.
Standard examples.
Consequences (L3, exercise)
From the axioms alone, one can derive:
for all for all These are not axioms — they are theorems. Proving them from the axiom list is a good exercise.
Definition — Subspace (L4)
A subset
is a subspace of a vector space if:
Equivalently,
is itself a vector space with respect to the operations inherited from .
Geometric picture. In
2. Linear systems and homogeneous equations
Definition — Homogeneous equation (L3)
A linear equation
is homogeneous if , and non-homogeneous otherwise.
Lemma — Sums of homogeneous solutions (L3, first proof of the course)
If
and are both solutions of a homogeneous linear equation (or a homogeneous system), then so is . Proof. Add the two instances of
and group by coefficient. The right-hand side is . The argument fails for a non-homogeneous equation:
.
Lemma — Solution set of homogeneous system is a subspace (L4)
Let
be a homogeneous system of linear equations in variables. Its solution set is a subspace of . Proof. Check the three subspace conditions:
satisfies the system; the sum of two solutions is a solution (the Lemma above applied equation by equation); a scalar multiple of a solution is a solution (factor out of ).
Lemma — Particular + homogeneous decomposition (L4)
Let
be any particular solution of . Then the complete solution set is Proof sketch. If
, then . Conversely, .
3. Row reduction
Definition — Elementary row operations (L4)
The three elementary row operations on an augmented matrix are:
- Add a scalar multiple of one row to another:
- Swap two rows:
- Scale a row by a nonzero scalar:
with Each operation is invertible — it can be undone by an operation of the same type — and therefore does not change the solution set of the system.
Definition — Row echelon form and RREF (L4)
A matrix is in row echelon form (REF) if:
- All zero rows are at the bottom.
- The leading nonzero entry (pivot) of each nonzero row lies strictly to the right of the pivot in the row above.
A matrix is in reduced row echelon form (RREF) if additionally:
- Every pivot equals
. - Every entry above a pivot is
(as well as every entry below).
Definition — Pivot and free variables (L4)
In the RREF of the coefficient matrix of a linear system:
- A pivot column is a column containing a pivot. The corresponding variable is a pivot variable (determined by the system).
- A free column has no pivot. The corresponding variable is a free variable (can take any real value; becomes the parameter in the parametric solution).
Theorem — Uniqueness of RREF (L4, proof in Hefferon Ch. 1)
The RREF of a matrix is unique: it does not depend on the sequence of row operations used to reach it. In particular, the set of pivot columns is uniquely determined by the original matrix.
See Row reduction and RREF for a full treatment with worked examples, and a proof of the dimension statement below.
Theorem — Dimension of null space equals number of free variables (L4, L6)
Let
be an matrix with RREF having pivot columns. Then:
- The number of free variables is
. - The solution space of
(the null space of ) has dimension . - Equivalently:
, where .
4. Span
Definition — Linear combination (L4)
Let
be a vector space and . A linear combination of these vectors is any expression
Definition — Span (L4)
The span of a set
of vectors in a vector space is By convention,
. Only finite linear combinations are permitted by this definition.
Lemma — Span is a subspace (L4)
For any set
of vectors in a vector space , is a subspace of . Proof. (i)
by the convention or via . (ii) The sum of two linear combinations of is a linear combination of (combine coefficients). (iii) A scalar multiple of a linear combination of is a linear combination of (absorb the scalar).
Spanning as solvability (L5)
A set
spans if and only if for every the system is consistent. This fails if and only if the RREF of the coefficient matrix has a zero row — equivalently, if the coefficient matrix has fewer than pivot rows.
5. Linear independence and dependence
Definition — Linear dependence (L5)
Vectors
are linearly dependent if there exist scalars , not all zero, such that Such a relation is called a non-trivial linear combination equal to
.
Definition — Linear independence (L5)
Vectors
are linearly independent if the only linear combination equalling is the trivial one: whenever , it follows that .
Immediate facts.
- Any set containing
is linearly dependent ( ). - A single nonzero vector is linearly independent.
- The empty set
is linearly independent (vacuously).
Lemma — Dependence ↔ non-unique representations (L6)
Vectors
are linearly dependent if and only if some vector can be written as two different linear combinations of . Proof.
A non-trivial relation gives two representations of : the trivial one and the non-trivial one. Subtract one representation from the other to obtain a non-trivial relation.
Lemma — Dependence ↔ one vector in span of others (L5, L6)
Vectors
are linearly dependent if and only if there exists an index such that (i.e., can be written as a linear combination of the remaining vectors). Proof.
Express in terms of the rest and rearrange to get a non-trivial relation. In the non-trivial relation, at least one ; isolate and divide by .
Lemma — Removing a redundant vector preserves span (L6)
If a set
is linearly dependent, there exists such that . Proof. By the previous lemma, some
. The inclusion is immediate. For the reverse inclusion, substitute the expression for into any linear combination involving it.
6. Bases
Definition — Basis (L5)
A basis of a vector space
is a set that is:
- linearly independent, and
- spanning:
.
Examples. The standard basis
Procedure — Building a basis from a finite spanning set (L6)
If
for a finite set : while is dependent, remove a redundant vector (one that lies in the span of the rest). The procedure terminates (since decreases at each step) and yields a basis for . Remark. Finiteness is essential: the procedure does not terminate in infinite-dimensional spaces.
7. Dimension
Definition — Dimension (L6)
The dimension of a vector space
, written , is the number of vectors in any basis of . (Well-definedness — the fact that all bases have the same size — is the content of the theorem below.) By convention,
.
Key Lemma — spanning set bounds independent set size (L6)
If
(the need not be independent), then no vectors in can be linearly independent. Proof. Let
and write . Let be the matrix of coefficients. Since has more columns than rows, has a non-trivial solution (the RREF has to have free variables). Then , so are dependent.
Theorem — All bases have the same size (L6)
Let
be finitely-spanned. All bases of contain the same number of vectors. Proof. Let
and be two bases with and . Since spans and is independent, the Key Lemma gives . Symmetrically (swapping roles), . Hence .
Lemma — Steinitz exchange (Axler 2.22, L6)
Let
for a finite set with . If is linearly independent, then . Proof idea. Induct on
. Repeatedly swap vectors in for vectors in , maintaining a set of size that spans . At each step the independence of forces a non-trivial component among the remaining -vectors, allowing a swap. The induction can run at most steps, so . (Full proof in L6.)
Proposition — Unique representation in a basis (L7)
Let
be a basis of . For every there exist unique scalars with . Proof. Existence:
spans . Uniqueness: two representations give ; independence forces for all .
Definition — Coordinate vector (L7)
Given a basis
of and , the coordinate vector of with respect to is
Proposition —
independent vectors in an -dimensional space form a basis (L7) In an
-dimensional vector space :
- Any set of exactly
linearly independent vectors spans (hence is a basis). - Any set of exactly
vectors that spans is linearly independent (hence is a basis). Proof sketch. For the first: if
independent vectors did not span, one could add a vector outside their span, giving independent vectors in — but has a spanning set of size , contradicting the Key Lemma. The second is dual.
8. Linear transformations
Definition — Linear transformation (L8)
Let
and be vector spaces. A linear transformation is a function satisfying:
for all for all , Equivalently:
for all .
Lemma — Basic consequences of linearity (L8, L9)
Let
be a linear transformation. Then:
for all Proof.
; subtract from both sides. For the second, set in condition 2.
Theorem — Linear maps
are exactly matrices (L8) Every
matrix defines a linear map from to . Conversely, every linear map arises this way: the matrix of is the matrix whose -th column is . Proof. Linearity of
follows from distributivity. Conversely, where .
Definition — Matrix of a linear map (standard bases, L8)
The matrix of
with respect to the standard bases is the matrix The
-th column of is the image of the -th standard basis vector.
Definition — Matrix of a linear map (abstract bases, L8)
Let
be linear with , . Given bases for and for , the matrix of with respect to and is the matrix where It satisfies
for all .
Column picture of
(L8)
, where is the -th column of . The product is a linear combination of the columns of with the entries of as coefficients. As ranges over , the set of all outputs is — the column space of .
9. Kernel, image, and rank-nullity
Definition — Kernel and image (L9)
Let
be a linear transformation.
- The kernel (or null space) of
: - The image (or range) of
: Both are subspaces:
and .
In matrix language. For
Definition — Rank and nullity (L9)
For a linear map
:
- Nullity of
: - Rank of
: For a matrix
: number of pivot columns in the RREF of .
Theorem — Rank-nullity (L9, proof next week)
Let
be a linear transformation with finite-dimensional. Then Proof strategy. Take a basis
of . Extend to a basis of . Show is a basis for . Then with and .
Interpretation.
Quick reference — named results
| Result | Where proved |
|---|---|
| Sums of homogeneous solutions | L3 |
| Solution set of homogeneous system = subspace | L4 |
| Particular + homogeneous decomposition | L4 |
| Span is a subspace | L4 |
| Uniqueness of RREF | Hefferon Ch. 1; see Row reduction and RREF |
| Dependence ↔ non-unique representations | L6 |
| Dependence ↔ one vector in span of others | L5, L6 |
| Removing redundant vector preserves span | L6 |
| All bases have the same size | L6 |
| Steinitz exchange lemma | L6 |
| Unique representation in a basis | L7 |
| L7 | |
| Linear maps | L8 |
| L8, L9 | |
| Rank-nullity theorem | L9 (proof: after midterm) |
| Dim null space = # free variables | L4, L6; see Row reduction and RREF |