MT2025 Linear Algebra Lecture Notes

Remaining TODOs: 30

Relevant reading:

For chapters 1-5: Jim Hefferon. Linear Algebra.

For chapter 6: Lloyd N. Trefethen & David Bau. Numerical Linear Algebra.

1 Linear systems

1.i Solving Linear Systems

Definition 1.1.1: A linear combination of variables

𝑥_{1}, 𝑥_{2}, \dots, 𝑥_{𝑛}

has the form

𝑎_{1} 𝑥_{1} + 𝑎_{2} 𝑥_{2} + \dots + 𝑎_{𝑛} 𝑥_{𝑛},

with

𝑎_{1}, \dots, 𝑎_{𝑛} \in ℝ

Definition 1.1.2: A linear equation has the form

𝑎_{1} 𝑥_{1} + \dots + 𝑎_{𝑛} 𝑥_{𝑛} = 𝑑,

𝑑 \in ℝ

. An

𝑛

-tuple

(𝑆_{1}, \dots, 𝑆_{𝑛})

is a solution of that equation, or satisfies that equation, if substituting

𝑥_{𝑖}

for

𝑆_{𝑖}

gives a true statement.

In a system of equations, the $𝑛$ th row is denoted with the Greek letter rho as $𝜌_{𝑛}$ .

Definition 1.1.3: Elementary row operations are operations that can be carried out on a system of linear equations without changing the solution set.

These operations, all affecting row $𝑖$ , are:

swapping two rows, $𝜌_{𝑗} \leftrightarrow 𝜌_{𝑖}$ , where $𝑖 \neq 𝑗$ ;
scaling a row, $𝑛 𝜌_{𝑖}$ where $𝑛 \in ℝ \ {0}$ ;
adding one row to another row, $𝑛 𝜌_{𝑗} + 𝜌_{𝑖}$ , where $𝑛 \in ℝ \ {0}$ and $𝑖 \neq 𝑗$ .

Lemma 1.1.4: Elementary row operations preserve the solution set of a linear system.

Proof:

Consider some system of linear equations

\begin{aligned} 𝑎_{1, 1} 𝑥_{1} + 𝑎_{1, 2} 𝑥_{2} + \dots + 𝑎_{1, 𝑛} 𝑥_{𝑛} & = 𝑑_{1}; \\ 𝑎_{2, 1} 𝑥_{1} + 𝑎_{2, 2} 𝑥_{2} + \dots + 𝑎_{2, 𝑛} 𝑥_{𝑛} & = 𝑑_{2}; \\ ⋮ \\ 𝑎_{𝑖, 1} 𝑥_{1} + 𝑎_{𝑖, 2} 𝑥_{2} + \dots + 𝑎_{𝑖, 𝑛} 𝑥_{𝑛} & = 𝑑_{𝑖} . \end{aligned}

For the tuple $(𝑆_{1}, 𝑆_{2}, \dots, 𝑆_{𝑛})$ to satisfy this system of equations, we must have that $𝑎_{1, 1} 𝑆_{1} + \dots + 𝑎_{1, 𝑛} 𝑆_{𝑛} = 𝑑_{1}$ and that $𝑎_{2, 1} 𝑆_{1} + \dots + 𝑎_{2, 𝑛} 𝑆_{𝑛} = 𝑑_{2}$ , and so on; swapping the order of two of the linear equations in the system does not change the validity of this solution, as logical and is commutative. Hence operation (i) is an elementary row operation.

If we multiply a linear equation by some non-zero scalar $𝜆$ , that equation still holds true, and so the solution set to the system is still valid. Hence operation (ii) is an elementary operation.

Any solution set that satisfies the system of linear equations must satisfy each individual equation. If we add two equations together, the solutions will still hold, so operation (iii) is an elementary row operation.

Definition 1.1.5: A leading variable is the first variable in an equation with a non-zero coefficient.

Definition 1.1.6: A system of equations is in echelon form if each row’s leading variable is to the right of the leading variable in the row immediately above it, with the exception of the first row, and any rows with all-zero coefficients are at the bottom of the system.

Definition 1.1.7: In an echelon form linear system, any variables that do not appear as leading variables are free variables. These can be used as parameters to describe a solution set.

Example: If we have a system of equations

\begin{aligned} 𝑥 + 3 𝑦 + 2 & 𝑧 + 6 & 𝑤 = 5 \\ 𝑧 + 2 & 𝑤 = 3 \end{aligned}

then $𝑦$ and $𝑤$ are free variables. We can parametrise the solution set using $𝑦$ and $𝑤$ as parameters to say that

{(\begin{matrix} 𝑥 \\ 𝑦 \\ 𝑧 \\ 𝑤 \end{matrix}) = (\begin{matrix} 2 \\ 0 \\ 3 \\ 0 \end{matrix}) + 𝑦 (\begin{matrix} - 3 \\ 1 \\ 0 \\ 0 \end{matrix}) + 𝑤 (\begin{matrix} - 4 \\ 0 \\ - 2 \\ 1 \end{matrix}), 𝑦, 𝑤 \in ℝ}

but it is more clear to write $𝑦$ and $𝑤$ as new variables:

{(\begin{matrix} 𝑥 \\ 𝑦 \\ 𝑧 \\ 𝑤 \end{matrix}) = (\begin{matrix} 2 \\ 0 \\ 3 \\ 0 \end{matrix}) + 𝜆 (\begin{matrix} - 3 \\ 1 \\ 0 \\ 0 \end{matrix}) + 𝜇 (\begin{matrix} - 4 \\ 0 \\ - 2 \\ 1 \end{matrix}), 𝜆, 𝜇 \in ℝ}

Definition 1.1.8: A linear equation is homogeneous if the constant is zero.

The Gaussian elimination of a system of linear equations follows the same operations as the Gaussian elimination of its associated system of homogeneous linear equations.

It is helpful to study homogeneous systems because these always have a particular solution, the zero vector.

In general, we can say that the general solution to a system of linear equations is the sum of a particular solution and the solution to the associated system of homogeneous equations.

Lemma 1.1.9: The zero vector is always a particular solution of a homogeneous system of linear equations.

Proof:

Take substituting $𝑥_{1}, \dots, 𝑥_{𝑛}$ for $0$ in each equation in a homogeneous system gives $𝑎_{1, 1} (0) + \dots + 𝑎_{1, 𝑛} (0) = 0; \dots; 𝑎_{𝑖, 1} (0) + \dots + 𝑎_{𝑖, 𝑛} (0) = 0$ which is trivially true and so $\vec{0}$ is a particular solution of any homogeneous system of linear equations.

Lemma 1.1.10: For any homogeneous linear system of equations, there exist vectors ${\vec{𝛽}}_{1}, \dots, {\vec{𝛽}}_{𝑘}$ such that the solution set of the system is

{𝑐_{1} {\vec{𝛽}}_{1} + \dots + 𝑐_{𝑛} {\vec{𝛽}}_{𝑘} | 𝑐_{1}, \dots, 𝑐_{𝑘} \in ℝ},

where $𝑘$ is the number of free variables in an echelon form of the system.

This can be rephrased as: every leading variable in a homogeneous system can be expressed as a linear combination of free variables.

Proof:

Consider some homogeneous system that has been transformed into echelon form, ignoring any trivially true equations ( $0 = 0$ ). If the system consists entirely of tautologies, the lemma is trivially true as there are no leading variables which need be expressed.

We will denote the index of the leading variable in a row $𝑟$ as $𝓁︀ (𝑟)$ .

Consider the bottom equation, row $𝑖$ ,

𝑎_{𝑖, 𝓁︀ (𝑖)} 𝑥_{𝓁︀ (𝑖)} + 𝑎_{𝑖, 𝓁︀ (𝑖) + 1} 𝑥_{𝓁︀ (𝑖) + 1} + \dots + 𝑎_{𝑖, 𝑛} 𝑥_{𝑛} = 0,

where $𝑎_{𝓁︀ (𝑖)} \neq 0$ . Here, $𝑥_{𝓁︀ (𝑖) + 1}, \dots, 𝑥_{𝑛}$ are free variables as there are no rows below this in which they could be leading. The leading variable $𝑥_{𝓁︀ (𝑖)}$ can be expressed in terms of the free variables:

𝑥_{𝓁︀ (𝑖)} = \frac{- (𝑎_{𝑖, 𝓁︀ (𝑖) + 1} 𝑥_{𝓁︀ (𝑖) + 1} + \dots + 𝑎_{𝑖, 𝑛} 𝑥_{𝑛})}{𝑎_{𝑖, 𝓁︀ (𝑖)}} .

Suppose that every leading variable $𝑥_{𝓁︀ (𝑚)}$ for $𝑚 \in {𝑖 - 𝑘 + 1, \dots, 𝑖 - 1, 𝑖}$ for arbitrary $𝑘$ can be expressed as a linear combination of free variables. Then the leading variable of the $𝑘$ th equation can be expressed as a linear combination of free variables, since every other variable in the $𝑘$ th equation is either a free variable, or is a leading variable in a lower equation and so can be expressed as a linear combination of free variables itself.

Hence if the $(𝑖 - 𝑘_{1})$ th leading variable can be expressed as a linear combination of free variables, so can the $(𝑖 - 𝑘)$ th equation. Hence by induction, every leading variable can be expressed as a linear combination of free variables.

Definition 1.1.11: The set of vectors

{𝑐_{1} {\vec{𝛽}}_{1} + \dots + 𝑐_{𝑛} {\vec{𝛽}}_{𝑘} | 𝑐_{1}, \dots, 𝑐_{𝑘} \in ℝ}

is generated by by or is spanned by by the set

{{\vec{𝛽}}_{1}, \dots, {\vec{𝛽}}_{𝑘}}

Lemma 1.1.12: For a linear system and a particular solution $\vec{𝑝}$ , the system is satisfied by the solution set

{\vec{𝑝} + 𝑐_{1} {\vec{𝛽}}_{1} + \dots + 𝑐_{𝑛} {\vec{𝛽}}_{𝑘} | 𝑐_{1}, \dots, 𝑐_{𝑘} \in ℝ} .

Proof:

Suppose that $\vec{𝑠}$ satisfies the system. Then $\vec{ℎ} = \vec{𝑠} - \vec{𝑝}$ satisfies the associated homogeneous system since for all $𝑘 \in {1, \dots, 𝑖},$

\begin{aligned} 𝑎_{𝑘, 1} (𝑠_{1} - 𝑝_{1}) + \dots + 𝑎_{𝑘, 𝑛} (𝑠_{1} - 𝑝_{1}) & = (𝑎_{𝑘, 1} 𝑠_{1} + \dots + 𝑎_{𝑘, 𝑛} 𝑠_{𝑛}) - (𝑎_{𝑘, 1} 𝑝_{1} + \dots + 𝑎_{𝑘, 𝑛} 𝑝_{𝑛}) \\ = 𝑑_{𝑘} - 𝑑_{𝑘} \\ = 0, \end{aligned}

where $𝑑_{𝑘}$ is the constant of the $𝑘$ th equation and $𝑠_{𝑗}$ and $𝑝_{𝑗}$ are the $𝑗$ th components of $\vec{𝑠}$ and $\vec{𝑝}$ respectively.

Suppose that we have a vector $\vec{ℎ}$ that satisfies the associated homogeneous system, then $\vec{𝑝} + \vec{ℎ}$ satisfies the system because, for all $𝑘 \in {1, \dots, 𝑘}$ ,

\begin{aligned} 𝑎_{𝑘, 1} (𝑝_{1} + ℎ_{1}) + \dots + 𝑎_{𝑘, 𝑛} (𝑝_{1} + ℎ_{1}) & = (𝑎_{𝑘, 1} 𝑝_{1} + \dots + 𝑎_{𝑘, 𝑛} 𝑝_{𝑛}) + (𝑎_{𝑘, 1} ℎ_{1} + \dots + 𝑎_{𝑘, 𝑛} ℎ_{𝑛}) \\ = 𝑑_{𝑘} + 0 \\ = 𝑑_{𝑘} . \end{aligned}

Theorem 1.1.13: The solution set of any linear system has the form

{\vec{𝑝} + 𝑐_{1} {\vec{𝛽}}_{1} + \dots + 𝑐_{𝑘} {\vec{𝛽}}_{𝑘} | 𝑐_{1}, \dots, 𝑐_{𝑘} \in ℝ},

where $𝑝$ is any particular solution and $𝑘$ is the number of free variables in the echelon form of the system.

Proof:

This follows from Lemma 1.1.10 and Lemma 1.1.12.

Corollary 1.1.14: A linear system of equations has either no solutions, one solution, or infinitely many solutions.

1.ii Linear Geometry

Definition 1.2.1: A square matrix is nonsingular if it is the matrix of coefficients of a homogeneous system with a unique solution. Otherwise (i.e. the homogeneous system has infinitely many solutions), it is singular.

Definition 1.2.2: The line (in $ℝ^{2}$ ), plane (in $ℝ^{3}$ ), or $𝑘$ -dimensional linear surface, $𝑘$ -flat or $𝑘$ -dimensional hyperplane (in $ℝ^{𝑘})$ is a set of the form

{\vec{𝑎} + 𝑡_{1} {\vec{𝑣}}_{1} + \dots + 𝑡_{𝑘} {\vec{𝑣}}_{𝑘} | 𝑡_{1}, \dots, 𝑡_{𝑛 - 1} \in ℝ},

where

{\vec{𝑣}}_{1}, \dots, {\vec{𝑣}}_{𝑘} \in ℝ^{𝑛}

and

𝑘 \leq 𝑛

. More specifically, it is comprised of the endpoints of these vectors when their tips are at the origin.

Remark: That the column vectors associated with a parameter

𝑡_{*}

lie entirely within the line, not just their tips.

Definition 1.2.3: The length of a vector $\vec{𝑣}$ is defined as

| \vec{𝑣} | = ‖ \vec{𝑣} ‖ = \sqrt{𝑣_{1}^{2} + \dots + 𝑣_{𝑛}^{2}} .

Definition 1.2.4: For any nonzero vector

\vec{𝑣}

, we normalise

\vec{𝑣}

to unit length by carrying out

\vec{𝑣} / ‖ \vec{𝑣} ‖

Definition 1.2.5: The dot product, scalar product or inner product of two vectors $\vec{𝑢}$ and $\vec{𝑣}$ is defined as

\vec{𝑢} \cdot \vec{𝑣} = 𝑢 - 1 𝑣_{1} + \dots + 𝑢_{𝑛} 𝑣_{𝑛} .

Remark: That

\vec{𝑣} \cdot \vec{𝑣} = 𝑣_{1}^{2} + \dots + 𝑣_{𝑛}^{2} = {‖ \vec{𝑣} ‖}^{2}

Theorem 1.2.6 (Cauchy-Schwartz inequality): For any $\vec{𝑢}, \vec{𝑣} \in ℝ^{𝑛}$ ,

| \vec{𝑢} \cdot \vec{𝑣} | \leq | \vec{𝑢} | | \vec{𝑣} |,

with equality only if there exists $𝑘 \in 𝑅$ such that $\vec{𝑢} = 𝑘 \vec{𝑣}$ .

Proof:

\begin{aligned} | \vec{𝑢} \cdot \vec{𝑣} | \leq | \vec{𝑢} | | \vec{𝑣} | \\ ⟺ & \vec{𝑢} \cdot \vec{𝑣} \leq | \vec{𝑢} | | \vec{𝑣} | \\ ⟺ & (| \vec{𝑢} | \vec{𝑣} | |) (\vec{𝑢} \cdot \vec{𝑣}) \leq {| \vec{𝑢} |}^{2} {| \vec{𝑣} |}^{2} \\ ⟺ & 0 \leq {| \vec{𝑢} |}^{2} {| \vec{𝑣} |}^{2} - (| \vec{𝑢} | | \vec{𝑣} |) (\vec{𝑢} \cdot \vec{𝑣}) \\ ⟺ & 0 \leq \frac{1}{2} ({| \vec{𝑢} |}^{2} {| \vec{𝑣} |}^{2} - 2 (| \vec{𝑢} | \vec{𝑣}) \cdot (| \vec{𝑣} | \vec{𝑢}) + {| \vec{𝑢} |}^{2} {| \vec{𝑣} |}^{2}) \\ ⟺ & 0 \leq \frac{1}{2} (| \vec{𝑢} | \vec{𝑣} - | \vec{𝑣} | \vec{𝑢}) \cdot (| \vec{𝑢} | \vec{𝑣} - | \vec{𝑣} | \vec{𝑢}) \\ ⟺ & 0 \leq \frac{1}{2} {| (| \vec{𝑢} | \vec{𝑣} - | \vec{𝑣} | \vec{𝑢}) |}^{2} \\ ⟺ & 0 \leq \frac{1}{2} {| (| \vec{𝑢} | \vec{𝑣} - | \vec{𝑣} | \vec{𝑢}) |}^{2} \end{aligned}

which is true because $| * |$ is always positive, so ${| * |}^{2}$ is also always positive.

Equality occurs iff $(| \vec{𝑢} | \vec{𝑣} - | \vec{𝑣} | \vec{𝑢}) = 0$ .

If $\exists 𝑘 \in ℝ : \vec{𝑢} = 𝑘 \vec{𝑣}$ , then $(| \vec{𝑢} | \vec{𝑣} - | \vec{𝑣} | \vec{𝑢}) = (𝑘 | \vec{𝑣} | \vec{𝑣} - 𝑘 | \vec{𝑣} | \vec{𝑣}) = 0$ .

If $(| \vec{𝑢} | \vec{𝑣} - | \vec{𝑣} | \vec{𝑢}) = 0$ , then

\begin{aligned} \forall 𝑖 < 𝑛 : \\ \sqrt{𝑢_{1}^{2} + \dots + 𝑢_{𝑛}^{2}} 𝑣_{𝑖} = \sqrt{𝑣_{1}^{2} + \dots + 𝑣_{𝑛}^{2}} 𝑢_{𝑖} \\ ⟹ & \frac{\sqrt{𝑢_{1}^{2} + \dots + 𝑢_{𝑛}^{2}}}{\sqrt{𝑣_{1}^{2} + \dots + 𝑣_{𝑛}^{2}}} = \frac{𝑢_{𝑖}}{𝑣_{𝑖}} \\ ⟹ & \frac{𝑢_{𝑖}}{𝑣_{𝑖}} = 𝑘, 𝑘 \in ℝ \\ ⟹ & \exists 𝑘 \in ℝ : \vec{𝑢} = 𝑘 \vec{𝑣} . \end{aligned}

Hence equality occurs iff $\exists 𝑘 \in ℝ : \vec{𝑢} = 𝑘 \vec{𝑣}$ .

Theorem 1.2.7 (Triangle inequality): For any $\vec{𝑢}, \vec{𝑣} \in ℝ^{𝑛}$ , $| \vec{𝑢} + \vec{𝑣} | \leq | \vec{𝑢} | + | \vec{𝑣} |,$ with equality iff $\exists 𝑘 \in ℝ : \vec{𝑢} = 𝑘 \vec{𝑣}$ .

Proof:

Both sides of the inequality are positive, so squaring both sides does not change the validity of the inequality.

\begin{aligned} {| \vec{𝑢} + \vec{𝑣} |}^{2} & \leq {(| \vec{𝑢} | + | \vec{𝑣} |)}^{2} \\ ⟺ & (\vec{𝑢} + \vec{𝑣}) \cdot (\vec{𝑢} + \vec{𝑣}) & \leq {| \vec{𝑢} |}^{2} + 2 | \vec{𝑢} | | \vec{𝑣} | + {| \vec{𝑣} |}^{2} \\ ⟺ & \vec{𝑢} \cdot \vec{𝑢} + 2 (\vec{𝑢} \cdot \vec{𝑣}) + \vec{𝑣} \cdot \vec{𝑣} & \leq {| \vec{𝑢} |}^{2} + 2 | \vec{𝑢} | | \vec{𝑣} | + {| \vec{𝑣} |}^{2} \\ ⟺ & {| \vec{𝑢} |}^{2} + 2 (\vec{𝑢} \cdot \vec{𝑣}) + {| \vec{𝑣} |}^{2} & \leq {| \vec{𝑢} |}^{2} + 2 | \vec{𝑢} | | \vec{𝑣} | + {| \vec{𝑣} |}^{2} \\ ⟺ & 2 (\vec{𝑢} \cdot \vec{𝑣}) & \leq 2 | \vec{𝑢} | | \vec{𝑣} | \end{aligned}

which is true by the Cauchy-Schwartz inequality (Theorem 1.2.6).

Equality occurs iff $\exists 𝑘 \in ℝ : \vec{𝑢} = 𝑘 \vec{𝑣}$ , by the Cauchy-Schwartz inequality again.

Definition 1.2.8: The angle between two vectors $\vec{𝑢}, \vec{𝑣} \in ℝ^{𝑛}$ is defined as

𝜃 = arccos (\frac{\vec{𝑢} \cdot \vec{𝑣}}{| \vec{𝑢} | | \vec{𝑣} |}) .

Remark: That this is always defined since, following from the Cauchy-Schwartz inequality,

\frac{\vec{𝑢} \cdot \vec{𝑣}}{| \vec{𝑢} | | \vec{𝑣} |} \in [- 1, 1] .

Remark: That this always gives an angle in the range

[0, 𝜋]

Remark: That this corresponds to our intuition about angles.

Remark: The formula in Definition 1.2.8 follows from the Law of Cosines.

Proof:

Consider two vectors $\vec{𝑢}, \vec{𝑣} \in ℝ$ , and call the angle between them $𝜃$ . Using the Law of Cosines on the triangle with sides $\vec{𝑢}, \vec{𝑣}$ and $(\vec{𝑢} - \vec{𝑣})$ gives that

{| \vec{𝑢} - \vec{𝑣} |}^{2} = {| \vec{𝑢} |}^{2} + {| \vec{𝑣} |}^{2} - 2 | \vec{𝑢} | | \vec{𝑣} | cos 𝜃 .

The left side gives

{(𝑢_{1} - 𝑣_{1})}^{2} + \dots + {(𝑢_{𝑛} + 𝑣_{𝑛})}^{2} = (𝑢_{1}^{2} - 2 𝑢_{1} 𝑣_{1} + 𝑣_{1}^{2}) + \dots + (𝑢_{𝑛}^{2} - 2 𝑢_{𝑛} 𝑣_{𝑛} + 𝑣_{𝑛}^{2}),

while the right side gives

(𝑢_{1}^{2} + \dots + 𝑢_{𝑛}^{2}) + (𝑣_{1}^{2} + \dots + 𝑣_{𝑛}^{2}) - 2 | \vec{𝑢} | | \vec{𝑣} | cos 𝜃 .

Combining the two sides and cancelling like terms gives

\begin{aligned} - 2 (𝑢_{1} 𝑣_{1} + \dots + 𝑢_{𝑛} 𝑣_{𝑛}) & = - 2 \vec{𝑢} \cdot \vec{𝑣} \\ = - 2 | \vec{𝑢} | | \vec{𝑣} | cos 𝜃, \end{aligned}

which simplifies and rearranges to give Definition 1.2.8.

Remark: That the Law of Cosines is just an extension of Pythagoras’ theorem:

