Week 2 Span Lemmas, Matrices, Matrix–Vector Product, the Fundamental Spaces, Matrix Transformations

📌 Sources & numbering: Friday lecture (“Woche 2”) + Wednesday lecture + tablet notes. Numbering follows the course script (Lemma 1.24–1.26, Def. 2.1–2.18). Part of the Wednesday recording around the break is missing (transcript is garbled). The proof of Lemma 2.11 and the row-space pictures are reconstructed from the tablet notes.

📌 Notation used throughout: vectors are bold lowercase ($\mathbf{v},\mathbf{x}$), the zero vector is $0$, and matrices are plain uppercase ($A,B$). Following the lecture, vectors are written with round brackets $\left(\begin{array}{c}\cdot \end{array}\right)$ and matrices with square brackets $\left[\begin{array}{c}\cdot \end{array}\right]$. The spaces are $\mathbf{C}(A)$ (column space), $\mathbf{R}(A)$ (row space) and $\mathbf{N}(A)$ (null space).

---

1. Executive Overview & Core Objectives

This week finishes the chapter on vectors with three lemmas about the span: adding a linear combination to a sequence of vectors leaves the span unchanged, so does removing one, and $m$ linearly independent vectors in ${\mathbb{R}}^m$ span all of ${\mathbb{R}}^m$. It then introduces matrices, first as a compact notation for sequences of vectors and covectors, and the matrix–vector product $A\mathbf{x}$ as a notation for linear combinations of the columns. From this, the lecture builds the column space, the rank (number of independent columns), the transpose, the row space, and the null space. It ends by reinterpreting a matrix as a transformation $T_A:{\mathbb{R}}^n\to {\mathbb{R}}^m$ with a geometric meaning: stretching, mirroring, rotation, or shear.

Learning objectives. After this week you should be able to:

• prove set equalities by double inclusion ($S\subseteq T$ and $T\subseteq S$);
• state and prove Lemma 1.24, Korollar 1.25, and Lemma 1.26 (the exchange argument);
• use the different matrix notations: table, entrywise $a_{ij}$, dotless $[a_{ij}]$, column notation and row notation;
• recognise identity, diagonal, upper/lower triangular and symmetric matrices, and use the Kronecker delta;
• compute $A\mathbf{x}$ in three equivalent ways (column combination, entrywise formula, row scalar products), and prove that they agree;
• translate ”$\mathbf{b}$ is a linear combination of the columns” and “the columns are linearly independent” into matrix language (Beob. 2.5);
• determine independent columns, $\mathrm{rank}(A)$, $\mathbf{C}(A)$, $\mathbf{R}(A)$, $\mathbf{N}(A)$ for concrete matrices, and know which ambient space each one lives in;
• prove Lemma 2.11 (the independent columns span the column space);
• compute transposes, and interpret $T_A$ and $A(X)$ geometrically.

---

2. Core Concepts & Formal Definitions

2.1 Recap from Week 1: span and linear independence

💡 Definition (Span): For ${\mathbf{v}}_1,\dots ,{\mathbf{v}}_n\in {\mathbb{R}}^m$, $\mathrm{Span}({\mathbf{v}}_1,\dots ,{\mathbf{v}}_n)={\sum }_{j=1}^n{\lambda }_j{\mathbf{v}}_j:{\lambda }_1,\dots ,{\lambda }_n\in \mathbb{R}$, the set of all linear combinations. The vectors span ${\mathbb{R}}^m$ if $\mathrm{Span}({\mathbf{v}}_1,\dots ,{\mathbf{v}}_n)={\mathbb{R}}^m$, i.e. every $\mathbf{w}\in {\mathbb{R}}^m$ is a linear combination of them.

• Geometric picture in ${\mathbb{R}}^3$: three vectors on a common line through the origin span that line; three vectors in a common plane through the origin span that plane; three linearly independent vectors span the whole space.
• The span is a set: an unordered collection, each element counted once. Therefore the order of the vectors in the sequence does not matter for the span, because vector addition is commutative.
• The empty linear combination (the sum over no vectors) is $0$. Hence $\mathrm{Span}()=0$, and $0$ is a linear combination of any sequence, including the empty one.

Facts on linear independence used repeatedly (Korollar 1.21):

• (ii) ${\mathbf{v}}_1,\dots ,{\mathbf{v}}_n$ are linearly independent $⟺$ the only way to write $0={\sum }_j{\lambda }_j{\mathbf{v}}_j$ is ${\lambda }_1=\cdots ={\lambda }_n=0$ (only the trivial combination).
• (iii) ${\mathbf{v}}_1,\dots ,{\mathbf{v}}_n$ are linearly independent $⟺$ no ${\mathbf{v}}_k$ is a linear combination of the previous vectors ${\mathbf{v}}_1,\dots ,{\mathbf{v}}_{k-1}$. Equivalently, they are linearly dependent $⟺$ some ${\mathbf{v}}_k$ is a linear combination of its predecessors.
• A linearly independent sequence never contains $0$, since $0$ is a linear combination of the (possibly empty) sequence before it.

2.2 Three lemmas about the span

💡 Lemma 1.24 (adding a linear combination does not change the span): Let ${\mathbf{v}}_1,\dots ,{\mathbf{v}}_n\in {\mathbb{R}}^m$, and let $\mathbf{v}$ be a linear combination of ${\mathbf{v}}_1,\dots ,{\mathbf{v}}_n$. Then
$\mathrm{Span}({\mathbf{v}}_1,\dots ,{\mathbf{v}}_n)=\mathrm{Span}({\mathbf{v}}_1,\dots ,{\mathbf{v}}_n,\mathbf{v})$.

💡 Korollar 1.25 (removing a linear combination does not change the span): Let ${\mathbf{v}}_1,\dots ,{\mathbf{v}}_n\in {\mathbb{R}}^m$, and let ${\mathbf{v}}_k$ be a linear combination of the other vectors. Then
$\mathrm{Span}({\mathbf{v}}_1,\dots ,{\mathbf{v}}_n)=\mathrm{Span}({\mathbf{v}}_1,\dots ,{\mathbf{v}}_{k-1},{\mathbf{v}}_{k+1},\dots ,{\mathbf{v}}_n)$.

💡 Lemma 1.26 (“Challenge 1.6 in ${\mathbb{R}}^m$”): Let ${\mathbf{v}}_1,\dots ,{\mathbf{v}}_m\in {\mathbb{R}}^m$ be linearly independent (exactly $m$ vectors in ${\mathbb{R}}^m$). Then $\mathrm{Span}({\mathbf{v}}_1,\dots ,{\mathbf{v}}_m)={\mathbb{R}}^m$.

• Main use of Korollar 1.25: as long as a sequence is linearly dependent, we may delete redundant vectors without shrinking the span.
• Lemma 1.26 generalises Fakt 1.5 / Challenge 1.6 from Week 1. In ${\mathbb{R}}^2$, two vectors that are not on a common line span the plane. The point is that we never need to “see” independence geometrically in high dimensions; the definition alone suffices.
• A stronger version of this exchange argument appears later as the Steinitz exchange lemma (Steinitz’sches Austauschlemma).

2.3 Matrices

💡 Definition 2.1 (Matrix): An $m\times n$ matrix is a table of real numbers with $m$ rows (Zeilen) and $n$ columns (Spalten):
$A=\left[\begin{array}{ccccccccccccc}{a}_{11}& a_{12}& \cdots & a_{1n}{a}_{21}& a_{22}& \cdots & a_{2n}⋮& ⋮& \ddots & ⋮a_{m1}& a_{m2}& \cdots & a_{mn}\end{array}\right]$.
$a_{ij}$ is the entry in row $i$ and column $j$. ${\mathbb{R}}^{m\times n}$ denotes the set of all $m\times n$ matrices.

Notations for the same object:

Notation	Form	Interpretation
Table / entrywise	$a_{ij}$ as above	a table of numbers
Dotless (punktlose) notation	$A=[a_{ij}{]}_{i=1,,j=1}^{m,;n}$	compact; useful in definitions
Column notation (Spaltennotation)	$A=\left[\begin{array}{cccc}{\mathbf{v}}_1& {\mathbf{v}}_2& \cdots & {\mathbf{v}}_n\end{array}\right]$, ${\mathbf{v}}_j\in {\mathbb{R}}^m$	columns are vectors
Row notation (Zeilennotation)	rows ${\mathbf{u}}_1^{\top },\dots ,{\mathbf{u}}_m^{\top }\in ({\mathbb{R}}^n{)}^{\ast }$ stacked	rows are covectors (row vectors)

