Week 3 Linear Transformations, Their Matrices, Induction, Matrix Multiplication

Sources & numbering

Friday lecture (first part of Week 3: linear transformations, Abschnitt 2.2) + Wednesday lecture (second part: matrix multiplication, Abschnitt 2.3) + tablet notes. Numbering follows the course script (Def. 2.19 – Lemma 2.40).

• The proofs of Beob. 2.20, Lemma 2.38 (transpose of a product), Korollar 2.39 and distributivity (Lemma 2.40(i)) were skipped in the lecture (“easy” / “see script”). Short proofs are included and marked supplementary.
• The Wednesday clicker could not run (no internet), so nothing is missing from it.

Notation

• Vectors are bold ($\mathbf{x},{\mathbf{x}}^{\prime }$); matrices are uppercase ($A,B,C$).
• $T_A$ is the matrix transformation of $A$ (Def. 2.18): $T_A(\mathbf{x})=A\mathbf{x}$.
• ${\mathbf{e}}_j$ are the standard unit vectors.
• $0$ (bold) is the zero vector; $0$ (thin) is the number zero. The difference matters for linear functionals, whose outputs are numbers.

---

1. Executive Overview & Core Objectives

This week answers the question “what is a matrix?”. Linear transformations are defined axiomatically, as maps that preserve vector addition and scalar multiplication. Two directions are then established. Every matrix transformation is linear (Beob. 2.20). Conversely, every linear transformation is a matrix transformation, with a unique matrix whose columns are the images of the standard unit vectors (Theorem 2.23). Its proof introduces mathematical induction. Matrix multiplication is then derived rather than postulated: $AB$ is the matrix of the composition $T_A\circ T_B$. This explains the column rule, the “rows times columns” rule, associativity, the reversed order in $(AB{)}^{\top }=B^{\top }{A}^{\top }$, and why $AB\ne BA$ in general.

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

• state the linearity axioms, prove that a given map is linear (directly or via a matrix), and disprove linearity with a concrete counterexample;
• use the consequences $T(0)=0$ and $T({\sum }_j{\lambda }_j{\mathbf{x}}_j)={\sum }_j{\lambda }_{j}T({\mathbf{x}}_j)$;
• write a proof by induction (base case, induction hypothesis, induction step), and relate it to an informal “and so on” proof;
• state and prove Theorem 2.23, and compute the matrix of a linear map from $T({\mathbf{e}}_1),\dots ,T({\mathbf{e}}_n)$;
• define composition, prove that it preserves linearity, and derive the matrix of $T_A\circ T_B$;
• compute $AB$ in three ways (columns $A{\mathbf{x}}_j$, rows times columns, entry formula ${\sum }_{\ell }{a}_{i\ell }{b}_{\ell j}$), with correct dimension checks;
• apply $(AB{)}^{\top }=B^{\top }{A}^{\top }$, $IA=A=AI$, distributivity, and associativity (with its transformation proof), and know that commutativity fails.

---

2. Core Concepts & Formal Definitions

2.1 Linear transformations and linear functionals (Abschnitt 2.2)

Definition 2.19 (Linear transformation / linear functional)

A function $T:{\mathbb{R}}^n\to {\mathbb{R}}^m$ is a linear transformation (lineare Transformation), and a function $T:{\mathbb{R}}^n\to \mathbb{R}$ is a linear functional (lineares Funktional), if the following linearity axioms (Linearitätsaxiome) hold for all $\mathbf{x},{\mathbf{x}}^{\prime }\in {\mathbb{R}}^n$ and all $\lambda \in \mathbb{R}$:

• (i) $T(\mathbf{x}+{\mathbf{x}}^{\prime })=T(\mathbf{x})+T({\mathbf{x}}^{\prime })$
• (ii) $T(\lambda \mathbf{x})=\lambda T(\mathbf{x})$

Axiomatic vs. constructive definitions. An axiom here is a defining property.

• A constructive definition says what the objects look like. Example: a vector is a tuple of reals.
• An axiomatic definition says which properties the objects must have, without saying what they look like. Example: linear transformations are all functions satisfying (i) and (ii).
• With an axiomatic definition, always check that objects with these properties exist; otherwise the definition is pointless. Here they do: matrix transformations (Beob. 2.20).
• A theory is then built on the axioms alone (Lemma 2.21, Lemma 2.22, Theorem 2.23).

Interpretation: preservation of the linear operations

	sum relation	scaling relation
original vectors	$\mathbf{x},{\mathbf{x}}^{\prime },\mathbf{x}+{\mathbf{x}}^{\prime }$: the third is the sum of the first two	$\mathbf{x},\lambda \mathbf{x}$: the second is $\lambda$ times the first
transformed vectors	$T(\mathbf{x}),T({\mathbf{x}}^{\prime }),T(\mathbf{x}+{\mathbf{x}}^{\prime })$: still sum, by (i)	$T(\mathbf{x}),T(\lambda \mathbf{x})$: still $\lambda$ times, by (ii)

A linear transformation preserves vector addition and scalar multiplication (Erhaltung von Vektoraddition und Skalarmultiplikation). Relations between the inputs survive the transformation.

Beobachtung 2.20

Every matrix transformation $T_A$ is a linear transformation.

To prove it, check the axioms for $T_A(\mathbf{x})=A\mathbf{x}$: (i) $A(\mathbf{x}+{\mathbf{x}}^{\prime })=A\mathbf{x}+A{\mathbf{x}}^{\prime }$ and (ii) $A(\lambda \mathbf{x})=\lambda A\mathbf{x}$. Both follow from the rules of vector addition, scalar multiplication and Def. 2.4 (proof in §3.1).

Definition (official meaning of a covector)

For a fixed $\mathbf{v}\in {\mathbb{R}}^m$, the linear functional $T(\mathbf{x})={\mathbf{v}}^{\top }\mathbf{x}={\sum }_{i=1}^m{v}_i{x}_i$ is the covector ${\mathbf{v}}^{\top }$ (Def. 1.18). Officially, a covector is a linear functional; “row vector” is our working picture of it.

2.2 Basic consequences of the axioms

Lemma 2.21 ("Null rein, Null raus", zero in, zero out)

If $T$ is a linear transformation (or linear functional), then $T(0)=0$ (respectively $T(0)=0$).

Lemma 2.22 (Preservation of linear combinations)

Let $T$ be a linear transformation (or linear functional), ${\mathbf{x}}_1,\dots ,{\mathbf{x}}_{\ell }\in {\mathbb{R}}^n$ and ${\lambda }_1,\dots ,{\lambda }_{\ell }\in \mathbb{R}$. Then
$T\left({\sum }_{j=1}^{\ell }{\lambda }_j{\mathbf{x}}_j\right)={\sum }_{j=1}^{\ell }{\lambda }_{j}T({\mathbf{x}}_j).$
(The board first wrote ${\mathbf{x}}_1,\dots ,{\mathbf{x}}_n$; the number of vectors is $\ell$.)

If a vector is a linear combination of others before transforming, it is the same linear combination of the transformed vectors after transforming. Preserving addition and scaling means preserving everything built from them.