\underset{Pythagoras' theorem}{\underset{⏟}{𝑐^{2} = 𝑎^{2} + 𝑏^{2}}} - 2 𝑎 𝑏 cos 𝜃

Corollary 1.2.9: Vectors from

ℝ^{𝑛}

are orthogonal (perpendicular) iff their dot product is zero (since

arccos 0 = \frac{𝜋}{2}

). They are parallel iff the absolute value of their dot product is the product of their length (since

arccos 1 = arccos (- 1) = 0

1.iii Reduced echelon form

Definition 1.3.1: In reduced echelon form, every leading variable has a coefficient of 1, and is the only nonzero entry in its column.

Remark: That for free variables, there are no restrictions on coefficients, or other entries in that column.

This is useful because we can just read the solution off.

Example: Consider the following system matrix in reduced echelon form:

(\begin{matrix} 1 & 0 & 0 & 3 & 3 \\ 0 & 1 & 0 & 0 & 4 \\ 0 & 0 & 1 & 1 / 2 & 1 \end{matrix}) .

The solution set of this system is simply

{(\begin{matrix} 3 \\ 4 \\ 1 \\ 0 \end{matrix}) + 𝜆 (\begin{matrix} 3 \\ 0 \\ 1 / 2 \\ 1 \end{matrix}) | 𝜆 \in ℝ} .

To get to reduced echelon form, we use Gauss-Jordan reduction, whereby we first carry out Gaussian elimination, then scale each row such that the leading variables have coefficients of 1, then eliminate any non-leading and non-free variables in each row by working upwards.

Lemma 1.3.2: Elementary row operations are reversible.

Proof:

$𝜌_{𝑖} \leftrightarrow 𝜌_{𝑗}$ has the inverse of $𝜌_{𝑗} \leftrightarrow 𝜌_{𝑖}$ . $𝑘 𝜌_{𝑖}$ has the inverse of $\frac{1}{𝑘} 𝜌_{𝑖}$ for $𝑘 \neq 0$ . $𝑘 𝜌_{𝑖} + 𝜌_{𝑗}$ has the inverse $- 𝑘 𝜌_{𝑖} + 𝜌_{𝑗}$ , where $𝑖 \neq 𝑗$ .

Definition 1.3.3: Matrices that reduce to each other (using elementary row operations) are interreducible, equivalent with respect to the relationship of row reducibility, or row equivalent. They are said to be in the same row equivalence class.

Remark: Row equivalence classes are disjoint; any matrix belongs to exactly one row equivalence class.

Lemma 1.3.4: Between matrices, ‘reduces to’ is an equivalence relation.

Proof:

To be an equivalence relation, ‘reduces to’ must satisfy reflexivity, symmetry and transitivity.

Reflexivity is trivial since we can reduce $𝐴 \to 𝐴$ through carryig out no operations.

Symmetry follows from Lemma 1.3.2.

The relation is transitive because if we can reduce $𝐴 \to 𝐵$ and $𝐵 \to 𝐶$ , we can carry out the operations in order to go from $𝐴 \to 𝐵 \to 𝐶$ to reduce $𝐴 \to 𝐶$ .

Lemma 1.3.5 (Linear combination lemma): A linear combination of linear combinations is a linear combination.

Proof:

Given the set of linear combinations ${𝑐_{𝑖, 1} 𝑥_{1} + \dots 𝑐_{𝑖,_{𝑛}} 𝑥_{𝑛} | 𝑖 \in {1, \dots, 𝑚}, 𝑚 \in ℕ_{1}}$ , consider the linear combination of these

\begin{aligned} 𝑑_{1} (𝑐_{1, 1} 𝑥_{1} + \dots 𝑐_{1,_{𝑛}} 𝑥_{𝑛}) + \dots + 𝑑_{𝑚 (𝑐_{𝑚, 1} 𝑥_{1} + \dots 𝑐_{𝑚,_{𝑛}} 𝑥_{𝑛})} \\ = & (𝑑_{1} 𝑐_{1, 1} 𝑥_{1} + \dots + 𝑑_{1} 𝑐_{1, 𝑛} 𝑥_{𝑛}) + \dots + (𝑑_{𝑚} 𝑐_{𝑚, 1} 𝑥_{1} + \dots + 𝑑_{𝑚} 𝑐_{𝑚, 𝑛} 𝑥_{𝑛}) \\ = & (𝑑_{1} 𝑐_{1, 1} + \dots + 𝑑_{𝑚} 𝑐_{𝑚, 1}) 𝑥_{1} + \dots + (𝑑_{1} 𝑐_{1, 𝑛} + \dots + 𝑑_{𝑚} 𝑐_{𝑚,_{𝑛}}) 𝑥_{𝑛} \end{aligned}

which is a linear combination.

Corollary 1.3.6: Where one matrix reduces to another, each row of the second is a linear combination of the first.

Lemma 1.3.7: In an echelon form matrix, no nonzero row is a linear combination of the other nonzero rows.

Proof:

Consider any row of the matrix. The leading entry in that row is one, but the entry in that column in every other row is equal to zero (by the definition of reduced echelon form), so there is no linear combination of other rows that can make this row.

Remark: The thing that Gaussian elimination really eliminates is any linear relationships between rows.

Theorem 1.3.8: Each matrix is row equivalent to a unique (“canonical”) reduced echelon form matrix.

Proof:

We proceed by induction on the number of columns, $𝑛$ , for a fixed arbitrary number of rows $𝑚$ .

Let $𝐴 \in {ℳ︀}_{𝑚 \times 1}$ .

If $𝐴$ is the zero matrix, then it is in reduced echelon form and is not row-equivalent to any other matrix (this follows from Corollary 1.3.6). Otherwise, when reduced to reduced-echelon form, the only nonzero entry must be a 1 in the first row. Regardless, the reduced echelon form matrix is unique.

Now assume that, for some $𝑛 > 1$ , all $𝑚 \times 𝑘$ matrices for $𝑘 < 𝑛$ have a unique reduced echelon form matrix, and consider $𝐴 \in {ℳ︀}_{𝑚 \times 𝑛}$ .

Suppose that $𝐴$ reduces to two distinct reduced echelon form matrices, $𝐵$ and $𝐶$ . Let $\hat{𝐴}$ be the matrix consisting of the first $𝑛 - 1$ columns of $𝐴$ . Any sequence of operations that reduces $𝐴$ to reduced echelon form must also reduce $\hat{𝐴}$ to reduced echelon form, and by the inductive hypothesis, $\hat{𝐴}$ reduces to a unique reduced echelon form matrix. Therefore, $𝐵$ and $𝐶$ must differ in the $𝑛$ th column.

We write the linear system with matrix of coefficients $𝐴$ as

\begin{matrix} 𝑎_{1, 1} 𝑥_{1} + \dots + 𝑎_{1, 𝑛} 𝑥_{𝑚} = 0; \\ ⋮ \\ 𝑎_{𝑚, 1} 𝑥_{1} + \dots + 𝑎_{𝑚, 𝑛} 𝑥_{𝑚} = 0; \end{matrix}

the systems with matrices of coefficients $𝐵$ and $𝐶$ are written similarly. These systems must all have the same solution sets, since carrying out elementary row operations on linear systems does not change the solution set. With $𝐵$ and $𝐶$ differing only in the $𝑛$ th column, suppose they differ in row $𝑖$ . We subtract row $𝑖$ of the systems represented by $𝐵$ and $𝐶$ to get that $(𝑐_{𝑖, 𝑛} - 𝑏_{𝑖, 𝑛}) 𝑥_{𝑛} = 0$ . Since $𝑐_{𝑖, 𝑛} \neq 𝑏_{𝑖, 𝑛}$ , $𝑥_{𝑛} = 0$ .

Therefore, $𝑥_{𝑛}$ is not a free variable, so the $𝑛$ th columns of $𝐵$ and $𝐶$ must contain the leading entry of some row, since any column that does not have a leading entry is associated with a free variable.

Because the first $(𝑛 - 1)$ columns of $𝐵$ and $𝐶$ are equal, a leading variable in the $𝑛$ th column must be in the same position in $𝐵$ and $𝐶$ , and must be equal to 1; therefore, $𝐵$ and $𝐶$ are equal, so $𝐴$ reduces to a unique reduced echelon form matrix.

Remark: To decide if two matrices are row-equivalent, we reduce them to reduced echelon form and see if they are equivalent (this works because equivalence relations are transitive).

2 Vector spaces

2.i Definition of vector space

Definition 2.1.1: A vector space (over $ℝ$ ) consists of a set $𝑉$ along with two operations ‘ $+$ ’ and ‘ $\cdot$ ’ subject to the condition that, for all $\vec{𝑢}, \vec{𝑣}, \vec{𝑤} \in 𝑉, 𝑟, 𝑠 \in ℝ$ :

$𝑉$ is closed under addition i.e. $\vec{𝑢} + \vec{𝑣} \in 𝑉$
addition is commutative i.e. $\vec{𝑢} + \vec{𝑣} = \vec{𝑣} + \vec{𝑢}$
addition is associative
there is an additive identity, i.e. $\exists \vec{0} \in 𝑉 . \forall \vec{𝑣} \in 𝑉 . \vec{𝑣} + \vec{0} = \vec{𝑣}$
every element of $𝑉$ has an additive inverse, i.e. $\forall \vec{𝑣} \in 𝑉 . \exists \vec{𝑤} \in 𝑉 . \vec{𝑣} + \vec{𝑤} = \vec{0}$
$𝑉$ is closed under scalar multiplication i.e. $𝑟 \cdot \vec{𝑣} \in 𝑉$
scalar multiplication distributes over addition of scalars, i.e. $(𝑟 + 𝑠) \cdot \vec{𝑣} = 𝑟 \cdot \vec{𝑣} + 𝑠 \cdot \vec{𝑣}$
scalar multiplication distributes over vector addition, i.e. $𝑟 \cdot (\vec{𝑢} + \vec{𝑣}) = 𝑟 \cdot \vec{𝑢} + 𝑟 \cdot \vec{𝑣}$
ordinary scalar multiplication associates with scalar multiplication, i.e. $(𝑟 𝑠) \vec{𝑣} = 𝑟 \cdot (𝑠 \cdot \vec{𝑣})$
$1 \cdot \vec{𝑣} = \vec{𝑣}$

Remark: A vector space is space in which linear combinations can be made.

Example: For all

𝑛

ℝ^{𝑛}

is a vector space under the natural operations.

Example: For all

𝑛

, the set of

𝑛

th degree polynomials,

{𝒫︀}_{𝑛} = {𝑎_{0} + 𝑎_{1} 𝑥 + 𝑎_{2} 𝑥^{2} + \dots + 𝑎_{𝑛} 𝑥^{𝑛} | 𝑎_{0}, \dots, 𝑎_{𝑛} \in ℝ}

is a vector space under the natural operations.

Example: The set of

𝑚 \times 𝑛

matrices

𝑀_{𝑚 \times 𝑛}

is a vector space.

Remark: That

\emptyset

is not a vector space because it does not have an additive identity, but

{(\begin{matrix} 0 \\ 0 \end{matrix})}

is a vector space.

Definition 2.1.2: A vector space with one element is a trivial vector space.

Lemma 2.1.3: In any vector space $𝑉$ , for any $\vec{𝑣} \in 𝑉$ and $𝑟 \in ℝ$ , we have

$0 \cdot \vec{𝑣} = \vec{0}$
$(- 1 \cdot \vec{𝑣}) + \vec{𝑣} = \vec{0}$
$𝑟 \cdot \vec{0} = \vec{0}$

Proof:

For (i), note that $\vec{𝑣} = (1 + 0) \cdot \vec{𝑣} = \vec{𝑣} + (0 \cdot \vec{𝑣})$ . Add to both sides the additive inverse $𝑤$ such that $\vec{𝑣} + \vec{𝑤} = \vec{0}$ .

\begin{matrix} \vec{𝑤} + \vec{𝑣} = \vec{𝑤} + \vec{𝑣} + 0 \cdot 𝑣 \\ \vec{0} = \vec{0} + 0 \cdot 𝑣 \\ \vec{0} = 0 \cdot 𝑣 . \end{matrix}

(ii): $(- 1 \cdot \vec{𝑣}) + \vec{𝑣} = (- 1 + 1) \cdot \vec{𝑣} = 0 \cdot \vec{𝑣} = \vec{0}$ .

(iii) $𝑟 \cdot \vec{0} = 𝑟 \cdot (0 \cdot \vec{0}) = (𝑟 \cdot 0) \cdot \vec{0} = \vec{0}$

Definition 2.1.4: For any vector space, a subspace is a subset that is itself a vector space, under the inherited operations.

Remark: Any vector space has a trivial subspace

{\vec{0}}

Remark: Any vector space has itself for a subspace.

Definition 2.1.5: A subspace that it not the entire space is a proper subset.

Lemma 2.1.6: For a nonempty subset $𝑆$ of a vector space, under the inherited operations the following are equivalent statements

$𝑆$ is a subspace of that vector space
$𝑆$ is closed under linear combinations of pairs of vectors
$𝑆$ is closed under linear combinations of any number of vectors

Remark: It is often easier to verify closure if the solution set is parametrised, e.g. rather than

{(\begin{matrix} 𝑥 \\ 𝑦 \\ 𝑧 \end{matrix}) | 2 𝑥 - 𝑦 + 𝑧 = 0}

, use

{𝑦 (\begin{matrix} \frac{1}{2} \\ 1 \\ 0 \end{matrix}) + 𝑧 (\begin{matrix} - \frac{1}{2} \\ 0 \\ 1 \end{matrix}) | 𝑦, 𝑧 \in ℝ}

Definition 2.1.7: The span (or linear closure) of a nonempty subset

𝑆

of a vector space is the set of all linear combinations of vectors from

𝑆

[𝑆] = span (𝑆) = {𝑐_{1} {\vec{𝑠}}_{1} + \dots + 𝑐_{𝑛} {\vec{𝑠}}_{𝑛} | 𝑐_{1}, \dots, 𝑐_{𝑛} \in 𝑅, {\vec{𝑠}}_{1}, \dots, {\vec{𝑠}}_{𝑛} \in 𝑆}

Definition 2.1.8:

[\emptyset] = {\vec{0}}

Lemma 2.1.9: In a vector space, the span of any subset is a subspace.

Proof:

If the subset $𝑆$ is empty, its span is the trivial subspace by definition. Otherwise, for two elements of $[𝑆]$ , $\vec{𝑣} = 𝑐_{1} {\vec{𝑠}}_{1} + \dots + 𝑐_{𝑛} {\vec{𝑠}}_{𝑛}, \vec{𝑤} = 𝑑_{1} {\vec{𝑠}}_{1} + \dots + 𝑑_{𝑛} {\vec{𝑠}}_{𝑛}$ , where ${\vec{𝑠}}_{*} \in 𝑆$ and $𝑝, 𝑟 \in ℝ$ ,

\begin{aligned} 𝑝 \cdot \vec{𝑣} + 𝑟 \cdot \vec{𝑤} & = (𝑝 𝑐_{1} {\vec{𝑠}}_{1} + \dots + 𝑝 𝑐_{𝑛} {\vec{𝑠}}_{𝑛}) + (𝑟 𝑑_{1} {\vec{𝑠}}_{1} + \dots + 𝑟 𝑑_{𝑛} {\vec{𝑠}}_{𝑛}) \\ = (𝑝 𝑐_{1} + 𝑟 𝑑_{1}) {\vec{𝑠}}_{1} + \dots + (𝑝 𝑐_{𝑛} + 𝑟 𝑑_{𝑛}) {\vec{𝑠}}_{𝑛} \end{aligned}

which is a linear combination of elements of $𝑆$ and so is a member of $[𝑆]$ , hence $[𝑆]$ is closed under linear combinations of pairs of elements; by Lemma 2.1.6, $[𝑆]$ is a subspace.

Remark: To express a subspace as a span, parametrise then the span is of the set containing the vector coefficients of each parameter.

Remark: Spans are not unique.

2.ii Linear Independence

Definition 2.2.1: In any vector space, a set of vectors is linearly independent if none of its elements is a linear combination of the others from the set. Otherwise the set is linearly dependent.

Definition 2.2.2: If a set is linearly dependent, its vectors are in a linear relationship.

Lemma 2.2.3: A subset $𝑆$ of a vector space is linearly independent iff among its elements the only linear relationship $𝑐_{1} 𝑠_{1} + \dots + 𝑐_{𝑛} 𝑠_{𝑛} = 0$ is the trivial one, $𝑐_{*} = 0$ .

Proof:

If $𝑆$ is linearly independent, there is no vector $𝑠 \in 𝑆$ that can be expressed as a linear combination of other elements of $𝑆$ , so there is no linear relationship between elements of $𝑆$ with non-zero coefficients, i.e. the only linear relationship is the trivial one.

If $𝑆$ is linearly dependent, there exists a vector $𝑠 \in 𝑆$ that can be represented as a linear combination of other elements of $𝑆$ , so there is a linear relationship among the elements of $𝑆$ with at least one non-zero coefficient, being that of $𝑠$ . Hence by contraposition, if the only linear relationship among elements of $𝑆$ is the trivial one, $𝑆$ is linearly independent.

Lemma 2.2.4: Suppose $𝑉$ is a vector space, $𝑆$ is a subset of that space, and $\vec{𝑣} \in 𝑉$ , then

[𝑆 \cup {\vec{𝑣}}] = [𝑆] ⟺ \vec{𝑣} \in [𝑆] .

Proof:

$⟹$ : Suppose $\vec{𝑣} \notin [𝑆]$ , then $[𝑆 \cup {\vec{𝑣}}] \neq [𝑆]$ since $\vec{𝑣} \in [𝑆 \cup {\vec{𝑣}}]$ ; the implication follows from contraposition.

$⟸$ : Suppose $\vec{𝑣} \in [𝑆]$ , then $\vec{𝑣} = 𝑐_{1} {\vec{𝑠}}_{1} + \dots + 𝑐_{𝑛} {\vec{𝑠}}_{𝑛}$ for $𝑐_{1}, \dots, 𝑐_{𝑛} \in ℝ, {\vec{𝑠}}_{1}, \dots, {\vec{𝑠}}_{𝑛} \in 𝑆$ . Then for any $\vec{𝑤} \in [𝑆 \cup {\vec{𝑣}}]$ ,

\begin{aligned} \vec{𝑤} & = 𝑑_{1} {\vec{𝑠}}_{1} + \dots + 𝑑_{𝑛} {\vec{𝑠}}_{𝑛} + 𝑑_{𝑛 + 1} \vec{𝑣} \\ = (𝑑_{1} + 𝑐_{1} 𝑑_{𝑛_{1}}) {\vec{𝑠}}_{1} + \dots + (𝑑_{𝑛} + 𝑐_{𝑛} 𝑑_{𝑛 + 1}) {\vec{𝑠}}_{𝑛} by expansion of \vec{𝑣}, \end{aligned}

so $\vec{𝑤} \in [𝑆]$ . Therefore, $[𝑆 \cup {\vec{𝑣}}] \subseteq [𝑆]$ . Note also that clearly $[𝑆] \subseteq [𝑆 \cup {\vec{𝑣}}]$ , so by double inclusion $[𝑆 \cup {\vec{𝑣}}] = [𝑆]$ .

Corollary 2.2.5: For

\vec{𝑣} \in 𝑆

[𝑆] = [𝑆 \ {\vec{𝑣}}]

iff

\vec{𝑣}

is dependent on other vectors in

𝑆

Corollary 2.2.6: A set

𝑆

is linearly independent iff for any

\vec{𝑣} \in 𝑆

[𝑆 \ {\vec{𝑣}}] \subset [𝑆]

Lemma 2.2.7: Suppose that $𝑆$ is linearly independent and that $\vec{𝑣} \notin 𝑆$ , then $𝑆 \cup {\vec{𝑣}}$ is linearly independent iff $\vec{𝑣} \notin [𝑆]$ .

Proof:

Suppose that $\vec{𝑣} \in [𝑆]$ , so $\vec{𝑣} = 𝑐_{1} {\vec{𝑠}}_{1} + \dots + 𝑐_{𝑛} {\vec{𝑠}}_{𝑛}$ for ${\vec{𝑠}}_{1}, \dots, {\vec{𝑠}}_{𝑛} \in 𝑆$ . Since $𝑣 \notin 𝑆$ , it is not equal to any of the ${\vec{𝑠}}_{𝑖}$ s so this is a nontrivial linear dependence among elements of $𝑆 \cup {\vec{𝑣}}$ . Therefore, $𝑠 \cup {\vec{𝑣}}$ is not linearly independent.

Now suppose that $𝑆 \cup {\vec{𝑣}}$ is linearly dependent, so there exists a nontrivial combination $\vec{0} = 𝑐_{1} {\vec{𝑠}}_{1} + \dots + 𝑐_{𝑛} {\vec{𝑠}}_{𝑛} + 𝑐_{𝑛 + 1} \vec{𝑣}$ . By assumption, $𝑆$ is linear independent, so $𝑐_{𝑛 + 1} \neq 0$ . Therefore, we can rearrange the equation to find that $\vec{𝑣} = (\frac{𝑐_{1}}{𝑐_{𝑛 + 1}}) {\vec{𝑠}}_{1} + \dots + (\frac{𝑐_{𝑛}}{𝑐_{𝑛 + 1}}) {\vec{𝑠}}_{𝑛}$ , so $\vec{𝑣} \in [𝑆]$ .

Therefore we have that $𝑆 \cup {\vec{𝑣}}$ is linearly dependent iff $\vec{𝑣} \in [𝑆]$ , so $𝑆 \cup {\vec{𝑣}}$ is linear independent iff $\vec{𝑣} \notin [𝑆]$ .

Corollary 2.2.8: In a vector space, any finite set has a linearly independent subset with the same span.

Proof:

For a finite set $𝑆 ≔ {{\vec{𝑠}}_{1}, \dots, {\vec{𝑠}}_{𝑛}}$ , if $𝑆$ is linearly independent then the statement is trivially true as $𝑆 \subseteq 𝑆$ . Note that if $𝑆$ is a singleton set, it is trivially linearly independent.

Otherwise, there exists an ${\vec{𝑠}}_{𝑖}$ which can be expressed as a linear combination of the other elements of $𝑆$ ; by Corollary 2.2.5, $𝑆^{'} ≔ 𝑆 \ {{\vec{𝑠}}_{𝑖}}$ has the same span as $𝑆$ . $| 𝑆^{'} | < | 𝑆 |$ , and since $𝑆^{'}$ is finite we can keep removing dependent elements until we either reach a nontrivial independent set with the same span, or we reach a singleton set, which is trivially independent.

Corollary 2.2.9: A subset $𝑆 = {{\vec{𝑠}}_{1}, \dots, {\vec{𝑠}}_{𝑛}}$ is linearly dependent iff some $𝑠_{𝑖} \in 𝑆$ can be represented as a linear combination of other elements in $𝑆$ listed before it.

Proof:

Let $𝑆_{0} = {}, 𝑆_{1} = {{\vec{𝑠}}_{1}}, 𝑆_{2} = {{\vec{𝑠}}_{1}, {\vec{𝑆}}_{2}}, \dots$ . Then if $𝑆$ is linearly dependent, there exists a first $𝑖 \geq 1$ such that $𝑆_{𝑖 - 1} \cup {{\vec{𝑠}}_{𝑖}}$ is linearly dependent, i.e. ${\vec{𝑠}}_{𝑖} \in [𝑆_{𝑖 - 1}]$ .

Lemma 2.2.10: Any subset of a linearly independent set is also linearly independent. Any superset of a linearly dependent set is linearly dependent.

2.iii Basis and dimension

Definition 2.3.1: A basis for a vector space is a sequence of vectors that is linearly independent and that spans the space. Denoted

⟨ 𝛽_{1}, 𝛽_{2}, \dots ⟩

Definition 2.3.2: For any $ℝ^{𝑛}$ ,

𝜀_{𝑛} = ⟨ (\begin{matrix} 1 \\ 0 \\ ⋮ \\ 0 \end{matrix}), (\begin{matrix} 0 \\ 1 \\ ⋮ \\ 0 \end{matrix}), \dots, (\begin{matrix} 0 \\ 0 \\ ⋮ \\ 1 \end{matrix}) ⟩

is the standard basis or natural basis. We denote these vectors

{\vec{𝑒}}_{1}, \dots, {\vec{𝑒}}_{𝑛}

. (Sometimes the vectors in

𝜀_{3}

are denoted

\vec{𝑖}, \vec{𝑗}, \vec{𝑘}

Theorem 2.3.3: In any vector space, a subset is a basis iff each vector in the space can be expressed as a linear combination of elements of the subset in exactly one way.

Proof:

A sequence is a basis iff its elements form a spanning subset of the space, and is linearly independent. A subset is spanning iff each vector in the space can be expressed as a linear combination of elements in the subset, so we need only show that a spanning subset is linearly independent iff every vector in the space has a unique expression as a linear combination of elements of the subset.

Consider two such expressions of a vector $\vec{𝑣}$ , $\vec{𝑣} = 𝑐_{1} {\vec{𝛽}}_{1} + \dots + 𝑐_{𝑛} {\vec{𝛽}}_{𝑛}$ and $\vec{𝑣} = 𝑑_{1} {\vec{𝛽}}_{1} + \dots + 𝑑_{𝑛} {\vec{𝛽}}_{𝑛}$ for a subset $𝑆 ≔ {{\vec{𝛽}}_{1}, \dots, {\vec{𝛽}}_{𝑛}}$ . These are equal by transitivity of equality, so we can subtract them to get that $(𝑐_{1} - 𝑑_{1}) {\vec{𝛽}}_{1} + \dots + (𝑐_{𝑛} - 𝑑_{𝑛}) {\vec{𝛽}}_{𝑛} = \vec{0}$ . The $𝑐_{𝑖}$ s equal the $𝑑_{𝑖}$ s iff $𝑐_{𝑖} - 𝑑_{𝑖} = 0$ for $1 \leq 𝑖 \leq 𝑛$ , which holds iff $𝑆$ is linearly independent, since the only linear dependence amongst its elements is the trivial one.

Definition 2.3.4: In a vector space with bases $𝐵$ the representation of $\vec{𝑣}$ with respect to $𝐵$ is the column vector of the coefficients used to express $\vec{𝑣}$ as a linear combination of the bases vectors:

{Rep}_{𝐵} (\vec{𝑣}) = {(\begin{matrix} 𝑐_{1} \\ ⋮ \\ 𝑐_{𝑛} \end{matrix})}_{𝐵}

where $𝐵 = ⟨ {\vec{𝛽}}_{1}, \dots, {\vec{𝛽}}_{𝑛} ⟩$ and $\vec{𝑣} = 𝑐_{1} {\vec{𝛽}}_{1} + \dots + 𝑐_{𝑛} {\vec{𝛽}}_{𝑛}$ .

$𝑐_{1}, \dots, 𝑐_{𝑛}$ are the coordinates of $\vec{𝑣}$ with respect to $\vec{𝑣}$ .

Remark: Any

\vec{𝑤} \in ℝ^{𝑛}

has

{Rep}_{𝜀_{𝑛}} (\vec{𝑤}) = \vec{𝑤} .

Lemma 2.3.5: If $𝐵$ is an $𝑛$ -element basis of a vector space $𝒱︀$ , then for any set of vectors ${{\vec{𝑣}}_{1}, \dots, {\vec{𝑣}}_{𝑘}}$ ,

𝑎_{1} {\vec{𝑣}}_{1} + \dots + 𝑎_{𝑘} {\vec{𝑣}}_{𝑘} = {\vec{0}}_{𝒱︀} ⟺ 𝑎_{1} {Rep}_{𝐵} ({\vec{𝑣}}_{1}) + \dots + 𝑎_{𝑘} {Rep}_{𝐵} ({\vec{𝑣}}_{𝑘}) = {\vec{0}}_{ℝ^{𝑛}} .

Proof:

Take a basis $𝐵 = ⟨ {\vec{𝛽}}_{1}, \dots, {\vec{𝛽}}_{𝑛} ⟩$ and suppose ${Rep}_{𝐵 ({\vec{𝑣}}_{𝑖})}$ is the $𝑖$ th column of a matrix $𝐶 \in {ℳ︀}_{𝑘 \times 𝑛}$ for $1 \leq 𝑖 \leq 𝑘$ such that ${\vec{𝑣}}_{1} = 𝑐_{1, 1} {\vec{𝛽}}_{1} + \dots + 𝑐_{𝑛, 1} {\vec{𝛽}}_{𝑛}$ etc.

Then we can substitute these into $𝑎_{1} {\vec{𝑣}}_{1} + \dots + 𝑎_{𝑘} {\vec{𝑣}}_{𝑘} = {\vec{0}}_{𝒱︀}$ to give

\begin{aligned} {\vec{0}}_{𝒱︀} & = 𝑎_{1} (𝑐_{1, 1} {\vec{𝛽}}_{1} + \dots + 𝑐_{𝑛, 1} {\vec{𝛽}}_{𝑛}) + \dots + 𝑎_{𝑘} (𝑐_{1, 𝑘} {\vec{𝛽}}_{1} + \dots + 𝑐_{𝑛, 𝑘} {\vec{𝛽}}_{𝑛}) \\ = (𝑎_{1} 𝑐_{1, 1} + \dots + 𝑎_{𝑘} 𝑐_{1, 𝑘}) {\vec{𝛽}}_{1} + \dots + (𝑎_{1} 𝑐_{𝑛, 1} + \dots + 𝑎_{𝑘} 𝑐_{𝑛, 𝑘}) {\vec{𝛽}}_{𝑘} . \end{aligned}

Because elements of bases are linearly independent, this only holds if $𝑎_{1} 𝑐_{1, 1} + \dots + 𝑎_{𝑘} 𝑐_{1, 𝑘} = \dots = 𝑎_{1} 𝑐_{𝑛, 1} + \dots + 𝑎_{𝑘} 𝑐_{𝑛, 𝑘} = 0$ . This gives us a linear system which we can re-express with column vectors, giving

\begin{aligned} {\vec{0}}_{ℝ^{𝑛}} & = 𝑎_{1} (\begin{matrix} 𝑐_{1, 1} \\ ⋮ \\ 𝑐_{𝑛, 1} \end{matrix}) + \dots + 𝑎_{𝑘} (\begin{matrix} 𝑐_{1, 𝑘} \\ ⋮ \\ 𝑐_{𝑛, 𝑘} \end{matrix}) \\ = 𝑎_{1} {Rep}_{𝐵} ({\vec{𝑣}}_{1}) + \dots + 𝑎_{𝑘} {Rep}_{𝐵} ({\vec{𝑣}}_{𝑘}) . \end{aligned}

Note that not only does the relationship hold, but the coefficients $𝑎_{*}$ are the same.

Definition 2.3.6: A vector space is finite-dimensional if it has a basis with only finitely many vectors.

Theorem 2.3.7: In any finite-dimensional vector space, all bases have the same number of elements.

Proof:

Consider some finite-dimensional vector space; by definition, it has a finite basis. Pick one finite basis $𝐵 = ⟨ {\vec{𝛽}}_{1}, \dots, {\vec{𝛽}}_{𝑛} ⟩$ of minimal size, and, for the sake of contradiction, take any other basis $𝐷 = ⟩ {\vec{𝛿}}_{1}, \dots, {\vec{𝛿}}_{𝑚} ⟩$ , with $𝑚 \neq 𝑛$ , noting that $𝑚 > 𝑛$ since $𝐵$ is minimal.

Assume that the elements of $𝐷$ are unique (otherwise it would not be a basis), then the only linear relationship amongst the $𝛿_{𝑖}$ s must be the trivial one. By Lemma 2.3.5, the only linear relationship amongst the representations of the $𝛿_{𝑖}$ s with respect to $𝐵$ is the trivial one.

A linear relationship amongst the representations of the $𝛿_{𝑖}$ s with respect to $𝐵$ can be represented by a homogeneous system of $𝑛$ linear equations, with $𝑚 > 𝑛$ unknowns. Since there are more unknowns than equations, and the system is homogeneous, there are infinitely many solutions and so there must be more than just the trivial linear relationship among the $𝛿_{𝑖}$ s. Therefore, the $𝛿_{𝑖}$ s are not linearly independent, so $𝐷$ is not a basis; this is a contradiction, so all bases of $𝒱︀$ must be the same size.

Definition 2.3.8: The dimension of a vector space is the number of vectors in any of its bases.

Corollary 2.3.9: No linearly independent set can have a size greater than the dimension of the enclosing space, assuming a finite-dimensional space.

Corollary 2.3.10: Any linearly independent set can be expanded to make a basis.

Proof:

Take a linearly independent set $𝑆$ of a vector space $𝒱︀$ .

If $𝑆$ is not already a basis for $𝑉$ , then it must not span the space. Therefore we can add a vector that is not in $[𝑆]$ to $𝑆$ , and retain linear independence by Lemma 2.2.7. Keep adding until the resulting set does span the space, which will occur in a finite number of steps by Corollary 2.3.9.

Corollary 2.3.11: Any spanning set can be shrunk to a basis.

Proof:

Take a spanning set $𝑆$ . If $𝑆 = \emptyset$ then it is already a basis (and the enclosing space must be trivial). If $𝑆 = {\vec{0}}$ then it can be shrunk to the empty basis without changing its span.

Otherwise, $\exists \vec{𝑠} \in 𝑆$ s.t. $\vec{𝑠} \neq \vec{0}$ and we can form a basis $𝐵 ≔ ⟨ \vec{𝑠} ⟩$ . If $[𝐵] = [𝑆]$ then we are done. Otherwise, $\exists \vec{𝑡} \in [𝑆]$ s.t. $\vec{𝑡} \notin [𝐵]$ , so we can append $\vec{𝑡}$ to $𝐵$ . By Lemma 2.2.7, $𝐵$ is still linearly independent. We can then check if $[𝐵] = [𝑆]$ , and keep repeating this process until the spans are equal, which must happen in a finite number of steps.

Corollary 2.3.12: In an $𝑛$ -dimensional space, a set composed of $𝑛$ vectors is linearly independent iff it spans the space.

Proof:

A set composed of $𝑛$ vectors is linearly independent iff it is a basis: the “if” direction is clear, and the other directions holds because any linearly independent set can be expanded to a basis, but it already has $𝑛$ elements so must already be a basis.

A subset of $𝑛$ vectors spans the space iff it is a basis: again the “if” direction is clear, and the other direction holds because any spanning set can be shrunk to a basis, but it already has $𝑛$ elements so must already be a basis.

Definition 2.3.13: The row space of a matrix is the span of the set of its rows. The row rank is the dimension of this space, the number of linearly independent rows.

Lemma 2.3.14: If two matrices $𝐴$ and $𝐵$ are related by a row operation, $𝜌_{𝑖} \leftrightarrow 𝜌_{𝑗}$ , $𝑘 𝜌_{𝑖}$ or $𝑘 𝜌_{𝑖} + 𝜌_{𝑗}$ for $𝑖 \neq 𝑗$ , then their row spaces are equal.

Proof:

By Corollary 1.3.6, each row of $𝐵$ is a linear combination of the rows of $𝐴$ ; that is, each row of $𝐵$ is in the rowspace of $𝐴$ . It follows by the Linear Combination Lemma that Rowspace( $𝐵$ ) $\subseteq$ Rowspace( $𝐴$ ), since each element of the rowspace of $𝐵$ is a linear combination of the rows of $𝐵$ , so is a linear combination of a linear combination of the rows of $𝐴$ , i.e. just a linear combination of the rows of $𝐴$ . Because elementary row operations are reversible (by Lemma 1.3.2), the same argument can be applied to show that Rowspace( $𝐵$ ) $\supseteq$ Rowspace( $𝐴$ ); by double-inclusion, the rowspaces are equal.

Corollary 2.3.15: Row-equivalent matrices have the same row space and therefore the same row rank.

Lemma 2.3.16: The nonzero rows of an echelon form matrix make up a linearly independent set.

Proof:

This is a restatement of Lemma 1.3.7 using new terminology.

Definition 2.3.17: The column space of a matrix is the span of the set of its columns. The column rank is the dimension of the column space, the number of linearly independent columns.

Definition 2.3.18: The transpose of a matrix is the result of interchanging its rows and columns, so that the column

𝑗

of the matrix

𝐴

is row

𝑗

𝐴^{⊤}

and vice-versa.

Lemma 2.3.19: Row operations do not change the column rank.

Proof:

By Lemma 1.1.4, row operations do not change the solution space of a system, so they must preserve linear relationships among columns. Therefore, they do not change the number of linearly independent columns, so they preserve column rank.

Remark: Unlike the row space, the column space might change under row operations; it is only the column rank that is invariant under row operations.

Theorem 2.3.20: For any matrix, the row rank and column rank are equal.

Proof:

Any matrix $𝐴$ is row-equivalent to a reduced echelon form matrix, with the same row and column rank as $𝐴$ by Lemmas 2.3.15 and 2.3.19. The row rank of $𝐴$ is the number of nonzero rows in the reduced echelon form matrix, which is equal to the number of leading entries in the reduced echelon form matrix; the column rank of $𝐴$ is also equal to the number of leading entries, since the columns containing leading entries form a subset of the standard basis, so all other columns can be expressed as a linear combination of the rows containing leading entries.

Definition 2.3.21: The rank of a matrix is its row rank or column rank.

Theorem 2.3.22: For linear systems with $𝑛$ unknowns and with matrix of coefficients $𝐴$ , the rank of $𝐴$ is $𝑟$ iff the vector space of solutions of the associated homogeneous system has dimension $(𝑛 - 𝑟)$ .

Proof:

The rank of $𝐴$ is $𝑟$ iff the reduced echelon form matrix of $𝐴$ has $𝑟$ leading variables. There must be $(𝑛 - 𝑟)$ free variables in the reduced echelon form matrix, so the solution space of the associated homogeneous system has dimension $(𝑛 - 𝑟)$ .

Corollary 2.3.23: Where the matrix $𝐴$ is $𝑛 \times 𝑛$ , the following statements are equivalent:

the rank of $𝐴$ is $𝑛$
$𝐴$ is nonsingular
the rows of $𝐴$ form a linearly independent set
the columns of $𝐴$ form a linearly independent set
any linear system whose matrix of coefficients is $𝐴$ has one and only one solution.

Proof:

TODO

Definition 2.3.24: Where

𝑊_{1}, \dots, 𝑊_{𝑘}

are subspaces of a vector space, their sum is the span of their union:

𝑊_{1} + \dots + 𝑊_{𝑘} = [𝑊_{1} \cup \dots \cup 𝑊_{𝑘}]

Definition 2.3.25: The concatenation of the sequences $𝐵_{1}, \dots, 𝐵_{𝑘}$ adjoins them into a single sequence.

𝐵_{1} ⏜ 𝐵_{2} ⏜ \dots ⏜ 𝐵_{𝑘} = ⟨ {\vec{𝛽}}_{1, 1}, \dots, {\vec{𝛽}}_{1, 𝑛_{1}}, \dots, {\vec{𝛽}}_{𝑘, 1}, \dots, {\vec{𝛽}}_{𝑘, 𝑛_{𝑘}} ⟩

Definition 2.3.26: A collection of subspaces

{𝑊_{1}, \dots, 𝑊_{𝑘}}

is independent if no nonzero vector from any

𝑊_{𝑖}

is a linear combination of vectors from the other subspaces. Equivalently, among

{\vec{𝑤}}_{𝑖}

s from different

𝑊_{𝑖}

s, any linear relationship is trivial.

Lemma 2.3.27: Let $𝑉$ be a vector space that is the sum of some of its subspaces, $𝑉 = 𝑊_{1} + \dots + 𝑊_{𝑘}$ . Let $𝐵_{1}, \dots, 𝐵_{𝑘}$ be bases for these subspaces. Then the following are equivalent:

Any $\vec{𝑣} \in 𝑉$ can be expressed as a combination of unique ${\vec{𝑤}}_{𝑖} \in 𝑊_{𝑖}$ , $\vec{𝑣} = {\vec{𝑤}}_{1}, \dots, {\vec{𝑤}}_{𝑘}$ ;
The concatenation $𝐵_{1} ⏜ \dots ⏜ 𝐵_{𝑘}$ is a basis for $𝑉$ ;
The $𝑊_{𝑖}$ s are independent.

Proof: TODO? possibly out of scope

Definition 2.3.28: A vector space

𝑉

is the direct sum (or internal direct sum) of its subspaces

𝑊_{1}, \dots, 𝑊_{𝑘}

𝑉 = 𝑊_{1} + \dots + 𝑊_{𝑘}

and the collection

{𝑊_{1}, \dots, 𝑊_{𝑘}}

is independent. We write

𝑉 = 𝑊_{1} \oplus 𝑊_{2} \oplus \dots \oplus 𝑊_{𝑘}

Remark: If the conditions of Lemma 2.3.27 hold, then

𝑉

is a direct sum of

𝑊_{1}, \dots, 𝑊_{𝑘}

Corollary 2.3.29: The dimension of a direct sum is the sum of the dimensions of its summands.

Proof:

In Lemma 2.3.27, the number of vectors in the concatenated basis is the same as the sum of the number of vectors in each sub-basis.

Definition 2.3.30: When a vector space is the direct sum of two of its subspaces, those subspaces are complements.

Example: In

ℝ^{2}

, the

𝑥

- and

𝑦

-axes are complements.

Lemma 2.3.31: A vector space is the direct sum of two of its subspaces $𝑊_{1}, 𝑊_{2}$ iff $𝑉 = 𝑊_{1} + 𝑊_{2}$ and $𝑊_{1} \cap 𝑊_{2} = {\vec{0}}$ i.e. their intersection is trivial.

Proof:

If $𝑉 = 𝑊_{1} \oplus 𝑊_{2}$ , then by definition of direct sum, $𝑉 = 𝑊_{1} + 𝑊_{2}$ ; furthermore, since $𝑊_{1}$ and $𝑊_{2}$ are independent, the linear combination $\vec{𝑣} = \vec{𝑣}$ for $𝑣 \in 𝑊_{1} \cap 𝑊_{2}$ can only have the trivial solution $\vec{𝑣} = \vec{0}$ if we want a member of $𝑊_{1}$ on the left side and a member of $𝑊_{2}$ on the right, w.l.o.g.

Conversely, if $𝑊_{1} \cap 𝑊_{2}$ then if we express ${\vec{𝑤}}_{0} \in 𝑊_{1}$ as a linear combination of ${\vec{𝑤}}_{1}, \dots, {\vec{𝑤}}_{𝑛} \in 𝑊_{2}$ , $𝑤_{0} = 𝑐_{1} {\vec{𝑤}}_{1} + \dots + 𝑐_{𝑛} {\vec{𝑤}}_{𝑛}$ then ${\vec{𝑤}}_{0}$ must also be in $𝑊_{2}$ , as linear combinations of elements of a vector space are also in that vector space. But the intersection of $𝑊_{1}$ and $𝑊_{2}$ is trivial, so $𝑊_{1}$ and $𝑊_{2}$ satisfy the definition of independence; since they sum to $𝑉$ , they form a direct sum of $𝑉$ .

3 Maps between spaces

3.i Isomorphisms

Definition 3.1.1: An isomorphism between two vector spaces $𝑉$ and $𝑊$ is a map $𝑓 : 𝑉 \to 𝑊$ such that

$𝑓$ is a bijection/correspondence;
$𝑓$ preserves structure: if $𝑣_{1}, 𝑣_{2} \in 𝑉$ then
$𝑓 (𝑣_{1} + 𝑣_{2}) = 𝑓 (𝑣_{1}) + 𝑓 (𝑣_{2})$
and if $𝑣 \in 𝑉$ and $𝑟 \in ℝ$ then
$𝑓 (𝑟 𝑣) = 𝑟 𝑓 (𝑣) .$

(We write $𝑉 ≅ 𝑊$ , read “V is isomorphic to W”, when such a map exists.)

To verify that $𝑓 : 𝑉 \to 𝑊$ is an isomorphism, show that:

$𝑓$ is injective/one-to-one, i.e. $𝑓 ({\vec{𝑣}}_{1}) = {𝑓 (\vec{𝑣})}_{2} \Leftrightarrow {\vec{𝑣}}_{1} = {\vec{𝑣}}_{2} \forall {\vec{𝑣}}_{1}, {\vec{𝑣}}_{2} \in 𝑉$ ;
$𝑓$ is surjective/onto, i.e. $\forall \vec{𝑤} \in 𝑊 \exists \vec{𝑣} \in 𝑉 : 𝑓 (\vec{𝑣}) = \vec{𝑤}$ ;
$𝑓$ preserves addition, i.e. $𝑓 ({\vec{𝑣}}_{1} + {\vec{𝑣}}_{2}) = 𝑓 ({\vec{𝑣}}_{1}) + 𝑓 ({\vec{𝑣}}_{2}) \forall {\vec{𝑣}}_{1}, {\vec{𝑣}}_{2} \in 𝑉$ ;
$𝑓$ preserves scalar multiplication, i.e. $𝑓 (𝑟 \cdot \vec{𝑣}) = 𝑟 \cdot 𝑓 (\vec{𝑣}) \forall \vec{𝑣} \in 𝑉, 𝑟 \in ℝ$ .

Remark: Structure preservation is special. Many bijections do not preserve addition and scalar multiplication.

Definition 3.1.2: An automorphism is an isomorphism of a space with itself.

Example: A dilation map

𝑑_{𝑠} : ℝ^{2} \to ℝ^{2}

that multiplies all vectors by a nonzero scalar

𝑠

is an automorphism of

ℝ^{2}

Example: A rotation or turning map

𝑡_{𝜃}

that rotates all vectors through an angle

𝜃

is an automorphism.

Remark: Automorphisms are relevant to study, despite seeming trivial, because they formalise the intuitive notion that space near the

𝑥

-axis is like space near the

𝑦

-axis.

Lemma 3.1.3: An isomorphism maps the zero vector to the zero vector.

Proof: Where $𝑓 : 𝑉 \to 𝑊$ is an isomorphism, fix some $\vec{𝑣} \in 𝑉$ . Then

𝑓 ({\vec{0}}_{𝑉}) = 𝑓 (0 \cdot \vec{𝑣}) = 0 \cdot 𝑓 (\vec{𝑣}) = {\vec{0}}_{𝑊} .

Lemma 3.1.4: For any map $𝑓 : 𝑉 \to 𝑊$ between vector spaces, the following statements are equivalent:

$𝑓$ preserves structure
$𝑓$ preserves linear combinations of two vectors
$𝑓$ preserves linear combinations of any finite number of vectors

Proof:

TODO (in Hefferon)

Lemma 3.1.5: The inverse of an isomorphism is also an isomorphism.

Proof:

Suppose that $𝑉 ≅ 𝑊$ by $𝑓 : 𝑉 \to 𝑊$ . Because isomorphisms are bijections, $𝑓$ has an inverse $𝑓^{- 1} : 𝑊 \to 𝑉$ .

Suppose that ${\vec{𝑤}}_{1}, {\vec{𝑤}}_{2} \in 𝑊$ . Because it is an isomorphism, $𝑓$ is surjective and $\exists {\vec{𝑣}}_{1}, {\vec{𝑣}}_{2} \in 𝑉 : {\vec{𝑤}}_{1} = 𝑓 ({\vec{𝑣}}_{1}), {\vec{𝑤}}_{2} = 𝑓 ({\vec{𝑣}}_{2})$ . Then

\begin{aligned} 𝑓^{- 1} (𝑐_{1} \cdot {\vec{𝑤}}_{1} + 𝑐_{2} \cdot {\vec{𝑤}}_{2}) & = 𝑓^{- 1} (𝑐_{1} \cdot 𝑓 ({\vec{𝑣}}_{1}) + 𝑐_{2} \cdot 𝑓 ({\vec{𝑣}}_{2})) \\ = 𝑓^{- 1} (𝑓 (𝑐_{1} \cdot {\vec{𝑣}}_{1} + 𝑐_{2} \cdot {\vec{𝑣}}_{2})) \\ = 𝑐_{1} \cdot {\vec{𝑣}}_{1} + 𝑐_{2} \cdot {\vec{𝑣}}_{2} \\ = 𝑐_{1} \cdot 𝑓^{- 1} ({\vec{𝑤}}_{1}) + 𝑐_{2} \cdot 𝑓^{- 1} ({\vec{𝑤}}_{2}) since {\vec{𝑤}}_{1} = 𝑓 ({\vec{𝑣}}_{1}) and {\vec{𝑤}}_{2} = 𝑓 ({\vec{𝑣}}_{2}) . \end{aligned}

Therefore $𝑓^{- 1}$ preserves structure and hence satisfies the necessary conditions to be an isomorphism.

Theorem 3.1.6: Isomorphism is an equivalence relation between vector spaces.

Proof:

Isomorphism is reflexive, since the identity function is an isomorphism, since it is clearly a bijection and preserves structure:

id (𝑐_{1} {\vec{𝑣}}_{1} + 𝑐_{2} {\vec{𝑣}}_{2}) = 𝑐_{1} {\vec{𝑣}}_{1} + 𝑐_{2} {\vec{𝑣}}_{2} = 𝑐_{1} id ({\vec{𝑣}}_{1}) + 𝑐_{2} id ({\vec{𝑣}}_{2}) .

Symmetry holds by Lemma 3.1.5.

For transitivity, suppose that $𝑉 ≅ 𝑊$ and $𝑊 ≅ 𝑈$ , and let $𝑓 : 𝑉 \to 𝑊$ and $𝑔 : 𝑊 \to 𝑈$ be isomorphisms. Then $𝑔 \circ 𝑓$ is bijective, and structure preserving:

\begin{aligned} (𝑓 \circ 𝑔) (𝑐_{1} {\vec{𝑣}}_{1} + 𝑐_{2} {\vec{𝑣}}_{2}) & = 𝑓 (𝑔 (𝑐_{1} {\vec{𝑣}}_{1} + 𝑐_{2} {\vec{𝑣}}_{2})) \\ = 𝑓 (𝑐_{1} 𝑔 ({\vec{𝑣}}_{1}) + 𝑐_{2} 𝑔 ({\vec{𝑣}}_{2})) \\ = 𝑐_{1} 𝑓 (𝑔 ({\vec{𝑣}}_{1})) + 𝑐_{2} 𝑓 (𝑔 ({\vec{𝑣}}_{2})) \\ = 𝑐_{1} (𝑓 \circ 𝑔) ({\vec{𝑣}}_{1}) + 𝑐_{2} (𝑓 \circ 𝑔) ({\vec{𝑣}}_{2}) . \end{aligned}

Lemma 3.1.7: If spaces are isomorphic then they have the same dimension.

Proof:

TODO (in Hefferon)

Lemma 3.1.8: If spaces have the same dimension then they are isomorphic.

Proof:

TODO (in Hefferon)

Theorem 3.1.9: Vector spaces are isomorphic iff they have the same dimension.

Proof:

From Lemma 3.1.7 and Lemma 3.1.8.

Corollary 3.1.10: Every finite-dimensional vector space is isomorphic to exactly one of the $ℝ^{𝑛}$ .

Thus the real spaces ${ℝ^{𝑛} | 𝑛 \in ℕ}$ form a set of canonical representatives of the isomorphism classes.

3.ii Homomorphisms

Definition 3.2.1: A homomorphism or linear map between vector spaces is a function

ℎ : 𝑉 \to 𝑊

that preserves addition and scalar multiplication. Such a function is said to satisfy linearity.

Lemma 3.2.2: A linear map maps the zero vector to the zero vector.

Proof:

The proof is the same as the proof to Lemma 3.1.3.

Lemma 3.2.3: The following statements are equivalent for any map $𝑓 : 𝑉 \to 𝑊$ between vector spaces:

$𝑓$ is a homomorphism;
$𝑓 (𝑐_{1} \cdot {\vec{𝑣}}_{1} + 𝑐_{2} \cdot {\vec{𝑣}}_{2}) = 𝑐_{1} \cdot 𝑓 ({\vec{𝑣}}_{1}) + 𝑐_{2} \cdot 𝑓 ({\vec{𝑣}}_{2})$ ;
$𝑓 (𝑐_{1} \cdot {\vec{𝑣}}_{1} + \dots + 𝑐_{𝑛} \cdot {\vec{𝑣}}_{𝑛}) = 𝑐_{1} 𝑓 ({\vec{𝑣}}_{1}) + \dots + 𝑐_{𝑛} 𝑓 ({\vec{𝑣}}_{𝑛})$ .

Proof:

TODO (in Hefferon)

Example: The inclusion map

𝜄 : ℝ^{2} \to ℝ^{3}; (\begin{matrix} 𝑥 \\ 𝑦 \end{matrix}) \mapsto (\begin{matrix} 𝑥 \\ 𝑦 \\ 0 \end{matrix})

is a homomorphism.

Example: The derivative is a homomorphism on polynomial spaces (and in general).

Definition 3.2.4: The trace of a square matrix is the sum down the upper-left to bottom-right diagonal. So $Tr : {ℳ︀}_{2 \times 2} \to ℝ$ is:

Tr ((\begin{matrix} 𝑎 & 𝑏 \\ 𝑐 & 𝑑 \end{matrix})) = 𝑎 + 𝑑 .

Remark:

Tr

is a linear map.

Theorem 3.2.5: A homomorphism is determined by its action on a basis: if $𝑉$ is a vector space with basis $⟨ {\vec{𝛽}}_{1}, \dots, {\vec{𝛽}}_{𝑛} ⟩$ , $𝑊$ is a vector space, and ${\vec{𝑤}}_{1}, \dots, {\vec{𝑤}}_{𝑛} \in 𝑊$ (not necessarily distinct), then there exists a homomorphism from $𝑉$ to $𝑊$ sending each ${\vec{𝛽}}_{𝑖}$ to ${\vec{𝑤}}_{𝑖}$ , and that homomorphism is unique.

Proof:

TODO (in Hefferon)

Definition 3.2.6: Let

𝑉

and

𝑊

be vector spaces and let

𝐵 = ⟨ {\vec{𝛽}}_{1}, \dots, {\vec{𝛽}}_{𝑛} ⟩

be a basis for

𝑉

. A function defined on that basis

𝑓 : 𝐵 \to 𝑊

is extended linearly to a function

\hat{𝑓} : 𝑉 \to 𝑊

if, for all

\vec{𝑣} \in 𝑉

s.t.

\vec{𝑣} = 𝑐_{1} \cdot {\vec{𝛽}}_{1} + \dots + 𝑐_{𝑛} \cdot {\vec{𝛽}}_{𝑛}

, the action of the map is

\hat{𝑓} (\vec{𝑣}) = 𝑐_{1} \cdot 𝑓 ({\vec{𝛽}}_{1}) + \dots + 𝑐_{𝑛} 𝑓 ({\vec{𝛽}}_{𝑛})

Example (Derivation of $𝑡_{𝜃}$ (rotation)):

(\begin{matrix} 1 \\ 0 \end{matrix}) \mapsto (\begin{matrix} cos 𝜃 \\ sin 𝜃 \end{matrix}); (\begin{matrix} 0 \\ 1 \end{matrix}) \mapsto (\begin{matrix} - sin 𝜃 \\ cos 𝜃 \end{matrix}) .

Extending linearly:

\begin{matrix} 𝑡_{𝜃} ((\begin{matrix} 𝑥 \\ 𝑦 \end{matrix})) = 𝑡_{𝜃} (𝑥 \cdot (\begin{matrix} 1 \\ 0 \end{matrix}) + 𝑦 \cdot (\begin{matrix} 0 \\ 1 \end{matrix})) \\ = 𝑥 \cdot 𝑡_{𝜃} ((\begin{matrix} 1 \\ 0 \end{matrix})) + 𝑦 \cdot 𝑡_{𝜃} (\begin{matrix} 0 \\ 1 \end{matrix}) \\ = 𝑥 \cdot (\begin{matrix} cos 𝜃 \\ sin 𝜃 \end{matrix}) + 𝑦 \cdot (- sin 𝜃, cos 𝜃) \\ = (\begin{matrix} 𝑥 cos 𝜃 - 𝑦 sin 𝜃 \\ 𝑥 sin 𝜃 + 𝑦 cos 𝜃 \end{matrix}) . \end{matrix}

Definition 3.2.7: A linear map from a space into itself

𝑡 : 𝑉 \to 𝑉

is a linear transformation. This is also known as an endomorphism.

Remark: An automorphism is a bijective endomorphism.

Lemma 3.2.8: For vector spaces $𝑉$ and $𝑊$ , the set of linear functions from $𝑉$ to $𝑊$ is itself a vector space, a subspace of the space of all functions from $𝑉$ to $𝑊$ . We denote the space of linear maps from $𝑉$ to $𝑊$ by $ℒ︀ (𝑉, 𝑊)$ .

Alternatively: a linear combination of homomorphisms is also a homomorphism.

Proof:

TODO (in Hefferon)

Lemma 3.2.9: Under a homomorphism, the image of any subspace of the domain is a subspace of the codomain. In particular, the image of the entire space, the range of the homomorphism, is a subspace of the codomain.

That is, given vector spaces $𝑉, 𝑊$ and a homomorphism $ℎ : 𝑉 \to 𝑊$ , $𝑊^{'} ≔ {ℎ (𝑣) : 𝑣 \in 𝑉^{'}} \subseteq 𝑊 \forall 𝑉^{'} \subseteq 𝑉$ where $𝑉^{'}$ and $𝑊^{'}$ are subspaces of $𝑉$ and $𝑊$ respectively.

Proof:

TODO (in Hefferon)

Definition 3.2.10: The range space of a homomorphism $ℎ : 𝑉 \to 𝑊$ is

ℛ︀ (ℎ) = {ℎ (\vec{𝑣}) | \vec{𝑣} \in 𝑉},

sometimes denoted

ℎ (𝑉)

. The dimension of the range space is the map’s rank.

Definition 3.2.11: For any function

ℎ : 𝑉 \to 𝑊

, the set of elements of

𝑉

that map to

\vec{𝑤} \in 𝑊

is the inverse image

ℎ^{- 1} (\vec{𝑤}) = {\vec{𝑣} \in 𝑉 | ℎ (\vec{𝑣}) = \vec{𝑤}} .

Lemma 3.2.12: For any homomorphism the inverse image of a subspace of the range is a subspace of the domain. In particular, the inverse image of the trivial subspace of the range is a subspace of the domain.

Proof:

TODO (in Hefferon)

Definition 3.2.13: The null space, or kernel, of a linear map $ℎ : 𝑉 \to 𝑊$ is the inverse image of ${\vec{0}}_{𝑊}$ .

𝒩︀ (ℎ) = ℎ^{- 1} ({\vec{0}}_{𝑊}) = {\vec{𝑣} \in 𝑉 | ℎ (\vec{𝑣}) = {\vec{0}}_{𝑊}} .

Definition 3.2.14: The dimension of the null space is the map’s nullity.

Theorem 3.2.15 (rank-nullity theorem): Given a linear map $ℎ : 𝑉 \to 𝑊$ ,

Dim (𝑉) = Dim (ℛ︀ (ℎ)) + Dim (𝒩︀ (ℎ)) .

Proof:

TODO (in Hefferon)

Lemma 3.2.16: Under a linear map, the image of a linearly dependent set is linearly dependent.

Proof:

Suppose that $𝑐_{1} {\vec{𝑣}}_{1} + \dots + 𝑐_{𝑛} {\vec{𝑣}}_{𝑛} = {\vec{0}}_{𝑉}$ with some $𝑐_{𝑖}$ nonzero. Apply $ℎ$ to both sides: $ℎ (𝑐_{1} {\vec{𝑣}}_{1} + \dots + 𝑐_{𝑛} {\vec{𝑣}}_{𝑛}) = 𝑐_{1} ℎ ({\vec{𝑣}}_{1}) + \dots + 𝑐_{𝑛} ℎ ({\vec{𝑣}}_{𝑛})$ and $ℎ ({\vec{0}}_{𝑉}) = {\vec{0}}_{𝑊}$ . We still have some $𝑐_{𝑖}$ nonzero, so the set of the $ℎ ({\vec{𝑣}}_{𝑖})$ s is linearly dependent.

Theorem 3.2.17: Where $𝑉$ is an $𝑛$ -dimensional vector space, these are equivalent statements:

$ℎ$ is one-to-one/injective;
$ℎ$ has an inverse from its range to its domain that is a linear map;
$𝒩︀ (ℎ) = {\vec{0}}$ , that is, $nullity (ℎ) = 0$ ;
$rank (ℎ) = 𝑛$ ;
if $⟨ {\vec{𝛽}}_{1}, \dots, {\vec{𝛽}}_{𝑛} ⟩$ is a basis for $𝑉$ then $⟨ ℎ ({\vec{𝛽}}_{1}), \dots, ℎ ({\vec{𝛽}}_{𝑛})$ is a basis for $ℛ︀ (ℎ)$ .

Proof:

TODO (in Hefferon)

Remark: A one-to-one homomorphism is an isomorphism.

3.iii Computing linear maps

Definition 3.3.1: Suppose that $𝑉$ and $𝑊$ are vector space of dimensions $𝑛$ and $𝑚$ with bases $𝐵$ and $𝐷$ , and that $ℎ : 𝑉 \to 𝑊$ is a linear map. If

{Rep}_{𝐷} (ℎ ({\vec{𝛽}}_{1})) = {(\begin{matrix} ℎ_{1, 1} \\ ⋮ \\ ℎ_{𝑚, 1} \end{matrix})}_{𝐷}; \dots = \dots; {Rep}_{𝐷} (ℎ ({\vec{𝛽}}_{𝑛})) = {(\begin{matrix} ℎ_{1, 𝑛} \\ ⋮ \\ ℎ_{𝑚, 𝑛} \end{matrix})}_{𝐷}

then

{Rep}_{𝐵, 𝐷} (ℎ) = {(\begin{matrix} ℎ_{1, 1} & \dots & ℎ_{1, 𝑛} \\ ⋱ & ⋮ \\ ℎ_{𝑚, 𝑛} \end{matrix})}_{𝐵, 𝐷}

is the matrix representation of

ℎ

with respect to

𝐵, 𝐷

Theorem 3.3.2: Assume that $𝑉$ and $𝑊$ are vector spaces of dimensions $𝑛$ and $𝑚$ , and that $ℎ : 𝑉 \to 𝑊$ is a linear map. If $ℎ$ is represented by

{Rep}_{𝐵, 𝐷} (ℎ) = {(\begin{matrix} ℎ_{1, 1} & \dots & ℎ_{1, 𝑛} \\ ⋱ & ⋮ \\ ℎ_{𝑚, 𝑛} \end{matrix})}_{𝐵, 𝐷}

and $\vec{𝑣}$ is represented by

{Rep}_{𝐵 (\vec{𝑣})} = (\begin{matrix} 𝑐_{1} \\ ⋮ \\ 𝑐_{𝑛} \end{matrix})

then the representation of the image of $\vec{𝑣}$ is

{Rep}_{𝐷} (ℎ (\vec{𝑣})) = {(\begin{matrix} 𝑐_{1} ℎ_{1, 1} + \dots + 𝑐_{𝑛} ℎ_{1, 𝑛} \\ ⋮ \\ 𝑐_{1} ℎ_{𝑚, 1} + \dots + 𝑐_{𝑛} ℎ_{𝑚, 𝑛} \end{matrix})}_{𝐷} .

Definition 3.3.3: The matrix-vector product of an $𝑚 \times 𝑛$ matrix and an $𝑛 \times 1$ vector is

(\begin{matrix} 𝑎_{1, 1} & \dots & 𝑎_{1, 𝑛} \\ ⋮ & ⋱ & ⋮ \\ 𝑎_{𝑚, 1} & \dots & 𝑎_{𝑚, 𝑛} \end{matrix}) (\begin{matrix} 𝑣_{1} \\ ⋮ \\ 𝑣_{𝑛} \end{matrix}) = (\begin{matrix} 𝑎_{1, 1} 𝑣_{1} + \dots + 𝑎_{1, 𝑛} 𝑣_{𝑛} \\ ⋮ \\ 𝑎_{𝑚, 1} 𝑣_{1} + \dots + 𝑎_{𝑚, 𝑛} {\vec{𝑣}}_{𝑛} \end{matrix}) .

Theorem 3.3.4: Any matrix represents a homomorphism between vector spaces of appropriate dimensions, with respect to any pair of bases.

Proof:

TODO (in Hefferon)

Theorem 3.3.5: The rank of a matrix equals the rank of any map that it represents.

Proof:

TODO (in Hefferon)

Definition 3.3.7: A linear map that is one-to-one and onto is nonsingular, otherwise it is singular. That is, a linear map is nonsingular iff it is an isomorphism.

Lemma 3.3.8: A nonsingular map is represented by a square matrix. A square matrix represents nonsingular maps iff it is a nonsingular matrix. Thus, a matrix represents an isomorphism iff it is nonsingular.

Proof:

Assume that the homomorphism $ℎ : 𝑉 \to 𝑊$ is nonsingular. Thus by Corollary 3.3.6, for any matrix $𝐻$ representing $ℎ$ , $𝐻$ has full column rank and full row rank. Since a matrix’s row rank is equal to its column rank, the number of rows is equal to the number of columns and so $𝐻$ is a square matrix; since it has full rank, it is nonsingular.

Conversely, assume that $𝐻$ is a square nonsingular $𝑛 \times 𝑛$ matrix. To be nonsingular, it must have full row and column rank, which is true iff $ℎ$ is an isomorphism, by Lemma 3.1.7, since the domain and codomain have the same dimension.

3.iii.i Computing range and null spaces

TODO - rewatch end of lecture

3.iv Matrix operations

Theorem 3.4.1: Let

ℎ, 𝑔 : 𝑉 \to 𝑊

be linear maps represented with respect to bases

𝐵, 𝐷

by the matrices

𝐻

and

𝐺

and let

𝑟

be a scalar. Then with respect to

𝐵, 𝐷

the linear map

𝑟 \cdot ℎ : 𝑉 \to 𝑊

is represented by

𝑟 𝐻

and the map

ℎ + 𝑔 : 𝑉 \to 𝑊

is represented by

𝐻 + 𝐺

Definition 3.4.2: A zero matrix has all entries zero. We write

𝑍_{𝑛 \times 𝑚}

𝑍

0_{𝑛 \times 𝑚}

or just

0

Lemma 3.4.3: The composition of linear maps is linear.

Proof:

Let $ℎ : 𝑉 \to 𝑊$ and $𝑔 : 𝑊 \to 𝑈$ be linear.

\begin{aligned} (𝑔 \circ ℎ) (𝑐_{1} \cdot {\vec{𝑣}}_{𝑤} + 𝑐_{2} \cdot {\vec{𝑣}}_{2}) & = 𝑔 (ℎ (𝑐_{1} \cdot {\vec{𝑣}}_{1} + 𝑐_{2} \cdot {\vec{𝑣}}_{2})) \\ = 𝑔 (𝑐_{1} \cdot ℎ ({\vec{𝑣}}_{1}) + 𝑐_{2} \cdot ℎ ({\vec{𝑣}}_{2})) \\ = 𝑐_{1} \cdot 𝑔 (ℎ ({\vec{𝑣}}_{1})) + 𝑐_{2} \cdot 𝑔 (ℎ ({\vec{𝑣}}_{2})) \\ = 𝑐_{1} \cdot (𝑔 \circ ℎ) ({\vec{𝑣}}_{1}) + 𝑐_{2} \cdot (𝑔 \circ ℎ) ({\vec{𝑣}}_{2}) \end{aligned}

hence $𝑔 \circ ℎ$ is linear.

Theorem 3.4.4: A composition of linear maps is represented by the matrix product of the representations.

Proof:

TODO (in Hefferon)

(TODO: arrow diagrams)

Remark: Matrix multiplication is not commutative in general.

Theorem 3.4.5: If $𝐹, 𝐺, 𝐻$ are matrices, and the matrix products are defined, then the product is associate and distributes over matrix addition.

Proof:

Associativity holds because matrix multiplication represents function composition, which is associative.

Distributivity is similar, coming from the linearity of linear maps.

Lemma 3.4.6: In a product of two matrices

𝐺

and

𝐻

, the columns of

𝐺 𝐻

are formed by taking

𝐺

times the columns of

𝐻

and the rows of

𝐺 𝐻

are formed by taking the rows of

𝐺

times

𝐻

Definition 3.4.7: A matrix with all zeros except for a $1$ in the $𝑖, 𝑗$ th entry is an $𝑖, 𝑗$ -unit matrix or matrix unit.

Left-multiplying the $𝑖, 𝑗$ -unit matrix copies row $𝑗$ of the multiplicand into row $𝑖$ of the result; right-multiplying by the $𝑖, 𝑗$ -unit copies column $𝑖$ of the multiplicand into column $𝑗$ of the result.

Scaling a unit matrix scales the result.

Definition 3.4.8: The main diagonal or leading diagonal or principle diagonal goes from the upper left to lower right.

Definition 3.4.9: An identity matrix is square and every entry is 0 except for 1s in the leading diagonal.

\forall 𝐴 \in ℝ^{𝑛 \times 𝑛}, 𝐼_{𝑛} 𝐴 = 𝐴 𝐼_{𝑛} 𝐴 .

Definition 3.4.10: A diagonal matrix is square and has 0s off of the main diagonal.

Definition 3.4.11: A permutation matrix is square and is all 0s except for a single 1 in each row and column.

Left-multiplying by a permutation matrix permutes rows, right-multiplying permutes columns.

Definition 3.4.12: The elementary reduction matrices result from applying a single Gaussian operation to an identity matrix.

$𝐼 \overset{𝑘 𝜌_{𝑖}}{\to} 𝑀_{𝑖} (𝑘)$ for $𝑘 \neq 0$ (think Multiply);
$𝐼 \overset{𝜌_{𝑖} \leftrightarrow 𝜌_{𝑗}}{\to} 𝑃_{𝑖, 𝑗}$ for $𝑖 \neq 𝑗$ (think Permute);
$𝐼 \overset{𝑘 𝜌_{𝑖} + 𝜌_{𝑗}}{\to} 𝐶_{𝑖, 𝑗} (𝑘)$ for $𝑖 \neq 𝑗$ (think Carry over?)

Lemma 3.4.13: Matrix multiplication can do Gaussian reduction.

Proof:

Clear - just left-multiply by the relevant elementary reduction matrix.

Corollary 3.4.14: For any matrix

𝐻

there are elementary reduction matrices

𝑅_{1}, \dots, 𝑅_{𝑟}

such that

𝑅_{𝑟} \cdot 𝑅_{𝑟 - 1} \dots 𝑅_{1} \cdot 𝐻

is in reduced echelon form.

Definition 3.4.15: If we have

𝜋 \circ 𝜄 = id

, we say that

𝜄

is the right-inverse of

𝜋

, and likewise

𝜋

is the left-inverse of

𝜄

Definition 3.4.16: A function $𝑓$ has a two-sided inverse $𝑔$ if $𝑔$ is a right-inverse and left-inverse. In this case, the inverse in unique.

Note: this means that $𝑓$ is a bijection.

Note: recall that if a linear map has a two-sided inverse, the inverse is also a linear map.

Definition 3.4.17: A matrix

𝐺

is a left-inverse matrix of the matrix

𝐻

𝐺 𝐻

is the identity matrix. It is a right inverse if

𝐻 𝐺

is the identity matrix. A matrix

𝐻

with a two-sided inverse is an invertible matrix. The two-sided inverse is denoted

𝐻^{- 1}

Lemma 3.4.18: If a matrix has both a left inverse and right inverse then the two are equal.

Proof: See Theorem 3.4.19.

Theorem 3.4.19: A matrix is invertible iff it is nonsingular.

Proof:

Given a matrix $𝐻$ , fix spaces of appropriate dimension for the domain and codomain and fix bases for these spaces. With respect to these bases, $𝐻$ represents a map $ℎ$ . The statements are true about the map and therefore they are true about the matrix.

This also proves Lemma 3.4.18.

Lemma 3.4.20: A product of invertible matrices is invertible. That is, if

𝐺, 𝐻

are invertible and

𝐺 𝐻

is defined then

𝐺 𝐻

is invertible and

{(𝐺 𝐻)}^{- 1} = 𝐻^{- 1} 𝐺^{- 1}

Lemma 3.4.21: A matrix

𝐻

is invertible iff it can be written as the product of elementary reduction matrices. We can compute the inverse by applying to the identity matrix the same row steps, in the same order, that Gauss-Jordan reduce

𝐻

Corollary 3.4.22: The inverse of a $2 \times 2$ matrix exists and equals

{(\begin{matrix} 𝑎 & 𝑏 \\ 𝑐 & 𝑑 \end{matrix})}^{- 1} = \frac{1}{𝑎 𝑑 - 𝑏 𝑐} (\begin{matrix} 𝑑 & - 𝑏 \\ - 𝑐 & 𝑎 \end{matrix})

iff $𝑎 𝑑 - 𝑏 𝑐$ .

Proof:

\begin{aligned} (\frac{1}{𝑎 𝑑 - 𝑏 𝑐} (\begin{matrix} 𝑑 & - 𝑏 \\ - 𝑐 & 𝑎 \end{matrix})) (\begin{matrix} 𝑎 & 𝑏 \\ 𝑐 & 𝑑 \end{matrix}) & = \frac{1}{𝑎 𝑑 - 𝑏 𝑐} (\begin{matrix} 𝑎 𝑑 - 𝑏 𝑐 & 𝑑 𝑏 - 𝑏 𝑑 \\ - 𝑎 𝑐 + 𝑎 𝑐 & - 𝑐 𝑏 + 𝑎 𝑑 \end{matrix}) \\ = (\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}); \\ (\begin{matrix} 𝑎 & 𝑏 \\ 𝑐 & 𝑑 \end{matrix}) (\frac{1}{𝑎 𝑑 - 𝑏 𝑐} (\begin{matrix} 𝑑 & - 𝑏 \\ - 𝑐 & 𝑎 \end{matrix})) & = \frac{1}{𝑎 𝑑 - 𝑏 𝑐} (\begin{matrix} 𝑎 𝑑 - 𝑏 𝑐 & - 𝑎 𝑏 + 𝑏 𝑎 \\ 𝑐 𝑑 - 𝑑 𝑐 & - 𝑏 𝑐 + 𝑑 𝑎 \end{matrix}) \\ = (\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}) . \end{aligned}

3.v Change of basis

Definition 3.5.1: The change in basis matrix for bases $𝐵, 𝐷 \subset 𝑉$ is the representation of the identity map $id : 𝑉 \to 𝑉$ with respect to those bases.

{Rep}_{𝐵, 𝐷} (id) = (\begin{matrix} ⋮ & ⋮ \\ {Rep}_{𝐷} ({\vec{𝛽}}_{1}) & \dots & {Rep}_{𝐷} ({\vec{𝛽}}_{𝑛}) \\ ⋮ & ⋮ \end{matrix}) .

Lemma 3.5.2: ${Rep}_{𝐷} (\vec{𝑣}) = {Rep}_{𝐵, 𝐷} (id) \cdot {Rep}_{𝐵} (\vec{𝑣})$ .

Proof:

Trivial.

Lemma 3.5.3: A matrix changes base iff it is nonsingular.

Proof:

TODO: in Hefferon

Corollary 3.5.4: A matrix is nonsingular iff it represents the identity map with respect to some pair of bases.

Theorem 3.5.5: To convert from the matrix $𝐻$ representing a map $ℎ$ with respect to $𝐵, 𝐷$ to the matrix $\hat{𝐻}$ representing $ℎ$ w.r.t $\hat{𝐵}, \hat{𝐷}$ ,

\begin{aligned} \hat{𝐻} = {Rep}_{\hat{𝐵}, \hat{𝐷}} (ℎ) & = {Rep}_{𝐷, \hat{𝐷}} (id) \cdot 𝐻 \cdot {Rep}_{\hat{𝐵}, 𝐵} (id) \\ = {Rep}_{𝐷, \hat{𝐷}} (id) \cdot {Rep}_{𝐵, 𝐷} (id) \cdot {Rep}_{\hat{𝐵}, 𝐵} (id) . \end{aligned}

Proof:

TODO by arrow diagram

Definition 3.5.6: Same-sized matrices

𝐻

and

\hat{𝐻}

are matrix equivalentif there are nonsingular matrices

𝑃, 𝑄

s.t.

\hat{𝐻} = 𝑃 𝐻 𝑄

, that is, we can change bases to get

\hat{𝐻}

from

𝐻

Corollary 3.5.7: Matrix-equivalent matrices represent the same map, with respect to appropriate pairs of bases.

Theorem 3.5.8: Matrix equivalence is an equivalence relation.

Proof:

Matrix equivalence is transitive, since $𝐻 = 𝐼 𝐻 𝐼$ .

Matrix equivalence is symmetric, since if $\hat{𝐻} = 𝑃 𝐻 𝑄$ for nonsingular $𝑃, 𝑄$ , then $𝑃^{- 1} \hat{𝐻} 𝑄^{- 1} = 𝑃^{- 1} 𝑃 𝐻 𝑄 𝑄^{- 1} = 𝐻$ .

Matrix equivalence is transitive, since if $𝐵 = 𝑃 𝐴 𝑄$ and $𝐶 = 𝑅 𝐵 𝑆$ for nonsingular $𝑃, 𝑄, 𝑅, 𝑆$ , then $𝐶 = (𝑅 𝑃) 𝐴 (𝑄 𝑆)$ , with $(𝑅 𝑃)$ and $(𝑄 𝑆)$ nonsingular since the product of nonsingular matrices is nonsingular.

Theorem 3.5.9: Any $𝑚 \times 𝑛$ matrix of rank $𝑘$ is matrix equivalent to the $𝑚 \times 𝑛$ matrix that is all zeros except that the first $𝑘$ diagonal entries are 1.

Definition 3.5.10: This is a block partial-identity form, so called because you have an identity matrix in the top left of the matrix.

Remark: Block partial-identity matrices are projection maps between the same bases.

Remark: All matrices are projection maps with respect to some bases.

Corollary 3.5.11: Matrix equivalence classes are characterised by rank: two same-sized matrices are matrix equivalent iff they have the same rank.

Proof: Two same-sized matrices with the same rank are equivalent to the same block partial-identity matrix.

3.vi Projection

Definition 3.6.1: The orthogonal projection of a vector $\vec{𝑣}$ into the line spanned by a nonzero vector $\vec{𝑠}$ is

{proj}_{[\vec{𝑠}]} (\vec{𝑣}) = \frac{\vec{𝑣} \cdot \vec{𝑠}}{\vec{𝑠} \cdot \vec{𝑠}} \cdot \vec{𝑠} .

Remark:

${proj}_{[\vec{𝑠}]} (\vec{𝑣})$ is a scalar multiple of $\vec{𝑠}$ whose tip lies directly “underneath” the tip of $\vec{𝑣}$ , where the “up” direction is the vector orthogonal to $\vec{𝑠}$ that intersects $\vec{𝑣}$ ; it is orthogonal to $(\vec{𝑣} - {proj}_{[\vec{𝑠}]} (\vec{𝑣}))$ .

Remark:

Another way of thinking about projection is that ${proj}_{[\vec{𝑠}]} (\vec{𝑣})$ is the “shadow” of $\vec{𝑣}$ on $\vec{𝑠}$ , when a light source is shone orthogonally on to $\vec{𝑠}$ .

Remark:

We can derive the projection formula from the above remarks.

${proj}_{[\vec{𝑠}]} (\vec{𝑣}) = 𝑐 \vec{𝑠}$ where $𝑐 \in ℝ$ . Then by Pythagoras, ${| \vec{𝑣} |}^{2} = {| 𝑐 \vec{𝑠} |}^{2} + {| \vec{𝑣} - 𝑐 \vec{𝑠} |}^{2}$ .

Hence

\begin{aligned} \vec{𝑣} \cdot \vec{𝑣} = 𝑐^{2} (\vec{𝑠} \cdot \vec{𝑠}) + \vec{𝑣} \cdot \vec{𝑣} + 𝑐^{2} (\vec{𝑠} \cdot \vec{𝑠}) - 2 𝑐 (\vec{𝑣} \cdot \vec{𝑠}) \\ ⟹ & 2 𝑐 (\vec{𝑣} \cdot \vec{𝑠}) = 2 𝑐^{2} (\vec{𝑠} \cdot \vec{𝑠}) \\ ⟹ & 𝑐 = \frac{\vec{𝑣} \cdot \vec{𝑠}}{\vec{𝑠} \cdot \vec{𝑠}} . \end{aligned}

Therefore ${proj}_{[\vec{𝑠}]} (\vec{𝑣}) = \frac{\vec{𝑣} \cdot \vec{𝑠}}{\vec{𝑠} \cdot \vec{𝑠}} \cdot \vec{𝑠}$ .

TODO: picture

Definition 3.6.2: Vectors

{\vec{𝑣}}_{1}, \dots {\vec{𝑣}}_{𝑘} \in ℝ^{𝑛}

are mutually orthogonal when any two are orthogonal:

\forall 𝑖, 𝑗 \in {1, \dots, 𝑘}, 𝑖 \neq 𝑗, {\vec{𝑣}}_{𝑖} \cdot {\vec{𝑣}}_{𝑗} = 0

Theorem 3.6.3: If the vectors in a set ${{\vec{𝑣}}_{1}, \dots, {\vec{𝑣}}_{𝑘}} \subset ℝ^{𝑛}$ are mutually orthogonal and nonzero then that set is linearly independent.

Proof:

Consider a linear relation among the ${\vec{𝑣}}_{𝑖}$ s: $\vec{0} = 𝑐_{1} {\vec{𝑣}}_{1} + \dots + 𝑐_{𝑘} {\vec{𝑣}}_{𝑘}$ . Taking the dot product of any ${\vec{𝑣}}_{𝑖}$ with both sides of the equation gives ${\vec{𝑣}}_{𝑖} \cdot (𝑐_{1} {\vec{𝑣}}_{1} + \dots + 𝑐_{𝑘} {\vec{𝑣}}_{𝑘}) = {\vec{𝑣}}_{𝑖} \cdot \vec{0} = 0$ . Since, for $𝑖 \neq 𝑗$ , ${\vec{𝑣}}_{𝑖} \cdot {\vec{𝑣}}_{𝑗} = 0$ due to orthogonality, the left side reduces to $𝑐_{𝑖} ({\vec{𝑣}}_{𝑖} \cdot {\vec{𝑣}}_{𝑖})$ , so $𝑐_{𝑖} ({\vec{𝑣}}_{𝑖} \cdot {\vec{𝑣}}_{𝑖}) = 0$ . Since ${\vec{𝑣}}_{𝑖} \cdot {\vec{𝑣}}_{𝑖} \neq 0$ , it must be that $𝑐_{𝑖} = 0$ . This holds for all the $𝑐_{𝑖}$ s, so the only linear relationship among the ${\vec{𝑣}}_{𝑖}$ s is the trivial one, so the set is linearly independent.

Corollary 3.6.4: In a $𝑘$ -dimensional vector space, if the vectors in a size $𝑘$ set are mutually orthogonal and nonzero then that set is a basis for the space.

Proof:

Any linearly independent subset of size $𝑘$ in a $𝑘$ dimensional space is a basis.

Definition 3.6.5: An orthogonal basis for a vector space is a basis of mutually orthogonal vectors.

Theorem 3.6.6 (Gram-Schmidt process): If $⟨ {\vec{𝛽}}_{1}, \dots, {\vec{𝛽}}_{𝑘} ⟩$ is a basis for a subspace of $ℝ^{𝑛}$ then the vectors

\begin{aligned} {\vec{𝜅}}_{1} & = {\vec{𝛽}}_{1}; \\ {\vec{𝜅}}_{2} & = {\vec{𝛽}}_{2} - {proj}_{[{\vec{𝜅}}_{1}]} ({\vec{𝛽}}_{2}); \\ {\vec{𝜅}}_{3} & = {\vec{𝛽}}_{3} - {proj}_{[{\vec{𝜅}}_{1}]} ({\vec{𝛽}}_{3}) - {proj}_{[{\vec{𝜅}}_{2}]} ({\vec{𝛽}}_{3}); \\ ⋮ \\ {\vec{𝜅}}_{𝑘} & = {\vec{𝛽}}_{𝑘} - \sum_{𝑖 = 1}^{𝑘 - 1} {proj}_{[{\vec{𝜅}}_{𝑖}]} ({\vec{𝛽}}_{𝑘}) \end{aligned}

form an orthogonal basis for the same subspace.

Proof:

We show by induction by each $𝜅_{𝑖}$ is nonzero, is in the span of $⟨ {\vec{𝛽}}_{1}, \dots, {\vec{𝛽}}_{𝑖} ⟩$ , and is orthogonal to all the previous $\vec{𝜅}$ s, and thus by Corollary 3.6.4, $⟨ {\vec{𝜅}}_{1}, \dots, {\vec{𝜅}}_{𝑘} ⟩$ is a basis for the same subspace for which $⟨ {\vec{𝛽}}_{1}, \dots, {\vec{𝛽}}_{𝑘} ⟩$ is.

For $𝑖 = 1$ , ${\vec{𝜅}}_{1} = {\vec{𝛽}}_{1}$ , so is clearly nonzero, is vacuously orthogonal to all previous $\vec{𝜅}$ s, and is clearly in the span of $⟨ {\vec{𝛽}}_{1} ⟩$ .

Now assume that $𝜅_{𝑗}$ is nonzero, orthogonal to the previous $\vec{𝜅}$ s and is in the span of $⟨ {\vec{𝛽}}_{1}, \dots, {\vec{𝛽}}_{𝑗} ⟩$ for all $𝑗$ less than some fixed $𝑖 > 1$ .

Then $𝜅_{𝑖} = {\vec{𝛽}}_{𝑖} - \sum_{𝑗 = 1}^{𝑖 - 1} {proj}_{[{\vec{𝜅}}_{𝑗}]} ({\vec{𝛽}}_{𝑖})$ . This sum can be iteratively reduced to be in terms of the $\vec{𝛽}$ s, so $𝜅_{𝑖} \neq 0$ or else there would be a nontrivial linear dependence among the $\vec{𝛽}$ s, which would be a contradiction as we know them to be linearly independent as they are a basis. (Note also that the coefficients of the $\vec{𝛽}$ s must be nonzero as, by the inductive hypothesis, all previous $\vec{𝜅}$ s are nonzero.)

Because $𝜅_{𝑖}$ is a linear combination of $\vec{𝛽}$ s, it is in the span of $⟨ {\vec{𝛽}}_{1}, \dots, {\vec{𝛽}}_{𝑖 + 1} ⟩$ . Also, it is orthogonal to all the previous $\vec{𝜅}$ s: for all $1 < 𝑗 < 𝑖$ ,

\begin{aligned} {\vec{𝜅}}_{𝑗} \cdot {\vec{𝜅}}_{𝑖} & = {\vec{𝜅}}_{𝑗} \cdot ({\vec{𝛽}}_{𝑖} - \sum_{𝑙 = 1}^{𝑖 - 1} {proj}_{[{\vec{𝜅}}_{𝑙}]} ({\vec{𝛽}}_{𝑖})) \\ = {\vec{𝜅}}_{𝑗} \cdot ({\vec{𝛽}}_{𝑖} - {proj}_{[{\vec{𝜅}}_{𝑗}]} ({\vec{𝛽}}_{𝑖})) - \sum_{\begin{matrix} 𝑙 = 1; \\ 𝑙 \neq 𝑗 \end{matrix}}^{𝑖 - 1} {proj}_{[{\vec{𝜅}}_{𝑙}]} ({\vec{𝛽}}_{𝑖}) \\ = 0; \end{aligned}

here the first term is zero since the projection is orthogonal, and the remaining terms are 0 by the inductive hypothesis (all previous $\vec{𝜅}$ s are mutually orthogonal).

By induction, all the $𝜅$ s are nonzero, in the span of the initial basis, and are mutually orthogonal, so also form a basis of the subspace.

Definition 3.6.7: An orthonormal basis is an orthogonal basis with members normalised to length 1.

4 Determinants

4.i Definition

Definition 4.1.1: An $𝑛 \times 𝑛$ determinant is a function $det : {ℳ︀}_{𝑛 \times 𝑛} \to ℝ$ s.t.

$det ({\vec{𝜌}}_{1}, \dots, 𝑘 \cdot {\vec{𝜌}}_{𝑖} + {\vec{𝜌}}_{𝑗}, \dots ., {\vec{𝜌}}_{𝑛}) = det ({\vec{𝜌}}_{1}, \dots, {\vec{𝜌}}_{𝑗}, \dots, {\vec{𝜌}}_{𝑛})$ for $𝑖 \neq 𝑗$
$det ({\vec{𝜌}}_{1}, \dots, {\vec{𝜌}}_{𝑗}, \dots, {\vec{𝜌}}_{𝑖}, \dots, {\vec{𝜌}}_{𝑛}) = - det ({\vec{𝜌}}_{1}, \dots, {\vec{𝜌}}_{𝑗}, \dots, {\vec{𝜌}}_{𝑖}, \dots, {\vec{𝜌}}_{𝑛})$ for $𝑖 \neq 𝑗$
$det ({\vec{𝜌}}_{1}, \dots, 𝑘 \cdot {\vec{𝜌}}_{𝑖}, \dots, {\vec{𝜌}}_{𝑛}) = 𝑘 \cdot det ({\vec{𝜌}}_{1}, \dots, {\vec{𝜌}}_{𝑛})$ for any $𝑘 \in ℝ$
$det (𝐼) = 1$ where $𝐼$ is an identity matrix.

Common notation is $| 𝑇 | = det (𝑇)$ .

Remark: Condition (ii) is redundant because row swaps can be done by a series of row additions and multiplications.

Lemma 4.1.2: A matrix with two identical rows has a determinant of 0.

Proof: Swapping the rows multiplies the determinant by

- 1

, but gives an identical matrix and so the determinant must be the same; therefore the determinant must be zero.

Lemma 4.1.3: A matrix with a zero row has a determinant of 0.

Proof: Multiplying the zero row by a scalar

𝑘

multiplies the determinant by

𝑘

, but does not change the matrix; therefore the determinant must be invariant under scalar multiplication and must be equal to

0

Lemma 4.1.4: A matrix is nonsingular iff its determinant is nonzero.

Proof:

Take a matrix $𝑇$ with determinant zero, and carry out Gauss-Jordan reduction to get to $\hat{𝑇}$ . By Conditions (i) - (iii) of the determinant function, $det (\hat{𝑇}) = 0$ also; if $𝑇$ were nonsingular then it would reduce to the identity matrix, which has determinant equal to 1; therefore, $𝑇$ is singular. If $𝑇$ were nonsingular, it must have a nonzero determinant to begin with.

Lemma 4.1.5: The determinant of an echelon form matrix is the product down the leading diagonal.

Proof: If the echelon matrix is singular then it has a zero row, so the determinant is zero which is the product down the leading diagonal.

If the echelon form matrix is nonsingular, then none of its diagonal entries are zero, so we can divide by those entries and use Condition (iii) to get 1s on the diagonal. Then we eliminate the nondiagonal entries, which by Condition (i) does not change the determinant, to get to the identity matrix, which has determinant 1. So, in this case we also get the determinant being equal to the product down the diagonal.

Lemma 4.1.6: For each $𝑛$ , if there is an $𝑛 \times 𝑛$ determinant function then it is unique.

Proof:

Suppose there are two functions ${det}_{1}, {det}_{2} : {ℳ︀}_{𝑛 \times 𝑛} \to ℝ$ satisfying the properties of Definition 4.1.1 and its consequences Lemmas 4.1.2 - 4.1.5. Given a square matrix M, fix some way of performing Gauss’s method to bring the matrix to echelon form. By using this fixed reduction, we can compute the value that these two functions must return on $𝑀$ , and they must return the same value (by Lemma 4.1.5). Since they give the same output on every input, they are the same function.

Definition 4.1.7: Let $𝑉$ be a vector space. A map $𝑓 : 𝑉^{𝑛} \to ℝ$ is multilinear if

$𝑓 ({\vec{𝜌}}_{1}, \dots, \vec{𝑣} + \vec{𝑤}, \dots, {\vec{𝜌}}_{𝑛}) = 𝑓 ({\vec{𝜌}}_{1}, \dots, \vec{𝑣}, \dots, {\vec{𝜌}}_{𝑛}) + 𝑓 ({\vec{𝜌}}_{1}, \dots, \vec{𝑤}, \dots, {\vec{𝜌}}_{𝑛})$
$𝑓 ({\vec{𝜌}}_{1}, \dots, 𝑘 \cdot \vec{𝑣}, \dots, {\vec{𝜌}}_{𝑛}) = 𝑘 \cdot 𝑓 ({\vec{𝜌}}_{1}, \dots, \vec{𝑣}, \dots, {\vec{𝜌}}_{𝑛})$

Lemma 4.1.8: Determinants are multilinear.

Proof:

Property (ii) here is just Condition (iii) in Definition 4.1.1, so we need only verify property (i).

TODO

Corollary 4.1.9: Determinants can be expressed as a sum of determinants of matrices with only one nonzero value in each row, or as a linear combination of permutation matrices.

Example:

\begin{aligned} det (\begin{matrix} 1 & 2 \\ 3 & 4 \end{matrix}) & = det (\begin{matrix} 1 & 0 \\ 3 & 0 \end{matrix}) + det (\begin{matrix} 1 & 0 \\ 0 & 4 \end{matrix}) + det (\begin{matrix} 0 & 2 \\ 3 & 0 \end{matrix}) + det (\begin{matrix} 0 & 2 \\ 0 & 4 \end{matrix}) \\ = det (\begin{matrix} 1 & 0 \\ 0 & 4 \end{matrix}) + det (\begin{matrix} 0 & 2 \\ 3 & 0 \end{matrix}) because an all-zero column gives a 0 determinant \\ = 4 det (\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}) + 6 det (\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}) . \end{aligned}