• Motivation: the sequence of vectors $\left(\left(\begin{array}{c}1\\ 3\\ 5\end{array}\right),\left(\begin{array}{c}2\\ 4\\ 6\end{array}\right)\right)$ becomes the $3\times 2$ matrix $\left[\begin{array}{cc}1& 2\\ 3& 4\\ 5& 6\end{array}\right]$. Read row-wise, the same table is the sequence of covectors $(1;2),(3;4),(5;6)$.
• Dimensions of rows and columns: in an $m\times n$ matrix, each column has $m$ entries (so ${\mathbf{v}}_j\in {\mathbb{R}}^m$), and each row has $n$ entries (so ${\mathbf{u}}_i^{\top }\in ({\mathbb{R}}^n{)}^{\ast }$).
• $({\mathbb{R}}^n{)}^{\ast }$, the dual space, is used here simply as a label for “row vectors of length $n$”. Covectors are, for now, “tipped-over” vectors; their formal definition comes later.

💡 Definition 2.2 (Matrix addition, scalar multiplication, negative): For $A=[a_{ij}],B=[b_{ij}]\in {\mathbb{R}}^{m\times n}$ (the same shape) and $\lambda \in \mathbb{R}$:
$A+B:=[a_{ij}+b_{ij}]$, $\lambda A:=[\lambda a_{ij}]$, $-A:=[-a_{ij}]$.
The zero matrix $0$ has all entries $0$. It is written as a non-bold $0$ (an abuse of notation; context decides whether it is the number or the matrix).

These are exactly the vector operations, applied entry by entry. Later, matrices themselves will be treated abstractly as vectors.

Matrix shapes:

Name	Condition	Picture
tall (hoch)	$m>n$	more rows than columns
square (quadratisch)	$m=n$
wide (breit)	$m<n$	more columns than rows

💡 Definition (Kronecker delta): ${\delta }_{ij}=1$ if $i=j$, and ${\delta }_{ij}=0$ otherwise.

Special square matrices ($m\times m$):

Type	Condition	$3\times 3$ example
Identity matrix $I$	$a_{ij}={\delta }_{ij}$, i.e. $I=[{\delta }_{ij}{]}_{i=1,j=1}^{m,m}$	$\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right]$
Diagonal matrix	$i\ne j\Rightarrow a_{ij}=0$	$\left[\begin{array}{ccc}2& 0& 0\\ 0& 4& 0\\ 0& 0& 5\end{array}\right]$
Upper triangular (obere Dreiecksmatrix)	$i>j\Rightarrow a_{ij}=0$ (zeros below the diagonal)	$\left[\begin{array}{ccc}2& 1& 0\\ 0& 4& 7\\ 0& 0& 5\end{array}\right]$
Lower triangular (untere Dreiecksmatrix)	$i<j\Rightarrow a_{ij}=0$ (zeros above the diagonal)	$\left[\begin{array}{ccc}2& 0& 0\\ 1& 4& 0\\ 0& 7& 5\end{array}\right]$
Symmetric	$a_{ij}=a_{ji}$ for all $i,j$	$\left[\begin{array}{ccc}2& 1& 0\\ 1& 4& 7\\ 0& 7& 5\end{array}\right]$

• The diagonal always runs from top-left to bottom-right (entries $a_{11},a_{22},\dots ,a_{mm}$).
• The conditions only constrain the off-diagonal entries (or one side of them). Diagonal entries may be anything, including $0$.
• The zero matrix is diagonal, upper triangular, lower triangular and symmetric, but not the identity. The identity is diagonal, upper and lower triangular, and symmetric.
• Symmetric means the matrix is unchanged by mirroring at the diagonal. In the example, $a_{13}=a_{31}=0$ and $a_{23}=a_{32}=7$.

2.4 Matrix–vector multiplication (Abschnitt 2.1.1)

💡 Definition 2.4 (Matrix–vector product): Let $A=\left[\begin{array}{ccc}{\mathbf{v}}_1& \cdots & {\mathbf{v}}_n\end{array}\right]\in {\mathbb{R}}^{m\times n}$ and $\mathbf{x}=\left(\begin{array}{c}{x}_1⋮x_n\end{array}\right)\in {\mathbb{R}}^n$. The vector
$A\mathbf{x}:={\sum }_{j=1}^n{x}_j{\mathbf{v}}_j\in {\mathbb{R}}^m$
is the product of $A$ and $\mathbf{x}$. It is the linear combination of the columns of $A$ with the scalars from $\mathbf{x}$.

⚠️ Exam Trap: $A\mathbf{x}$ is defined only if the number of columns of $A$ equals the number of entries of $\mathbf{x}$ (both are $n$). Otherwise it is simply undefined, like a dimension-mismatch error in a programming language. The result has as many entries as $A$ has rows ($m$). Picture: an ($m$ high, $n$ wide) matrix times an ($n$ high) vector gives an ($m$ high) vector. (In the Q&A the lecturer briefly said “rows” by mistake, then corrected it: the condition is on the columns.)

⚠️ Exam Trap: ${\sum }_j{x}_j{\mathbf{v}}_j$ looks like a scalar product but is not one: each ${\mathbf{v}}_j$ is a vector, so $x_j{\mathbf{v}}_j$ is a scalar multiple of a vector, and the sum is a vector in ${\mathbb{R}}^m$.

The three equivalent views (proven in §3.5):

View	Formula	Source
Linear combination of the columns	$A\mathbf{x}={\sum }_{j=1}^n{x}_j{\mathbf{v}}_j$	Def. 2.4
Direct, entrywise (“no columns”)	$(A\mathbf{x}{)}_i={\sum }_{j=1}^n{a}_{ij}{x}_j=a_{i1}{x}_1+\cdots +a_{in}{x}_n$	Beob. 2.6
Row notation: $m$ scalar products	$A\mathbf{x}=\left(\begin{array}{c}{\mathbf{u}}_1^{\top }\mathbf{x}⋮{\mathbf{u}}_m^{\top }\mathbf{x}\end{array}\right)$	Beob. 2.8

💡 Korollar 2.7: For the $m\times m$ identity matrix, $I\mathbf{x}=\mathbf{x}$ for all $\mathbf{x}\in {\mathbb{R}}^m$. As a transformation, $I$ maps every vector to itself; this is why it is called the identity.

💡 Beobachtung 2.5 (Def. 1.4 and Korollar 1.21(ii) in matrix language): Let $A\in {\mathbb{R}}^{m\times n}$.
(i) $\mathbf{b}\in {\mathbb{R}}^m$ is a linear combination of the columns of $A$ $⟺$ there exists $\mathbf{x}\in {\mathbb{R}}^n$ with $A\mathbf{x}=\mathbf{b}$.
(ii) The columns of $A$ are linearly independent $⟺$ $\mathbf{x}=0$ is the only vector with $A\mathbf{x}=0$.

The form $A\mathbf{x}=\mathbf{b}$ is how systems of linear equations will be written later in the course.

2.5 Column space and rank

💡 Definition 2.9 (Column space, Spaltenraum): For $A\in {\mathbb{R}}^{m\times n}$,
$\mathbf{C}(A):=A\mathbf{x}:\mathbf{x}\in {\mathbb{R}}^n\subseteq {\mathbb{R}}^m$.
It equals the span of the columns of $A$. (“C” stands for column space; it is written as a bold C, to distinguish it from a matrix named $C$.)

• $0\in \mathbf{C}(A)$ always, because $A0=0$.
• Appending a column that is a linear combination of the existing columns does not change $\mathbf{C}(A)$ (Lemma 1.24).

💡 Definition 2.10 (Independent columns, rank): Let $A=\left[\begin{array}{ccc}{\mathbf{v}}_1& \cdots & {\mathbf{v}}_n\end{array}\right]$. Column ${\mathbf{v}}_j$ is independent if ${\mathbf{v}}_j$ is not a linear combination of the previous columns ${\mathbf{v}}_1,\dots ,{\mathbf{v}}_{j-1}$; otherwise ${\mathbf{v}}_j$ is dependent. The rank of $A$, $\mathrm{rank}(A)$, is the number of independent columns.