2.3 The matrix of a linear transformation

Theorem 2.23

Let $T:{\mathbb{R}}^n\to {\mathbb{R}}^m$ be a linear transformation. There is exactly one $m\times n$ matrix $A$ with $T=T_A$, i.e. $T(\mathbf{x})=A\mathbf{x}$ for all $\mathbf{x}\in {\mathbb{R}}^n$. It is
$A=\left[\begin{array}{cccc}T({\mathbf{e}}_1)& T({\mathbf{e}}_2)& \cdots & T({\mathbf{e}}_n)\end{array}\right].$

• Two functions are equal when they agree on every input.
• Insight (Erkenntnis): “linear transformation” and “matrix transformation” are the same concept under two names. The only difference is how the information is given. For $T_A$ the matrix is handed to you; for an abstract linear $T$ you compute it from $T({\mathbf{e}}_1),\dots ,T({\mathbf{e}}_n)$.
• Terminology: a Theorem is a statement that is interesting in itself, not just a tool. (A Lemma is mainly a tool.)
• On the value of such insights: basic research is often done for understanding, not for immediate applications. Number theory of primes was “useless” for centuries until cryptography made it indispensable.

Useful fact used everywhere

$A{\mathbf{e}}_j$ = column $j$ of $A$. Example:
$\left[\begin{array}{ccc}3& 5& 4\\ 2& 7& 1\end{array}\right]\left(\begin{array}{c}0\\ 1\\ 0\end{array}\right)=\left(\begin{array}{c}5\\ 7\end{array}\right).$

• Column view: only column 2 gets a nonzero scalar.
• Row view: in each scalar product, only the middle entry survives.

2.4 Mathematical induction (vollständige Induktion)

Definition (Proof by induction)

To prove a statement $P(\ell )$ for all natural numbers $\ell \ge {\ell }_0$:

1. Base case (Basisfall): prove $P({\ell }_0)$ directly.
2. Induction step (Induktionsschritt): for every $\ell >{\ell }_0$, prove that if $P(\ell -1)$ holds, then $P(\ell )$ holds.

The assumption ”$P(\ell -1)$ holds” is the induction hypothesis (Induktionsannahme). Then $P(\ell )$ holds for all $\ell \ge {\ell }_0$.

• Domino analogy: infinitely many dominoes numbered $0,1,2,\dots$. The base case knocks over domino 0. The step guarantees that whenever domino $\ell -1$ falls, it knocks over domino $\ell$. The process never “finishes”, but every particular domino (e.g. number 10 000 or one million) falls at some point. That is exactly the claim ”$P(\ell )$ for every $\ell$”.
• That induction is a valid proof method is accepted as a principle here. It is the price for getting rid of the dots.
• Induction is the formal, dotless version of an informal “repeat … and so on” proof. Both do the same thing. A classic induction example in the script is the “little Gauss” formula $1+2+\cdots +n=\frac{n(n+1)}{2}$.

Exam

Proofs with “and so on” (dots) are accepted, and induction is also fine. According to the lecturer, past exams practically never require induction.

2.5 Composition and matrix multiplication (Abschnitt 2.3)

Definition 2.31 (Composition, Komposition)

Let $T:{\mathbb{R}}^n\to {\mathbb{R}}^k$ and $S:{\mathbb{R}}^k\to {\mathbb{R}}^m$ be linear transformations. Their composition $S\circ T:{\mathbb{R}}^n\to {\mathbb{R}}^m$ is defined by
$(S\circ T)(\mathbf{x}):=S(T(\mathbf{x})).$
“Apply first $T$, then $S$.” The same $k$ is required: the output of $T$ must be a legal input of $S$. The intermediate dimension $k$ disappears from the result.

Lemma 2.32

If $T:{\mathbb{R}}^n\to {\mathbb{R}}^k$ and $S:{\mathbb{R}}^k\to {\mathbb{R}}^m$ are linear transformations, then $S\circ T:{\mathbb{R}}^n\to {\mathbb{R}}^m$ is a linear transformation.

Chain of reasoning for matrices:

1. $T_A$ and $T_B$ are linear (Beob. 2.20).
2. So $T_A\circ T_B$ is linear (Lemma 2.32).
3. So $T_A\circ T_B$ is a matrix transformation (Theorem 2.23).

Which matrix is it?

Lemma 2.33

Let $A$ be an $m\times k$ matrix, so $T_A:{\mathbb{R}}^k\to {\mathbb{R}}^m$. Let $B=\left[\begin{array}{ccc}{\mathbf{x}}_1& \cdots & {\mathbf{x}}_n\end{array}\right]$ be a $k\times n$ matrix, so $T_B:{\mathbb{R}}^n\to {\mathbb{R}}^k$ and $T_A\circ T_B:{\mathbb{R}}^n\to {\mathbb{R}}^m$. Then the $m\times n$ matrix
$C=\left[\begin{array}{cccc}A{\mathbf{x}}_1& A{\mathbf{x}}_2& \cdots & A{\mathbf{x}}_n\end{array}\right]$
is the unique matrix with $T_C=T_A\circ T_B$.

Dimension reminder: an $m\times k$ matrix maps ${\mathbb{R}}^k\to {\mathbb{R}}^m$ (input size = number of columns, output size = number of rows).

Definition 2.34 (Matrix multiplication, column notation)

Let $A$ be $m\times k$ and $B=\left[\begin{array}{ccc}{\mathbf{x}}_1& \cdots & {\mathbf{x}}_n\end{array}\right]$ be $k\times n$. The $m\times n$ matrix
$AB:=\left[\begin{array}{cccc}A{\mathbf{x}}_1& A{\mathbf{x}}_2& \cdots & A{\mathbf{x}}_n\end{array}\right]$
is the product of $A$ and $B$. Recipe: write $B$ column by column, and multiply each column by $A$ from the left.

Korollar 2.35

For $A$ ($m\times k$) and $B$ ($k\times n$): $T_A\circ T_B=T_{AB}$.
In matrix language: $A(B\mathbf{x})=(AB)\mathbf{x}$ for all $\mathbf{x}\in {\mathbb{R}}^n$.

Many textbooks present the entry formula first, and it looks arbitrary. Here it is derived: matrix multiplication is composition of the corresponding transformations.

Beobachtung 2.36 ("usual" definition: rows of $A$ times columns of $B$)

