Week 4 Mixed Products, Inverse Matrices & Gauss Elimination

Sources and coverage

• Lecture A (Monday): CS Lens on Fibonacci numbers and iterated squaring; special cases of matrix multiplication (covectors, outer product); mixed products and the cost of different evaluation orders. The recording stops at the break (the transcript turns into noise during the clicker on multiplying three matrices), so the second half of Monday is missing. The clicker topic is reconstructed in §4.3 with a standard example; the numbers used in the lecture could not be recovered.
• Lecture B (Wednesday): invertible functions, the inverse of a linear transformation, when a matrix transformation is invertible, invertible/singular matrices, the inverse matrix, the $1\times 1$ and $2\times 2$ formulas, and the rules for inverting products and transposes.
• Handouts “Gauss Elimination, Worked Example” (nice, ugly, failure, B. Gärtner): a preview of Chapter 3, which according to the lecturer starts on Friday. They are worked through completely in §4.5–4.7.
• Script numbers were taken from the audio. Numbers marked (no. inferred) were unclear in the recording and should be checked against the official script.

Discrepancies and corrections

• Lemma 2.50 was named for both cases (“wide matrix → not invertible” and “tall matrix → not invertible”). In the script these are most likely two separate statements (2.50 / 2.51). Check the script.
• On the rule $(AB{)}^{-1}=B^{-1}{A}^{-1}$ the lecturer first said “first undo $B$, then $A$” and corrected himself straight away: $AB$ means first $B$, then $A$, so the inverse first undoes $A$, then $B$.
• On the question “does $ad=bc$ imply the columns are dependent?” he briefly said “independent” and corrected it: if $ad=bc$, the columns are linearly dependent.
• The CS Lens material (Fibonacci) is explicitly not exam-relevant. It is background only.

---

1. Executive Overview & Core Objectives

This week has two halves.

Monday: every product of a matrix with a vector, covector or scalar can be computed with the rules of matrix multiplication, but the objects involved are mathematically different, and the order of evaluation decides how expensive the computation is.

Wednesday: the result is the same no matter which bracketing you choose (associativity), which leads to the central question of the week: when can a matrix transformation be undone? The answer: exactly when $A$ is square and has linearly independent columns. Equivalently, there is a matrix $B$ with $BA=I$. This $B$ is unique and is called the inverse matrix $A^{-1}$.

The Gauss handouts show the algorithm (Chapter 3) for solving $Ax=b$ systematically, and when it fails.

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

• Classify the special cases of matrix multiplication by the type of their result: matrix·vector, covector·matrix, scalar product, outer product, scalar multiples.
• Evaluate mixed products such as $x^{\top }{A}^{\top }Ax$ correctly, recognise them (e.g. $=\Vert Ax{\Vert }^2$), and choose an efficient evaluation order.
• Define invertible (bijective) functions and give the two ways a function can fail to be invertible.
• Prove: the inverse of an invertible linear transformation is linear (Lemma 2.48).
• State and prove the three equivalent characterisations of invertible matrix transformations (Lemma 2.52).
• Define invertible / singular / $A^{-1}$, prove that the inverse is unique, and use $BA=I⟺AB=I$.
• Invert $1\times 1$ and $2\times 2$ matrices and verify the result.
• Use $(AB{)}^{-1}=B^{-1}{A}^{-1}$ and $(A^{\top }{)}^{-1}=(A^{-1}{)}^{\top }$.
• Carry out Gauss elimination with elimination matrices $E_{ij}$, permutation matrices $P_{ij}$ and back substitution, and recognise the failure case.

---

2. Core Concepts & Formal Definitions

2.1 Special cases of matrix multiplication (Monday)

Recall that the product of an $m\times n$ matrix $A$ and an $n\times p$ matrix $B$ is the $m\times p$ matrix whose entry $(i,j)$ is the scalar product of row $i$ of $A$ and column $j$ of $B$. Column $j$ of $AB$ is $A$ times column $j$ of $B$.

If one of the two factors is flat (only one row or one column), the product is numerically identical to an operation we already know. The objects involved are still different:

Product	Dimensions as matrices	Result type	Meaning
matrix · vector $Ax$	$(m\times n)(n\times 1)$	vector in ${\mathbb{R}}^m$	applying a matrix transformation
covector · matrix $u^{\top }A$	$(1\times m)(m\times n)$	covector	”transformation of covectors”
covector · vector $v^{\top }w$	$(1\times n)(n\times 1)$	scalar	scalar product $v\cdot w$
vector · covector $v{w}^{\top }$	$(m\times 1)(1\times n)$	$m\times n$ matrix	outer product (äußeres Produkt)
matrix · $1\times 1$	$(m\times 1)(1\times 1)$	vector	scalar multiple, scalar written on the right
$1\times 1$ · covector	$(1\times 1)(1\times n)$	covector	scaling a covector
$1\times 1$ · $1\times 1$	$(1\times 1)(1\times 1)$	scalar	ordinary real multiplication

Covector (Kovektor) and outer product

A covector is a row vector $u^{\top }\in {\mathbb{R}}^{n\ast }$ ("$1\times n$"). It can be multiplied with a matrix from the left if it has as many entries as the matrix has rows:
$u^{\top }A\in {\mathbb{R}}^{n\ast }\text{for }u\in {\mathbb{R}}^m,A\in {\mathbb{R}}^{m\times n}.$
The outer product of $v\in {\mathbb{R}}^m$ and $w\in {\mathbb{R}}^n$ is the $m\times n$ matrix
$v{w}^{\top }=\left[\begin{array}{ccc}{v}_1{w}_1& \cdots & v_1{w}_n\\ ⋮& & ⋮\\ v_m{w}_1& \cdots & v_m{w}_n\end{array}\right].$
Compare: covector · vector $=$ number, while vector · covector $=$ matrix.

Intuition: same arithmetic, different objects

Matrix·vector and matrix·($m\times 1$ matrix) produce the same numbers, but the first is applying a transformation to a vector, while the second is a composition of two transformations. The lecturer deliberately keeps vectors and matrices apart (different brackets). Gilbert Strang, for example, treats vectors as $n\times 1$ matrices; the lecturer’s view is “that is bad”. For computing, though, you may treat every object as a matrix.

Exam Trap: scalar multiplication is not a special case of matrix multiplication

$\lambda A$ for an arbitrary matrix $A$ cannot be written as a matrix product with a $1\times 1$ matrix: the dimensions only match when $A$ has a single row or column. Scalar multiplication is a separate operation (Def. 2.2). Writing the scalar on the right ($v\cdot 2$) is not officially defined, but it is accepted (“to break the rules, you first have to master them”).

2.2 Mixed products (gemischte Produkte)