• “Independent column” is a different concept from “linearly independent”, although the two are related. It is a property of a single column relative to the columns to its left.
• $0\le \mathrm{rank}(A)\le n$. For the $0\times 0$ (empty) matrix, the rank is $0$.
• $\mathrm{rank}(A)=n⟺$ the columns are linearly independent (Korollar 1.21(iii)).
• $\mathrm{rank}(A)=0⟺A=0$ (the zero matrix). See §3.8.
• Stated now, proven later: reordering the columns does not change the rank. The set of independent columns may change, but their number does not. So the left-to-right convention is ultimately arbitrary.
• Preview: $\mathrm{rank}(A)$ will turn out to be the dimension of $\mathbf{C}(A)$, and surprisingly also of $\mathbf{R}(A)$. The dimension of $\mathbf{N}(A)$ will also be expressible through the rank.

💡 Lemma 2.11 (the independent columns span the column space): Let $A$ be an $m\times n$ matrix with $r$ independent columns, and let $C$ be the $m\times r$ submatrix (Untermatrix) consisting of the independent columns. Then $\mathbf{C}(A)=\mathbf{C}(C)$.

A submatrix is what remains of the table after deleting some rows and/or columns. Here we delete the $n-r$ dependent columns and keep all $m$ rows.

2.6 Transposition and row space

💡 Definition 2.12 (Transpose): Let $A=[a_{ij}{]}_{i=1,,j=1}^{m,;n}$ be an $m\times n$ matrix. The transpose of $A$ is the $n\times m$ matrix
$A^{\top }:=B=[b_{ij}{]}_{i=1,,j=1}^{n,;m}$ with $b_{ij}=a_{ji}$ for all $i,j$.

• Geometrically, transposing mirrors the table at the diagonal: the dimensions swap and row/column indices swap. The entry at position $(5,7)$ of $A^{\top }$ is the entry at $(7,5)$ of $A$.
• Vectors and matrices both have a transpose, but these are different operations on different objects. A vector $\mathbf{v}$ becomes the covector ${\mathbf{v}}^{\top }$, e.g. ${\left(\begin{array}{c}1\text{3}\text{5}\end{array}\right)}^{\top }=(1;3;5)$. An $m\times 1$ matrix becomes a $1\times m$ matrix, e.g. ${\left[\begin{array}{c}1\text{3}\text{5}\end{array}\right]}^{\top }=\left[\begin{array}{ccc}1& 3& 5\end{array}\right]$. Geometrically the same thing happens: the object is tipped over.
• $A$ is symmetric $⟺A^{\top }=A$ (directly from $b_{ij}=a_{ji}$).

⚠️ Exam Trap: A vector is not “a matrix with one column”, even though many internet sources claim so. Matrices are really transformations (§2.8), and vectors are different objects. That is why the brackets differ: round for vectors, square for matrices. Turning an $m\times 1$ matrix into a vector would be an explicit conversion (like a “cast” in programming), not an identity.

💡 Definition 2.14 (Row space, Zeilenraum): For $A\in {\mathbb{R}}^{m\times n}$, $\mathbf{R}(A):=\mathbf{C}(A^{\top })\subseteq {\mathbb{R}}^n$.

It is defined via the transpose so that we only take linear combinations of (column) vectors, never of covectors. It lies in ${\mathbb{R}}^n$ because each row of $A$ has $n$ entries, and $A^{\top }\in {\mathbb{R}}^{n\times m}$ has columns in ${\mathbb{R}}^n$.

2.7 Null space (Abschnitt 2.15)

💡 Definition 2.17 (Null space, Nullraum): For $A\in {\mathbb{R}}^{m\times n}$,
$\mathbf{N}(A):=\mathbf{x}\in {\mathbb{R}}^n:A\mathbf{x}=0\subseteq {\mathbb{R}}^n$.
Intuitively, it is everything that is transformed to $0$.

• $0\in \mathbf{N}(A)$ always ($A0=0$). In general nothing more is guaranteed.
• $\mathbf{N}(A)=0⟺$ the columns of $A$ are linearly independent (Beob. 2.5(ii)).
• $\mathbf{N}(A)={\mathbb{R}}^n⟺A=0$.
• There are relationships between $\mathbf{C}(A)$, $\mathbf{R}(A)$ and $\mathbf{N}(A)$; these will be worked out later in the course.

2.8 Matrices as linear transformations (Abschnitt 2.2)

💡 Definition 2.18 (Matrix transformation): Let $A$ be an $m\times n$ matrix. The function
$T_A:{\mathbb{R}}^n\to {\mathbb{R}}^m$, $T_A(\mathbf{x})=A\mathbf{x}$
(“input” $\mathbf{x}$, “output” $A\mathbf{x}$) is the matrix transformation with matrix $A$.

• A function (also called map, mapping, Abbildung) is a rule that assigns exactly one output to every input. $T_A$ is a function because $A\mathbf{x}$ is defined and unique for every $\mathbf{x}\in {\mathbb{R}}^n$.
• $m$ and $n$ are arbitrary: the output dimension can be smaller ($n>m$), equal, or larger ($n<m$) than the input dimension.
• This is the “true” nature of a matrix: not a table, but a transformation.

💡 Definition (Image of a set): For a set $X\subseteq {\mathbb{R}}^n$ of inputs, $A(X):=A\mathbf{x}:\mathbf{x}\in X$.

With this notation, $\mathbf{C}(A)=A({\mathbb{R}}^n)$.

---

3. Step-by-Step Derivations & Mathematical Proofs

3.1 Proof pattern: equality of sets by double inclusion

To show two sets $S$ and $T$ are equal, prove two inclusions:

1. $S\subseteq T$: every element of $S$ is an element of $T$.
2. $T\subseteq S$: every element of $T$ is an element of $S$.

Then $S=T$. Why this works: $S\subseteq T$ says $T$ is “at most bigger” than $S$; $T\subseteq S$ says $S$ is “at most bigger” than $T$; together neither can contain an element the other lacks.

3.2 Proof of Lemma 1.24

Let $S:=\mathrm{Span}({\mathbf{v}}_1,\dots ,{\mathbf{v}}_n)$ and $T:=\mathrm{Span}({\mathbf{v}}_1,\dots ,{\mathbf{v}}_n,\mathbf{v})$.

$S\subseteq T$ (the easy direction). Let $\mathbf{w}\in S$. By definition of the span, $\mathbf{w}={\sum }_{j=1}^n{\lambda }_j{\mathbf{v}}_j$ for some ${\lambda }_j\in \mathbb{R}$. Then also

$\mathbf{w}={\sum }_{j=1}^n{\lambda }_j{\mathbf{v}}_j+0\cdot \mathbf{v},$

which is a linear combination of ${\mathbf{v}}_1,\dots ,{\mathbf{v}}_n,\mathbf{v}$. Hence $\mathbf{w}\in T$.
Logic: a linear combination of some vectors is always a linear combination of more vectors; the extra vectors just get the scalar $0$. Adding vectors can never shrink the span.

$T\subseteq S$ (the interesting direction). Let $\mathbf{w}\in T$. Then there are ${\lambda }_1,\dots ,{\lambda }_n,\lambda \in \mathbb{R}$ with

$\mathbf{w}={\sum }_{j=1}^n{\lambda }_j{\mathbf{v}}_j+\lambda \mathbf{v}.(1)$

By the assumption of the lemma, $\mathbf{v}$ is a linear combination of ${\mathbf{v}}_1,\dots ,{\mathbf{v}}_n$, so there are (different) scalars ${\mu }_1,\dots ,{\mu }_n$ with

$\mathbf{v}={\sum }_{j=1}^n{\mu }_j{\mathbf{v}}_j.(2)$

Substitute (2) into (1):

$\mathbf{w}={\sum }_{j=1}^n{\lambda }_j{\mathbf{v}}_j+\lambda {\sum }_{j=1}^n{\mu }_j{\mathbf{v}}_j={\sum }_{j=1}^n({\lambda }_j+\lambda {\mu }_j),{\mathbf{v}}_j.$

Why the last step is allowed: vector arithmetic obeys the same rules as real numbers (distributivity, commutativity, associativity). We pull $\lambda$ into the second sum and collect, for each $j$, the two coefficients of ${\mathbf{v}}_j$: ${\lambda }_j$ from the first sum and $\lambda {\mu }_j$ from the second. The summation index $j$ is a “loop variable” that is local to each sum, so both sums may use the same name.
Concrete instance ($n=2$): $(3{\mathbf{v}}_1+4{\mathbf{v}}_2)+(5{\mathbf{v}}_1+6{\mathbf{v}}_2)=8{\mathbf{v}}_1+10{\mathbf{v}}_2$.