Write $A$ in row notation with rows ${\mathbf{u}}_1^{\top },\dots ,{\mathbf{u}}_m^{\top }$ ($A\in {\mathbb{R}}^{m\times k}$), and $B=\left[\begin{array}{ccc}{\mathbf{x}}_1& \cdots & {\mathbf{x}}_n\end{array}\right]\in {\mathbb{R}}^{k\times n}$. Then
$AB=\left[\begin{array}{cccc}{\mathbf{u}}_1^{\top }{\mathbf{x}}_1& {\mathbf{u}}_1^{\top }{\mathbf{x}}_2& \cdots & {\mathbf{u}}_1^{\top }{\mathbf{x}}_n\\ ⋮& ⋮& & ⋮\\ {\mathbf{u}}_m^{\top }{\mathbf{x}}_1& {\mathbf{u}}_m^{\top }{\mathbf{x}}_2& \cdots & {\mathbf{u}}_m^{\top }{\mathbf{x}}_n\end{array}\right]=[{\mathbf{u}}_i^{\top }{\mathbf{x}}_j{]}_{i=1,j=1}^{m,n}\in {\mathbb{R}}^{m\times n},$
i.e. $mn$ scalar products. Entry $(i,j)$ = (row $i$ of $A$) · (column $j$ of $B$).
Why it works: column $j$ of $AB$ is $A{\mathbf{x}}_j=({\mathbf{u}}_i^{\top }{\mathbf{x}}_j{)}_{i=1}^m$, by the row view of matrix–vector multiplication (Beob. 2.8).
Both $k$‘s must agree: rows of $A$ and columns of $B$ must have the same length for the scalar product.

Beobachtung 2.37 (Dotless direct definition)

For $A=[a_{ij}{]}_{i=1,j=1}^{m,k}$ and $B=[b_{ij}{]}_{i=1,j=1}^{k,n}$:
$AB={\left[{\sum }_{\ell =1}^k{a}_{i\ell }{b}_{\ell j}\right]}_{i=1,j=1}^{m,n}.$
The inner sum is exactly ${\mathbf{u}}_i^{\top }{\mathbf{x}}_j$, with $k$ terms. This is complete but impractical; it is rarely used directly.

Picture: place $A$ on the left, $B$ on top, and $AB$ in the corner where the row of $A$ and the column of $B$ meet. Dimensions fit automatically ($AB$ has as many rows as $A$ and as many columns as $B$).

2.6 Rules for matrix multiplication

Lemma 2.38 (Transpose of a product)

For $A$ ($m\times k$) and $B$ ($k\times n$): $(AB{)}^{\top }=B^{\top }{A}^{\top }$.

• Dimension check: $B^{\top }$ is $n\times k$ and $A^{\top }$ is $k\times m$, so the product is defined.
• $A^{\top }{B}^{\top }$ ($k\times m$ times $n\times k$) is in general not even defined; it only works if $m=n$.
• The rule extends to more factors, e.g. $(ABC{)}^{\top }=C^{\top }{B}^{\top }{A}^{\top }$. Bracketing doesn’t matter, by Lemma 2.40.

Korollar 2.39 (Identity)

Let $I$ be the $m\times m$ identity matrix. Then $IA=A$ for all $m\times n$ matrices $A$, and $AI=A$ for all $n\times m$ matrices $A$.

$I$ behaves like the number 1: multiplying by it changes nothing, as long as its size matches.

Lemma 2.40 (Distributivity and associativity, Abschnitt 2.3.3)

Whenever the sizes fit:

• (i) Distributivity: $A(B+C)=AB+AC$ and $(A+B)C=AC+BC$.
• (ii) Associativity: $(AB)C=A(BC)$.

• These are not automatic. Matrices are not real numbers, and matrix multiplication is a complicated operation, so the rules must be proven.
• Distributivity is a “boring” direct computation (supplementary proof in §3.9). Associativity has an elegant proof via transformations (§3.10).
• Generalized associativity: for any number of factors, the bracketing is irrelevant, e.g. $(AB)(CD)=A((BC)D)=\cdots =ABCD$. Brackets can be dropped. Formally this follows by induction, or by the same argument as for three matrices.

Matrix multiplication is NOT commutative

$AB=BA$ does not hold in general (it may happen for special matrices). Doing transformations in a different order gives a different result, just as putting on socks then shoes differs from shoes then socks.

---

3. Step-by-Step Derivations & Mathematical Proofs

3.1 Proof of Beobachtung 2.20 (supplementary)

Write $A=\left[\begin{array}{ccc}{\mathbf{v}}_1& \cdots & {\mathbf{v}}_n\end{array}\right]$. By Def. 2.4, $A\mathbf{x}={\sum }_j{x}_j{\mathbf{v}}_j$.

(i) The $j$-th coordinate of $\mathbf{x}+{\mathbf{x}}^{\prime }$ is $x_j+x_j^{\prime }$ (definition of vector addition). Hence
$A(\mathbf{x}+{\mathbf{x}}^{\prime })={\sum }_{j=1}^n(x_j+x_j^{\prime }){\mathbf{v}}_j={\sum }_{j=1}^n{x}_j{\mathbf{v}}_j+{\sum }_{j=1}^n{x}_j^{\prime }{\mathbf{v}}_j=A\mathbf{x}+A{\mathbf{x}}^{\prime }.$

(ii) The $j$-th coordinate of $\lambda \mathbf{x}$ is $\lambda x_j$. Hence
$A(\lambda \mathbf{x})={\sum }_{j=1}^n(\lambda x_j){\mathbf{v}}_j=\lambda {\sum }_{j=1}^n{x}_j{\mathbf{v}}_j=\lambda A\mathbf{x}.$

Both steps use only the vector rules (distributivity, scalars pull out). $■$

3.2 Example 1: $T(\mathbf{x})={\mathbf{v}}^{\top }\mathbf{x}$ is a linear functional (direct check)

Fix $\mathbf{v}\in {\mathbb{R}}^m$ and let $T(\mathbf{x})={\sum }_{i=1}^m{v}_i{x}_i$.

(i)
$T(\mathbf{x}+{\mathbf{x}}^{\prime })={\sum }_{i=1}^m{v}_i(x_i+x_i^{\prime })={\sum }_{i=1}^m{v}_i{x}_i+{\sum }_{i=1}^m{v}_i{x}_i^{\prime }=T(\mathbf{x})+T({\mathbf{x}}^{\prime }).$
The first equality uses the definition of vector addition (coordinates add). The second uses the distributive law in $\mathbb{R}$, which splits the sum.

(ii)
$T(\lambda \mathbf{x})={\sum }_{i=1}^m{v}_i(\lambda x_i)=\lambda {\sum }_{i=1}^m{v}_i{x}_i=\lambda T(\mathbf{x}).$
The first equality uses the definition of scalar multiplication (each coordinate is scaled). The second pulls the common factor $\lambda$ out of the real sum. $■$

Such proofs never get stuck: just compute. But note where the definitions of the vector operations enter.

3.3 Proof of Lemma 2.21

Pick any $\mathbf{x}\in {\mathbb{R}}^n$. The zero vector can be written as $0=0\cdot \mathbf{x}$. Then by axiom (ii)
$T(0)=T(0\cdot \mathbf{x})\stackrel{\text{(ii)}}{=}0\cdot T(\mathbf{x})=0(\text{or }0).$
In the target space, anything times $0$ is the zero vector (or the number $0$ for a functional). $■$

Use: an immediate test against linearity. If $T(0)\ne 0$, then $T$ is not linear. Example: the constant map $T(\mathbf{x})=\mathbf{v}\ne 0$ outputs $\mathbf{v}\ne 0$ at $0$.

3.4 Proof of Lemma 2.22, version 1: informal (“and so on”)