A mixed product contains matrices, vectors, covectors and scalars together, e.g. $x^{\top }{A}^{\top }Ax$. You evaluate it by treating every factor as a matrix:

• vectors in ${\mathbb{R}}^m$ as $m\times 1$ matrices;
• covectors in ${\mathbb{R}}^{n\ast }$ as $1\times n$ matrices;
• scalars as $1\times 1$ matrices.

Then you only need to adjust the brackets of the result to its type. Two rules from last week carry over:

Lemma 2.40 (generalised associativity)

The value of a product of matrices does not depend on how it is bracketed.

Lemma 2.38 (transpose of a product)

$(AB{)}^{\top }=B^{\top }{A}^{\top }$
(transpose the factors, reverse the order).

Exam Trap: same value, different cost

All bracketings give the same result, but the computational effort can differ by orders of magnitude. Rule of thumb: never form a large intermediate matrix (e.g. $A^{\top }A$ or an outer product $w{v}^{\top }$) if you can work with vectors instead.

2.3 Invertible functions (Wednesday)

Definition (invertible / bijective function)

Let $X,Y$ be sets and $T:X\to Y$ a function. $T$ is called invertible (umkehrbar), or bijective (bijektiv), if
$\forall y\in Y\exists !x\in X:T(x)=y,$
i.e. each possible output comes from exactly one input. In that case $T$ is the forward transformation (Vorwärtstransformation) and
$T^{-1}:Y\to X,T^{-1}(y):=\text{the unique }x\text{ with }T(x)=y$
is the inverse (Inverse / Umkehrfunktion), i.e. the backward transformation (Rückwärtstransformation).

A function can fail to be invertible in two ways:

1. There is a $y$ with no $x$ such that $T(x)=y$ (not surjective).
2. There is a $y$ with more than one $x$ such that $T(x)=y$ (not injective).

The course does not need “surjective” or “injective”; it only talks about invertible functions.

Non-examples

• $f(x)=x^2$ on $\mathbb{R}$: $25$ has the two preimages $5$ and $-5$ (failure of type 2).
• The “least invertible linear function” $T:{\mathbb{R}}^n\to {\mathbb{R}}^m$, $T(x)=0$ (the zero matrix): every $y\ne 0$ has no preimage (type 1); $y=0$ has all $x$ as preimages when $n>0$ (type 2).

Fact 2.47 (inverses cancel) (no. inferred: "2.47")

If $T:X\to Y$ is invertible, then $T^{-1}$ is invertible with $(T^{-1}{)}^{-1}=T$, and
$T^{-1}(T(x))=x\forall x\in X,T(T^{-1}(y))=y\forall y\in Y.$

Practical meaning: in an expression $T(T^{-1}(y))$ you may “cancel” $T$ and $T^{-1}$, just as multiplying and then dividing by the same number cancels.

2.4 Invertible linear and matrix transformations

Lemma 2.48 (the inverse of a linear transformation is linear)

Let $T:{\mathbb{R}}^n\to {\mathbb{R}}^m$ be an invertible linear transformation. Then $T^{-1}:{\mathbb{R}}^m\to {\mathbb{R}}^n$ is also a linear transformation.

This is not automatic: an inverse function does not in general inherit the properties of the original. For linearity it does hold (proof in §3.1).

Corollary 2.49

If the matrix transformation $T_A:{\mathbb{R}}^n\to {\mathbb{R}}^m$ is invertible, then $T_A^{-1}:{\mathbb{R}}^m\to {\mathbb{R}}^n$ is also a matrix transformation.

Lemma 2.50 (only square matrices can be invertible)

Let $A$ be an $m\times n$ matrix.

• If $m<n$ (wide matrix), then $T_A$ is not invertible.
• If $m>n$ (tall matrix), then $T_A$ is not invertible either. (Probably Lemma 2.51 in the script.)

Intuition (not a rigorous proof)

• Wide: there are “more inputs than outputs”, so two inputs will probably land on the same output (failure of type 2).
• Tall: there are “more outputs than inputs”, so some output will probably have no input (failure of type 1).

Caution: this argument is valid only for linear transformations. There are non-linear bijections ${\mathbb{R}}^2\to \mathbb{R}$, so “size of the spaces” alone proves nothing. The rigorous argument is in the script around Lemma 2.50.

So only $m=n$ remains, and even then not every matrix works (the zero matrix fails).

Q&A: the empty $0\times 0$ matrix is invertible. ${\mathbb{R}}^0$ contains exactly one element, so the only map ${\mathbb{R}}^0\to {\mathbb{R}}^0$ is the identity, which is invertible.

Lemma 2.52 (characterising invertible matrix transformations) (no. inferred)

Let $A$ be an $m\times m$ matrix. The following three statements are equivalent:

1. $T_A:{\mathbb{R}}^m\to {\mathbb{R}}^m$ is invertible.
2. There is an $m\times m$ matrix $B$ with $BA=I$.
3. The columns of $A$ are linearly independent.

Statement 3 is the practical test: check whether the columns are linearly independent. An equivalent formulation (from a question during the break): the null space (Nullraum) of $A$ contains only $0$.

Lemma 2.53

Let $A,B$ be $m\times m$ matrices with $BA=I$. Then also $AB=I$.

This is remarkable, because matrix multiplication is not commutative in general ($AB\ne BA$). It holds here because the transformations undo each other in either order; a student found this argument himself. The proof is in the script.

2.5 Invertible matrices and the inverse (§2.4.2)

Definition 2.54 (invertible / singular) (no. inferred)

Let $A$ be an $m\times m$ matrix. $A$ is invertible (invertierbar) if there is an $m\times m$ matrix $B$ with
$BA=I.$
Otherwise $A$ is called singular (singulär).

• By Lemma 2.52, “invertible” is equivalent to “the columns are linearly independent”. Keep both interpretations in mind.
• “Singular” is used only for square matrices. Wide and tall matrices are never invertible, so they are not called singular.

Observation 2.55 (equivalent conditions, uniqueness) (no. inferred)

For $m\times m$ matrices the following are equivalent:
$BA=I⟺AB=I⟺(AB=I\wedge BA=I).$
All three versions appear as definitions in the literature. The third has the advantage that it does not presuppose Lemma 2.53. If such a $B$ exists, it is unique.

Definition 2.56 (inverse matrix)

Let $A$ be an $m\times m$ matrix. $A$ is invertible iff there is an $m\times m$ matrix $B$ with $BA=I$ (equivalently $AB=I$, equivalently $AB=BA=I$). This $B$ is unique; it is called the inverse (Inverse) of $A$ and written
$A^{-1}.$
Moreover, $A^{-1}$ is itself invertible and $(A^{-1}{)}^{-1}=A$.

Inverses of small matrices