Since ${\lambda }_j+\lambda {\mu }_j\in \mathbb{R}$ are just real numbers (the names $\lambda ,{\lambda }_j,{\mu }_j$ carry no special meaning), $\mathbf{w}$ is a linear combination of ${\mathbf{v}}_1,\dots ,{\mathbf{v}}_n$, i.e. $\mathbf{w}\in S$.

Both inclusions hold, so $S=T$. $■$

💡 Proof vs. computation: This proof is a computation, but done with variables instead of concrete numbers. That turns it into a statement about all possible vectors and scalars at once.

3.3 Proof of Korollar 1.25

Let $S:=\mathrm{Span}({\mathbf{v}}_1,\dots ,{\mathbf{v}}_{k-1},{\mathbf{v}}_{k+1},\dots ,{\mathbf{v}}_n)$. By assumption, ${\mathbf{v}}_k$ is a linear combination of exactly these vectors. Apply Lemma 1.24 with $\mathbf{v}:={\mathbf{v}}_k$ appended at the end:

$S=\mathrm{Span}({\mathbf{v}}_1,\dots ,{\mathbf{v}}_{k-1},{\mathbf{v}}_{k+1},\dots ,{\mathbf{v}}_n,{\mathbf{v}}_k)=\mathrm{Span}({\mathbf{v}}_1,\dots ,{\mathbf{v}}_n).$

The second equality holds because the sequence is only reordered (${\mathbf{v}}_k$ moved to the end). The span does not depend on the order, since vector addition is commutative. $■$

3.4 Proof of Lemma 1.26 (exchange argument)

Idea. We know $m$ linearly independent vectors that span ${\mathbb{R}}^m$: the standard unit vectors ${\mathbf{e}}_1,\dots ,{\mathbf{e}}_m$. Every $\mathbf{v}\in {\mathbb{R}}^m$ satisfies

$\mathbf{v}={\sum }_{i=1}^m{v}_i{\mathbf{e}}_i,\text{e.g. }\left(\begin{array}{c}{v}_1{v}_2\end{array}\right)=v_1\left(\begin{array}{c}1\\ 0\end{array}\right)+v_2\left(\begin{array}{c}0\\ 1\end{array}\right).$

So $\mathrm{Span}({\mathbf{e}}_1,\dots ,{\mathbf{e}}_m)={\mathbb{R}}^m$. Now swap the ${\mathbf{e}}_i$ out for the ${\mathbf{v}}_i$ one at a time, making sure the span never changes. It starts as ${\mathbb{R}}^m$, so it ends as ${\mathbb{R}}^m$.

Invariant before step $k$ ($k=1,\dots ,m$): the sequence

$({\mathbf{v}}_1,\dots ,{\mathbf{v}}_{k-1},\text{ the }m-k+1\text{ remaining unit vectors})$

has $m$ elements and spans ${\mathbb{R}}^m$. For $k=1$ this is $({\mathbf{e}}_1,\dots ,{\mathbf{e}}_m)$, which spans ${\mathbb{R}}^m$.

Step $k$:

1. Insert ${\mathbf{v}}_k$ right after ${\mathbf{v}}_{k-1}$, giving $({\mathbf{v}}_1,\dots ,{\mathbf{v}}_k,\text{remaining unit vectors})$.
2. Since the old sequence spans ${\mathbb{R}}^m$ and ${\mathbf{v}}_k\in {\mathbb{R}}^m$, ${\mathbf{v}}_k$ is a linear combination of the other vectors. So the new sequence is linearly dependent, and by Lemma 1.24 its span is still ${\mathbb{R}}^m$.
3. By Korollar 1.21(iii), some vector of this dependent sequence is a linear combination of its predecessors (the vectors to its left).
4. That vector is not one of ${\mathbf{v}}_1,\dots ,{\mathbf{v}}_k$:
   • ${\mathbf{v}}_1$ could only be a combination of its (empty) set of predecessors if ${\mathbf{v}}_1=0$, which is impossible in an independent sequence.
   • ${\mathbf{v}}_i$ for $i\le k$ is not a combination of ${\mathbf{v}}_1,\dots ,{\mathbf{v}}_{i-1}$, because ${\mathbf{v}}_1,\dots ,{\mathbf{v}}_m$ are linearly independent (Korollar 1.21(iii)).
5. Hence it is one of the remaining unit vectors (there are $m-k+1\ge 1$ of them). Being a combination of its predecessors, it is in particular a combination of the other vectors. By Korollar 1.25 we delete it without changing the span.
6. Now the sequence is $({\mathbf{v}}_1,\dots ,{\mathbf{v}}_k,m-k\text{ unit vectors})$ and spans ${\mathbb{R}}^m$. The invariant holds for $k+1$.

After step $m$, no unit vectors remain, and $\mathrm{Span}({\mathbf{v}}_1,\dots ,{\mathbf{v}}_m)={\mathbb{R}}^m$. $■$

• The lecture showed this as a Scratch animation for $m=3$; the argument is identical for any $m$. Edge case $m=0$: zero vectors in ${\mathbb{R}}^0$; the empty sequence spans $0={\mathbb{R}}^0$. ✓
• “…and so on” proofs are not fully satisfactory formally. The rigorous “dotless” version of such a proof is mathematical induction (vollständige Induktion), which comes later.

3.5 The three views of $A\mathbf{x}$ agree; $I\mathbf{x}=\mathbf{x}$

Beob. 2.6 (entrywise formula). In column notation, ${\mathbf{v}}_j=\left(\begin{array}{c}{a}_{1j}⋮a_{mj}\end{array}\right)$. Scalar multiplication and addition of vectors act entry by entry, so the $i$-th entry of ${\sum }_j{x}_j{\mathbf{v}}_j$ is

$(A\mathbf{x}{)}_i={\sum }_{j=1}^n{x}_j{a}_{ij}=a_{i1}{x}_1+a_{i2}{x}_2+\cdots +a_{in}{x}_n.$

Read backwards: in the full result vector

$A\mathbf{x}=\left(\begin{array}{c}{a}_{11}{x}_1+a_{12}{x}_2+\cdots +a_{1n}{x}_n{a}_{21}{x}_1+a_{22}{x}_2+\cdots +a_{2n}{x}_n⋮a_{m1}{x}_1+a_{m2}{x}_2+\cdots +a_{mn}{x}_n\end{array}\right),$

the “first summands” form the vector $x_1{\mathbf{v}}_1$, the second summands form $x_2{\mathbf{v}}_2$, …, and the last form $x_n{\mathbf{v}}_n$. So the formula is exactly the column combination. This justifies why the table computation is the “right” one.

Beob. 2.8 (row view). The $i$-th row of $A$ is ${\mathbf{u}}_i^{\top }=(a_{i1};\cdots ;a_{in})$. The scalar product multiplies matching coordinates and sums: ${\mathbf{u}}_i^{\top }\mathbf{x}={\sum }_j{a}_{ij}{x}_j=(A\mathbf{x}{)}_i$. Hence $A\mathbf{x}=({\mathbf{u}}_1^{\top }\mathbf{x},\dots ,{\mathbf{u}}_m^{\top }\mathbf{x}{)}^{\top }$, i.e. $m$ scalar products.

Korollar 2.7. With $a_{ij}={\delta }_{ij}$:

$(I\mathbf{x}{)}_i={\sum }_{j=1}^m{\delta }_{ij}{x}_j=x_i,$

because exactly one term ($j=i$) survives. So $I\mathbf{x}=\mathbf{x}$; the ones on the diagonal just “collect” the coordinates of $\mathbf{x}$ unchanged.

Useful consequence (columns = images of unit vectors). For the $j$-th standard unit vector ${\mathbf{e}}_j\in {\mathbb{R}}^n$:

$A{\mathbf{e}}_j={\sum }_{k=1}^n({\mathbf{e}}_j{)}_k{\mathbf{v}}_k={\mathbf{v}}_j.$

The $j$-th column of $A$ is where $T_A$ sends ${\mathbf{e}}_j$. This is exactly what the geometric pictures show as $A{\mathbf{e}}_1,A{\mathbf{e}}_2$.

3.6 Proof of Beobachtung 2.5