Definition 4.1.10: An $𝑛$ -permutation is a bijective function on the first $𝑛$ positive integers $Φ : {1, \dots, 𝑛} \to {1, \dots, 𝑛}$ .

In a permutation, each number $1, \dots, 𝑛$ is an output associated with exactly one input. We sometimes denote a permutation as the sequence $Φ = ⟨ Φ (1), \dots, Φ (𝑛) ⟩$ .

Definition 4.1.11: The permutation expansion for determinants is

| 𝑇 | = \sum_{𝑖 = 1}^{𝑛} [| 𝑃_{Φ_{𝑖}} | \cdot \prod_{𝑗 = 1}^{𝑛} 𝑡_{𝑗, Φ_{𝑖} (𝑗)}]

where $Φ_{1}, \dots, Φ_{𝑛!}$ are all of the $𝑛$ -permutations, and $𝑃_{Φ_{𝑖}}$ is the permutation matrix corresponding to the permutation $Φ_{𝑖}$ .

This is derived from using both conditions of multilinearity to break up the matrix into multiple matrices corresponding to each permutation, and then extracting the relevant coefficients.

Theorem 4.1.12: For each $𝑛$ there is an $𝑛 \times 𝑛$ determinant functions.

Proof:

By Lemma 4.1.19.

Theorem 4.1.13: The determinant of a matrix is equal to the determinant of its tranpose.