$1\times 1$:
${\left[\begin{array}{c}a\end{array}\right]}^{-1}=\left[\begin{array}{c}\frac{1}{a}\end{array}\right]\text{if }a\ne 0.$
Matrix inversion generalises taking reciprocals of real numbers, including the restriction “not $0$”.

$2\times 2$:
${\left[\begin{array}{cc}a& b\\ c& d\end{array}\right]}^{-1}=\frac{1}{ad-bc}\left[\begin{array}{cc}d& -b\\ -c& a\end{array}\right]\text{if }ad\ne bc.$
If $ad=bc$, the matrix is singular: its columns are linearly dependent (proof in §3.5).

The scalar factor $\frac{1}{ad-bc}$ multiplies every entry (scalar multiplication); it is just written compactly in front. Where the formula comes from is covered in the second part of the course (determinants). For larger $m$ there is still a closed formula (Cramer’s rule, Cramersche Regel), but it grows quickly and is inefficient. Chapter 3 gives an efficient algorithm (Gauss).

Lemma 2.58 (inverse of a product) (no. inferred)

If $A$ and $B$ are invertible $m\times m$ matrices, then $AB$ is invertible and
$(AB{)}^{-1}=B^{-1}{A}^{-1}.$
More generally $(ABC{)}^{-1}=C^{-1}{B}^{-1}{A}^{-1}$.

Lemma 2.59 (inverse and transpose)

If $A$ is invertible, then $A^{\top }$ is invertible and
$(A^{\top }{)}^{-1}=(A^{-1}{)}^{\top }.$

Intuition: socks and shoes

$AB$ means first $B$, then $A$ (as transformations, $x\mapsto A(Bx)$). To undo it you first undo the step done last, $A$, and then $B$. You put on socks and then shoes in the morning, and take off shoes and then socks in the evening.

---

3. Step-by-Step Derivations & Mathematical Proofs

3.1 Proof of Lemma 2.48 ($T^{-1}$ is linear)

A linear transformation is defined axiomatically by two properties:

1. $T(x+x^{\prime })=T(x)+T(x^{\prime })$;
2. $T(\lambda x)=\lambda T(x)$.

We check both for $T^{-1}$.

Idea. We have to use the linearity of $T$ somewhere, so we have to bring $T$ into play. The trick is to write $y=T(T^{-1}(y))$ (Fact 2.47) and then apply $T^{-1}$ at the end; the $T^{-1}T$ pairs cancel.

Axiom 1. To show: $T^{-1}(y+y^{\prime })=T^{-1}(y)+T^{-1}(y^{\prime })$ for all $y,y^{\prime }\in {\mathbb{R}}^m$.

Name $x:=T^{-1}(y)$ and $x^{\prime }:=T^{-1}(y^{\prime })$. By linearity of $T$ (axiom 1 for $T$):
$T(\underset{x}{\underbrace{T^{-1}(y)}}+\underset{x^{\prime }}{\underbrace{T^{-1}(y^{\prime })}})=T(T^{-1}(y))+T(T^{-1}(y^{\prime }))=y+y^{\prime }.$
The last step is Fact 2.47: $T\circ T^{-1}$ “does nothing”. Now apply $T^{-1}$ to both sides. A function gives equal outputs for equal inputs, so this is allowed:
$\underset{=T^{-1}(y)+T^{-1}(y^{\prime })\text{(Fact 2.47)}}{\underbrace{T^{-1}\left(T\right(T^{-1}(y)+T^{-1}(y^{\prime })\left)\right)}}=T^{-1}(y+y^{\prime }).$
That is exactly the claim, read backwards. ✓

Axiom 2. To show: $T^{-1}(\lambda y)=\lambda T^{-1}(y)$.

With $x:=T^{-1}(y)$, axiom 2 for $T$ gives
$T(\lambda T^{-1}(y))=\lambda T(T^{-1}(y))=\lambda y.$
Applying $T^{-1}$ to both sides, the $T^{-1}T$ on the left cancels:
$\lambda T^{-1}(y)=T^{-1}(\lambda y).✓■$

3.2 Proof of Corollary 2.49

Three known results combine into a new one:

1. $T_A$ is a linear transformation, because every matrix transformation is linear (Observation 2.20).
2. $T_A^{-1}$ is linear by Lemma 2.48.
3. Every linear transformation is a matrix transformation (Theorem 2.23). Hence $T_A^{-1}=T_B$ for some matrix $B$. $■$

An aside from the lecture

This is a typical proof pattern: the power lies in the known results, and the proof only combines them. According to the lecturer, AI systems that recently solved hundreds of open mathematical problems often work exactly this way. Their advantage is finding which known results fit together.

3.3 Proof of Lemma 2.52 (circular chain $1\Rightarrow 2\Rightarrow 3\Rightarrow 1$)

Proof pattern: if every statement implies the next one in a circle, then all three are true or all three are false.

$(1)\Rightarrow (2)$. Let $T_A$ be invertible.

• By Corollary 2.49, $T_A^{-1}$ is a matrix transformation, so $T_A^{-1}=T_B$ for some $m\times m$ matrix $B$.
• Since $T_B$ undoes $T_A$ (Fact 2.47), for every standard unit vector $e_j$:
  $e_j=T_B(T_A(e_j))=B(A{e}_j)=(BA)e_j.$
  The last equality is re-bracketing (Corollary 2.35: the product matrix represents the composition).
• But $(BA)e_j$ is column $j$ of $BA$. So column $j$ of $BA$ equals $e_j$ for every $j$, i.e. $BA=I$. ✓

$(2)\Rightarrow (3)$. Let $BA=I$. To show: the columns of $A$ are linearly independent.

• $Ax$ is a linear combination of the columns of $A$ with coefficients $x_1,\dots ,x_m$.
• Independence means: the only combination giving $0$ is the trivial one, i.e. $Ax=0\Rightarrow x=0$ (Observation 2.5).
• So let $Ax=0$. Then
  $x=Ix=(BA)x=B(Ax)=B0=0.$
  The steps use $BA=I$, associativity, the assumption $Ax=0$, and “matrix times zero vector is zero”. ✓

$(3)\Rightarrow (1)$. Let the columns of $A$ be linearly independent.

• Existence: $m$ linearly independent vectors in ${\mathbb{R}}^m$ span all of ${\mathbb{R}}^m$ (Lemma 1.26; the Scratch animation). In matrix language: for every $y\in {\mathbb{R}}^m$ there is an $x$ with $T_A(x)=Ax=y$.
• Uniqueness: the coefficients of a linear combination of linearly independent vectors are unique (Lemma 1.22). So this $x$ is unique.
• “For every $y$ exactly one $x$” is precisely the definition of invertible. ✓ $■$

3.4 Uniqueness of the inverse (Observation 2.55)