(i) ”$\mathbf{b}$ is a linear combination of ${\mathbf{v}}_1,\dots ,{\mathbf{v}}_n$” means there are $x_1,\dots ,x_n$ with ${\sum }_j{x}_j{\mathbf{v}}_j=\mathbf{b}$. By Def. 2.4, this says $A\mathbf{x}=\mathbf{b}$ for $\mathbf{x}=(x_1,\dots ,x_n{)}^{\top }\in {\mathbb{R}}^n$.

(ii) By Korollar 1.21(ii), the columns are linearly independent $⟺$ ${\sum }_j{x}_j{\mathbf{v}}_j=0$ forces all $x_j=0$. In matrix language: $A\mathbf{x}=0\Rightarrow \mathbf{x}=0$. Since $A0=0$ is always a solution, $\mathbf{x}=0$ is the unique solution. $■$

3.7 $\mathbf{C}(A)$ is the span of the columns

$\mathbf{C}(A)=\{A\mathbf{x}:\mathbf{x}\in {\mathbb{R}}^n\}=\{{\sum }_{j=1}^n{x}_j{\mathbf{v}}_j:x_1,\dots ,x_n\in \mathbb{R}\}=\mathrm{Span}({\mathbf{v}}_1,\dots ,{\mathbf{v}}_n).$

Running $\mathbf{x}$ over all of ${\mathbb{R}}^n$ means running over all choices of scalars, which gives all linear combinations. Each $A\mathbf{x}\in {\mathbb{R}}^m$, so $\mathbf{C}(A)\subseteq {\mathbb{R}}^m$.

3.8 The extreme cases of rank and null space

$\mathrm{rank}(A)=n⟺$ columns linearly independent. $\mathrm{rank}(A)=n$ means every column is independent, i.e. no ${\mathbf{v}}_j$ is a combination of ${\mathbf{v}}_1,\dots ,{\mathbf{v}}_{j-1}$. This is exactly the alternative characterisation of linear independence in Korollar 1.21(iii).

$\mathrm{rank}(A)=0⟺A=0$.

• ($\Rightarrow$) No column is independent, so every column is a combination of the previous ones. Column 1 is a combination of the empty sequence, so ${\mathbf{v}}_1=0$. Column 2 is a combination of ${\mathbf{v}}_1=0$, hence $0$, and so on. A combination of zero vectors is the zero vector, so all columns are $0$.
• ($\Leftarrow$) Each zero column is a combination of its predecessors (the empty combination already gives $0$), so all columns are dependent.
• Note: “every column is a multiple of the first column” does not give rank 0. If ${\mathbf{v}}_1\ne 0$, the first column is independent and the rank is $1$.

$\mathbf{N}(A)=0⟺$ columns linearly independent. This is a direct restatement of Beob. 2.5(ii).

$\mathbf{N}(A)={\mathbb{R}}^n⟺A=0$.

• ($\Leftarrow$) $0\mathbf{x}=0$ for every $\mathbf{x}$.
• ($\Rightarrow$, contrapositive) Suppose $A\ne 0$, so some $a_{ij}\ne 0$. Then $A{\mathbf{e}}_j={\mathbf{v}}_j$ has $i$-th entry $a_{ij}\ne 0$, so $A{\mathbf{e}}_j\ne 0$, and ${\mathbf{e}}_j\notin \mathbf{N}(A)$. Hence $\mathbf{N}(A)\ne {\mathbb{R}}^n$. $■$

3.9 Proof of Lemma 2.11 (from tablet notes)

Let ${\mathbf{u}}_1,\dots ,{\mathbf{u}}_r$ be the independent columns and ${\mathbf{w}}_1,\dots ,{\mathbf{w}}_{n-r}$ the dependent columns, each in the order in which they appear in $A$. There are $n-r$ dependent columns because there are $n$ columns in total.

Key observation. For every $j$, ${\mathbf{w}}_j$ is a linear combination of

${\mathbf{u}}_1,\dots ,{\mathbf{u}}_r,{\mathbf{w}}_1,\dots ,{\mathbf{w}}_{j-1}.$

Reason: ${\mathbf{w}}_j$ is dependent, so it is a linear combination of the columns of $A$ before it. Every column before ${\mathbf{w}}_j$ is either an independent column (some ${\mathbf{u}}_i$) or an earlier dependent column (some ${\mathbf{w}}_k$, $k<j$), so the list above contains all of them. It may contain some extra columns (independent columns located after ${\mathbf{w}}_j$), but these can simply get the scalar $0$.

Building up the span. Start with

$\mathrm{Span}({\mathbf{u}}_1,\dots ,{\mathbf{u}}_r)=\mathbf{C}(C).$

Append ${\mathbf{w}}_1,{\mathbf{w}}_2,\dots ,{\mathbf{w}}_{n-r}$ one after the other. At step $j$, the appended vector ${\mathbf{w}}_j$ is a linear combination of the vectors already present (key observation), so by Lemma 1.24 the span does not change. After all steps:

$\mathbf{C}(C)=\mathrm{Span}({\mathbf{u}}_1,\dots ,{\mathbf{u}}_r,{\mathbf{w}}_1,\dots ,{\mathbf{w}}_{n-r})=\mathbf{C}(A),$

where the last equality holds because this sequence contains exactly the columns of $A$, just reordered, and the span does not depend on the order. $■$

Intuition: going left to right, a dependent column is already “covered” by what came before, so it contributes nothing new to the span and can be forgotten.

3.10 $T_A$ is well defined, and determined by its columns

$T_A$ is a function since $A\mathbf{x}$ exists and is unique for every $\mathbf{x}\in {\mathbb{R}}^n$ (Def. 2.4), and it lands in ${\mathbb{R}}^m$. Moreover, by Def. 2.4 and §3.5,

$T_A(\mathbf{x})=x_1(A{\mathbf{e}}_1)+\cdots +x_n(A{\mathbf{e}}_n),$

so $T_A$ is completely determined by the images of the unit vectors, which are the columns.

---

4. Worked Examples & Applications

4.1 One product, three ways

Linear combination written as a matrix–vector product:

$7\left(\begin{array}{c}1\\ 3\\ 5\end{array}\right)+8\left(\begin{array}{c}2\\ 4\\ 6\end{array}\right)=\left[\begin{array}{cc}1& 2\\ 3& 4\\ 5& 6\end{array}\right]\left(\begin{array}{c}7\\ 8\end{array}\right)=\left(\begin{array}{c}23\\ 53\\ 83\end{array}\right).$

• Columns: $7\cdot (1,3,5)+8\cdot (2,4,6)=(7,21,35)+(16,32,48)=(23,53,83)$.
• Rows (scalar products):
  • row 1: $1\cdot 7+2\cdot 8=7+16=23$
  • row 2: $3\cdot 7+4\cdot 8=21+32=53$
  • row 3: $5\cdot 7+6\cdot 8=35+48=83$
• Entrywise formula: identical arithmetic, organised as $a_{i1}{x}_1+a_{i2}{x}_2$.

Dimension check: $(3\times 2)$ times ${\mathbb{R}}^2$ gives ${\mathbb{R}}^3$. ✓

4.2 Matrix operations (Def. 2.2)

$\left[\begin{array}{cc}1& 2\\ 3& 4\end{array}\right]+\left[\begin{array}{cc}5& 6\\ 7& 8\end{array}\right]=\left[\begin{array}{cc}6& 8\\ 10& 12\end{array}\right],2\left[\begin{array}{cc}1& 2\\ 3& 4\end{array}\right]=\left[\begin{array}{cc}2& 4\\ 6& 8\end{array}\right],-\left[\begin{array}{cc}1& 2\\ 3& 4\end{array}\right]=\left[\begin{array}{cc}-1& -2\\ -3& -4\end{array}\right].$

⚠️ Exam Trap: $A+B$ is defined only when $A$ and $B$ have the same number of rows and the same number of columns.

4.3 Clicker: ${\mathbf{v}}^{\top }\left[\begin{array}{cc}0& 1\\ -1& 0\end{array}\right]\mathbf{v}$

Let $\mathbf{v}=\left(\begin{array}{c}{v}_1\\ v_2\end{array}\right)$ be arbitrary.

1. Matrix–vector product (row view): row 1 is $(0;1)$, giving $0\cdot v_1+1\cdot v_2=v_2$. Row 2 is $(-1;0)$, giving $-v_1$. So $\left[\begin{array}{cc}0& 1\\ -1& 0\end{array}\right]\mathbf{v}=\left(\begin{array}{c}{v}_2\\ -v_1\end{array}\right)$.
2. Scalar product with ${\mathbf{v}}^{\top }=(v_1;v_2)$: $v_1{v}_2+v_2(-v_1)=0$.