Split off the last term, then use the axioms:
$T\left({\sum }_{j=1}^{\ell }{\lambda }_j{\mathbf{x}}_j\right)=T({\sum }_{j=1}^{\ell -1}{\lambda }_j{\mathbf{x}}_j+{\lambda }_{\ell }{\mathbf{x}}_{\ell })\stackrel{\text{(i)}}{=}T\left({\sum }_{j=1}^{\ell -1}{\lambda }_j{\mathbf{x}}_j\right)+T({\lambda }_{\ell }{\mathbf{x}}_{\ell })\stackrel{\text{(ii)}}{=}T\left({\sum }_{j=1}^{\ell -1}{\lambda }_j{\mathbf{x}}_j\right)+{\lambda }_{\ell }T({\mathbf{x}}_{\ell }).$

The sum inside $T$ is now one term shorter. Do the same for $\ell -1$:
$=T\left({\sum }_{j=1}^{\ell -2}{\lambda }_j{\mathbf{x}}_j\right)+{\lambda }_{\ell -1}T({\mathbf{x}}_{\ell -1})+{\lambda }_{\ell }T({\mathbf{x}}_{\ell }).$

Repeat for $\ell -2,\dots ,1$:
$=\underset{T(0)=0}{\underbrace{T\left(\sum _{j=1}^0{\lambda }_j{\mathbf{x}}_j\right)}}+{\lambda }_{1}T({\mathbf{x}}_1)+\cdots +{\lambda }_{\ell -1}T({\mathbf{x}}_{\ell -1})+{\lambda }_{\ell }T({\mathbf{x}}_{\ell })={\sum }_{j=1}^{\ell }{\lambda }_{j}T({\mathbf{x}}_j).$

The leftover is the empty sum $0$, and $T(0)=0$ by Lemma 2.21. This is understandable and finite (for $\ell =10000$ you would do 10 000 steps), but the “and so on” is not fully formal.

3.5 Proof of Lemma 2.22, version 2: by induction (dotless)

Let $P(\ell )$ be the statement of the lemma for $\ell$ vectors.

Base case $\ell =0$. Both sides are empty sums. The claim reads $T(0)=0$, which is exactly Lemma 2.21. ✓

Induction step ($\ell >0$). Assume $P(\ell -1)$ (induction hypothesis). As in the first two steps of §3.4:
$T\left({\sum }_{j=1}^{\ell }{\lambda }_j{\mathbf{x}}_j\right)=T\left({\sum }_{j=1}^{\ell -1}{\lambda }_j{\mathbf{x}}_j\right)+{\lambda }_{\ell }T({\mathbf{x}}_{\ell }).$
The induction hypothesis now replaces the first term in one go, with no further repetition:
$={\sum }_{j=1}^{\ell -1}{\lambda }_{j}T({\mathbf{x}}_j)+{\lambda }_{\ell }T({\mathbf{x}}_{\ell })={\sum }_{j=1}^{\ell }{\lambda }_{j}T({\mathbf{x}}_j).$
So $P(\ell -1)\Rightarrow P(\ell )$. By induction, $P(\ell )$ holds for all $\ell \ge 0$. $■$

Exam Trap (induction step)

Apply the hypothesis to the sum (inside $T$), giving ${\sum }_{j=1}^{\ell -1}{\lambda }_{j}T({\mathbf{x}}_j)$. Do not write ${\sum }_{j}T({\lambda }_j{\mathbf{x}}_j)$ and stop there. (The lecturer first slipped here and corrected it.)

3.6 Proof of Theorem 2.23

Step 1: there is only one candidate (uniqueness). If $T=T_A$, then in particular $T({\mathbf{e}}_j)=T_A({\mathbf{e}}_j)=A{\mathbf{e}}_j$ for every $j\in [n]$. But $A{\mathbf{e}}_j$ is column $j$ of $A$. So column $j$ is forced to be $T({\mathbf{e}}_j)$, and the only possible matrix is
$A=\left[\begin{array}{ccc}T({\mathbf{e}}_1)& \cdots & T({\mathbf{e}}_n)\end{array}\right].$
Any matrix that works must be this one.

Step 2: this candidate works for all $\mathbf{x}$ (existence). So far $T$ and $T_A$ agree on the unit vectors; we need agreement everywhere:
$T_A(\mathbf{x})=A\mathbf{x}\stackrel{\text{Def. 2.4}}{=}{\sum }_{j=1}^n{x}_{j}T({\mathbf{e}}_j)\stackrel{\text{Lemma 2.22}}{=}T\left({\sum }_{j=1}^n{x}_j{\mathbf{e}}_j\right)=T(\mathbf{x}).$

• The first equality: $A\mathbf{x}$ is the combination of the columns $T({\mathbf{e}}_j)$ with scalars $x_j$.
• The second: preservation of linear combinations, read from right to left.
• The last: every vector is the combination of the unit vectors with its own coordinates, e.g. in ${\mathbb{R}}^3$: $\mathbf{x}=x_1{\mathbf{e}}_1+x_2{\mathbf{e}}_2+x_3{\mathbf{e}}_3$. $■$

3.7 Proof of Lemma 2.32

Check the axioms of Def. 2.19 for $S\circ T$, using only that $S$ and $T$ are linear.

(i)
$(S\circ T)(\mathbf{x}+{\mathbf{x}}^{\prime })=S(T(\mathbf{x}+{\mathbf{x}}^{\prime }))\stackrel{\text{(i) for }T}{=}S(T(\mathbf{x})+T({\mathbf{x}}^{\prime }))\stackrel{\text{(i) for }S}{=}S(T(\mathbf{x}))+S(T({\mathbf{x}}^{\prime }))=(S\circ T)(\mathbf{x})+(S\circ T)({\mathbf{x}}^{\prime }).$

(ii)
$(S\circ T)(\lambda \mathbf{x})=S(T(\lambda \mathbf{x}))\stackrel{\text{(ii) for }T}{=}S(\lambda T(\mathbf{x}))\stackrel{\text{(ii) for }S}{=}\lambda S(T(\mathbf{x}))=\lambda ((S\circ T)(\mathbf{x})).$
The outer brackets around $(S\circ T)(\mathbf{x})$ avoid ambiguity; when in doubt, add brackets. $■$

The proof uses exactly the available properties, no more and no less. The end-of-proof sign is $\square$ or $■$; the old Latin “q.e.d.” (quod erat demonstrandum) is rarely used today.

3.8 Proof of Lemma 2.33

By Theorem 2.23, the matrix $C$ of the linear map $T_A\circ T_B$ exists, is unique, and has columns $(T_A\circ T_B)({\mathbf{e}}_j)$ for $j\in [n]$. Compute them:
$(T_A\circ T_B)({\mathbf{e}}_j)\stackrel{\text{Def. 2.31}}{=}{T}_A(T_B({\mathbf{e}}_j))\stackrel{\text{Def. 2.18}}{=}A(B{\mathbf{e}}_j)=A{\mathbf{x}}_j,$
because $B{\mathbf{e}}_j$ is column $j$ of $B$, which we named ${\mathbf{x}}_j$. So $C=\left[\begin{array}{ccc}A{\mathbf{x}}_1& \cdots & A{\mathbf{x}}_n\end{array}\right]$. $■$