Proof:

TODO (in Hefferon)

Corollary 4.1.14: A matrix with two equal columns is singular. Column swaps change the sign of a determinant. Determinants are multilinear in their columns.

Proof:

By transposition.

Definition 4.1.15: In a permuation

Φ = ⟨ \dots, 𝑘, \dots, 𝑗, \dots ⟩

, elements such that

𝑘 > 𝑗

are in an inversion of their natural order.

Lemma 4.1.16: A row-swap in a permutation matrix changes the number of inversions from even to odd, or from odd to even; it changes the parity of the number of inversions.

Proof:

If we swap adjacent rows, all other row relations remain unchanged, and we either create or remove an inversion between the two rows we changed. Hence the parity changes.

To swap non-adjacent rows $𝑖$ and $𝑗$ (with $𝑗 > 𝑖$ ), we can instead swap adjacent rows $(𝑗 - 𝑖)$ times ( $𝑖 \leftrightarrow 𝑖 + 1, 𝑖 + 1 \leftrightarrow 𝑖 + 2, \dots, 𝑗 - 1 \leftrightarrow 𝑗$ ), followed by $(𝑗 - 𝑖 - 1)$ row swaps back up; this is the sum of two consecutive numbers which is odd, so the parity changes an odd number of times, so the parity changes.