Let $B$ and $B^{\prime }$ both satisfy the (equivalent) conditions, so in particular $B^{\prime }A=I$ and $AB=I$. Then
$B=IB=(B^{\prime }A)B=B^{\prime }(AB)=B^{\prime }I=B^{\prime }.$

• Step 2 uses $B^{\prime }A=I$.
• Step 3 uses associativity.
• Step 4 uses $AB=I$. $■$

This direct algebraic computation is all that is needed. (The high-level argument via the uniqueness of the matrix of a transformation also works.)

3.5 The $2\times 2$ formula and the case $ad=bc$

Verification. It is enough to check one product (Lemma 2.53), but both are easy:
$\left[\begin{array}{cc}a& b\\ c& d\end{array}\right]\left[\begin{array}{cc}d& -b\\ -c& a\end{array}\right]=\left[\begin{array}{cc}ad-bc& -ab+ba\\ cd-dc& -cb+da\end{array}\right]=\left[\begin{array}{cc}ad-bc& 0\\ 0& ad-bc\end{array}\right]=(ad-bc)I.$
Without the factor $\frac{1}{ad-bc}$ you get a diagonal matrix, but not $I$. Dividing by $ad-bc$ fixes this.

Student question: does $ad=bc$ imply the columns are dependent? Yes. Write $c_1=\left(\begin{array}{c}a\\ c\end{array}\right)$ and $c_2=\left(\begin{array}{c}b\\ d\end{array}\right)$. If $ad-bc=0$:
$d{c}_1-c{c}_2=\left(\begin{array}{c}da-cb\\ dc-cd\end{array}\right)=\left(\begin{array}{c}0\\ 0\end{array}\right),b{c}_1-a{c}_2=\left(\begin{array}{c}ba-ab\\ bc-ad\end{array}\right)=\left(\begin{array}{c}0\\ 0\end{array}\right).$

• If $(c,d)\ne (0,0)$, the first combination is non-trivial.
• If $(a,b)\ne (0,0)$, the second one is.
• If both are zero, $A=0$ and the columns are trivially dependent.

So $ad=bc⟺$ the columns are dependent $⟺$ $A$ is singular. In the second part of the course, $ad-bc$ will be called the determinant.

3.6 Proofs of Lemmas 2.58 and 2.59 (in the script; not done in lecture)

(2.58) By Observation 2.55 it suffices to find one matrix $C$ with $C(AB)=I$:
$(B^{-1}{A}^{-1})(AB)=B^{-1}(A^{-1}A)B=B^{-1}IB=B^{-1}B=I.$
So $AB$ is invertible with $(AB{)}^{-1}=B^{-1}{A}^{-1}$. For three factors, apply the rule twice:
$(ABC{)}^{-1}=((AB)C{)}^{-1}=C^{-1}(AB{)}^{-1}=C^{-1}{B}^{-1}{A}^{-1}.$

(2.59) Using Lemma 2.38 ($(XY{)}^{\top }=Y^{\top }{X}^{\top }$):
$(A^{-1}{)}^{\top }{A}^{\top }=(A{A}^{-1}{)}^{\top }=I^{\top }=I.$
So $A^{\top }$ is invertible with $(A^{\top }{)}^{-1}=(A^{-1}{)}^{\top }$. $■$

3.7 CS Lens: Fibonacci with matrix powers (not exam-relevant)

Fibonacci numbers.
$F_0=0,F_1=1,F_n=F_{n-1}+F_{n-2}(n\ge 2):0,1,1,2,3,5,8,13,21,34,\dots$

The naive method, a Python list where each new value is F[-1] + F[-2], computes all $F_0,\dots ,F_{100}$, even if only $F_{100}$ is wanted.

Key observation: one step is one matrix–vector multiplication.
$\left(\begin{array}{c}{F}_{n-1}\\ F_n\end{array}\right)=\underset{A}{\underbrace{\left[\begin{array}{cc}0& 1\\ 1& 1\end{array}\right]}}\left(\begin{array}{c}{F}_{n-2}\\ F_{n-1}\end{array}\right).$

• Row 1 of $A$ times the vector keeps $F_{n-1}$.
• Row 2 adds the two entries, which gives $F_n$.

Applying this repeatedly (formally by induction) gives
$\left(\begin{array}{c}{F}_{n-1}\\ F_n\end{array}\right)=A\cdot A\cdots A\left(\begin{array}{c}{F}_0\\ F_1\end{array}\right)=A^{n-1}\left(\begin{array}{c}0\\ 1\end{array}\right).$
The second equality uses associativity: compute $A^{n-1}$ first, then apply it to the vector. Since $\left(\begin{array}{c}0\\ 1\end{array}\right)=e_2$, the vector $A^{n-1}{e}_2$ is the second column of $A^{n-1}$. So $F_n$ is the bottom-right entry of $A^{n-1}$. (In fact $A^k=\left[\begin{array}{cc}{F}_{k-1}& F_k\\ F_k& F_{k+1}\end{array}\right]$.)

Iterated squaring (iteratives Quadrieren). Use $A^{2k}=(A^k{)}^2$ and $A^{2k+1}=(A^k{)}^{2}A$:
$A^{99}=(A^{49}{)}^{2}A,A^{49}=(A^{24}{)}^{2}A,A^{24}=(A^{12}{)}^2,A^{12}=(A^6{)}^2,A^6=(A^3{)}^2,A^3=A^{2}A.$
Working back up:

Power	Matrix
$A^3$	$\left[\begin{array}{cc}1& 2\\ 2& 3\end{array}\right]$
$A^6$	$\left[\begin{array}{cc}5& 8\\ 8& 13\end{array}\right]$
$A^{12}$	$\left[\begin{array}{cc}89& 144\\ 144& 233\end{array}\right]$
$A^{24}$	$\left[\begin{array}{cc}28657& 46368\\ 46368& 75025\end{array}\right]$
$A^{49}$	$\left[\begin{array}{cc}4807526976& 7778742049\\ 7778742049& 12586269025\end{array}\right]$
$A^{99}$	bottom right: $F_{100}=354224848179261915075$

This takes only about $2{\log }_{2}n$ $2\times 2$ matrix multiplications instead of about $n$ additions.

Why not use Binet’s formula? From the exercise sheet,
$F_n=\frac{1}{\sqrt{5}}\left({\left(\frac{1+\sqrt{5}}{2}\right)}^n-{\left(\frac{1-\sqrt{5}}{2}\right)}^n\right).$
On a computer, $\sqrt{5}$ is only available as a floating-point number (Fließkommazahl), an approximation. For large $n$ rounding errors appear and the result has to be rounded to an integer. The lecturer considers iterated squaring the most practical method.

Reference: J. Matoušek, Thirty-three Miniatures: Mathematical and Algorithmic Applications of Linear Algebra.