The existence and uniqueness of $C$ come “for free” from Lemma 2.32 + Theorem 2.23; the proof just computes its columns.

3.9 Supplementary proofs: Lemma 2.38, Korollar 2.39, Lemma 2.40(i)

Lemma 2.38. Use Beob. 2.37 and $b_{ij}^{\top }=b_{ji}$. For all $i\in [n]$, $j\in [m]$:
$((AB{)}^{\top }{)}_{ij}=(AB{)}_{ji}={\sum }_{\ell =1}^k{a}_{j\ell }{b}_{\ell i}={\sum }_{\ell =1}^k\underset{(B^{\top }{)}_{i\ell }}{\underbrace{b_{\ell i}}}\underset{(A^{\top }{)}_{\ell j}}{\underbrace{a_{j\ell }}}=(B^{\top }{A}^{\top }{)}_{ij}.$
Real multiplication commutes, so each product can be read in the order $B^{\top }$ then $A^{\top }$. $■$

Korollar 2.39.

• $IA$: its columns are $I{\mathbf{x}}_j={\mathbf{x}}_j$ (Korollar 2.7), so $IA=A$.
• $AI$ (with $A$ of size $n\times m$): its columns are $A{\mathbf{e}}_j$ = column $j$ of $A$, so $AI=A$. $■$

Lemma 2.40(i). Let $B=[{\mathbf{x}}_j]$ and $C=[{\mathbf{y}}_j]$ (columns). Column $j$ of $A(B+C)$ is $A({\mathbf{x}}_j+{\mathbf{y}}_j)=A{\mathbf{x}}_j+A{\mathbf{y}}_j$ (Beob. 2.20). This is column $j$ of $AB+AC$.

For $(A+B)C$, column $j$ is $(A+B){\mathbf{y}}_j$. Write $A=[{\mathbf{a}}_{\ell }]$, $B=[{\mathbf{b}}_{\ell }]$, so $A+B=[{\mathbf{a}}_{\ell }+{\mathbf{b}}_{\ell }]$. Then
$(A+B){\mathbf{y}}_j={\sum }_{\ell }{y}_{\ell j}({\mathbf{a}}_{\ell }+{\mathbf{b}}_{\ell })={\sum }_{\ell }{y}_{\ell j}{\mathbf{a}}_{\ell }+{\sum }_{\ell }{y}_{\ell j}{\mathbf{b}}_{\ell }=A{\mathbf{y}}_j+B{\mathbf{y}}_j.■$

3.10 Proof of associativity, Lemma 2.40(ii)

Proving $(AB)C=A(BC)$ entrywise via ${\sum }_{\ell }$ formulas is a “Index-Schweinerei” (index mess). Instead, use transformations.

Step 1: identify both sides as matrices of compositions. By Korollar 2.35 ($T_A\circ T_B=T_{AB}$), applied twice:

• $(AB)C$ is the matrix of $T_{AB}\circ T_C=(T_A\circ T_B)\circ T_C$.
• $A(BC)$ is the matrix of $T_A\circ T_{BC}=T_A\circ (T_B\circ T_C)$.

Step 2: the two compositions are the same transformation. It looks as if we only moved the problem to associativity of $\circ$, but that one is easy. For every $\mathbf{x}$:
$((T_A\circ T_B)\circ T_C)(\mathbf{x})=(T_A\circ T_B)(T_C(\mathbf{x}))=T_A(T_B(T_C(\mathbf{x}))),$
$(T_A\circ (T_B\circ T_C))(\mathbf{x})=T_A((T_B\circ T_C)(\mathbf{x}))=T_A(T_B(T_C(\mathbf{x}))).$
Whatever the bracketing, the result is “apply $T_C$, then $T_B$, then $T_A$”. Equal outputs for all inputs mean equal functions.

Step 3: conclude. These are the same linear transformation, and by Theorem 2.23 a linear transformation has exactly one matrix. Hence $(AB)C=A(BC)$. $■$

---

4. Worked Examples & Applications

4.1 Proving linearity via a matrix (Example 2)

$T:{\mathbb{R}}^3\to {\mathbb{R}}^2$, $T(\mathbf{x})=\left(\begin{array}{c}{x}_1+2x_2\\ 3x_2+4x_3\end{array}\right)$. (The board first said $3x_1$; it was corrected to $3x_2$.)

Instead of checking the axioms, observe $T=T_A$ with
$A=\left[\begin{array}{ccc}1& 2& 0\\ 0& 3& 4\end{array}\right]:A\mathbf{x}=\left(\begin{array}{c}1\cdot x_1+2\cdot x_2+0\cdot x_3\\ 0\cdot x_1+3\cdot x_2+4\cdot x_3\end{array}\right)=T(\mathbf{x}).$
Each output coordinate is (row of $A$) · $\mathbf{x}$, so row $i$ holds the coefficients of output $i$. The zeros appear because $x_3$ is missing in the first output and $x_1$ in the second; with other formulas there need not be zeros. By Beob. 2.20, $T$ is linear. ✓

Equivalently, via Theorem 2.23: $T({\mathbf{e}}_1)=(1,0{)}^{\top }$, $T({\mathbf{e}}_2)=(2,3{)}^{\top }$, $T({\mathbf{e}}_3)=(0,4{)}^{\top }$ are the columns.

4.2 Simple linear maps (Examples 3, 4)

• Zero map $T(\mathbf{x})=0\in {\mathbb{R}}^m$: linear, $T=T_0$ with the zero matrix.
• Identity map $T(\mathbf{x})=\mathbf{x}$ on ${\mathbb{R}}^m$: linear, $T=T_I$ with the identity (unit) matrix (Einheitsmatrix).

4.3 Disproving linearity (Examples 5, 6)

To refute “for all …” statements, one concrete counterexample suffices. This is much easier than a proof.

Example 5: the 1-norm. $T(\mathbf{x})={\sum }_{i=1}^m|x_i|=\Vert \mathbf{x}{\Vert }_1$ (an alternative length, used in some applications; the usual one is the 2-norm). Compute:
$T(\lambda \mathbf{x})={\sum }_{i=1}^m|\lambda x_i|=|\lambda |{\sum }_{i=1}^m|x_i|=|\lambda |T(\mathbf{x}).$
That is $|\lambda |$, not $\lambda$. For $\mathbf{x}\ne 0$ and $\lambda <0$, the left side $T(\lambda \mathbf{x})>0$, but $\lambda T(\mathbf{x})<0$ (since $T(\mathbf{x})>0$). Concretely, $\mathbf{x}={\mathbf{e}}_1$, $\lambda =-1$ gives $T(-{\mathbf{e}}_1)=1\ne -1$. Axiom (ii) fails, so $T$ is not linear.