Answer: always $0$, independent of $\mathbf{v}$.

⚠️ Exam Trap: The popular wrong answer was “depends on $\mathbf{v}$”. Always compute symbolically before guessing.

Geometric reason: this matrix rotates every vector by $90°$ (clockwise: ${\mathbf{e}}_1\mapsto (0,-1)$). A vector rotated by $90°$ is orthogonal to the original, so the scalar product is $0$.

4.4 Column space: Fakt 1.5 in matrix language

$\mathbf{C}\left(\left[\begin{array}{cc}2& 3\\ 3& -1\end{array}\right]\right)=\mathrm{Span}\left(\left(\begin{array}{c}2\\ 3\end{array}\right),\left(\begin{array}{c}3\\ -1\end{array}\right)\right)={\mathbb{R}}^2.$

This also follows from Lemma 1.26: the columns are two linearly independent vectors in ${\mathbb{R}}^2$ (neither is a multiple of the other). If the two columns were linearly dependent, the column space would only be a line (or $0$).

4.5 Rank by scanning columns left to right

(a) $A=\left[\begin{array}{cc}2& 4\\ 3& 1\end{array}\right]$:

• ${\mathbf{v}}_1=(2,3{)}^{\top }\ne 0$, so it is not a combination of the empty sequence: independent.
• ${\mathbf{v}}_2=(4,1{)}^{\top }$: is it $\lambda (2,3{)}^{\top }$? From the first entry $\lambda =2$, but then the second entry would be $6\ne 1$. So it is independent.
• $\mathrm{rank}(A)=2$. Geometrically, the columns are not on a common line.

(b) $A=\left[\begin{array}{cc}2& 4\\ 3& 6\end{array}\right]$:

• ${\mathbf{v}}_1=(2,3{)}^{\top }$ is independent.
• ${\mathbf{v}}_2=(4,6{)}^{\top }=2{\mathbf{v}}_1$ is dependent.
• $\mathrm{rank}(A)=1$. Both columns lie on one line through the origin. By Lemma 2.11, $\mathbf{C}(A)=\mathrm{Span}((2,3{)}^{\top })$.

(c) Order matters for which columns, not for how many: $A=\left[\begin{array}{cc}0& 1\\ 0& 0\end{array}\right]$.

• Left to right: $(0,0{)}^{\top }$ is dependent (zero column), $(1,0{)}^{\top }$ is independent. Rank $1$.
• Reversed $\left[\begin{array}{cc}1& 0\\ 0& 0\end{array}\right]$: $(1,0{)}^{\top }$ is independent, $(0,0{)}^{\top }$ is dependent. Rank $1$.

Different independent columns, same rank, as promised by the (later-proven) invariance under reordering.

⚠️ Exam Trap: The first column is independent $⟺$ it is nonzero. Every zero column is dependent, wherever it appears.

4.6 Transpose

$A=\left[\begin{array}{ccc}1& 2& 3\\ 4& 5& 6\end{array}\right]\in {\mathbb{R}}^{2\times 3}⟹A^{\top }=\left[\begin{array}{cc}1& 4\\ 2& 5\\ 3& 6\end{array}\right]\in {\mathbb{R}}^{3\times 2}.$

Check one entry: $b_{12}=4=a_{21}$. ✓ The first row of $A$ becomes the first column of $A^{\top }$.

⚠️ Exam Trap: In the definition $A^{\top }=[b_{ij}{]}_{i=1,,j=1}^{n,;m}$, the index ranges also swap: $i$ runs to $n$ and $j$ to $m$. (The lecturer misspoke ”$j=1$ to $n$” on the board audio; the tablet has it correct.)

4.7 Row spaces (tablet pictures)

• $\mathbf{R}\left(\left[\begin{array}{cc}2& 4\\ 3& 1\end{array}\right]\right)=\mathrm{Span}\left(\left(\begin{array}{c}2\\ 4\end{array}\right),\left(\begin{array}{c}3\\ 1\end{array}\right)\right)={\mathbb{R}}^2$. The rows, made into columns of $A^{\top }$, are linearly independent.
• $\mathbf{R}\left(\left[\begin{array}{cc}2& 4\\ 3& 6\end{array}\right]\right)=\mathrm{Span}\left(\left(\begin{array}{c}2\\ 4\end{array}\right),\left(\begin{array}{c}3\\ 6\end{array}\right)\right)$ is a line, since $(3,6)=\frac{3}{2}(2,4)$.

Notice that in both cases the row space “looks as big as” the column space (${\mathbb{R}}^2$ vs. ${\mathbb{R}}^2$; line vs. line). This is a preview of $\dim \mathbf{R}(A)=\dim \mathbf{C}(A)=\mathrm{rank}(A)$.

4.8 Null space computation

Claim:$\mathbf{N}\left(\left[\begin{array}{cc}2& 4\\ 3& 6\end{array}\right]\right)=\left\{\left(\begin{array}{c}x\\ y\end{array}\right)\in {\mathbb{R}}^2:y=-\frac{x}{2}\right\}$

1. By definition, $(x,y{)}^{\top }\in \mathbf{N}(A)⟺\left[\begin{array}{cc}2& 4\\ 3& 6\end{array}\right]\left(\begin{array}{c}x\\ y\end{array}\right)=\left(\begin{array}{c}0\\ 0\end{array}\right)$.
2. Row view: each row times the vector gives one entry of the result, so this is a system of two linear equations:
   • $2x+4y=0$
   • $3x+6y=0$
3. The second equation is $\frac{3}{2}$ times the first, so both say the same thing. Drop one.
4. Solve $2x+4y=0$ for $y$: $y=-\frac{x}{2}$.

Geometrically, $\mathbf{N}(A)$ is the line through the origin with slope $-\frac{1}{2}$.
Sanity check: $(2,-1{)}^{\top }\in \mathbf{N}(A)$, since $2\cdot 2+4\cdot (-1)=0$ and $3\cdot 2+6\cdot (-1)=0$. Equivalently, $2{\mathbf{v}}_1-{\mathbf{v}}_2=0$, a nontrivial combination giving $0$. This is consistent with the columns being dependent ($\mathrm{rank}=1$) and with Beob. 2.5(ii).

4.9 Matrix transformations

(a) Swap / mirroring. $A=\left[\begin{array}{cc}0& 1\\ 1& 0\end{array}\right]$:

$T_A\left(\begin{array}{c}{x}_1\\ x_2\end{array}\right)=\left[\begin{array}{cc}0& 1\\ 1& 0\end{array}\right]\left(\begin{array}{c}{x}_1\\ x_2\end{array}\right)=\left(\begin{array}{c}{x}_2\\ x_1\end{array}\right)\in {\mathbb{R}}^2.$

Row 1 $(0;1)$ picks out $x_2$; row 2 $(1;0)$ picks out $x_1$. E.g. $(3,4{)}^{\top }\mapsto (4,3{)}^{\top }$. Seen as points, this is the reflection at the main diagonal $y=x$.

(b) Non-square. $A=\left[\begin{array}{cc}1& 1\end{array}\right]\in {\mathbb{R}}^{1\times 2}$:

$T_A\left(\begin{array}{c}{x}_1\\ x_2\end{array}\right)=\left[\begin{array}{cc}1& 1\end{array}\right]\left(\begin{array}{c}{x}_1\\ x_2\end{array}\right)=(x_1+x_2)\in {\mathbb{R}}^1.$

The input needs 2 coordinates (2 columns); the output is a vector in ${\mathbb{R}}^1$, which looks like a number but is formally a 1-dimensional vector. This matrix is “essentially a covector”; covectors as transformations come next week.

(c) Geometry of $A(X)$ for an L-shaped point set $X$ (each column is the image of a unit vector, $A{\mathbf{e}}_j$):