---

4. Worked Examples & Applications

4.1 Evaluating the mixed product $x^{\top }{A}^{\top }Ax$ (Monday)

Let $A\in {\mathbb{R}}^{m\times n}$ and $x\in {\mathbb{R}}^n$.

Bracketing 1: $(x^{\top }{A}^{\top })(Ax)$.

• $x^{\top }{A}^{\top }$ is covector·matrix, so a covector.
• $Ax$ is a vector.
• Covector·vector is a scalar.
• By Lemma 2.38, $x^{\top }{A}^{\top }=(Ax{)}^{\top }$, so
  $x^{\top }{A}^{\top }Ax=(Ax{)}^{\top }(Ax)=\Vert Ax{\Vert }^2$
  (squared Euclidean norm: the scalar product of $Ax$ with itself, without the square root).

Bracketing 2: $x^{\top }(A^{\top }A)x$.

• $A^{\top }A$ is an $n\times n$ matrix.
• Covector·matrix is a covector; covector·vector is a scalar.
• The same scalar results, by associativity.

Exam Trap: efficiency

Bracketing 2 computes the matrix product $A^{\top }A$. For a large $A$ this costs about $m\cdot n^2$ multiplications. Bracketing 1 only needs $Ax$, about $mn$ multiplications, plus a scalar product of length $m$. Same value, very different running time.

4.2 The extreme example $v^{\top }w{v}^{\top }w$

Let $v,w\in {\mathbb{R}}^n$.

• $(v^{\top }w)(v^{\top }w)$ is scalar times scalar, $=(v\cdot w{)}^2$. Cost: about $n$ multiplications plus one squaring.
• $v^{\top }(w{v}^{\top })w$ forms the outer product $w{v}^{\top }$, an $n\times n$ matrix; then matrix·vector and covector·vector. The result is the same scalar.

For $n=1000$, the first variant needs about $1000$ operations, while the outer product alone has $10^6$ entries. Massively inefficient.

4.3 Clicker (Monday): in which order should three matrices be multiplied? (reconstructed)

The clicker’s exact dimensions were lost in the recording; the fragments mention $2\times 3$, $3\times 4$, $4\times 4$. The principle:

Cost of a matrix product

Multiplying an $m\times n$ matrix by an $n\times p$ matrix in the standard way takes $m\cdot n\cdot p$ scalar multiplications. The result is $m\times p$.

Example (standard textbook example)

$A$: $10\times 100$, $B$: $100\times 5$, $C$: $5\times 50$.

• $(AB)C$: $AB$ costs $10\cdot 100\cdot 5=5000$ and gives a $10\times 5$ matrix; $(AB)C$ costs $10\cdot 5\cdot 50=2500$. Total 7500.
• $A(BC)$: $BC$ costs $100\cdot 5\cdot 50=25000$ and gives a $100\times 50$ matrix; $A(BC)$ costs $10\cdot 100\cdot 50=50000$. Total 75000.

Same result, ten times the effort. Rule of thumb: first collapse the dimension that makes the intermediate result small.

4.4 Clicker (Wednesday): how many $2\times 2$ matrices with entries in $\{0,1\}$ are invertible?

There are $2^4=16$ matrices. Use the criterion “columns linearly independent” and go through the cases for column 1:

• Column 1 $=\left(\begin{array}{c}0\\ 0\end{array}\right)$: always dependent, so $0$ invertible.
• Column 1 is one of the 3 non-zero vectors $\left(\begin{array}{c}1\\ 0\end{array}\right),\left(\begin{array}{c}0\\ 1\end{array}\right),\left(\begin{array}{c}1\\ 1\end{array}\right)$:
  • column 2 $=0$: dependent;
  • column 2 $=$ column 1: dependent;
  • the remaining 2 choices: independent. (Two distinct non-zero 0/1 vectors in ${\mathbb{R}}^2$ are never multiples of each other.)

Result: $3\cdot 2=$ 6 of 16 are invertible, 10 are singular. Most of the class answered correctly.

Intuition: almost all real matrices are invertible

This example is somewhat misleading. With larger entries, say between $0$ and $10$, singular matrices are the exception: for $2\times 2$, column 2 would have to be exactly a multiple of column 1. Over $\mathbb{R}$, the singular matrices form a null set (Nullmenge): a “randomly drawn” real matrix is invertible. In the Scratch animation, the “L” only becomes non-invertible at the exact moment it collapses onto a line, which happens extremely rarely.

4.5 Example from the beginning of Wednesday

$A=\left[\begin{array}{cc}1& 0\\ 0& \frac{3}{4}\end{array}\right]$ scales by $\frac{3}{4}$ in the $y$-direction. The backward transformation scales by $\frac{4}{3}$:
$A^{-1}=\left[\begin{array}{cc}1& 0\\ 0& \frac{4}{3}\end{array}\right],A^{-1}A=\left[\begin{array}{cc}1& 0\\ 0& \frac{4}{3}\cdot \frac{3}{4}\end{array}\right]=I.✓$
Check with the $2\times 2$ formula: $ad-bc=\frac{3}{4}$, so $\frac{1}{3/4}\left[\begin{array}{cc}\frac{3}{4}& 0\\ 0& 1\end{array}\right]=\left[\begin{array}{cc}1& 0\\ 0& \frac{4}{3}\end{array}\right]$. ✓

---

Gauss elimination: the handouts (preview of Chapter 3)

Algorithm (Gauss elimination + back substitution)

Given $Ax=b$ with $A\in {\mathbb{R}}^{m\times m}$:

1. Elimination (column by column $j=1,\dots ,m-1$):
   • If the pivot $a_{jj}$ (current entry) is $0‘$, swap row $j$ with a lower row whose entry in column $j$ is $\ne 0$. This is a permutation matrix (Permutationsmatrix) $P_{jk}$. If no such row exists: give up.
   • For each row $i>j$: subtract ${\ell }_{ij}\cdot$ row $j$ from row $i$, with ${\ell }_{ij}=\frac{a_{ij}}{a_{jj}}$, so that entry $(i,j)$ becomes $0$.
   • Always apply each operation to $b$ as well.
2. Back substitution (Rückwärtseinsetzen): solve the resulting upper triangular system from the bottom up for $x_m,x_{m-1},\dots ,x_1$.

Elimination and permutation matrices

“Subtract $\ell \cdot$ row $j$ from row $i$” is multiplication from the left by the elimination matrix (Eliminationsmatrix)
$E_{ij}=I-\ell e_i{e}_j^{\top }(\text{identity with }-\ell \text{ at position }(i,j)).$
Swapping rows $j$ and $k$ is multiplication by $P_{jk}$ (the identity with rows $j$ and $k$ swapped). For example,
$P_{12}=\left[\begin{array}{cccc}0& 1& 0& 0\\ 1& 0& 0& 0\\ 0& 0& 1& 0\\ 0& 0& 0& 1\end{array}\right].$
Both are applied to $A$ and $b$: $Ax=b⟺EAx=Eb$.