Example 6: a constant map. $T(\mathbf{x})=\mathbf{v}$ with a fixed $\mathbf{v}\ne 0$:
$\underset{=\mathbf{v}}{\underbrace{T(\mathbf{x}+{\mathbf{x}}^{\prime })}}\ne \underset{\mathbf{v}}{\underbrace{T(\mathbf{x})}}+\underset{\mathbf{v}}{\underbrace{T({\mathbf{x}}^{\prime })}}=2\mathbf{v},$
since $\mathbf{v}\ne 2\mathbf{v}$ for $\mathbf{v}\ne 0$. Axiom (i) fails (as does (ii)). Faster: $T(0)=\mathbf{v}\ne 0$ violates Lemma 2.21.

Exam Trap

To show “linear”, verify the axioms for all inputs, or exhibit a matrix. To show “not linear”, give specific numbers. A map whose graph looks “straight” is not necessarily linear: $T(x)=x+1$ fails because $T(0)=1$.

4.4 Clicker on linear functionals $T:{\mathbb{R}}^2\to \mathbb{R}$

1. “If $T(\mathbf{x})>0$ for some $\mathbf{x}$, then $T({\mathbf{x}}^{\prime })<0$ for some ${\mathbf{x}}^{\prime }$.” True. Take ${\mathbf{x}}^{\prime }=-\mathbf{x}=(-1)\mathbf{x}$; then $T(-\mathbf{x})\stackrel{\text{(ii)}}{=}(-1)T(\mathbf{x})<0$. Arbitrary functions don’t behave like this (e.g. $x\mapsto x^2$), but linear ones do: $T(-\mathbf{x})=-T(\mathbf{x})$.
2. “If $T(\mathbf{x})\ne 0$ for some $\mathbf{x}$, then for every $\mathbf{x}\ne 0$.” False. Counterexample $T(\mathbf{x})=x_1$ (linear: the covector $(10)$). Then $T({\mathbf{e}}_2)=0$ but $T({\mathbf{e}}_1)=1$.
3. ”$T(\mathbf{x}+{\mathbf{x}}^{\prime }+{\mathbf{x}}^{\prime \prime })=T(\mathbf{x})+T({\mathbf{x}}^{\prime })+T({\mathbf{x}}^{\prime \prime })$.” True:
   $T((\mathbf{x}+{\mathbf{x}}^{\prime })+{\mathbf{x}}^{\prime \prime })\stackrel{\text{(i)}}{=}T(\mathbf{x}+{\mathbf{x}}^{\prime })+T({\mathbf{x}}^{\prime \prime })\stackrel{\text{(i)}}{=}T(\mathbf{x})+T({\mathbf{x}}^{\prime })+T({\mathbf{x}}^{\prime \prime }).$

(The clicker had a bold $0$ where a thin $0$ belonged; the outputs of functionals are numbers.)

4.5 Composition is not commutative (stretch and mirror)

$B=\left[\begin{array}{cc}1& 0\\ 0& \frac{3}{4}\end{array}\right]$ compresses in the $y$-direction; $A=\left[\begin{array}{cc}0& 1\\ 1& 0\end{array}\right]$ mirrors at the diagonal.

“Stretching, then mirroring” is $T_A\circ T_B=T_{AB}$ (first $B$!). Column view:

• $A\cdot (1,0{)}^{\top }=(0,1{)}^{\top }$
• $A\cdot (0,\frac{3}{4}{)}^{\top }=(\frac{3}{4},0{)}^{\top }$

$AB=\left[\begin{array}{cc}0& \frac{3}{4}\\ 1& 0\end{array}\right].$

“Mirroring, then stretching” is $T_B\circ T_A=T_{BA}$:

• $B\cdot (0,1{)}^{\top }=(0,\frac{3}{4}{)}^{\top }$
• $B\cdot (1,0{)}^{\top }=(1,0{)}^{\top }$

$BA=\left[\begin{array}{cc}0& 1\\ \frac{3}{4}& 0\end{array}\right]\ne AB.$

Geometric check of $AB$: ${\mathbf{e}}_1$ is unchanged by the compression, then mirrored to ${\mathbf{e}}_2$, so column 1 is $(0,1{)}^{\top }$. The L-shapes produced in the two orders look similar but are different.

Exam Trap: order

$(S\circ T)(\mathbf{x})=S(T(\mathbf{x}))$ applies $T$ first. Likewise $AB\mathbf{x}=A(B\mathbf{x})$ applies $B$ first: read right to left.

4.6 Rows times columns

$\left[\begin{array}{cc}2& 3\\ 3& -1\end{array}\right]\left[\begin{array}{ccc}-3& 1& 3\\ 2& -1& 0\end{array}\right]=\left[\begin{array}{ccc}0& -1& 6\\ -11& 4& 9\end{array}\right].$
The product of a $2\times 2$ and a $2\times 3$ matrix is $2\times 3$: six scalar products.

entry	row · column	value
$(1,1)$	$2\cdot (-3)+3\cdot 2$	$0$
$(1,2)$	$2\cdot 1+3\cdot (-1)$	$-1$
$(1,3)$	$2\cdot 3+3\cdot 0$	$6$
$(2,1)$	$3\cdot (-3)+(-1)\cdot 2$	$-11$
$(2,2)$	$3\cdot 1+(-1)\cdot (-1)$	$4$
$(2,3)$	$3\cdot 3+(-1)\cdot 0$	$9$

Column check (Def. 2.34): column 2 of the product is $A(1,-1{)}^{\top }=1\cdot (2,3{)}^{\top }-1\cdot (3,-1{)}^{\top }=(-1,4{)}^{\top }$ ✓.

Here $BA$ is not defined: a $2\times 3$ times a $2\times 2$ matrix doesn’t fit.

Exam Traps (collection)