Definition 4.1.17: The signum of a permutation

sgn (Φ)

is −1 if the number of inversions in

Φ

is odd, and +1 if the number of inversions is even.

Corollary 4.1.18: If a permutation matrix has an odd number of inversions then swapping it to the identity takes an odd number of swaps. If it has an even number of inversions that swapping to the identity takes an even number.

Proof:

The identity matrix has zero inversions. To change an odd number to zero requires an odd number of swaps, and to change an even number to zero requires an even number of swaps.

Lemma 4.1.19: The function $𝑑 : {ℳ︀}_{𝑛 \times 𝑛} \to ℝ$ s.t.

𝑑 (𝑇) = \sum_{𝑖 = 1}^{𝑛} [sgn (Φ) \cdot \prod_{𝑗 = 1}^{𝑛} 𝑡_{𝑗, Φ_{𝑖} (𝑗)}]

is a determinant.

Proof:

We check the four conditions from Definition 4.1.1.

Condition (iv) holds because in the expansion of $𝑑 (𝐼)$ , the only nonzero term is the one corresponding to the identity permutation, which has a signum of 1, hence the determinant is 1.

For Condition (iii), suppose $𝑇 \overset{𝑘 𝜌_{𝑙}}{\to} \hat{𝑇}$ . Then

\begin{aligned} 𝑑 (\hat{𝑇}) & = \sum_{𝑖 = 1}^{𝑛} [sgn (Φ_{𝑖}) \cdot \prod_{𝑗 = 1}^{𝑛} {\hat{𝑡}}_{𝑗, Φ_{𝑖} (𝑗)}] \\ = \sum_{𝑖 = 1}^{𝑛} [sgn (Φ_{𝑖}) \cdot 𝑘 \cdot 𝑡_{𝑙, Φ_{𝑖} (𝑙)} \cdot \prod_{\begin{matrix} 1 \leq 𝑗 \leq 𝑛; \\ 𝑗 \neq 𝑙 \end{matrix}} 𝑡_{𝑗, Φ_{𝑖} (𝑗)}] \\ = 𝑘 \cdot \sum_{𝑖 = 1}^{𝑛} [sgn (Φ_{𝑖}) \cdot \prod_{𝑗 = 1}^{𝑛} 𝑡_{𝑗, Φ_{𝑖} (𝑗)} \\ = 𝑘 \cdot 𝑑 (𝑇) . \end{aligned}

For Condition (i), suppose $𝑇 \overset{𝑘 𝜌_{𝑙} + 𝜌_{𝑚}}{\to} \hat{𝑇}$ . Then

\begin{aligned} 𝑑 (\hat{𝑇}) & = \sum_{𝑖 = 1}^{𝑛} [sgn (Φ_{𝑖}) \cdot \prod_{𝑗 = 1}^{𝑛} {\hat{𝑡}}_{𝑗, Φ_{𝑖} (𝑗)}] \\ = \sum_{𝑖 = 1}^{𝑛} [sgn (Φ_{𝑖}) \cdot (𝑘 𝑡_{𝑙, Φ_{𝑖} (𝑚)} + 𝑡_{𝑚, Φ_{𝑖} (𝑚)}) \cdot \prod_{\begin{matrix} 1 \leq 𝑗 \leq 𝑛; \\ 𝑗 \neq 𝑚 \end{matrix}} 𝑡_{𝑗, Φ_{𝑖} (𝑗)}] \\ = \sum_{𝑖 = 1}^{𝑛} [sgn (Φ_{𝑖}) \cdot 𝑘 \cdot 𝑡_{𝑙, Φ_{𝑖} (𝑚)} \cdot \prod_{\begin{matrix} 1 \leq 𝑗 \leq 𝑛; \\ 𝑗 \neq 𝑚 \end{matrix}} 𝑡_{𝑗, Φ_{𝑖} (𝑗)}] \\ + \sum_{𝑖 = 1}^{𝑛} [sgn (Φ_{𝑖}) \cdot 𝑡_{𝑚, Φ_{𝑖} (𝑚)} \cdot \prod_{\begin{matrix} 1 \leq 𝑗 \leq 𝑛; \\ 𝑗 \neq 𝑚 \end{matrix}} 𝑡_{𝑗, Φ_{𝑖} (𝑗)}] by distributivity of addition over multiplication \\ = 𝑘 \cdot \sum_{𝑖 = 1}^{𝑛} [sgn (Φ_{𝑖}) \cdot 𝑡_{𝑙, Φ_{𝑖} (𝑚)} \cdot \prod_{\begin{matrix} 1 \leq 𝑗 \leq 𝑛; \\ 𝑗 \neq 𝑚 \end{matrix}} 𝑡_{𝑗, Φ_{𝑖} (𝑗)}] + 𝑑 (𝑇) \\ = 𝑑 (𝑇) \end{aligned}

since the first sum is the determinant of the matrix with row $𝑙$ the same as row $𝑚$ .

Condition (ii) follows from Condition (i).

Corollary 4.1.20: There exists a determinant function

det : {ℳ︀}_{𝑛 \times 𝑛} \to ℝ

for every

𝑛

4.ii Geometry of determinants

Definition 4.2.1: In $ℝ^{𝑛}$ the box or parallelepiped formed by $⟨ {\vec{𝑣}}_{1}, \dots, {\vec{𝑣}}_{𝑛} ⟩$ is the set ${𝑡_{1} {\vec{𝑣}}_{1} + \dots + 𝑡_{𝑛} {\vec{𝑣}}_{𝑛} | 𝑡_{1}, \dots, 𝑡_{𝑛} \in [0, 1]}$ .

Then the signed area of the box, denoted $△$ , is $| (\begin{matrix} {\vec{𝑣}}_{1} & \dots & {\vec{𝑣}}_{𝑛} \end{matrix}) |$ .

Definition 4.2.2: The sign of the determinant reflects the orientation or sense of the box.

Theorem 4.2.3: A transformation $𝑡 : ℝ^{𝑛} \to ℝ^{𝑛}$ changes the size of all boxes by the same factor, namely the size of the image of a box $| 𝑆 |$ is $| 𝑇 |$ times the size of the box $| 𝑆 |$ where $𝑇$ is the matrix representing $𝑡$ with respect to the standard basis.

That is, the determinant of a product is the product of the determinants; $| 𝑇 𝑆 | = | 𝑇 | \cdot | 𝑆 |$ .

Proof:

Suppose $𝑇$ is singular and thus does not have an inverse. Note that if $𝑇 𝑆$ is invertible then there is an $𝑀$ s.t. $(𝑇 𝑆) 𝑀 = 𝐼$ , so $𝑇 (𝑆 𝑀) = 𝐼$ , so $𝑇$ is invertible. The contrapositive of that observation is that if $𝑇$ is not invertible then neither is $𝑇 𝑆$ - if $det (𝑇) = 0$ then $| 𝑇 𝑆 | = 0$ .

Then suppose that $𝑇$ is nonsingular. Any nonsingular matrix factorises into a product of elementary matrices $𝑇 = 𝐸_{1} 𝐸_{2} \dots 𝐸_{𝑟}$ . Then if $| 𝐸 𝑆 | = | 𝐸 | \cdot | 𝑆 |$ for all matrices $𝑆$ and elementary matrices $𝐸$ , then $| 𝑇 𝑆 | = | 𝐸_{1} 𝐸_{2} \dots 𝐸_{𝑟} | = | 𝐸_{1} | \dots | 𝐸_{𝑟} | \cdot | 𝑆 | = | 𝐸_{1} 𝐸_{2} \dots 𝐸_{𝑟} | \cdot | 𝑆 | = | 𝑇 | | 𝑆 |$ .

TODO: prove that determinants of elementary matrices are multiplicative.

Corollary 4.2.4: If a matrix is invertible then the determinant of its inverse is the reciprocal of its inverse, i.e.

det (𝑇^{- 1}) = {(det (𝑇))}^{- 1}

Definition 4.2.5: The volume of a box is the absolute value of the determinant of a matrix with those vectors as columns.

Cramer’s rule

Think about a linear system as being a set of vectors forming a parallelogram, and a target point being the far point of a larger, stretched parallelogram. Then we want to find the factors by which we scale the parallelogram to get the larger one.

TODO: diagram

Theorem 4.2.6 (Cramer's rule): Let

𝐴

be an

𝑛 \times 𝑛

matrix with a nonzero determinant, let

\vec{𝑏}

be an

𝑛

-tall column vector, and consider the linear system

𝐴 \vec{𝑥} = \vec{𝑏}

. For any

𝑖 \in {1, \dots, 𝑛}

let

𝐵_{𝑖}

be the matrix obtained by substituting

\vec{𝑏}

for … TODO

note: this is not very efficient.

4.iii Laplace’s expansion

Definition 4.3.1: For any $𝑛 \times 𝑛$ matrix $𝑇$ , the $(𝑛 - 1) \times (𝑛 - 1)$ matrix formed by deleting row $𝑖$ and column $𝑗$ of $𝑇$ is the $𝑖, 𝑗$ -minor of $𝑇$ .

The $𝑖, 𝑗$ -cofactor $𝑇_{𝑖, 𝑗}$ of $𝑇$ is ${(- 1)}^{𝑖 + 𝑗}$ times the determinant of the $𝑖, 𝑗$ minor of $𝑇$ .

Theorem 4.3.2 (Laplace’s formula): Where $𝑇$ is an $𝑛 \times 𝑛$ matrix, we can find the determinant by expanding by cofactors on any row $𝑖$ or column $𝑗$ .

\begin{aligned} | 𝑇 | & = 𝑡_{𝑖, 1} \cdot 𝑇_{𝑖, 1} + 𝑡_{𝑖, 2} \cdot 𝑇_{𝑖, 2} + . . + 𝑡_{𝑖, 𝑛} \cdot 𝑇_{𝑖, 𝑛} for some row 𝑖 \\ = 𝑡_{1, 𝑗} \cdot 𝑇_{1, 𝑗} + 𝑡_{2, 𝑗} \cdot 𝑇_{2, 𝑗} + . . + 𝑡_{𝑛, 𝑗} \cdot 𝑇_{𝑛, 𝑗} for some column 𝑗 \end{aligned}

Proof:

TODO (exercise in Hefferon)

Definition 4.3.3: The matrix adjoint (or adjugate) to the square matrix $𝑇$ is

adj (𝑇) = (\begin{matrix} 𝑇_{1, 1} & 𝑇_{2, 1} & \dots & 𝑇_{𝑛, 1} \\ 𝑇_{1, 2} & 𝑇_{2, 2} & \dots & 𝑇_{𝑛, 2} \\ ⋮ & ⋮ & ⋮ \\ 𝑇_{1, 𝑛} & 𝑇_{2, 𝑛} & \dots & 𝑇_{𝑛, 𝑛} \end{matrix}) .

Note the entries are transposed from what we’d expect - ${adj (𝑇)}_{𝑖, 𝑗} = 𝑇_{𝑗, 𝑖}$ .

Theorem 4.3.4: Where $𝑇$ is a square matrix, $𝑇 \cdot adj (𝑇) = adj (𝑇) \cdot 𝑇 = | 𝑇 | \cdot 𝐼$ . Thus if $𝑇$ has an inverse, i.e. $| 𝑇 | \neq 0$ , then $𝑇^{- 1} = {(| 𝑇 |)}^{- 1} \cdot adj (𝑇)$ .

Proof:

The diagonal elements of $𝑇 \cdot adj (𝑇)$ are all equal to $| 𝑇 |$ , as they are Laplace expansions, $𝑡_{𝑖, 1} 𝑇_{𝑖, 1} + \dots + 𝑡_{𝑖, 𝑛} 𝑇_{𝑖, 𝑛}$ .

Then an element in column $𝑖$ and row $𝑗$ , with $𝑖 \neq 𝑗$ , is equal to $𝑡_{𝑖, 1} 𝑇_{𝑗, 1} + \dots + 𝑡_{𝑖, 𝑛} 𝑇_{𝑗, 𝑛}$ , which is the Laplace expansion for a matrix with row $𝑖$ equal to row $𝑗$ , which must be equal to zero.

Hence $𝑇 \cdot adj (𝑇) = | 𝑇 | \cdot 𝐼$ .

Remark: This is also not an efficient method of calculating matrix inverses, unless the matrix is sparse (i.e. mostly zeros).

5 Similarity

5.i Complex vector spaces

From now on, scalars will be complex.

Theorem 5.1.1:

Let $𝑝 (𝑥)$ be a polynomial. If $𝑑 (𝑥)$ is a non-zero polynomial then there are quotient and remainder polynomials $𝑞 (𝑥), 𝑟 (𝑥)$ s.t. $𝑝 (𝑥) = 𝑑 (𝑥) 𝑞 (𝑥) + 𝑟 (𝑥)$ where the degree of $𝑟 (𝑥)$ is strictly less than the degree of $𝑑 (𝑥)$ .

Corollary 5.1.2: The remainder when $𝑝 (𝑥)$ is divided by $(𝑥 - 𝜆)$ is the constant polynomial $𝑟 (𝑥) = 𝑝 (𝜆)$ .

Proof:

The remainder must be a constant polynomial as it has a degree less than one. Note that $𝑝 (𝑥) = (𝑥 - 𝜆) 𝑞 (𝑥) + 𝑟 (𝑥)$ ; substituting in $𝑥 = 𝜆$ gives $𝑝 (𝜆) = (𝜆 - 𝜆) 𝑞 (𝜆) + 𝑟 (𝜆) = 𝑟 (𝜆)$ , so $𝑟 (𝜆) = 𝑝 (𝜆)$ ; but $𝑟$ is a constant so $𝑟 (𝑥) = 𝑝 (𝜆)$ for all $𝑥$ .

Corollary 5.1.3: If $𝜆$ is a root of the polynomial $𝑝 (𝑥)$ , then $(𝑥 - 𝜆)$ is a factor of $𝑝 (𝑥)$ .

Proof: By Corollary 5.1.2,

𝑝 (𝑥) = (𝑥 - 𝜆) 𝑞 (𝑥) + 𝑝 (𝜆)

, but since

𝜆

is a root of

𝑝 (𝑥)

𝑝 (𝜆) = 0

; hence

(𝑥 - 𝜆) ∣ 𝑝 (𝑥)

Theorem 5.1.4: Any constant or linear polynomial is irreducible over the reals. A quadratic polynomial is irreducible over the reals iff its discriminant is negative. No cubic or higher-degree polynomial is irreducible over the reals.

Corollary 5.1.5: Any polynomial with real coefficients factors into a product of linear and irreducible quadratic polynomials with real coefficients. That factorisation is unique; any two factorisations have the same factors raised to the same powers.

Theorem 5.1.6 (Fundamental Theorem of Algebra): Polynomials with complex coefficients factor into linear polynomials with complex coefficients. The factorisation is unique.

Remark: The standard basis for

ℂ^{𝑛}

is the same as the standard basis for

ℝ^{𝑛}

5.ii Similarity

Definition 5.2.1: The matrices

𝑇

and

\hat{𝑇}

are similar if there is a nonsingular

𝑃

s.t.

\hat{𝑇} = 𝑃 𝑇 𝑃^{- 1}

Remark: The zero matrix is similar only to itself (since

𝑃 𝑍 𝑃^{- 1} = 𝑃 𝑍 = 𝑍

); the identity matrix is also similar only to itself (

𝑃 𝐼 𝑃^{- 1} = 𝑃 𝑃^{- 1} = 𝐼

Theorem 5.2.2: Similarity is an equivalence relation.

Proof:

Similarity is reflexive: $𝑇 = 𝐼 𝑇 𝐼^{- 1}$ .

Similarity is symmetric: if $\hat{𝑇} = 𝑃 𝑇 𝑃^{- 1}$ , then $𝑇 = 𝑃^{- 1} \hat{𝑇} 𝑃$ .

Similarity is transitive: if $𝐵 = 𝑃 𝐴 𝑃^{- 1}$ and $𝐶 = 𝑄 𝐵 𝑄^{- 1}$ , then $𝐶 = (𝑄 𝑃) 𝐴 𝑃^{- 1} 𝑄^{- 1} = (𝑄 𝑃) 𝐴 {(𝑄 𝑃)}^{- 1}$ .

Remark: Matrix similarity is a special case of matrix equivalence:

𝑆, 𝑇

similar

⟹

𝑆, 𝑇

equivalent, but the converse is not true.

Remark: Some (but not all) similarity classes have a canonical representation of a diagonal form.

Definition 5.2.3: A transformation is diagonalisable if it has a diagonal representation with respect to the same basis for the codomain as for the domain. A diagonalisable matrix is one that is similar to a diagonal matrix:

𝑇

is diagonalisable if there exists nonsingular

𝑃

such that

𝑃 𝑇 𝑃^{- 1}

is diagonal.

Example:

Proposition: This matrix is not diagonalisable:

𝑁 = (\begin{matrix} 0 & 0 \\ 1 & 0 \end{matrix}) .

Proof:

Suppose that there exists a diagonal matrix $𝐷 = 𝑃 𝑁 𝑃^{- 1}$ . Then consider

\begin{aligned} 𝐷^{2} & = 𝑃 𝑁 𝑃^{- 1} 𝑃 𝑁 𝑃^{- 1} \\ = 𝑃 𝑁^{2} 𝑃^{- 1} & = 𝑃 (\begin{matrix} 0 & 0 \\ 0 & 0 \end{matrix}) 𝑃^{- 1} \\ = (\begin{matrix} 0 & 0 \\ 0 & 0 \end{matrix}) . \end{aligned}

But $𝐷^{2} = (\begin{matrix} 𝑑_{1}^{2} & 0 \\ 0 & 𝑑_{2}^{2} \end{matrix})$ , hence $𝑑_{1} = 𝑑_{2} = 0$ . Hence $𝐷$ is the zero matrix, but the only matrix that is similar to the zero matrix is the zero matrix. Contradiction.

Lemma 5.2.4: A transformation $𝑡$ is diagonalisable iff there is a basis $𝐵$ and scalar $𝜆_{1}, \dots, 𝜆_{𝑛}$ s.t. $𝑡 ({\vec{𝛽}}_{𝑖}) = 𝜆_{𝑖} {\vec{𝛽}}_{𝑖}$ for each $𝑖$ .

Proof:

Consider a diagonal representation matrix

{Rep}_{𝐵, 𝐵} (𝑡) = (\begin{matrix} 𝜆_{1} & 0 \\ ⋮ & ⋱ & ⋮ \\ 0 & 𝜆_{𝑛} \end{matrix}) .

Then for a basis element $𝛽_{𝑖}$ ,

{Rep}_{𝐵} (𝑡 ({\vec{𝛽}}_{𝑖})) = {Rep}_{𝐵, 𝐵} (𝑡) {Rep}_{𝐵} ({\vec{𝛽}}_{𝑖}) = (\begin{matrix} 𝜆_{1} & 0 \\ ⋮ & ⋱ & ⋮ \\ 0 & 𝜆_{𝑛} \end{matrix}) (\begin{matrix} 0 \\ ⋮ \\ 1 \\ ⋮ \\ 0 \end{matrix}) = (\begin{matrix} 0 \\ ⋮ \\ 𝜆_{𝑖} \\ ⋮ \\ 0 \end{matrix}) .

Definition 5.2.5: A transformation

𝑡 : 𝑉 \to 𝑉

has a scalar eigenvalue

𝜆

if there is a nonzero eigenvector

\vec{𝜁} \in 𝑉

such that

𝑡 (\vec{𝜁}) = 𝜆 \cdot \vec{𝜁}

Definition 5.2.6: A square matrix

𝑇

has a scalar eigenvalue

𝜆

associated with the nonzero eigenvector

\vec{𝜁}

𝑇 \vec{𝜁} = 𝜆 \cdot \vec{𝜁}

Remark: To find the eigenvalues of a matrix

𝑀

, consider

𝑀 \vec{𝜁} = 𝑥 \vec{𝜁} ⟹ (𝑀 - 𝑥 𝐼) \vec{𝜁} = \vec{0}

. If

𝑀 - 𝑥 𝐼

is nonsingular, then there is exactly one solution which is the trivial one,

\vec{𝜁} = \vec{0}

. Therefore, we solve for

| 𝑀 - 𝑥 𝐼 | = 0

, then for each solution of

𝑥

(the eigenvalues), we can substitute back in to

(𝑀 - 𝑥 𝐼) \vec{𝜁} = \vec{0}

to find an eigenvector

\vec{𝜁}

Remark: If the matrix is upper diagonal or lower diagonal, the polynomial is easy to factorise as it is just the product along the diagonal.

Remark: If there is a repeated root with multiplicity

𝑝

, then that

𝜆_{𝑖}

is an eigenvalue with algebraic multiplicity

𝑝

. In general

𝑝

is greater than or equal to the geometric multiplicity of the eigenvector, i.e. the dimension of the eigenvector space.

Remark: Matrices that are similar have the same eigenvalues, but not necessarily the same eigenvectors.

Definition 5.2.7: The characteristic polynomial of a square matrix

𝑇

is the determinant

| 𝑇 - 𝑥 𝐼 |

where

𝑥

is a scalar variable. The characteristic equation is

| 𝑇 - 𝑥 𝐼 | = 0

. The characteristic polynomial of a transformation

𝑡

is the characteristic polynomial of any matrix representation

{Rep}_{𝐵, 𝐵} (𝑡)

Remark: The characteristic polynomial of an

𝑛 \times 𝑛

matrix, or of a transformation

𝑡 : ℂ^{𝑛} \to ℂ^{𝑛}

, is of degree

𝑛

. See problem sheet for proof that the characteristic polynomial is well-defined, i.e. is the same regardless of of the bases used to represent the transformation.

Lemma 5.2.8: A linear transformation on a nontrivial vector space has at least one eigenvalue.

Proof: Any root of the characteristic polynomial is an eigenvalue; every polynomial of degree

\geq 1

has at least one root in

ℂ

Definition 5.2.9: The eigenspace of a transformation

𝑡

associated with the eigenvalue

𝜆

𝑉_{𝜆}

{\vec{𝜁} | 𝑡 (\vec{𝜁}) = 𝜆 \vec{𝜁}}

. The eigenspace of a matrix is analogous.

Lemma 5.2.10: An eigenspace is a nontrivial subspace of $ℝ^{𝑛}$ .

Proof:

Note that $𝑉_{𝜆}$ is nonempty; it contains the zero vector since $𝑡 (\vec{0}) = \vec{0} = 𝜆 \cdot \vec{0}$ .

Also note that $𝑉_{𝜆}$ contains a nonzero vector because by definition $𝜆$ is an eigenvalue iff $𝑡 (\vec{𝜁}) = 𝜆 \vec{𝜁}$ has a nontrivial solution for $\vec{𝜁}$ .

Finally, $𝑉_{𝜆}$ is closed under linear combinations:

\begin{aligned} 𝑡 (𝑐_{1} {\vec{𝜁}}_{1} + \dots + 𝑐_{𝑛} {\vec{𝜁}}_{𝑛}) & = 𝑐_{1} 𝑡 ({\vec{𝜁}}_{1}) + \dots + 𝑐_{𝑛} 𝑡 ({\vec{𝜁}}_{𝑛}) since transformations are structure-preserving \\ = 𝑐_{1} 𝜆 {\vec{𝜁}}_{1} + \dots + 𝑐_{𝑛} 𝜆 {\vec{𝜁}}_{𝑛} \\ = 𝜆 (𝑐_{1} {\vec{𝜁}}_{1} + \dots + 𝑐_{𝑛} {\vec{𝜁}}_{𝑛}) since the 𝜁 s are eigenvectors with eigenvalue 𝜆, \end{aligned}

hence $𝑡$ maps elements of $𝑉_{𝜆}$ to elements of $𝑉_{𝜆}$ .

Theorem 5.2.11: For any set of distinct eigenvalues of a map or matrix, a set of associated eigenvectors, one per eigenvalue, is linearly independent.

Proof:

By induction on the number of eigenvalues.

For zero eigenvalues, this is trivially true as the set of associated eigenvectors is empty.

Assume true for $𝑘$ distinct eigenvalues.

If there are $𝑘 + 1$ distinct eigenvalues, $𝜆_{1}, \dots, 𝜆_{𝑘 + 1}$ , and let ${\vec{𝑣}}_{1}, \dots, {\vec{𝑣}}_{𝑘 + 1}$ be associated eigenvectors. Suppose that $\vec{0} = 𝑐_{1} {\vec{𝑣}}_{1} + \dots + 𝑐_{𝑘 + 1} {\vec{𝑣}}_{𝑘 + 1}$ . From this we derive two equations: by applying $𝑡$ to both sides, $\vec{0} = 𝑐_{1} 𝜆_{1} {\vec{𝑣}}_{1} + \dots + 𝑐_{𝑘 + 1} 𝜆_{𝑘 + 1} {\vec{𝑣}}_{𝑘 + 1}$ ; and by multiplying by $𝜆_{𝑘 + 1}$ , giving $\vec{0} = 𝜆_{𝑘 + 1} 𝑐_{1} {\vec{𝑣}}_{1} + \dots + 𝜆_{𝑘 + 1} 𝑐_{𝑘 + 1} {\vec{𝑣}}_{𝑘 + 1}$ . Subtract these equations to get $\vec{0} = 𝑐_{1} (𝜆_{𝑘 + 1} - 𝜆_{1}) {\vec{𝑣}}_{1} + \dots + 𝑐_{𝑘} (𝜆_{𝑘 + 1} - 𝜆_{𝑘}) {\vec{𝑣}}_{𝑘}$ . Then the inductive hypothesis tells us that these $𝑘$ vectors are all linearly independent, so there is only a trivial solution to this equation, i.e. $𝑐_{1} (𝜆_{𝑘 + 1} - 𝜆_{1}) = \dots = 𝑐_{𝑘} (𝜆_{𝑘 + 1} - 𝜆_{𝑘}) = 0$ , hence $𝑐_{𝑘 + 1}$ must be zero, so the $𝑘 + 1$ vectors are linearly independent.

Since true for $𝑘 + 1$ if true for $𝑘$ , and true for $𝑘 = 0$ , true for any number of eigenvalues by principle of induction.

Corollary 5.2.12: An $𝑛 \times 𝑛$ matrix with $𝑛$ distinct eigenvalues is diagonalisable.

Proof:

Form a basis of eigenvalues and apply Lemma 5.2.4.

6 Matrix factorisation

6.i LU factorisation

Definition 6.1.1: For an $𝑛 \times 𝑛$ matrix, we take a series of $(𝑛 - 1)$ “macro” transformations (made up of the product of some elementary matrices) $𝐿_{1}, 𝐿_{2}, \dots, 𝐿_{𝑛 - 1}$ that reduce $𝐴$ to echelon form, for now assuming that no row swaps are necessary. Let $𝑈 = 𝐿_{𝑛 - 1} \dots 𝐿_{1} 𝐴$ , $𝐿 = 𝐿_{1}^{- 1} \dots 𝐿_{𝑛 - 1}^{- 1}$ , then the LU factorisation of $𝐴$ is $𝐴 = 𝐿 𝑈$ .

We end up with $𝐿$ being lower triangular with $1$ along the diagonal and $𝑈$ being upper triangular.

What follows is the general procedure for LU factorisation.

Let ${\vec{𝑥}}_{𝑘}$ denote the $𝑘$ th column of the matrix before (macro-)step $𝑘$ . Then $𝐿_{𝑘}$ should be chosen so that

{\vec{𝑥}}_{𝑘} = (\begin{matrix} 𝑥_{1, 𝑘} \\ ⋮ \\ 𝑥_{𝑘, 𝑘} \\ 𝑥_{𝑘 + 1, 𝑘} \\ ⋮ \\ 𝑥_{𝑛, 𝑘} \end{matrix}) \overset{𝐿_{𝑘}}{\to} 𝐿_{𝑘} {\vec{𝑥}}_{𝑘} = (\begin{matrix} 𝑥_{1, 𝑘} \\ ⋮ \\ 𝑥_{𝑘, 𝑘} \\ 0 \\ ⋮ \\ 0 \end{matrix}) .

To do this, we subtract ${𝓁︀}_{𝑗, 𝑘}$ times row $𝑘$ from row $𝑗 > 𝑘$ , where ${𝓁︀}_{𝑗, 𝑘} = \frac{𝑥_{𝑗, 𝑘}}{𝑥_{𝑘, 𝑘}}$ .

Then define ${\vec{𝓁︀}}_{𝑘} ≔ (\begin{matrix} 0 \\ ⋮ \\ 0 \\ {𝓁︀}_{𝑘 + 1, 𝑘} \\ ⋮ \\ {𝓁︀}_{𝑛, 𝑘} \end{matrix})$ . Then $𝐿_{𝑘}$ can be written

𝐿_{𝑘} = 𝐼 - {\vec{𝓁︀}}_{𝑘} {\vec{𝑒}}_{𝑘}^{⊤} .

Remark:

This looks like the dot product of $\vec{𝓁︀}$ and ${\vec{𝑒}}_{𝑘}$ , but is the other way round! This just defines $𝐿_{𝑘}$ to be the identity matrix, with the $𝑘$ th column being $- {\vec{𝓁︀}}_{𝑘}$ .

By the sparsity pattern of ${\vec{𝓁︀}}_{𝑘}$ , we have ${\vec{𝑒}}_{𝑘}^{⊤} {\vec{𝓁︀}}_{𝑘} = 0$ . Therefore

\begin{aligned} (𝐼 - {\vec{𝓁︀}}_{𝑘} {\vec{𝑒}}_{𝑘}^{⊤}) (𝐼 + {\vec{𝓁︀}}_{𝑘} {\vec{𝑒}}_{𝑘}^{⊤}) & = 𝐼 - {\vec{𝓁︀}}_{𝑘} {\vec{𝑒}}_{𝑘}^{⊤} {\vec{𝓁︀}}_{𝑘} {\vec{𝑒}}_{𝑘}^{⊤} \\ = 𝐼 - {\vec{𝓁︀}}_{𝑘} \cdot 0 \cdot {\vec{𝑒}}_{𝑘}^{⊤} \\ = 𝐼 \end{aligned}

so $𝐿_{𝑘}^{- 1} = 𝐼 + {\vec{𝓁︀}}_{𝑘} {\vec{𝑒}}_{𝑘}^{⊤}$ - that is, inverting $𝐿_{𝑘}$ is done by negating the subdiagonal entries.

Remark:

Negating the subdiagonal entries does not in general compute the inverse of a lower-triangular matrix - but if the only non-zero subdiagonal entries are all in the same column, it will work.

Now considering $𝐿 ≔ 𝐿_{1}^{- 1} \dots 𝐿_{𝑛 - 1}^{- 1} = (𝐼 + {\vec{𝓁︀}}_{1} {\vec{𝑒}}_{1}^{⊤}) \dots (𝐼 + {\vec{𝓁︀}}_{𝑛 - 1} {\vec{𝑒}}_{𝑘}^{⊤})$ and taking into consideration the sparsity patterns of the $\vec{𝓁︀} 𝑠$ , ${\vec{𝑒}}_{𝑘}^{⊤} {\vec{𝓁︀}}_{𝑘} = 0$ and so $𝐿 ≔ 𝐼 + {\vec{𝓁︀}}_{1} {\vec{𝑒}}_{1}^{⊤} + \dots + {\vec{𝓁︀}}_{𝑛 - 1} {\vec{𝑒}}_{𝑛 - 1}^{⊤}$ , i.e. the entries in $𝐿$ are just the nonzero subdiagonal entries in the $𝐿_{𝑘}$ s.

Definition 6.1.2:(the LU algorithm)

\begin{aligned} 𝑈 ≔ 𝐴, 𝐿 ≔ 𝐼 \\ for 𝑘 ≔ 1 to 𝑛 - 1 : \\ for 𝑗 ≔ 𝑘 + 1 to 𝑛 : \\ 𝑙_{𝑗, 𝑘} ≔ \frac{𝑢_{𝑗, 𝑘}}{𝑢_{𝑘, 𝑘}} \\ 𝑢_{𝑗, 𝑘 : 𝑛} ≔ 𝑢_{𝑗, 𝑘 : 𝑛} - 𝑙_{𝑗, 𝑘} 𝑢_{𝑘, 𝑘 : 𝑛} \end{aligned}

where $𝑢_{𝑗, 𝑘 : 𝑛}$ denotes the subrow $𝑢_{𝑗, 𝑘}, \dots, 𝑢_{𝑗, 𝑛}$ .

Remark: To minimise memory use, use only one array that contains both

𝐿

and

𝑈

, making the 1s on the diagonal of

𝐿

implicit.

Remark: There are two floating point operations (flops) per modified entry (one multiplication, one subtraction). So approximately

\frac{2}{3} 𝑛^{3}

in the limit (

𝑛^{3}

from O(n^2) flops per each of

𝑛

macro steps).

Remark: But also note that this lends well to parallelism.

Corollary 6.1.3 (Solving linear systems via LU factorisation):

Suppose we have a linear system $𝐴 \vec{𝑥} = \vec{𝑏}$ and an LU factorisation $𝐴 = 𝐿 𝑈$ . Then

𝐿 \underset{\vec{𝑦}}{\underset{⏟}{𝑈 \vec{𝑥}}} = 𝑏,

so we can solve the system by first solving $𝐿 \vec{𝑦} = \vec{𝑏}$ and then $𝑈 \vec{𝑥} = \vec{𝑦}$ .

Thanks to the sparsity pattern of $𝐿$ , the system $𝐿 \vec{𝑦} = \vec{𝑏}$ can be efficiently solved by forward substitution (in the natural way, top down) (?). Similarly, $𝑈 \vec{𝑥} = \vec{𝑦}$ can be solved by backwards substitution (bottom-up).

Remark: Each of these requires about

𝑛^{2}

flops, much less than needed for computing the LU factorisation, hence the overall cost is that of the factorisation,

\frac{2}{3} 𝑛^{3}

in the limit.

Remark: This works well for multiple linear systems with the same matrix

𝐴

and different right-hand sides

\vec{𝑏}

- don’t invert

𝐴

, just LU-factorise it.

Definition 6.1.4: The LU algorithm can give large errors when using floating point arithmetic when we restrict to no row swaps, even when not dividing by 0 (consider if we replaced a zero in the top left with $10^{-} 20$ , then we get something that is pretty close in the pure case, but the floating-point errors are unacceptable). So row swaps are necessary for stability. With row swaps (pivoting), we get PLU factorisation.

Definition 6.1.5: In each macro-step of an LU factorisation,

𝑥_{𝑘, 𝑘}

is called the pivot.

But we might want a different pivot, if $𝑥_{𝑘, 𝑘}$ is zero or small; so carry out a row swap such that the largest value in $𝑥_{𝑘 : 𝑛, 𝑘}$ is the pivot. Recall that a row swap is represented by a permutation matrix.

Now the multipliers in each macro step are at most $1$ by absolute value.

Then we have $𝐿_{𝑛 - 1} 𝑃_{𝑛 - 1} \dots 𝐿_{1} 𝑃_{1} 𝐴 = 𝑈$ , but in fact we can separate the $𝑃$ s and $𝐿$ s and get that $𝑃 𝐴 = 𝐿 𝑈$ where $𝑃 = 𝑃_{𝑛 - 1} \dots 𝑃_{1}$ , and $𝐿$ is a lower triangular matrix related to the $𝐿_{𝑖}$ s, as described below.

Lemma 6.1.6:

Given $𝑈 = 𝐿_{𝑛 - 1} 𝑃_{𝑛 - 1} \dots 𝐿_{1} 𝑃_{1} 𝐴$ , we can rearrange the row operations to give $𝑈 = (𝐿_{𝑛 - 1}^{'} \dots 𝐿_{1}^{'}) (𝑃_{𝑛 - 1} \dots 𝑃_{1}) 𝐴$ where $𝐿_{𝑖}^{'} = (\prod_{𝑗 = 2}^{𝑖} 𝑃_{𝑛 - 𝑗}) 𝐿_{𝑖} (\prod_{𝑗 = 2}^{𝑖} 𝑃_{𝑗})$ . That is, the row operations can be reordered, with the row additions having their subdiagonal entries permuted.

Proof:

\begin{aligned} 𝐿_{𝑛}^{'} \dots 𝐿_{1}^{'} 𝑃_{𝑛} \dots 𝑃_{1} & = 𝐿_{𝑛} (𝑃_{𝑛} 𝐿_{𝑛 - 1} 𝑃_{𝑛}^{- 1}) (𝑃_{𝑛} 𝑃_{𝑛 - 1} 𝐿_{𝑛 - 2} 𝑃_{𝑛 - 1}^{- 1} 𝑃_{𝑛}^{- 1}) \dots (𝑃_{𝑛} \dots 𝑃_{2} 𝐿_{1} 𝑃_{2}^{- 1} \dots 𝑃_{𝑛}^{- 1}) 𝑃_{𝑛} \dots 𝑃_{1} \\ = 𝐿_{𝑛} 𝑃_{𝑛} \dots 𝐿_{1} 𝑃_{1} . \end{aligned}

Remark: The product of the

𝐿_{𝑘}^{'}

s is again lower-triangular and can inverted by negating the subdiagonal entries.

Corollary 6.1.7: With

𝐿 ≔ (𝐿_{𝑛 - 1}^{'} \dots 𝐿_{1}^{'}), 𝑃 ≔ 𝑃_{𝑛 - 1} \dots 𝑃_{1}

, we have that

𝑃 𝐴 = 𝐿 𝑈

, which is a PLU factorisation of

𝐴

Remark: Row swaps are known as partial pivots. Complete pivoting would also involve column swaps.

Definition 6.1.8:(Algorithm for PLU factorisation with partial pivoting)

\begin{aligned} 𝑈 ≔ 𝐴, 𝐿 ≔ 𝐼, 𝑃 ≔ 𝐼 \\ for 𝑘 ≔ 1 to 𝑛 - 1 : \\ select 𝑖 \geq 𝑘 to maximise | 𝑢_{𝑖, 𝑘} | \\ 𝑢_{𝑘, 𝑘 : 𝑛} ⟷ 𝑢_{𝑖, 𝑘 : 𝑛} \\ 𝑙_{𝑘, 1 : 𝑘 - 1} ⟷ 𝑙_{𝑖, 1 : 𝑘 - 1} \\ 𝑝_{𝑘, 1 : 𝑛} ⟷ 𝑝_{𝑖, 1 : 𝑛} \\ for 𝑗 ≔ 𝑘 + 1 to 𝑛 : \\ 𝑙_{𝑗, 𝑘} ≔ \frac{𝑢_{𝑗, 𝑘}}{𝑢_{𝑘, 𝑘}} \\ 𝑢_{𝑗, 𝑘 : 𝑛} ≔ 𝑢_{𝑗, 𝑘 : 𝑛} - 𝑙_{𝑗, 𝑘} 𝑢_{𝑘, 𝑘 : 𝑛} \end{aligned}

Remark: The asymptotic number of flops is still

\frac{2}{3} 𝑛^{3}

, but we now get better numerical stability.

Corollary 6.1.9 (Solving linear systems using PLU factorisation):

\begin{aligned} 𝐴 \vec{𝑥} = \vec{𝑏} \\ 𝑃 𝐴 \vec{𝑥} = 𝑃 \vec{𝑏} \\ 𝐿 \underset{\vec{𝑦}}{\underset{⏟}{𝑈 \vec{𝑥}}} = 𝑃 \vec{𝑏} \\ 𝐿 \vec{𝑦} = 𝑃 \vec{𝑏} \\ Solve for \vec{𝑦} \\ Then solve 𝑈 \vec{𝑥} = \vec{𝑦} . . \end{aligned}

6.ii QR factorisation

factorises $𝐴$ into $𝑄 𝑅$ where $𝑄$ ’s columns are orthogonal, and $𝑅$ is upper-diagonal (or, Right diagonal?)

Recall that if vectors in a set are nonzero and pairwise orthogonal, then that set is linearly independent.

Recall also that ${(𝐴 𝐵)}^{⊤} = 𝐵^{⊤} 𝐴^{⊤}$ and ${(𝐴 𝐵)}^{- 1} = 𝐵^{- 1} 𝐴^{- 1}$ .

We extend orthogonality to matrices.

Definition 6.2.1: A square matrix is orthogonal or orthonormal if its columns have length 1 and are pairwise orthogonal. Equivalently,

𝑄 \in 𝑅^{𝑛 \times 𝑛}

is orthogonal iff

𝑄^{⊤} = 𝑄^{- 1}

, i.e.

𝑄^{⊤} 𝑄 = 𝐼

Lemma 6.2.2: Multiplication by an orthogonal matrix preserves the length of vectors.

Proof:

{| 𝑄 \vec{𝑥} |}^{2} = {(𝑄 \vec{𝑥})}^{𝑇} 𝑄 \vec{𝑥} = {\vec{𝑥}}^{⊤} 𝑄^{⊤} 𝑄 \vec{𝑥} = {\vec{𝑥}}^{⊤} \vec{𝑥} = {| \vec{𝑥} |}^{2} .

Lemma 6.2.3: Similarly, angles are preserved under multiplication by an orthonormal matrix.

Proof:

\begin{aligned} (𝑄 \vec{𝑥}) \cdot (𝑄 \vec{𝑦}) & = {(𝑄 \vec{𝑥})}^{⊤} (𝑄 \vec{𝑦}) \\ = {\vec{𝑥}}^{⊤} 𝑄^{⊤} 𝑄 \vec{𝑦} \\ = {\vec{𝑥}}^{⊤} 𝑄^{- 1} 𝑄 \vec{𝑦} \\ = {\vec{𝑥}}^{⊤} \vec{𝑦} \\ = \vec{𝑥} \cdot \vec{𝑦} . \end{aligned}

Remark:Geometrically, multiplication by an orthogonal matrix is a rotation/reflection.

Definition 6.2.4: A similar definition of orthogonality can be defined for non-square matrices if the columns are non-zero, pairwise orthogonal, and each sum to 1. This definition still satisfies

𝑄^{⊤} 𝑄 = 𝐼

(but!

𝑄 𝑄^{⊤} \neq 𝐼

in general).

Theorem 6.2.5: Every matrix has a QR factorisation.

Proof: Recall the Gram-Schmidt process. We can define a slightly different process to produce an orthonormal basis for vectors ${\vec{𝑎}}_{1}, \dots, {\vec{𝑎}}_{𝑛}$ :

\begin{aligned} {\vec{𝑞}}_{1} = \frac{{\vec{𝑎}}_{1}}{| {\vec{𝑎}}_{1} |} \\ {\vec{𝑞}}_{2} = \frac{{\vec{𝑎}}_{2} - ({\vec{𝑞}}_{1} \cdot {\vec{𝑎}}_{2}) {\vec{𝑞}}_{1}}{| {\vec{𝑎}}_{2} - ({\vec{𝑞}}_{1} \cdot {\vec{𝑎}}_{2}) {\vec{𝑞}}_{1} |} \\ ⋮ \\ {\vec{𝑞}}_{𝑛} = \frac{{\vec{𝑎}}_{𝑛} - ({\vec{𝑞}}_{1} \cdot {\vec{𝑎}}_{𝑛}) {\vec{𝑞}}_{1} - \dots - ({\vec{𝑞}}_{𝑛 - 1} \cdot {\vec{𝑎}}_{𝑛}) {\vec{𝑞}}_{𝑛 - 1}}{| {\vec{𝑎}}_{𝑛} - ({\vec{𝑞}}_{1} \cdot {\vec{𝑎}}_{𝑛}) {\vec{𝑞}}_{1} - \dots - ({\vec{𝑞}}_{𝑛 - 1} \cdot {\vec{𝑎}}_{𝑛}) {\vec{𝑞}}_{𝑛 - 1} |} . \end{aligned}

Defining $𝑟_{𝑖, 𝑗} = {\vec{𝑞}}_{𝑖} \cdot {\vec{𝑎}}_{𝑗}$ for $𝑖 < 𝑗$ , and $𝑟_{𝑖, 𝑖} = | {\vec{𝑎}}_{𝑖} - ({\vec{𝑞}}_{1} \cdot {\vec{𝑎}}_{𝑖}) {\vec{𝑞}}_{1} - \dots - ({\vec{𝑞}}_{𝑖 - 1} \cdot {\vec{𝑎}}_{𝑖}) {\vec{𝑞}}_{𝑖 - 1} |$ , then we have

\begin{aligned} 𝑟_{1, 1} {\vec{𝑞}}_{1} & = {\vec{𝑎}}_{1} \\ 𝑟_{2, 2} {\vec{𝑞}}_{2} & = 𝑎_{2} - 𝑟_{1, 2} {\vec{𝑞}}_{1} \\ ⋮ \\ 𝑟_{𝑛, 𝑛} {\vec{𝑞}}_{𝑛} & = 𝑎_{𝑛} - 𝑟 (1, 𝑛) {\vec{𝑞}}_{1} - \dots - 𝑟_{𝑛 - 1, 𝑛} {\vec{𝑞}}_{𝑛 - 1} . \end{aligned}

Rearranging gives

\begin{aligned} {\vec{𝑎}}_{1} & = 𝑟_{1, 1} {\vec{𝑞}}_{1} \\ {\vec{𝑎}}_{2} & = 𝑟_{1, 2} {\vec{𝑞}}_{1} + 𝑟_{2, 2} {\vec{𝑞}}_{2} \\ ⋮ \\ {\vec{𝑎}}_{𝑛} & = 𝑟_{1, 𝑛} {\vec{𝑞}}_{1} + \dots + 𝑟_{𝑛, 𝑛} {\vec{𝑞}}_{𝑛}, \end{aligned}

so we have now obtained a QR factorisation of $𝐴$ , $𝐴 = 𝑄 𝑅$ :

(\begin{matrix} ⋮ & ⋮ \\ {\vec{𝑎}}_{1} & \dots & {\vec{𝑎}}_{𝑛} \\ ⋮ & ⋮ \end{matrix}) = (\begin{matrix} ⋮ & ⋮ \\ {\vec{𝑞}}_{1} & \dots & {\vec{𝑞}}_{𝑛} \\ ⋮ & ⋮ \end{matrix}) (\begin{matrix} 𝑟_{1, 1} & 𝑟_{1, 2} & \dots & 𝑟_{1, 𝑛} \\ 𝑟_{2, 2} & \dots & 𝑟_{2, 𝑛} \\ ⋱ & ⋮ \\ 𝑟_{𝑛, 𝑛} \end{matrix}) .

Definition 6.2.6: This is a reduced/thin QR factorisation. A full QR factorisation has additional columns in

𝑄

to make it square, and corresponding zeros in

𝑅

Remark: The algorithm can be written as:

for j := 1 to n
  qj = aj
  for i := 1 to (j - 1)
    r_ij := qi^T aj
    qj := qj - r_ij qi
  r_jj := abs(qj)
  qj := qj / r_jj

Remark: Each iteration of the innermost loop involved roughly

2 𝑚

(scalar) multiplications and

2 𝑚

additions/subtractions. Overall about

4 (\frac{1}{2} 𝑚 𝑛^{2}) = 2 𝑚 𝑛^{2}

flops, where

𝑛 \times 𝑚

in the shape of

𝐴

Remark: The classical Gram-Schmidt process is numerically unstable! So we can use the modified Gram-Schmidt process instead.

for i := 1 to n
  vi := ai
for i := 1 to n
  r_ii := abs(vi)
  qi = vi / r_ii
  for j := (i + 1) to n
    r_ij := qi^T vj
    vj := vj - r_ij qi

This is mathematically equivalent, and has the same flop count, but is more numerically stable: each ${\vec{𝑣}}_{𝑖}$ starts as ${\vec{𝑎}}_{𝑖}$ , and then has the ${\vec{𝑞}}_{𝑗}$ (for $𝑗 < 𝑖$ ) components removed as soon as they become available, so the $𝑟_{𝑖, 𝑗}$ s aren’t “disturbed” by the presence of already removed components.

Remark: Gram-Schmidt (for thin QR factorisation) can be viewed as triangular orthogonalisation: $𝐴 𝑅_{1} \dots 𝑅_{𝑛} = 𝑄$ , i.e. creating an orthogonal matrix via multiplication by triangular matrices.

Other methods (for full QR factorisation) proceed by orthogonal triangularisation: $𝑄_{𝑛} \dots 𝑄_{1} 𝐴 = 𝑅$ , i.e. creating a triangular matrix via multiplication by orthogonal matrices.

Such methods use Householder reflections or Givens rotations. They are numerically stable (because multiplying by orthogonal matrices tends to be numerically stable). Flop count (Householder and $𝑚 = 𝑛$ ) is about $\frac{4}{2} 𝑛^{3}$ .

Solving linear systems via QR factorisation

Consider a square system $𝐴 \vec{𝑥} = \vec{𝑏}$ with $𝐴$ nonsingular, and a QR factorisation $𝐴 = 𝑄 𝑅$ . Then

\begin{matrix} 𝑄 𝑅 \vec{𝑥} = \vec{𝑏} \\ ⟺ 𝑅 \vec{𝑥} = 𝑄^{⊤} \vec{𝑏}, \end{matrix}

which can be solved easily by substitution as $𝑅$ is upper triangular.

The overall cost is dominated by the factorisation; this is more expensive than LU, but has better numerical stability.

Least squares

Consider $𝐴 \vec{𝑥} = \vec{𝑏}$ with $𝐴 \in 𝑅^{𝑚 \times 𝑛}$ : more equations than unknowns (overdetermined).

We assume that $𝐴$ has full column rank $𝑛$ . In general the system cannot be solved exactly.

The least squares problem is to find $\vec{𝑥}$ such that $| \vec{𝑏} - 𝐴 \vec{𝑥} |$ is minimised. I.e. we want to find $\vec{𝑥}$ such that $\vec{𝑏} - 𝐴 \vec{𝑥}$ is orthogonal to the (hyper-)plane spanned by the columns of $𝐴$ ; if it is not orthogonal, then the residual will be longer than necessary. Alternatively, $𝐴 \vec{𝑥}$ should run parallel to the plane spanned by the columns of A, directly “underneath” $\vec{𝑏}$ . Equivalently:

𝐴^{⊤} (\vec{𝑏} - 𝐴 \vec{𝑥}) = \vec{0} ⟺ 𝐴^{⊤} 𝐴 \vec{𝑥} = 𝐴^{⊤} \vec{𝑏};

we call this the normal equation.

Lemma 6.2.7: If $𝐴 \in 𝑅^{𝑚 \times 𝑛}$ has full column rank $𝑛$ , then $𝐴^{𝑇} 𝐴$ is nonsingular.

Proof:

We show that the nullspace of $𝐴^{⊤} 𝐴$ is trivial.

Let $\vec{𝑥} \in ℝ^{𝑛}$ with $𝐴^{⊤} 𝐴 \vec{𝑥} = \vec{0}$ . Then ${| 𝐴 \vec{𝑥} |}^{2} = (𝐴 \vec{𝑥}) \cdot (𝐴 \vec{𝑥}) = {\vec{𝑥}}^{⊤} 𝐴^{⊤} 𝐴 \vec{𝑥} = 0$ , so $𝐴 \vec{𝑥} = 0$ . Since the columns of $𝐴$ are linear independent, it follows that $\vec{𝑥} = 0$ .

Hence the normal equation can be solved uniquely, so there is a unique solution to the least squares problem.

We can do this by QR factorisation.

If $𝐴 = 𝑄 𝑅$ , then

𝐴^{⊤} 𝐴 \vec{𝑥} = 𝐴^{⊤} \vec{𝑏} ⟺ 𝑅^{⊤} 𝑄^{⊤} 𝑄 𝑅 \vec{𝑥} = 𝑅^{⊤} 𝑄^{⊤} \vec{𝑏} ⟺ 𝑅^{⊤} 𝑅 \vec{𝑥} = 𝑅^{⊤} 𝑄^{⊤} \vec{𝑏}

Since $𝐴$ has full column rank, the matrix $𝑅$ is nonsingular. Thus, multiplying with the inverse of $𝑅^{𝑇}$ gives the system

𝑅 \vec{𝑥} = 𝑄^{⊤} \vec{𝑏}

which can be solved easily by back-substitution.

Remark: The least-squares method can be used to find a linear regression - we want to minimise the sum of the squares of the errors, where

𝐴 = (\begin{matrix} 1 & 𝑥_{1} \\ ⋮ & ⋮ \\ 1 & 𝑥_{𝑛} \end{matrix}), \vec{𝑥} = (\begin{matrix} 𝑐 \\ 𝑚 \end{matrix}), \vec{𝑏} = (\begin{matrix} 𝑦_{1} \\ ⋮ \\ 𝑦_{𝑛} \end{matrix})

to find the best regression line

𝑦 = 𝑚 𝑥 + 𝑐

Although in two dimensions, QR factorisation probably isn’t the easiest way to solve it, for higher-dimension regressions, it might be useful. Useful for machine learning!

6.iii Norms and Singular Value Decomposition

Definition 6.3.1: The 2-norm ${‖ \vec{𝑥} ‖}_{2}$ of a vector $\vec{𝑥} \in ℝ^{𝑛}$ is equal to the length, or Euclidean distance, of the vector:

| \vec{𝑥} | = {‖ \vec{𝑥} ‖}_{2} = \sqrt{\sum_{𝑖 = 1}^{𝑛} 𝑥_{𝑖}^{2}} = \sqrt{𝑥^{⊤} \vec{𝑥}} = \sqrt{\vec{𝑥} \cdot \vec{𝑥}} .

Definition 6.3.2: More generally, a vector norm is a function $‖ \cdot ‖ : ℝ^{𝑛} \to ℝ$ that satisfies $\forall \vec{𝑥}, \vec{𝑦} \in ℝ^{𝑛}, 𝑟 \in ℝ$ :

$‖ \vec{𝑥} ‖ \geq 0$ with equality iff $\vec{𝑥} = \vec{0}$ ;
$‖ \vec{𝑥} + \vec{𝑦} ‖ \leq ‖ \vec{𝑥} ‖ + ‖ \vec{𝑦} ‖$ ;
$‖ 𝑟 \vec{𝑥} ‖ = | 𝑟 | ‖ \vec{𝑥} ‖$ .

Remark: Unlike determinants, norms are not unique.

Definition 6.3.3: A commonly used norm is the $𝑝$ -norm:

{‖ \vec{𝑥} ‖}_{𝑝} = {(\sum_{𝑖 = 1}^{𝑛} {| 𝑥_{𝑖} |}^{𝑝})}^{\frac{1}{𝑝}}, for 𝑝 \geq 1 .

Definition 6.3.4: In

ℝ^{𝑛}

, a unit ball is the region for which

‖ \vec{𝑥} ‖ = 1

for some norm

‖ \cdot ‖

. In

ℝ^{2}

, for

𝑝

-norms: TODO images of unit balls for

𝑝 = 1, 2, 4, \infty

Definition 6.3.5: A vector norm $‖ \cdot ‖ : ℝ^{𝑛} \to ℝ$ induces an induced matrix norm $‖ \cdot ‖ : ℝ^{𝑚 \times 𝑛} \to ℝ$ :

\begin{aligned} ‖ 𝐴 ‖ & = sup_{\vec{𝑥} \in ℝ^{𝑛} \ {\vec{0}}} \frac{‖ 𝐴 \vec{𝑥} ‖}{‖ \vec{𝑥} ‖} \\ = sup_{\begin{matrix} \vec{𝑥} \in ℝ^{𝑛}; \\ ‖ \vec{𝑥} ‖ = 1 \end{matrix}} ‖ 𝐴 \vec{𝑥} ‖ \end{aligned}

where $sup$ denotes the supremum of a set; that is, a maximal element which is not necessarily contained within the set. For finite sets, this is the same as $max$ .

Intuitively, this is the largest amount by which the norm of a vector $\vec{𝑥}$ can be scaled by multiplying $𝐴$ with $\vec{𝑥}$ .

Lemma 6.3.6: For any $𝐴^{𝑚 \times 𝑛}, \vec{𝑥} \in ℝ^{𝑛}$ , $‖ 𝐴 \vec{𝑥} ‖ \leq ‖ 𝐴 ‖ ‖ \vec{𝑥} ‖$ for a vector norm $‖ \cdot ‖ : ℝ^{𝑛} \to ℝ^{𝑛}$ and its induced matrix norm $‖ \cdot ‖ : ℝ^{𝑚 \times 𝑛} \to ℝ$ .

Proof:

By the definition of an induced matrix norm, $‖ 𝐴 ‖ \Rightarrow \frac{‖ 𝐴 \vec{𝑥} ‖}{‖ \vec{𝑥} ‖} \forall \vec{𝑥} \in ℝ^{𝑛}$ , hence $‖ 𝐴 \vec{𝑥} ‖ \leq ‖ 𝐴 ‖ ‖ \vec{𝑥} ‖$ .

Remark: Matrix norms need not be induced; since matrices can be thought of as vectors in the vector space of matrices, norms that satisfy the prior definition can be defined on matrices, including the element-wise Frobenius norm.

Lemma 6.3.7: Let $‖ \cdot ‖$ denote an induced matrix norm. Then $‖ 𝐴 𝐵 ‖ \leq ‖ 𝐴 ‖ ‖ 𝐵 ‖$ .

Proof:

\begin{aligned} ‖ 𝐴 𝐵 \vec{𝑥} ‖ & \leq ‖ 𝐴 ‖ ‖ 𝐵 \vec{𝑥} ‖ by Lemma 6.3.6 \\ \leq ‖ 𝐴 ‖ ‖ 𝐵 ‖ ‖ \vec{𝑥} ‖ by Lemma 6.3.6 . \end{aligned}

Lemma 6.3.8: Let $𝑄 \in 𝑅^{𝑚 \times 𝑚}$ be an orthogonal matrix, and $𝐴 \in ℝ^{𝑚 \times 𝑛}$ . Then

\begin{matrix} {‖ 𝑄 ‖}_{2} = 1; \\ {‖ 𝑄 𝐴 ‖}_{2} = {‖ 𝐴 ‖}_{2} . \end{matrix}

Proof:

This is a rephrasing of Lemma 6.2.2.

Definition 6.3.9: The singular value decomposition (SVD) of a matrix $𝐴 \in 𝑅^{𝑚 \times 𝑛}$ (where $𝑚 \geq 𝑛$ ) is a factorisation $𝐴 = 𝑈 Σ 𝑉^{⊤}$ , where $𝑈 \in ℝ^{𝑚 \times 𝑚}$ and $𝑉 \in ℝ^{𝑛 \times 𝑛}$ are orthogonal, and $Σ \in ℝ^{𝑚 \times 𝑛}$ is diagonal. The diagonal entries $𝜎_{1} \geq 𝜎_{2} \geq \dots \geq 𝜎_{𝑛} \geq 0$ are called singular values of $𝐴$ .

The (pairwise orthogonal) columns of $𝑈$ are the left-singular vectors of the SVD, and the (pairwise orthogonal) columns of $𝑉$ are the right-singular vectors of the factorisation.

The SVD describes the action of A as a series of 3 transformations:

rotation/reflection by $𝑉^{⊤}$ ;
scaling along the axes by $Σ$ ;
another rotation/reflection, by $𝑈$ .

Corollary 6.3.10: The image of a unit sphere under any matrix is a hyperelipse.

Remark: It can be shown that every matrix has an SVD (Theorem 6.3.13).

Lemma 6.3.11: The action of $𝐴$ on the right-singular vectors ${\vec{𝑣}}_{𝑖}$ can be described by $𝐴 {\vec{𝑣}}_{𝑖} = 𝜎_{𝑖} {\vec{𝑢}}_{𝑖}$ for $1 \leq 𝑖 \leq 𝑛$ .

Proof:

\begin{aligned} 𝐴 & = 𝑈 Σ 𝑉^{⊤} \\ = 𝑈 Σ 𝑉^{- 1} since 𝑉 is orthogonal \\ \Rightarrow 𝐴 𝑉 & = 𝑈 Σ \\ ⟹ 𝐴 {\vec{𝑣}}_{𝑖} & = 𝜎_{𝑖} {\vec{𝑢}}_{𝑖} . \end{aligned}

Theorem 6.3.12: The map defined by a matrix $𝐴$ is the map represented by the diagonal matrix $Σ$ , with respect to the domain and codomain bases consisting of the left-singular and right-singular vectors, respectively.

Proof:

Let $\vec{𝑏} = 𝐴 \vec{𝑥}$ for some $\vec{𝑥} \in ℝ^{𝑛}$ .

Let ${\vec{𝑥}}^{'}$ be the representation of $\vec{𝑥}$ in the basis of the right singular vectors, $⟨ {\vec{𝑣}}_{1}, \dots, {\vec{𝑣}}_{𝑛} ⟩$ , s.t. ${\vec{𝑥}}^{'} = 𝑉^{⊤} \vec{𝑥}$ .

Similarly, let ${\vec{𝑏}}^{'}$ be the representation of $\vec{𝑏}$ in the basis of the left-singular vectors, $⟨ {\vec{𝑢}}_{1}, \dots, {\vec{𝑢}}_{𝑚} ⟩$ , s.t. ${\vec{𝑏}}^{'} = 𝑈^{⊤} \vec{𝑏}$ .

Then

\begin{aligned} \vec{𝑏} & = 𝑈^{⊤} \vec{𝑏} \\ = 𝑈^{⊤} 𝐴 \vec{𝑥} \\ = 𝑈^{⊤} 𝑈 Σ 𝑉^{⊤} \vec{𝑥} \\ = Σ 𝑉^{⊤} \vec{𝑥} \\ = Σ {\vec{𝑥}}^{'} . \end{aligned}

Theorem 6.3.13: Every matrix $𝐴 \in ℝ^{𝑚 \times 𝑛}$ has an SVD, with uniquely determined singular values $𝜎_{𝑖}$ s. Further, if $𝐴$ is square and the $𝜎_{𝑖}$ s are distinct, the left- and right-singular vectors are uniquely determined up to signs.

Proof:

TODO (in Trefethon & Bau)

Remark: An approximate SVD for an

𝑚 \times 𝑛

matrix can be computed in

𝑂 (𝑚 𝑛^{2})

flops. This typically involves an iterative phase, as the singular values are in general irrational, but this is typically not a bottleneck.

Remark: SVD looks similar to eigenvalue decomposition, but is not the same; if a diagonalisable matrix

𝐴

has an eigenvalue decomposition

𝐴 = 𝑈 Σ 𝑈^{- 1}

, then this is an SVD of

𝐴

iff

𝑈

is orthogonal, which is not generally the case - eigenvectors need not be orthogonal.

Theorems 6.3.14 - 6.3.20 link properties of a matrix $𝐴 \in ℝ^{𝑚 \times 𝑛}$ to properties of its SVD, given that we let $𝑟 \leq min {𝑚, 𝑛}$ be the number of nonzero singular values of $𝐴$ , and that we have $𝜎_{1} \geq \dots \geq 𝜎_{𝑟} \geq 0$ .

Theorem 6.3.14: The rank of $𝐴$ is $𝑟$ .

Proof: The rank of a diagonal matrix is the number of nonzero diagonal entries. Since

Σ

has full rank - since by definition all

𝜎_{𝑖}

s are greater than 0 - the rank is

𝑟

Theorem 6.3.15: $⟨ {\vec{𝑢}}_{1}, \dots, {\vec{𝑢}}_{𝑟} ⟩$ is an orthonormal basis of $𝐴$ ’s column space. Similarly, $⟨ {\vec{𝑣}}_{𝑟 + 1}, \dots, {\vec{𝑣}}_{𝑛} ⟩$ is an orthonormal basis of $𝐴$ ’s nullspace.

Proof:

This follows from the fact that $ℛ︀ (Σ) = ⟨ {\vec{𝑒}}_{1}, \dots, {\vec{𝑒}}_{𝑟} ⟩$ and $𝒩︀ (Σ) = ⟨ {\vec{𝑒}}_{𝑟 + 1}, \dots, {\vec{𝑒}}_{𝑛} ⟩$ ; the left- and right-multiplications of $𝑈$ and $𝑉^{⊤}$ respectively give the desired bases, which are orthonormal because $𝑈, 𝑉$ are orthogonal.

Remark: Column space and null space can be computed by QR factorisation, but SVD is more accurate.

Theorem 6.3.16: ${‖ 𝐴 ‖}_{2} = 𝜎_{1}$ where $𝜎_{1}$ is the largest singular value of $𝐴$ .

Proof:

\begin{aligned} {‖ 𝐴 ‖}_{2} & = {‖ 𝑈 Σ 𝑉^{𝑇} ‖}_{2} \\ = {‖ Σ ‖}_{2} \\ = 𝜎_{1} . \end{aligned}

Theorem 6.3.17: The nonzero singular values of $𝐴$ are the square roots of the nonzero eigenvalues of $𝐴 𝐴^{⊤}$ .

Proof:

\begin{aligned} 𝐴 𝐴^{⊤} & = 𝑈 Σ 𝑉^{⊤} 𝑉 Σ^{⊤} 𝑈^{⊤} \\ = 𝑈 Σ 𝑉^{- 1} 𝑉 Σ 𝑈^{- 1} since Σ diagonal and 𝑈, 𝑉 orthogonal \\ = 𝑈 Σ^{2} 𝑈^{- 1}, \end{aligned}

hence $𝐴 𝐴^{⊤}$ is similar to $Σ^{2}$ so has the same eigenvalues as $Σ^{2}$ , which are $𝜎_{1}^{2}, \dots, 𝜎_{𝑛}^{2}$ .

Lemma 6.3.18: The determinant of any orthogonal matrix $𝑄$ is 1.

Proof:

\begin{aligned} {det (𝑄)}^{2} & = det (𝑄) det (𝑄) \\ = det (𝑄) det (𝑄^{⊤}) \\ = det (𝑄 𝑄^{⊤}) \\ = det (𝐼) \\ = 1 \\ ⟹ det (𝑄) & = 1 . \end{aligned}

Theorem 6.3.19: Let $𝐴 \in 𝑅^{𝑛 \times 𝑛}$ be a square matrix. Then

| det (𝐴) | = \prod_{𝑖 = 1}^{𝑛} 𝜎_{𝑖} .

Proof:

\begin{aligned} | det (𝐴) | & = | det (𝑈 Σ 𝑉^{⊤}) | \\ = | det (𝑈) det (Σ) det (𝑉^{⊤}) | \\ = | det (Σ) | by Lemma 6.3.18 \\ = | \prod_{𝑖 = 1}^{𝑛} 𝜎_{𝑖} | since Σ diagonal \\ = \prod_{𝑖 = 1}^{𝑛} 𝜎_{𝑖} since 𝜎_{𝑖} > 0 for 1 \leq 𝑖 \leq 𝑛 . \end{aligned}

Theorem 6.3.20 (Low-rank approximation): For any $𝑘 \leq 𝑟$ , define

𝐴_{𝑘} ≔ \sum_{𝑖 = 1}^{𝑘} 𝜎_{𝑖} {\vec{𝑢}}_{𝑖} {\vec{𝑣}}_{𝑖}^{⊤} .

Then

{‖ 𝐴 - 𝐴_{𝑘} ‖}_{2} = inf_{\begin{matrix} 𝐵 \in ℝ^{𝑚 \times 𝑚}; \\ rank (𝐵) \leq 𝑘 \end{matrix}} {‖ 𝐴 - 𝐵 ‖}_{2} = 𝜎_{𝑘 + 1},

where $inf$ denotes the infimum (equivalent to minimum for finite sets); that is, $𝐴_{𝑘}$ is a low-rank approximation of $𝐴$ , where the Euclidean distance between $𝐴$ and $𝐴_{𝑘}$ is $𝜎_{𝑘 + 1}$ .

Proof:

TODO

Remark:

‖ 𝐴 - 𝐴_{𝑘} ‖ ≔ 0

𝑘 = min {𝑚, 𝑛}

Theorem 6.3.21 (Spectral theorem): Given a symmetric $𝑛 \times 𝑛$ matrix $𝐀$ , there exists an orthonormal basis for $ℝ^{𝑛}$ consisting of eigenvectors of $𝐀$ .

Proof: The SVD of

𝐴

𝐴 = 𝑈 Σ 𝑉^{⊤}

. Since

𝐴^{⊤} = 𝐴

{(𝑈 Σ 𝑉^{⊤})}^{⊤} = 𝑉 Σ 𝑈^{⊤} = 𝑈 Σ 𝑉^{⊤}

. Choosing

𝑈 = 𝑉

gives

𝐴 = 𝑉 Σ 𝑉^{⊤} = 𝑉 Σ 𝑉^{- 1}

, since

𝐕

is orthogonal, giving an eigenvalue decomposition with eigenvectors the rows or columns of

𝑉

. Clearly these form a basis for

ℝ^{𝑛}

, from Corollary 3.6.4.