Connection to this week

• $E_{ij}$ is invertible with $E_{ij}^{-1}=I+\ell e_i{e}_j^{\top }$ (“add back”). $P_{jk}$ is its own inverse.
• So every step is reversible, and the transformed system has exactly the same solutions as the original.
• $e_i{e}_j^{\top }$ is precisely an outer product from Monday.

4.6 Handout “nice” (with a row exchange)

$$\begin{array}{rl}3x_2-x_3+2x_4& =-1\\ 2x_1+x_2-x_3+2x_4& =5\\ -2x_1+5x_2-2x_3+6x_4& =4\\ 4x_1+11x_2-4x_3+8x_4& =2\end{array}\left[\begin{array}{ccccc}0& 3& -1& 2& -1\\ 2& 1& -1& 2& 5\\ -2& 5& -2& 6& 4\\ 4& 11& -4& 8& 2\end{array}\right]$$

Step 0, zero pivot. $a_{11}=0$, so swap rows 1 and 2 ($P_{12}$):
$\left[\begin{array}{ccccc}2& 1& -1& 2& 5\\ 0& 3& -1& 2& -1\\ -2& 5& -2& 6& 4\\ 4& 11& -4& 8& 2\end{array}\right]$

Column 1 (pivot $2$):

Step	Computation	New row
$E_{21}$: $\ell =0$	row 2 $-0\cdot$ row 1 ($E_{21}=I$)	$(0,3,-1,2\mid -1)$
$E_{31}$: $\ell =-1$	$(-2,5,-2,6\mid 4)-(-1)(2,1,-1,2\mid 5)$	$(0,6,-3,8\mid 9)$
$E_{41}$: $\ell =2$	$(4,11,-4,8\mid 2)-2(2,1,-1,2\mid 5)$	$(0,9,-2,4\mid -8)$

Column 2 (pivot $3$):

Step	Computation	New row
$E_{32}$: $\ell =2$	$(0,6,-3,8\mid 9)-2(0,3,-1,2\mid -1)$	$(0,0,-1,4\mid 11)$
$E_{42}$: $\ell =3$	$(0,9,-2,4\mid -8)-3(0,3,-1,2\mid -1)$	$(0,0,1,-2\mid -5)$

Column 3 (pivot $-1$):

Step	Computation	New row
$E_{43}$: $\ell =-1$	$(0,0,1,-2\mid -5)-(-1)(0,0,-1,4\mid 11)$	$(0,0,0,2\mid 6)$

Here $E_{43}$ has the entry $+1$ at position $(4,3)$.

Upper triangular form and back substitution:
$\left[\begin{array}{ccccc}2& 1& -1& 2& 5\\ 0& 3& -1& 2& -1\\ 0& 0& -1& 4& 11\\ 0& 0& 0& 2& 6\end{array}\right]$

Eq.	Before substitution	After substitution	Solution
4	$2x_4=6$	—	$x_4=3$
3	$-x_3+4x_4=11$	$-x_3+12=11$	$x_3=1$
2	$3x_2-x_3+2x_4=-1$	$3x_2+5=-1$	$x_2=-2$
1	$2x_1+x_2-x_3+2x_4=5$	$2x_1+3=5$	$x_1=1$

$x=\left(\begin{array}{c}1\\ -2\\ 1\\ 3\end{array}\right).$

Check (row 4 of the original system): $4\cdot 1+11\cdot (-2)-4\cdot 1+8\cdot 3=4-22-4+24=2$. ✓

4.7 Handout “ugly” (fractions, but it works)

$\left[\begin{array}{ccccc}1& 9& 2& 5& -2\\ 7& -3& 2& 0& 8\\ 6& 8& 1& -1& 2\\ -2& 3& 0& -5& 3\end{array}\right]$

Column 1 (pivot $1$):

Step	$\ell$	New row
$E_{21}$	$7$	$(7,-3,2,0\mid 8)-7(1,9,2,5\mid -2)=(0,-66,-12,-35\mid 22)$
$E_{31}$	$6$	$(6,8,1,-1\mid 2)-6(\dots )=(0,-46,-11,-31\mid 14)$
$E_{41}$	$-2$	$(-2,3,0,-5\mid 3)+2(\dots )=(0,21,4,5\mid -1)$

Column 2 (pivot $-66$):

$E_{32}$, with $\ell =\frac{-46}{-66}=\frac{23}{33}$. The scaled row 2 is $\frac{23}{33}(0,-66,-12,-35\mid 22)=(0,-46,-\frac{92}{11},-\frac{805}{33}\mid \frac{46}{3})$, so
$\text{row }{3}^{\prime }=\left(0,0,-\frac{29}{11},-\frac{218}{33}|-\frac{4}{3}\right).$

$E_{42}$, with $\ell =\frac{21}{-66}=-\frac{7}{22}$. The scaled row 2 is $-\frac{7}{22}(0,-66,-12,-35\mid 22)=(0,21,\frac{42}{11},\frac{245}{22}\mid -7)$, so
$\text{row }{4}^{\prime }=\left(0,0,\frac{2}{11},-\frac{135}{22}|6\right).$

Column 3 (pivot $-\frac{29}{11}$):

$E_{43}$, with $\ell =\frac{2/11}{-29/11}=-\frac{2}{29}$. The scaled row 3 is $-\frac{2}{29}\cdot \text{row }{3}^{\prime }=(0,0,\frac{2}{11},\frac{436}{957}\mid \frac{8}{87})$, so
$\text{row }{4}^{\prime \prime }=\left(0,0,0,-\frac{1147}{174}|\frac{514}{87}\right).$

Back substitution:

Eq.	Equation	Solution
4	$-\frac{1147}{174}{x}_4=\frac{514}{87}$	$x_4=-\frac{1028}{1147}$
3	$-\frac{29}{11}{x}_3-\frac{218}{33}{x}_4=-\frac{4}{3}$	$x_3=\frac{3156}{1147}$
2	$-66x_2-12x_3-35x_4=22$	$x_2=-\frac{411}{1147}$
1	$x_1+9x_2+2x_3+5x_4=-2$	$x_1=\frac{233}{1147}$

$x=\frac{1}{1147}\left(\begin{array}{c}233\\ -411\\ 3156\\ -1028\end{array}\right).$
This was checked with exact rational arithmetic.

Lesson from "ugly"

The algorithm is purely mechanical. Ugly fractions are not a sign of a mistake. Only a pivot that is $0$ (with no possible swap) stops it.

4.8 Handout “failure” (singular matrix)