• $AB$ needs #columns of $A$ = rows of $B$. The result is (#rows of $A$) × (#columns of $B$).
• $AB$ and $BA$ may differ, have different sizes, or one may be undefined.
• $(AB{)}^{\top }=B^{\top }{A}^{\top }$, not $A^{\top }{B}^{\top }$.
• The matrix of a linear map has the images $T({\mathbf{e}}_j)$ as columns, not rows.
• $IA=A$ needs $I$ of size (#rows of $A$); $AI=A$ needs $I$ of size (#columns of $A$).
• For a linear functional, $T(0)=0$ (number), not $0$.
• Lemma 2.22 is stated with $\ell$ vectors ${\mathbf{x}}_1,\dots ,{\mathbf{x}}_{\ell }$ (board typo: $n$).

---

5. Intuition & Conceptual Bridges

What linearity means geometrically

A linear map keeps the origin fixed (Lemma 2.21) and preserves every linear relation (Lemma 2.22). Parallelograms map to parallelograms (possibly flattened) and a scaled arrow maps to the equally scaled image. Since every $\mathbf{x}$ is ${\sum }_j{x}_j{\mathbf{e}}_j$, knowing where the $n$ unit vectors go determines everything. That is Theorem 2.23, and it’s why the pictures always show $A{\mathbf{e}}_1,A{\mathbf{e}}_2$.

Matrix = recipe for a linear map; product = doing two maps in a row

• Column $j$ of $A$ answers “where does ${\mathbf{e}}_j$ go?”.
• $AB$ answers “where does ${\mathbf{e}}_j$ go if I apply $B$, then $A$?”: first $B$ sends ${\mathbf{e}}_j$ to ${\mathbf{x}}_j$, then $A$ sends it to $A{\mathbf{x}}_j$. That is Def. 2.34 in one sentence.
• From this viewpoint, associativity is obvious (it’s just “apply $C$, $B$, $A$ in this order”), and non-commutativity is natural (order of operations matters).
• The rows-times-columns rule is the efficient way to compute $AB$; the transformation view explains why.

Why the transpose reverses order

Only $B^{\top }{A}^{\top }$ has matching inner dimensions, so it’s the only candidate that even makes sense. The same reversal appears when undoing actions: to undo “socks, then shoes” you remove the shoes first.

Bridges:

• Week 2: $T_A$, $A{\mathbf{e}}_j$ = column $j$, the pictures $A(X)$ (stretching, mirroring, rotation, shear), and $A\mathbf{x}$ in three views. Matrix multiplication repeats those three views, with a whole matrix $B$ instead of one vector $\mathbf{x}$.
• Week 1: covectors are officially linear functionals. ${\mathbf{v}}^{\top }\mathbf{x}$ is the special case of a $1\times m$ “matrix” times a vector.
• Computer graphics: drawing a 3D cube on paper is a matrix transformation ${\mathbb{R}}^3\to {\mathbb{R}}^2$ (see the margin picture in the script). Chaining transformations is matrix multiplication.
• Next: multiplying covectors (linear functionals) with matrices. Expressions like $B^{\top }{\mathbf{u}}_i$ will be introduced properly.
• Chapter 4: matrices become vectors of an abstract vector space, and linear transformations are generalized to such spaces (e.g. maps that act on matrices).
• Induction returns whenever a statement depends on a natural-number parameter (e.g. generalized associativity, products of $k$ matrices).

---

6. Summary & Self-Assessment Questions

Cheat sheet

Concept	Statement
Linear (Def. 2.19)	(i) $T(\mathbf{x}+{\mathbf{x}}^{\prime })=T(\mathbf{x})+T({\mathbf{x}}^{\prime })$, (ii) $T(\lambda \mathbf{x})=\lambda T(\mathbf{x})$; functional if the target is $\mathbb{R}$
Beob. 2.20	every $T_A$ is linear
Lemma 2.21	$T(0)=0$ (or $0$)
Lemma 2.22	$T({\sum }_j{\lambda }_j{\mathbf{x}}_j)={\sum }_j{\lambda }_{j}T({\mathbf{x}}_j)$
Theorem 2.23	linear $T=T_A$ for exactly one $A=[T({\mathbf{e}}_1)\cdots T({\mathbf{e}}_n)]$
Unit vector trick	$A{\mathbf{e}}_j$ = column $j$ of $A$
Induction	base case + ($P(\ell -1)\Rightarrow P(\ell )$) gives $P(\ell )$ for all $\ell$
Composition (Def. 2.31)	$(S\circ T)(\mathbf{x})=S(T(\mathbf{x}))$, $T$ first; inner dimension $k$ must match
Lemma 2.32	composition of linear maps is linear
Product (Def. 2.34)	$AB=[A{\mathbf{x}}_1\cdots A{\mathbf{x}}_n]$ for $B=[{\mathbf{x}}_1\cdots {\mathbf{x}}_n]$
Kor. 2.35	$T_A\circ T_B=T_{AB}$; $A(B\mathbf{x})=(AB)\mathbf{x}$
Beob. 2.36	$(AB{)}_{ij}={\mathbf{u}}_i^{\top }{\mathbf{x}}_j$ (row $i$ of $A$ · column $j$ of $B$)
Beob. 2.37	$(AB{)}_{ij}={\sum }_{\ell =1}^k{a}_{i\ell }{b}_{\ell j}$
Sizes	$(m\times k)(k\times n)=m\times n$
Lemma 2.38	$(AB{)}^{\top }=B^{\top }{A}^{\top }$; $(ABC{)}^{\top }=C^{\top }{B}^{\top }{A}^{\top }$
Kor. 2.39	$IA=A=AI$ (with matching sizes of $I$)
Lemma 2.40	$A(B+C)=AB+AC$, $(A+B)C=AC+BC$, $(AB)C=A(BC)$
Warning	$AB\ne BA$ in general

Practice questions

Question 1. Let $A=\left[\begin{array}{ccc}1& 0& 2\\ 0& 1& -1\end{array}\right]$ and $B=\left[\begin{array}{cc}1& 1\\ 0& 2\\ 3& 0\end{array}\right]$. Compute $AB$ and $BA$ (check sizes first). Verify one column of each with the column view.

Solution to Question 1

Sizes: $A$ is $2\times 3$ and $B$ is $3\times 2$.

• $AB$: inner dimensions $3=3$ ✓, result $2\times 2$.
• $BA$: inner dimensions $2=2$ ✓, result $3\times 3$.

So $AB\ne BA$ already because the sizes differ.

$AB$ (rows of $A$ · columns of $B$):

• $(1,1)$: $1\cdot 1+0\cdot 0+2\cdot 3=7$
• $(1,2)$: $1\cdot 1+0\cdot 2+2\cdot 0=1$
• $(2,1)$: $0\cdot 1+1\cdot 0+(-1)\cdot 3=-3$
• $(2,2)$: $0\cdot 1+1\cdot 2+(-1)\cdot 0=2$

$AB=\left[\begin{array}{cc}7& 1\\ -3& 2\end{array}\right].$
Column check: $A(1,0,3{)}^{\top }=1\cdot (1,0{)}^{\top }+0\cdot (0,1{)}^{\top }+3\cdot (2,-1{)}^{\top }=(7,-3{)}^{\top }$ ✓.

$BA$:

• row 1 of $B$ is $(1,1)$: against the columns $(1,0{)}^{\top },(0,1{)}^{\top },(2,-1{)}^{\top }$ of $A$ it gives $1,1,1$
• row 2 is $(0,2)$: gives $0,2,-2$
• row 3 is $(3,0)$: gives $3,0,6$

$BA=\left[\begin{array}{ccc}1& 1& 1\\ 0& 2& -2\\ 3& 0& 6\end{array}\right].$
Column check: column 3 is $B(2,-1{)}^{\top }=2\cdot (1,0,3{)}^{\top }-1\cdot (1,2,0{)}^{\top }=(1,-2,6{)}^{\top }$ ✓.

Question 2. Decide which maps are linear. Justify with a matrix or a concrete counterexample.
(a) $T:{\mathbb{R}}^2\to {\mathbb{R}}^3$, $T(\mathbf{x})=(x_1-x_2,2x_1,0{)}^{\top }$
(b) $T:{\mathbb{R}}^2\to \mathbb{R}$, $T(\mathbf{x})=x_1{x}_2$
(c) $T:{\mathbb{R}}^2\to \mathbb{R}$, $T(\mathbf{x})=x_1+1$
(d) $T:{\mathbb{R}}^2\to \mathbb{R}$, $T(\mathbf{x})=\Vert \mathbf{x}\Vert$ (Euclidean norm)

Solution to Question 2

(a) Linear. $T=T_A$ with $A=\left[\begin{array}{cc}1& -1\\ 2& 0\\ 0& 0\end{array}\right]$; row $i$ holds the coefficients of output $i$. Check: the columns are $T({\mathbf{e}}_1)=(1,2,0{)}^{\top }$ and $T({\mathbf{e}}_2)=(-1,0,0{)}^{\top }$. Linear by Beob. 2.20.

(b) Not linear. Take $\mathbf{x}=(1,1{)}^{\top }$, $\lambda =2$: $T(2\mathbf{x})=2\cdot 2=4$, but $\lambda T(\mathbf{x})=2\cdot 1=2$. Axiom (ii) fails.

(c) Not linear. $T(0)=1\ne 0$, contradicting Lemma 2.21. Its graph is a “straight” (affine) function, but not a linear one.

(d) Not linear. Take $\mathbf{x}={\mathbf{e}}_1$, $\lambda =-1$: $T(-{\mathbf{e}}_1)=1$, but $-T({\mathbf{e}}_1)=-1$. Axiom (ii) fails. It also contradicts clicker fact 1: a nonzero linear functional must take negative values somewhere, but norms never do.

Question 3. Let $R$ be the rotation of ${\mathbb{R}}^2$ by $90°$ counterclockwise and $F$ the reflection at the $x$-axis. Find their matrices with Theorem 2.23. Compute the matrices of $R\circ F$ and $F\circ R$ and interpret them geometrically.

Solution to Question 3

Matrices from the images of ${\mathbf{e}}_1,{\mathbf{e}}_2$:

• $R$: ${\mathbf{e}}_1\mapsto (0,1{)}^{\top }$ and ${\mathbf{e}}_2\mapsto (-1,0{)}^{\top }$, so $R=\left[\begin{array}{cc}0& -1\\ 1& 0\end{array}\right]$.
• $F$: ${\mathbf{e}}_1\mapsto {\mathbf{e}}_1$ and ${\mathbf{e}}_2\mapsto -{\mathbf{e}}_2$, so $F=\left[\begin{array}{cc}1& 0\\ 0& -1\end{array}\right]$.

$R\circ F$ (first $F$, then $R$) has matrix $RF$ (Korollar 2.35):
$RF=\left[\begin{array}{cc}0& -1\\ 1& 0\end{array}\right]\left[\begin{array}{cc}1& 0\\ 0& -1\end{array}\right]=\left[\begin{array}{cc}0& 1\\ 1& 0\end{array}\right].$
Check via unit vectors: ${\mathbf{e}}_1\stackrel{F}{\mapsto }{\mathbf{e}}_1\stackrel{R}{\mapsto }(0,1{)}^{\top }$ and ${\mathbf{e}}_2\stackrel{F}{\mapsto }-{\mathbf{e}}_2\stackrel{R}{\mapsto }(1,0{)}^{\top }$ ✓. This is the reflection at the diagonal $y=x$.

$F\circ R$ has matrix
$FR=\left[\begin{array}{cc}1& 0\\ 0& -1\end{array}\right]\left[\begin{array}{cc}0& -1\\ 1& 0\end{array}\right]=\left[\begin{array}{cc}0& -1\\ -1& 0\end{array}\right].$
Check: ${\mathbf{e}}_1\mapsto (0,1{)}^{\top }\mapsto (0,-1{)}^{\top }$ and ${\mathbf{e}}_2\mapsto (-1,0{)}^{\top }\mapsto (-1,0{)}^{\top }$ ✓. This is the reflection at the line $y=-x$.

$RF\ne FR$: another example of non-commutativity.

Question 4. A linear map $T:{\mathbb{R}}^2\to {\mathbb{R}}^2$ satisfies $T(1,1)=(3,1)$ and $T(1,-1)=(1,-1)$. Show that $T$ is uniquely determined, and find its matrix.

Solution to Question 4

By Theorem 2.23 we only need $T({\mathbf{e}}_1)$ and $T({\mathbf{e}}_2)$. Express the unit vectors through the given inputs:
${\mathbf{e}}_1=\frac{1}{2}[(1,1{)}^{\top }+(1,-1{)}^{\top }],{\mathbf{e}}_2=\frac{1}{2}[(1,1{)}^{\top }-(1,-1{)}^{\top }].$
By preservation of linear combinations (Lemma 2.22):
$T({\mathbf{e}}_1)=\frac{1}{2}[(3,1{)}^{\top }+(1,-1{)}^{\top }]=(2,0{)}^{\top },T({\mathbf{e}}_2)=\frac{1}{2}[(3,1{)}^{\top }-(1,-1{)}^{\top }]=(1,1{)}^{\top }.$
These values are forced by linearity, so there is only one possible $T$:
$A=\left[\begin{array}{cc}2& 1\\ 0& 1\end{array}\right].$
Check: $A(1,1{)}^{\top }=(3,1{)}^{\top }$ ✓ and $A(1,-1{)}^{\top }=(1,-1{)}^{\top }$ ✓.

Idea: knowing a linear map on any inputs whose combinations give ${\mathbf{e}}_1,\dots ,{\mathbf{e}}_n$ determines it completely.

Question 5. Prove by induction: for all $k\ge 1$ and matrices $A_1,\dots ,A_k$ whose sizes allow the product,
$(A_1{A}_2\cdots A_k{)}^{\top }=A_k^{\top }\cdots A_2^{\top }{A}_1^{\top }.$
Which earlier results do you need?

Solution to Question 5

Let $P(k)$ be the claim for $k$ factors. Brackets may be omitted by generalized associativity (Lemma 2.40(ii)).

Base case $k=1$: $(A_1{)}^{\top }=A_1^{\top }$ ✓. (Induction may start at any base value; here $k=1$ is natural, since an empty product of matrices is not defined in the lecture.)

Induction step ($k\ge 2$): assume $P(k-1)$. Group the product as $(A_1\cdots A_{k-1})A_k$ (associativity). Then
$(A_1\cdots A_{k-1}{A}_k{)}^{\top }\stackrel{\text{Lemma 2.38}}{=}{A}_k^{\top }(A_1\cdots A_{k-1}{)}^{\top }\stackrel{P(k-1)}{=}{A}_k^{\top }{A}_{k-1}^{\top }\cdots A_1^{\top }.$
In the first step, Lemma 2.38 is applied with $A:=A_1\cdots A_{k-1}$ and $B:=A_k$. In the second, the induction hypothesis is applied to the $k-1$ factors.

So $P(k-1)\Rightarrow P(k)$, and by induction $P(k)$ holds for all $k\ge 1$. $■$

Used: Lemma 2.38 (two factors) and associativity, to regroup and drop brackets. For $k=3$ this gives $(ABC{)}^{\top }=C^{\top }{B}^{\top }{A}^{\top }$ from the lecture.