Matrix	$A{\mathbf{e}}_1$, $A{\mathbf{e}}_2$	Effect on $X$
$\left[\begin{array}{cc}1& 0\\ 0& \frac{3}{4}\end{array}\right]$	$(1,0)$, $(0,\frac{3}{4})$	stretching/compression: squashes in $y$-direction by factor $\frac{3}{4}$
$\left[\begin{array}{cc}0& 1\\ 1& 0\end{array}\right]$	$(0,1)$, $(1,0)$	mirroring at the diagonal: mirrored L
$\left[\begin{array}{cc}\frac{1}{\sqrt{2}}& -\frac{1}{\sqrt{2}}\\ frac1\sqrt{2}& \frac{1}{\sqrt{2}}\end{array}\right]$	$(\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}})$, $(-\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}})$	rotation by $45°$ counterclockwise
$\left[\begin{array}{cc}1& -\frac{1}{2}\\ 0& 1\end{array}\right]$	$(1,0)$, $(-\frac{1}{2},1)$	shear: slanted, deformed L
$I$	$(1,0)$, $(0,1)$	nothing changes

Application: this is precisely what computer graphics does. There is an interactive Scratch animation in Moodle for experimenting with the four entries.

⚠️ Exam Trap (where things live): For $A\in {\mathbb{R}}^{m\times n}$, $\mathbf{C}(A)\subseteq {\mathbb{R}}^m$, while $\mathbf{R}(A)\subseteq {\mathbb{R}}^n$ and $\mathbf{N}(A)\subseteq {\mathbb{R}}^n$. Inputs live in ${\mathbb{R}}^n$, outputs in ${\mathbb{R}}^m$.

⚠️ Exam Trap (hypotheses): Lemma 1.24 needs $\mathbf{v}$ to be a linear combination; adding an arbitrary vector can enlarge the span. Lemma 1.26 needs exactly $m$ independent vectors in ${\mathbb{R}}^m$; e.g. two independent vectors in ${\mathbb{R}}^3$ only span a plane.

---

5. Intuition & Conceptual Bridges

• Span = reachable set. $\mathrm{Span}$ is everything reachable by scaling and adding. A vector that is already reachable (a linear combination) adds no new reach (Lemma 1.24), and conversely can be removed (Kor. 1.25).
• Rank = number of genuinely new directions. Scanning columns left to right, a column is independent exactly when it points somewhere the previous columns cannot reach. The rank counts these “new directions”, and Lemma 2.11 says they alone generate the entire column space. Rank $n$: every column adds something new. Rank $0$: nothing at all (zero matrix).
• Exchange argument = trading spanning vectors. Lemma 1.26 starts from a known spanning set (unit vectors) and trades them, one at a time, for the given independent vectors. Independence guarantees that what gets thrown out is always an old unit vector, never a new one. This is the core idea of the Steinitz exchange lemma later.
• Three readings of $A\mathbf{x}$. Column view: “how much of each column do I mix?” (good for span and rank questions). Row view: “how does $\mathbf{x}$ score against each row?” (good for computing and for equations). Entrywise: pure bookkeeping. Pick whichever makes a problem easiest; all give the same result.
• Matrices are transformations. $T_A$ takes inputs in ${\mathbb{R}}^n$ to outputs in ${\mathbb{R}}^m$. The columns tell you where the unit vectors go, and everything else follows by linear combination. $\mathbf{C}(A)$ is the set of all outputs, and $\mathbf{N}(A)$ is the set of inputs that get “crushed” to $0$. Independent columns mean only $0$ is crushed.
• Language translation as a learning tool. Beob. 2.5 says nothing new; it restates Week 1 notions (linear combination, independence) in matrix language as a double check of understanding.
• Bridges forward:
  • $A\mathbf{x}=\mathbf{b}$ will be the standard form of a system of linear equations. Beob. 2.5(i) already says it is solvable $⟺\mathbf{b}\in \mathbf{C}(A)$.
  • Dimension: $\mathrm{rank}(A)=\dim \mathbf{C}(A)=\dim \mathbf{R}(A)$, and $\dim \mathbf{N}(A)$ depends on the rank. Relationships between the three spaces come later.
  • Rank is invariant under column reordering (proof later).
  • Vector spaces: ${\mathbb{R}}^m$, $\mathbf{C}(A)$, $\mathbf{R}(A)$, $\mathbf{N}(A)$, and even ${\mathbb{R}}^{m\times n}$ will be treated abstractly as vector spaces.
  • Covectors as transformations (next week); matrix–matrix multiplication (behaves analogously to matrix–vector); mathematical induction (rigorous version of “and so on” proofs).

---

6. Summary & Self-Assessment Questions

Cheat sheet

Concept	Definition / formula	Lives in
Span	${\sum }_j{\lambda }_j{\mathbf{v}}_j$; order irrelevant; $\mathrm{Span}()=0$	${\mathbb{R}}^m$
Lemma 1.24 / Kor. 1.25	adding/removing a linear combination keeps the span
Lemma 1.26	$m$ independent vectors in ${\mathbb{R}}^m$ span ${\mathbb{R}}^m$
Matrix	$A=[a_{ij}{]}_{i=1,j=1}^{m,n}$, $a_{ij}$ = row $i$, column $j$	${\mathbb{R}}^{m\times n}$
Kronecker delta	${\delta }_{ij}=1$ if $i=j$, else $0$; $I=[{\delta }_{ij}]$
Diagonal / upper / lower / symmetric	$a_{ij}=0$ for $i\ne j$ / $i>j$ / $i<j$; $a_{ij}=a_{ji}$	square only
$A\mathbf{x}$ (columns)	${\sum }_j{x}_j{\mathbf{v}}_j$; needs columns of $A$ = entries of $\mathbf{x}$	${\mathbb{R}}^m$
$A\mathbf{x}$ (entrywise)	$(A\mathbf{x}{)}_i={\sum }_j{a}_{ij}{x}_j$
$A\mathbf{x}$ (rows)	$({\mathbf{u}}_1^{\top }\mathbf{x},\dots ,{\mathbf{u}}_m^{\top }\mathbf{x}{)}^{\top }$
Unit vector images	$A{\mathbf{e}}_j={\mathbf{v}}_j$; $I\mathbf{x}=\mathbf{x}$
Beob. 2.5	$\mathbf{b}\in$ col. comb. $⟺\exists \mathbf{x}:A\mathbf{x}=\mathbf{b}$; cols indep. $⟺$ ($A\mathbf{x}=0\Rightarrow \mathbf{x}=0$)
Column space	$\mathbf{C}(A)=A\mathbf{x}=\mathrm{Span}(\text{cols})$, contains $0$	${\mathbb{R}}^m$
Rank	# independent columns (not a combination of earlier ones); $0\le \mathrm{rank}\le n$
Rank extremes	$\mathrm{rank}=n⟺$ cols lin. indep.; $\mathrm{rank}=0⟺A=0$
Lemma 2.11	$\mathbf{C}(A)=\mathbf{C}(C)$, $C$ = submatrix of independent columns
Transpose	$A^{\top }\in {\mathbb{R}}^{n\times m}$, $(A^{\top }{)}_{ij}=a_{ji}$; symmetric $⟺A^{\top }=A$
Row space	$\mathbf{R}(A)=\mathbf{C}(A^{\top })$	${\mathbb{R}}^n$
Null space	$\mathbf{N}(A)=\mathbf{x}:A\mathbf{x}=0$, contains $0$	${\mathbb{R}}^n$
Null space extremes	$0⟺$ cols lin. indep.; ${\mathbb{R}}^n⟺A=0$
Transformation	$T_A:{\mathbb{R}}^n\to {\mathbb{R}}^m$, $\mathbf{x}\mapsto A\mathbf{x}$; $A(X)=A\mathbf{x}:\mathbf{x}\in X$

Practice questions

Question 1. Let $A=\left[\begin{array}{ccc}1& 2& 3\\ 2& 4& 7\end{array}\right]$. Determine the independent columns, $\mathrm{rank}(A)$, $\mathbf{C}(A)$, and $\mathbf{N}(A)$. Justify each step with a result from the lecture.

Solution to Question 1

Columns: ${\mathbf{v}}_1=(1,2{)}^{\top }$, ${\mathbf{v}}_2=(2,4{)}^{\top }$, ${\mathbf{v}}_3=(3,7{)}^{\top }$.

• ${\mathbf{v}}_1\ne 0$, so it is not a linear combination of the empty sequence: independent.
• ${\mathbf{v}}_2=2{\mathbf{v}}_1$: dependent.
• ${\mathbf{v}}_3$: it would have to be a combination of ${\mathbf{v}}_1,{\mathbf{v}}_2$. By Korollar 1.25, $\mathrm{Span}({\mathbf{v}}_1,{\mathbf{v}}_2)=\mathrm{Span}({\mathbf{v}}_1)$, so it would have to be $\lambda (1,2{)}^{\top }$. The first entry forces $\lambda =3$, giving $(3,6{)}^{\top }\ne (3,7{)}^{\top }$. So ${\mathbf{v}}_3$ is independent.