$\left[\begin{array}{ccccc}1& 2& 3& 4& -1\\ 5& 6& 7& 8& 5\\ 9& 10& 11& 12& 4\\ 13& 14& 15& 16& 2\end{array}\right]$

Column 1 ($\ell =5,9,13$):

Row	Result
2	$(0,-4,-8,-12\mid 10)$
3	$(0,-8,-16,-24\mid 13)$
4	$(0,-12,-24,-36\mid 15)$

Column 2 (pivot $-4$; $\ell =2,3$):

Row	Computation	Result
3	$(0,-8,-16,-24\mid 13)-2(0,-4,-8,-12\mid 10)$	$(0,0,0,0\mid -7)$
4	$(0,-12,-24,-36\mid 15)-3(0,-4,-8,-12\mid 10)$	$(0,0,0,0\mid -15)$

Column 3: the pivot is $0$, and every entry below it in column 3 is $0$ as well. No row exchange is possible: give up!

Interpretation. Rows 3 and 4 now say $0=-7$ and $0=-15$, so the system has no solution. The matrix has only two linearly independent rows; its columns are linearly dependent, e.g.
$c_1-2c_2+c_3=0:(1,5,9,13)-2(2,6,10,14)+(3,7,11,15)=0.$
By Lemma 2.52, $A$ is singular.

Exam Trap: two kinds of failure

• If $A$ is singular, the system $Ax=b$ has either no solution or infinitely many, depending on $b$. Here the last entries $-7,-15\ne 0$ give no solution. With a $b$ that produces $0$ in both of those rows, there would be infinitely many.
• A zero pivot alone is not a failure (see “nice”). Only a zero pivot with no non-zero entry below it to swap in stops the algorithm.

---

5. Intuition & Conceptual Bridges

• Transformations explain the algebra. $BA=I\Rightarrow AB=I$ looks like a coincidence algebraically, but as transformations it is obvious: “forward then back” and “back then forward” both return to the start. The same view explains $(AB{)}^{-1}=B^{-1}{A}^{-1}$ (socks and shoes).
• Inversion generalises division. $1\times 1$: $a\mapsto \frac{1}{a}$ for $a\ne 0$. $2\times 2$: division by $ad-bc$, which must be $\ne 0$. In general: ”$A$ is not zero” becomes “the columns of $A$ are independent”.
• Three views of “invertible”:
  • Geometric: the transformation does not flatten anything (the “L” does not collapse).
  • Algebraic: there is $B$ with $BA=I$.
  • Combinatorial: the columns are independent; equivalently, $Ax=0$ only for $x=0$.
• Link to Chapter 1: Lemma 1.22 (unique coefficients) and Lemma 1.26 ($m$ independent vectors span ${\mathbb{R}}^m$) are exactly the two parts of “exactly one preimage”.
• Link to Discrete Mathematics: “bijective” and the inverse function $f^{-1}$ appear there in §3.6 (Functions). There, functions are special relations and the inverse is the inverse relation $\hat{f}$.
• Coming next:
  • Chapter 3 (Friday): Gauss elimination as the efficient algorithm for solving $Ax=b$ and computing $A^{-1}$ (the handouts are the preview).
  • Second part of the course: determinants (where $ad-bc$ comes from) and mixed products such as $x^{\top }{A}^{\top }Ax$ (least squares, quadratic forms).
• CS perspective: associativity guarantees a correct result, but efficiency depends on the evaluation order. This is the classic “matrix chain multiplication” problem, solved with dynamic programming in algorithms courses.

---

6. Summary & Self-Assessment Questions

Cheat sheet

Concept	Fact
Covector·matrix	$u^{\top }A$ is a covector; needs $\#$entries of $u$ $=$ $\#$rows of $A$
Outer product	$v{w}^{\top }$ is an $m\times n$ matrix; $v^{\top }w$ is a scalar
Mixed products	treat everything as matrices; associativity (L. 2.40); $(AB{)}^{\top }=B^{\top }{A}^{\top }$ (L. 2.38)
$x^{\top }{A}^{\top }Ax$	$=\Vert Ax{\Vert }^2$; evaluate as $(Ax{)}^{\top }(Ax)$
Cost of $(m\times n)(n\times p)$	$mnp$ multiplications
Bijective	$\forall y\exists !x:T(x)=y$
L. 2.48	$T$ linear and invertible $\Rightarrow$ $T^{-1}$ linear
L. 2.50	wide or tall $\Rightarrow$ not invertible
L. 2.52	$T_A$ invertible $⟺\exists B:BA=I⟺$ columns independent
L. 2.53	$BA=I\Rightarrow AB=I$ (square matrices)
Def. 2.54 / 2.56	invertible / singular; $A^{-1}$ unique; $(A^{-1}{)}^{-1}=A$
$1\times 1$ inverse	$[a{]}^{-1}=[1/a]$ for $a\ne 0$
$2\times 2$ inverse	$\frac{1}{ad-bc}\left[\begin{array}{cc}d& -b\\ -c& a\end{array}\right]$ for $ad\ne bc$
L. 2.58	$(AB{)}^{-1}=B^{-1}{A}^{-1}$
L. 2.59	$(A^{\top }{)}^{-1}=(A^{-1}{)}^{\top }$
Gauss	$E_{ij}$: subtract ${\ell }_{ij}=a_{ij}/a_{jj}$ times row $j$; $P_{jk}$: swap rows; then back substitution
Fibonacci	$F_n$ = bottom-right entry of ${\left[\begin{array}{cc}0& 1\\ 1& 1\end{array}\right]}^{n-1}$; iterated squaring

Practice questions

Q1. Compute $A^{-1}$ for $A=\left[\begin{array}{cc}2& 1\\ 5& 3\end{array}\right]$ and verify both $A^{-1}A=I$ and $A{A}^{-1}=I$. Then solve $Ax=\left(\begin{array}{c}1\\ 2\end{array}\right)$ using $A^{-1}$.

Solution to Question 1

Inverse. $ad-bc=2\cdot 3-1\cdot 5=1\ne 0$, so $A$ is invertible:
$A^{-1}=\frac{1}{1}\left[\begin{array}{cc}3& -1\\ -5& 2\end{array}\right]=\left[\begin{array}{cc}3& -1\\ -5& 2\end{array}\right].$

Verification.
$A^{-1}A=\left[\begin{array}{cc}3\cdot 2-1\cdot 5& 3\cdot 1-1\cdot 3\\ -5\cdot 2+2\cdot 5& -5\cdot 1+2\cdot 3\end{array}\right]=\left[\begin{array}{cc}1& 0\\ 0& 1\end{array}\right]$
$A{A}^{-1}=\left[\begin{array}{cc}2\cdot 3+1\cdot (-5)& 2\cdot (-1)+1\cdot 2\\ 5\cdot 3+3\cdot (-5)& 5\cdot (-1)+3\cdot 2\end{array}\right]=\left[\begin{array}{cc}1& 0\\ 0& 1\end{array}\right]$
(By Lemma 2.53 one check would have been enough.)