Hence $\mathrm{rank}(A)=2$.

Column space: by Lemma 2.11, $\mathbf{C}(A)=\mathbf{C}(C)$ with $C=\left[\begin{array}{cc}1& 3\\ 2& 7\end{array}\right]$. The columns of $C$ are linearly independent: each is independent in $C$, so this follows by Korollar 1.21(iii). They are 2 linearly independent vectors in ${\mathbb{R}}^2$, so by Lemma 1.26, $\mathbf{C}(A)={\mathbb{R}}^2$.

Null space: solve $A\mathbf{x}=0$ (row view):

• $x_1+2x_2+3x_3=0$
• $2x_1+4x_2+7x_3=0$

Subtract twice the first equation from the second: $(2x_1+4x_2+7x_3)-2(x_1+2x_2+3x_3)=x_3=0$. Insert into the first equation: $x_1=-2x_2$. Therefore

$\mathbf{N}(A)=\left\{t\left(\begin{array}{c}-2\\ 1\\ 0\end{array}\right):t\in \mathbb{R}\right\},$

a line through the origin in ${\mathbb{R}}^3$. Check: $-2{\mathbf{v}}_1+1\cdot {\mathbf{v}}_2+0\cdot {\mathbf{v}}_3=0$ ✓, consistent with the columns being dependent (Beob. 2.5(ii)).

Question 2. Prove that $\mathrm{rank}(A)\le \min (m,n)$ for every $A\in {\mathbb{R}}^{m\times n}$. Hint: for the bound by $m$, use Lemma 1.26.

Solution to Question 2

$\mathrm{rank}(A)\le n$: there are only $n$ columns.

$\mathrm{rank}(A)\le m$: suppose, for contradiction, that $\mathrm{rank}(A)\ge m+1$. Let ${\mathbf{u}}_1,\dots ,{\mathbf{u}}_{m+1}$ be the first $m+1$ independent columns, in the order of $A$.

1. These form a linearly independent sequence. Each ${\mathbf{u}}_k$ is not a linear combination of all columns of $A$ before it, so in particular it is not a combination of ${\mathbf{u}}_1,\dots ,{\mathbf{u}}_{k-1}$ (a subset of those columns; a combination of the subset would be a combination of all of them, with zeros elsewhere). By Korollar 1.21(iii), ${\mathbf{u}}_1,\dots ,{\mathbf{u}}_{m+1}$ are linearly independent, and so are ${\mathbf{u}}_1,\dots ,{\mathbf{u}}_m$.
2. By Lemma 1.26, $\mathrm{Span}({\mathbf{u}}_1,\dots ,{\mathbf{u}}_m)={\mathbb{R}}^m$.
3. Hence ${\mathbf{u}}_{m+1}\in {\mathbb{R}}^m$ is a linear combination of ${\mathbf{u}}_1,\dots ,{\mathbf{u}}_m$, which are all columns before it. So ${\mathbf{u}}_{m+1}$ is dependent. Contradiction.

Therefore $\mathrm{rank}(A)\le m$, and altogether $\mathrm{rank}(A)\le \min (m,n)$. $■$

Consequence: a wide matrix ($m<n$) can never have linearly independent columns, so $\mathbf{N}(A)\ne 0$ for wide $A$. In particular, more than $m$ vectors in ${\mathbb{R}}^m$ are always linearly dependent.

Question 3. Find a matrix $A$ with $T_A\left(\begin{array}{c}{x}_1\\ x_2\end{array}\right)=\left(\begin{array}{c}{x}_1+x_2\\ x_1-x_2\\ 2x_2\end{array}\right)$ for all $x_1,x_2$. What are its dimensions? Determine $\mathbf{N}(A)$ and $\mathrm{rank}(A)$.

Solution to Question 3

Input in ${\mathbb{R}}^2$, output in ${\mathbb{R}}^3$, so $A\in {\mathbb{R}}^{3\times 2}$ (a tall matrix).

The columns are the images of the unit vectors ($A{\mathbf{e}}_j={\mathbf{v}}_j$):

• $T_A({\mathbf{e}}_1)=T_A(1,0)=(1,1,0{)}^{\top }$
• $T_A({\mathbf{e}}_2)=T_A(0,1)=(1,-1,2{)}^{\top }$

$A=\left[\begin{array}{cc}1& 1\\ 1& -1\\ 0& 2\end{array}\right].$

Check with the row view: $(1;1)\cdot \mathbf{x}=x_1+x_2$, $(1;-1)\cdot \mathbf{x}=x_1-x_2$, $(0;2)\cdot \mathbf{x}=2x_2$ ✓.

Null space: $A\mathbf{x}=0$ means $2x_2=0$, so $x_2=0$, and then $x_1+x_2=0$ gives $x_1=0$. So $\mathbf{N}(A)=0$. By Beob. 2.5(ii), the columns are linearly independent, so $\mathrm{rank}(A)=n=2$.

Question 4 (True/False; justify).
(a) For $A\in {\mathbb{R}}^{3\times 2}$ and $\mathbf{x}\in {\mathbb{R}}^3$, $A\mathbf{x}$ is defined.
(b) Every diagonal matrix is symmetric.
(c) For $A\in {\mathbb{R}}^{m\times n}$, $\mathbf{C}(A)\subseteq {\mathbb{R}}^n$.
(d) If the first column of $A\in {\mathbb{R}}^{m\times n}$ is zero, then $\mathrm{rank}(A)\le n-1$.
(e) There is a $2\times 3$ matrix $A$ with $\mathbf{N}(A)=0$.
(f) The zero matrix is upper triangular, lower triangular, diagonal and symmetric.

Solution to Question 4

(a) False. $A$ has 2 columns, but $\mathbf{x}$ has 3 entries. The product requires columns = entries, so it is undefined.

(b) True. For $i\ne j$, both $a_{ij}=0$ and $a_{ji}=0$, so $a_{ij}=a_{ji}$. For $i=j$ the condition $a_{ii}=a_{ii}$ is trivial.

(c) False. $A\mathbf{x}$ has $m$ entries (one per row), so $\mathbf{C}(A)\subseteq {\mathbb{R}}^m$. It is $\mathbf{R}(A)$ and $\mathbf{N}(A)$ that lie in ${\mathbb{R}}^n$.

(d) True. The zero vector is the empty linear combination, so the first column is dependent. At most the remaining $n-1$ columns can be independent.

(e) False. By Question 2, $\mathrm{rank}(A)\le \min (2,3)=2<3=n$. So the columns are not linearly independent (that would need rank $n$), and by Beob. 2.5(ii), $\mathbf{N}(A)\ne 0$.

(f) True. All of these conditions only demand zeros (or equal entries) off the diagonal, and the zero matrix has zeros everywhere. It is, however, not the identity.

Question 5. Prove for any $A\in {\mathbb{R}}^{m\times n}$: (i) $(A^{\top }{)}^{\top }=A$; (ii) a square matrix $A$ is symmetric $⟺A^{\top }=A$; (iii) a square matrix $A$ is upper triangular $⟺A^{\top }$ is lower triangular.

Solution to Question 5

Write $B=A^{\top }$, so $b_{ij}=a_{ji}$ (Def. 2.12), and $B\in {\mathbb{R}}^{n\times m}$.

(i) $B^{\top }\in {\mathbb{R}}^{m\times n}$ has entries $(B^{\top }{)}_{ij}=b_{ji}=a_{ij}$ for all $i,j$. Same dimensions and same entries, so $(A^{\top }{)}^{\top }=A$.

(ii) For square $A$, $A^{\top }$ has the same dimensions as $A$. Then $A^{\top }=A⟺b_{ij}=a_{ij}$ for all $i,j$ $⟺a_{ji}=a_{ij}$ for all $i,j$, which is exactly the definition of symmetric.

(iii) $A$ is upper triangular $⟺$ ($i>j\Rightarrow a_{ij}=0$). $A^{\top }$ is lower triangular $⟺$ ($i<j\Rightarrow b_{ij}=0$) $⟺$ ($i<j\Rightarrow a_{ji}=0$). Renaming the indices ($k:=j$, $l:=i$), this says ($k>l\Rightarrow a_{kl}=0$), which is exactly the upper-triangular condition for $A$. $■$