Solving. $Ax=b\Rightarrow x=A^{-1}Ax=A^{-1}b$:
$x=\left[\begin{array}{cc}3& -1\\ -5& 2\end{array}\right]\left(\begin{array}{c}1\\ 2\end{array}\right)=\left(\begin{array}{c}1\\ -1\end{array}\right).$

Check: $2\cdot 1+1\cdot (-1)=1$ and $5\cdot 1+3\cdot (-1)=2$. ✓

Q2. Prove: if $A$ is invertible, then for every $b$ the system $Ax=b$ has exactly one solution, namely $x=A^{-1}b$.

Solution to Question 2

Existence. Put $x:=A^{-1}b$. Then
$Ax=A(A^{-1}b)=(A{A}^{-1})b=Ib=b,$
using associativity and $A{A}^{-1}=I$ (Def. 2.56 / Lemma 2.53).

Uniqueness. Let $x^{\prime }$ also satisfy $A{x}^{\prime }=b$. Then
$x^{\prime }=I{x}^{\prime }=(A^{-1}A)x^{\prime }=A^{-1}(A{x}^{\prime })=A^{-1}b=x.$

So there is exactly one solution. $■$

This is exactly invertibility of $T_A$ from Lemma 2.52 (1): every $b$ has exactly one preimage.

Q3. True or false? Give a proof or a counterexample.
(a) If $A$ and $B$ are invertible, then $A+B$ is invertible.
(b) If $AB$ is invertible ($A,B$ square), then $A$ and $B$ are invertible.
(c) $(AB{)}^{-1}=A^{-1}{B}^{-1}$ for all invertible $A,B$.

Solution to Question 3

(a) False. $A=I$ and $B=-I$ are both invertible, but $A+B=0$ is singular.

(b) True. Let $C=(AB{)}^{-1}$.

• $B$ is invertible. $(CA)B=C(AB)=I$, so $CA$ is a left inverse of $B$. By Def. 2.54, $B$ is invertible.
• $A$ is invertible. $(AB)C=I$ by Lemma 2.53, i.e. $A(BC)=I$. By Observation 2.55 (the equivalent condition $A{B}^{\prime }=I$ with $B^{\prime }=BC$), $A$ is invertible.

(c) False in general. The correct rule is $(AB{)}^{-1}=B^{-1}{A}^{-1}$ (Lemma 2.58). Counterexample: $A=\left[\begin{array}{cc}1& 1\\ 0& 1\end{array}\right]$, $B=\left[\begin{array}{cc}1& 0\\ 1& 1\end{array}\right]$.

• $A^{-1}=\left[\begin{array}{cc}1& -1\\ 0& 1\end{array}\right]$ and $B^{-1}=\left[\begin{array}{cc}1& 0\\ -1& 1\end{array}\right]$.
• $A^{-1}{B}^{-1}=\left[\begin{array}{cc}2& -1\\ -1& 1\end{array}\right]$ and $B^{-1}{A}^{-1}=\left[\begin{array}{cc}1& -1\\ -1& 2\end{array}\right]$.
• $AB=\left[\begin{array}{cc}2& 1\\ 1& 1\end{array}\right]$, and its inverse (determinant $1$) is $\left[\begin{array}{cc}1& -1\\ -1& 2\end{array}\right]=B^{-1}{A}^{-1}\ne A^{-1}{B}^{-1}$.

The rule happens to hold when $A$ and $B$ commute.

Q4. Solve with Gauss elimination, writing out every elimination/permutation matrix:
$\begin{array}{rl}{x}_2+x_3& =1\\ x_1+2x_2+x_3& =1\\ 2x_1+7x_2+9x_3& =13\end{array}$

Solution to Question 4

$\left[\begin{array}{cccc}0& 1& 1& 1\\ 1& 2& 1& 1\\ 2& 7& 9& 13\end{array}\right]$

Zero pivot. $a_{11}=0$, so apply
$P_{12}=\left[\begin{array}{ccc}0& 1& 0\\ 1& 0& 0\\ 0& 0& 1\end{array}\right]:\left[\begin{array}{cccc}1& 2& 1& 1\\ 0& 1& 1& 1\\ 2& 7& 9& 13\end{array}\right]$

Column 1.

• $E_{21}$: $\ell =0$, so $E_{21}=I$.
• $E_{31}$: $\ell =2$, $E_{31}=\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ -2& 0& 1\end{array}\right]$. Row 3: $(2,7,9\mid 13)-2(1,2,1\mid 1)=(0,3,7\mid 11)$.

Column 2.

• $E_{32}$: $\ell =3$, $E_{32}=\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& -3& 1\end{array}\right]$. Row 3: $(0,3,7\mid 11)-3(0,1,1\mid 1)=(0,0,4\mid 8)$.

Back substitution.

• $4x_3=8\Rightarrow x_3=2$.
• $x_2+x_3=1\Rightarrow x_2=-1$.
• $x_1+2x_2+x_3=1\Rightarrow x_1-2+2=1\Rightarrow x_1=1$.

$x=\left(\begin{array}{c}1\\ -1\\ 2\end{array}\right).$

Check row 3: $2-7+18=13$. ✓

Q5. Let $A\in {\mathbb{R}}^{1000\times 1000}$ and $x\in {\mathbb{R}}^{1000}$. Estimate the number of scalar multiplications needed to evaluate $x^{\top }{A}^{\top }Ax$ (a) as $x^{\top }(A^{\top }A)x$ and (b) as $(Ax{)}^{\top }(Ax)$. What is the value, interpreted geometrically?

Solution to Question 5

Let $n=1000$.

(a) $x^{\top }(A^{\top }A)x$.

• $A^{\top }A$: $(n\times n)(n\times n)$, so $n^3=10^9$.
• $x^{\top }(A^{\top }A)$: covector·matrix, $n^2=10^6$.
• covector·vector: $n=10^3$.
• Total about $10^9$.

(b) $(Ax{)}^{\top }(Ax)$.

• $Ax$: $n^2=10^6$.
• Scalar product of $Ax$ with itself: $n=10^3$.
• Total about $10^6$, i.e. about 1000 times faster.

Value. $(Ax{)}^{\top }(Ax)=\Vert Ax{\Vert }^2$, the squared Euclidean length of the transformed vector $Ax$ (using $x^{\top }{A}^{\top }=(Ax{)}^{\top }$, Lemma 2.38). Both bracketings give the same number (Lemma 2.40). Only the cost differs.