Professor: J.P. Pretti | Term: Winter 2023

Vectors in $R^{n}$

A member of $R^{n}$ is called a vector. We often use overline arrows. Let $x \in R^{n}$ . Can also write as a row, but use $^{⊺}$ superscript.

40 - 3 = [40 - 3]^{⊤}

Two ways to think about vectors.

Algebraic. List of $n$ real numbers
Geometric. Directed line segment between 2 points

Given $u, v \in R^{n}$ with $u = u_{i} ⋮ u_{n}$ $v = v_{i} ⋮ v_{n}$ then $u = v$ if $u_{i} = v_{i}$ for $i = 1, \dots, n$

Two operations:

Addition: Input $2$ vectors in $R^{n}$ outputs 1 vector in $R^{n}$ .

Scalar Multiplication: 1 vector in $R^{n}$ & 1 real number outputs 1 vector in $R^{n}$

u + v = u_{1} + v_{1} ⋮ u_{n} + v_{n}

Properties: Let $u, v, w \in R^{n}$

$u + v = v + u$
$u + (v + w) = (u + v) + w$
$0 ⋮ 0 is the additive identity of R^{n} : u + 0 ⋮ 0 = u$
$u$ has an additive inverse. If $u = u_{1} ⋮ u_{n}$ , then $- u_{1} ⋮ - u_{n}$ is the additive inverse of $u = 0$

Definition

Let $c \in R, u \in R^{n} .$ Say $u = u_{1} ⋮ u_{n}$ , then $c u = c u_{1} ⋮ c u_{n}$ . This stretches $u$ by $∣ c ∣$ . If $c < 0$ , then switch direction of $u$ .

Properties: Let $c, d \in R, u, v \in R^{n}$

$(c + d) v = c v + d v$
$(c d) v = c (d v)$
$c (u + v) = c u + c v$
$0 v = 0$
If $c v = 0$ then $c = 0$ or $v = 0$

Proof of the third point above.

c u_{1} ⋮ u_{n} + v_{1} ⋮ v_{n} = c u_{1} + v_{1} ⋮ u_{n} + v_{n} = c (u_{1} + v_{1}) ⋮ c (u_{n} + v_{n}) = c u_{1} + c v_{1} ⋮ c u_{n} + c v_{n} = c u_{1} ⋮ c u_{n} + c v_{1} ⋮ c v_{n} = c u_{1} ⋮ u_{n} + c v_{1} ⋮ v_{n}

Standard Basis

Standard Basis for $R^{2}$

[34] = 3 [10] + 4 [01] = 3 e_{1} + 4 e_{2}

$E = {e_{1}, e_{2}, \dots, e_{n}}$ is the standard basis.

Dot Product

Vector $\cdot$ Vector $⟹$ Real Number

$u \cdot v = u_{1} v_{1} + u_{2} v_{2} + \dots + u_{n} v_{n}$

Properties

$u \cdot v = v \cdot u$
$(u + v) \cdot w = u \cdot w + v \cdot w$
$(c u) \cdot v = c (u \cdot v)$

$v \cdot v \geq 0$ (only $= 0$ iff $v = 0$ )

Length of Vector

$v \in R^{n}$ is $∣∣ v ∣∣ = v \cdot v$ (magnitude).

[34] = [34] \cdot [34] = 5

If $c \in R$ and $v \in R^{n}$ , then $∣∣ c v ∣∣ = ∣ c ∣∣∣ v ∣∣$

Unit Vectors

$v \in R^{n}$ is a unit vector if $∣∣ v ∣∣ = 1$

Normalization

When $v \in R^{n}$ is a non-zero vector, we can produce a unit vector.

\overset{v}{^} = \frac{v}{∣∣ v ∣∣}

\hat{[34]} = \frac{1}{5} [34] = [\frac{3}{5} \frac{4}{5}]

Angle

∣∣ u - v ∣ ∣^{2} = ∣∣ u ∣ ∣^{2} + ∣∣ v ∣ ∣^{2} - 2∣∣ u ∣∣∣∣ v ∣∣ cos θ

Also

∣∣ u - v ∣ ∣^{2} = (u - v) \cdot (u - v) = u \cdot u - v \cdot u - u \cdot v + v \cdot v = ∣∣ u ∣ ∣^{2} - 2 u \cdot v + ∣∣ v ∣ ∣^{2}

Angle between $u$ and $v$ $(0 \leq θ \leq π)$ .

$u \cdot v = ∣∣ u ∣∣∣∣ v ∣∣ cos θ$

$θ = arccos (\frac{u \cdot v}{∣∣ vv u ∣∣∣∣ v ∣∣})$

Orthogonality

Two vectors are perpendicular if $u \cdot v = 0$ .

More rules:

$e_{1} \cdot e_{2} = 0$
$v \cdot 0 = 0, \forall v \in R^{n}$

Find 2 vectors orthogonal to $[12]$ . $[- 4 2], [- 6 3]$

Without inspection, $v_{1} + 2 v_{2} = 0$

Find the angle in-between $[13] [31]$

θ = arccos \frac{[ 1 3 ] \cdot [ 3 1 ]}{[ 1 3 ] [ 3 1 ]} = arccos (\frac{2 3}{2 \cdot 2}) = \frac{π}{6}

Projection and Perpendicular

We want $p ro j_{w} v = c w$ for some $c \in R$ and $p ro j_{w} v \cdot p er p_{w} v = 0$ .

Then

v \cdot w = (c w + p er p_{w} v) \cdot w = (c w) \cdot w + p er p_{w} v \cdot w = c ∣∣ w ∣ ∣^{2} + 0

Definition

Let $v, w \in R^{n}$ and $w \neq = 0$ . Projection of $v$ onto $w$ is
$p ro j_{w} (v) = \frac{( v \cdot w )}{∣∣ w ∣ ∣ ^{2}}$

The length of $w$ does not impact length of projection.

Definition

Perpendicular of $v$ onto $w$ is defined by
$p er p_{w} (v) = v - p ro j_{w} (v)$

We have $p ro j_{w} v = (v \cdot \overset{w}{^}) \overset{w}{^}$

Also

p ro j_{w} v = \frac{∣∣ v ∣∣∣∣ w ∣∣ cos θ}{∣∣ w ∣ ∣ ^{2}} \cdot w = ∣∣ v ∣∣ cos θ \overset{w}{^}

Let $v = [v_{1} v_{2}] \in R^{2}$

then

p ro j_{e_{1}} v = \frac{[ v _{1} v _{2} ] \cdot [ 1 0 ]}{[ 1 0 ] [ 1 0 ]} [10] = v_{1} [10] = [v_{1} 0]

and $p er p_{e_{1}} v = [v_{1} v_{2}] - [v_{1} 0] = [0 v_{2}]$

$p er p_{w} v \cdot p ro j_{w} w = 0$
$p ro j_{w} (p ro j_{w} v) = p ro j_{w} v$
$p ro j_{w} (c_{1} v_{1} + c_{2} v_{2}) = c_{1} p ro j_{w} v_{1} + c_{2} p ro j_{w} v_{2}$

Fields

$R$ and $C$ are fields

Can multiply, add, subtract, and stay in set
Can divide by non-zero and stay in set
”Everything works” (commutative, associative, distributive, inverse).

Cross Product

Let $u = u_{1} u_{2} u_{3}, v = v_{1} v_{2} v_{3} \in R^{3}$ (only defined for $R^{3}$ )

Cross product is given by

u \times v = u_{2} v_{3} - u_{3} v_{2} - (u_{1} v_{3} - u_{3} v_{1}) u_{1} v_{2} - u_{2} v_{1}

Properties

$u, v \in R^{3}$ and let $z = u \times v$

$z \cdot v = 0$ and $z \cdot u = 0$
$v \times u = - z = - u \times v$
$∣∣ u \times v ∣∣ = ∣∣ u ∣∣∣∣ v ∣∣ sin θ$ , where $sin θ$ is the angle between $u, v$ (and $u, v$ are not zero vectors).

$∣∣ u \times v ∣∣ =$ area of parallelogram

$e_{1} \times e_{2} = e_{3}$ $e_{3} \times e_{2} = - e_{1}$ $(c u) \times v = c (u \times v)$ $u \times (c v) = c (u \times v)$

Spans, Lines, and Planes

Linear Combinations and Spans

Example

i [1 - i] + (2 + i) [3 i 0] = [- 3 + 7 i 1]

$[- 3 + 7 i 1]$ is a linear combination of $[1 - 1]$ and $[3 i 0]$ .

$[- 3 + 7 i 1] \in Span {[1 - i], [3 i 0]}$

Linear combination is a vector, span is a set.

Examples - True or False?

Every vector in $R^{2}$ is an element of Span ${e_{1}, e_{2}}$
Every vector in $R$ is an element of Span ${[10], [11]}$
Every vector in $R^{3}$ is an element of Span $⎩ ⎨ ⎧ 100, 110 ⎭ ⎬ ⎫$
True - $[v_{1} v_{2}] = v_{1} [10] + v_{2} [01]$
True - $[v_{1} v_{2}] = c_{1} [10] + c_{2} [11], v_{1} = c_{1} + c_{2}, v_{2} = c_{2}$
False

Geometry

Span ${0} = {0}$

For $v \neq = 0$ , Span ${v}$ is a line through origin with direction $v$ .

For $v, w \neq = 0$ , if $v, w$ are not parallel, then Span ${v, w}$ is a plane

Lines

Parametric Equations

$p, q$ are fixed numbers ( $q \neq = 0$ ). Parametric equations of line in $R^{2}$ through point $(x, y)$ with slope $\frac{p}{q}$ are

x y = x_{1} + qt t \in R = y_{1} + pt

Vector Equation of a Line in $R^{2}$

[x y] = [x_{1} y_{1}] + t [p q], t \in R

This is a vector equation of line $L$ in $R^{2}$ through $[x_{1} y_{1}]$ with direction $[p q]$ .

Line in $R^{2}$

$L = {u + t v : t \in R}$

Parametric Equations of a Line

Parameter $t$ “generates” points on the line. When $q = 0$ , we have $x = x_{1}, y = y_{1} + pt$ which is a vertical line with undefined slope.

Vector Equation of a Line

Let $u = [x_{1} y_{1}]$ and $v = [q p]$ .

$ℓ = u + t v, t \in R$

$u$ is on
$u - v$ is on $ℓ$
$v$ usually is not on $ℓ$
$v$ is on $ℓ$ iff $v \in$ Span ${u}$

Exercises:

Give parametric equations for the line $y = 3 x + 1$
Give a vector equation of a line through $[13]$ and $[22]$
Show that $L_{1} = {[43] + t [1 - 1] : t \in R}$ is the same line as $L_{2} = {[1 - 2] + t [2 - 2] : t \in R}$

[x_{1} y_{1}] = [01]

[q p] = [13]

$x = t, y = 1 + 3 t$

l = [13] + t ([13] - [22]) t \in R

Prove parallel and coincident (pass through the same point) or,

Can set up an algebraic system of equations using set equality.

Direction vectors are scalar multiples, immediately parallel.

Equations in $R^{n}$

Vector Equations

$l = u + t v, t \in R$

Parametric Equations

l_{1} l_{2} l_{n} = u_{1} + t v_{1} = u_{2} + t v_{2} ⋮ = u_{n} + t v_{n}

Lines

$L = {u + t v : t \in R}$

Lines through the origin can be described as the span.

Example of a Line in $R^{5}$

L = Span ⎩ ⎨ ⎧ 12345 ⎭ ⎬ ⎫

Line through the origin and $(1, 2, 3, 4, 5)$ .

Parametric equations: $x_{1} = t \dots x_{5} = 5 t t \in R$

Planes Through the Origin

$v, w$ (non-zero), $v \neq = c w$ for $c \in R$

$P = Span {v, w} = {s v + t w : s, t \in R}$

Plane Examples

P_{1} = s 102 + t 0 - 1 1

P_{2} = 0100 + s 102 + t 0 - 1 1

These two are not on $p_{2}$ . When scaled and added to $0100$ , then it is on it.

$v + w$ are on $p ⟺ u \in Span {v, w}$

Normal Vectors

102 \times 0 - 1 1 = 2 - 1 - 1

\in p_{1} x y z \cdot 2 - 1 - 1 = 0

$n = v \times w$ (normal vector to plane)

n = a b c, u \in P and p = x y z \in P

Normal form of $P$

n \cdot (p - u) = 0

Expanding $= a x + b y + cz = d$

$d = n \cdot u$

Exercise

Find a vector equation and a scalar equation of the plane containing $A (1, 0, 2), B (- 3, - 2, 4)$ and $C (1, 8, 5)$ .

Can find direction vectors:

102 - - 3 - 2 4 = 42 - 2

102 - 18 - 5 = 0 - 8 7

So a vector equation is:

p = 102 + s 42 - 2 + t 0 - 8 7 s, t \in R

Finding Scalar Equation, we can find a normal vector:

Orthogonal to the 2 direction vectors

n = 42 - 2 \times 0 - 8 7 = - 2 - 28 - 32

Our equation is thus

- 2 x - 28 y - 32 z = - 2 - 28 - 32 \cdot 102 = - 66

Simplifies to $x + 14 y + 16 z = 33$

Systems of Linear Equations

These show up everywhere.

Examples from linear algebra

Is a vector in the span of a given set?
Find a vector orthogonal to another vector(s)?
Determine the intersection of two planes

Linear Equation

a_{1} x_{1} + a_{2} x_{2} + \dots a_{n} x_{n} = b

where $a_{1}, a_{2}, \dots b \in F$

$a \to$ coefficients (known)

$x \to$ variables (unknown)

A system is multiple of these. For $a_{ij}, i$ is the equation and $j$ gives the variable.

Solving means we found $y_{1} \dots y_{n}$ into $x_{1} \dots x_{n}$ and LHS=RHS.

We view a system as simultaneous.

Solution Set

a) The solution set of $x_{1} + 2 x_{2} + x_{3} = 7$ .

S = ⎩ ⎨ ⎧ 7 - 2 s - t s t : s, t \in R ⎭ ⎬ ⎫ Scalar Equation = ⎩ ⎨ ⎧ 700 + s - 2 10 + t - 1 01 : s, t \in R ⎭ ⎬ ⎫ Vector Equation

b) Show that

x_{1} x_{2} x_{3} = 031 + t 1 - 2 3, t \in R

is a solution to

x_{1} + 2 x_{2} + x_{3} x_{1} - x_{2} - x_{3} = 7 = - 4

Let $t \in R$ . Then $x_{1} = t, x_{2} = 3 - 2 t, x_{3} = 1 + 3 t$ .

And indeed,

t + 2 (3 - 2 t) + 1 + 3 t = 7 + 0 t t - (3 - 2 t) - (1 + 3 t) = - 4 + 0 t = 7 = - 4

This shows that the given line is a solution.

Solution is either empty, one element (unique), infinite number of equations.

Solving Systems: Two big ideas.

Some systems are easy to solve ( $x_{1} = 7, x_{2} = i, x_{3} = 2 - i$ ).

Solve a “hard” system by changing it to a “simpler” but equivalent system. Two systems are equivalent if they have the same solution set.

How do we do this? We can multiply both sides by $c \neq = 0$ , and we can add equations. We cannot multiply by zero, square an equation, remove an equation, or insert an equation.

Elementary Operations

Swap elementary operation

e_{i} \leftrightarrow e_{j}

Scale elementary operation

e_{i} \to m e_{i}, m \in F ∖ {0}

Addition elementary operation

e_{j} \to c e_{i} + e_{j} i \neq = j, c \in F

A single elementary operation performed produces an equivalent system.

Unique solution (consistent)

x_{1} + x_{2} x_{1} - x_{2} = 1 = 1

Infinite solutions (consistent)

x_{1} + x_{2} - x_{1} - x_{2} = 1 = - 1

No solutions (inconsistent)

x_{1} + x_{2} x_{1} + x_{2} = 1 = 0

Solving Systems using EO’s

x_{1} + 2 x_{2} + x_{3} x_{1} - x_{2} - x_{3} = 7 = - 4

e_{2} \to (- 1) e_{1} + e_{2} gives: x_{1} + 2 x_{2} + x_{3} - 3 x_{2} - 2 x_{3} = 7 = - 11

e_{1} \to \frac{2}{3} e_{2} + e_{1} gives: x_{1} - \frac{1}{3} x_{3} - 3 x_{2} - 2 x_{3} = - \frac{1}{3} = - 11

e_{2} \to \frac{1}{3} e_{2} gives: x_{1} - \frac{1}{3} x_{3} x_{2} + \frac{2}{3} x_{3} = - \frac{1}{3} = \frac{11}{3}

Let $x_{3} = t$ for some $t \in R$ .

We get the solution set:

S = ⎩ ⎨ ⎧ - \frac{1}{3} + t \frac{1}{3} \frac{11}{3} - t \frac{2}{3} t : t \in R ⎭ ⎬ ⎫

Question

Is $(3, 2, 1)$ on $p = s 01 + s 235 + t 467, s, t \in R ?$

We need to solve

2 s + 4 t 3 s + 6 t 5 s + 7 t = - 2 = 2 = 0

Has a solution $⟹$ on the plane.

e_{1} \to \frac{1}{2} e_{1} gives: s + 2 t 3 s + 6 t 5 s + 7 t = - 1 = 2 = 0

e_{2} \to - 3 e_{1} + e_{2} gives: s + 2 t 0 5 s + 7 t = - 1 = 5 = 0

There is no solution. That is $(3, 2, 1)$ is not on $p$ .

Prove that the only vector orthogonal to

- 2 - 4 - 6, 372, and - 3 50

is $0$ .

We must solve

- 2 x_{1} - 4 x_{2} - 6 x_{3} 3 x_{1} + 7 x_{2} + 2 x_{3} - 3 x_{1} + 5 x_{2} = 0 = 0 = 0

We will work with an augmented matrix:

- 2 3 - 3 - 4 75 - 6 20 000

Matrix

$m \times n$ matrix, array of $m$ rows, $n$ columns. $a_{ij}$ is coefficient of $x_{j}$ in the $i$ th equation.

Elementary Row Operations

Row swap: $e_{i} \leftrightarrow e_{j} R_{i} \leftrightarrow R_{j}$
Row scale: $e_{i} \to c e_{i} R_{i} \to c R_{i}$
Row addition: $e_{i} \to c e_{j} + e_{i} R_{i} \to c R_{j} \to R_{i}$

Zero row: Row that has all zero entries.

If $B$ is from $A$ by finite ERO, $A$ is equivalent to $B$ .

Gauss-Jordan Algorithm (Big Picture)

Assume $x$ , “really exists”. Begin by forward elimination phase (the goal is REF).

Scale so all leading coefficients are 1. We can now use back substitution to solve or, continue with backwards elimination phase. The goal is RREF (Reduced Row Echelon Form). Place 0s above all leading coefficients.

Leftmost non-zero entry of a non-zero matrix is the leading entry.

Definition

Row Echelon Form: When all zero rows are at the bottom, leading entries appear in a column to the right of the columns entering the leading entries from columns above.

Gauss-Jordan Algorithm Examples

- 2 3 - 3 - 4 75 - 6 20 000 R_{1} \to - \frac{1}{2} R_{1} 13 - 3 275320000 R_{2} \to - 3 R_{1} + R_{2} R_{3} \to R_{3} + 3 R_{1} 1002111 3 - 7 9 000 R_{3} \to R_{3} - 11 R_{2} 100210 3 - 7 86 000 R_{3} \to \frac{1}{86} R_{3} 100210 3 - 7 1 000 R_{1} \to R_{1} - 3 R_{3} R_{2} \to R_{2} + 7 R_{3} 100210001000 R_{1} \to - 2 R_{2} + R_{1} gives: 100010001000 RREF

This tells us that $⎩ ⎨ ⎧ 000 ⎭ ⎬ ⎫$ is the unique solution to the system and so $0$ is indeed the only vector orthogonal to the three given vectors.

021 2 - 6 - 2 37541510 R_{1} \leftrightarrow R_{3} gives: 120 - 2 - 6 2 57310154 R_{2} \to - 2 R_{1} + R_{2} 100 - 2 - 2 2 5 - 3 3 10 - 5 4 R_{3} \to R_{2} + R_{3} gives: 100 - 2 - 2 0 5 - 3 0 10 - 5 - 1 REF

Hence there is no solution.

1 - 2 1 2 - 4 2 - 3 6 - 3 023 4 - 2 13 R_{2} \to 2 R_{1} + R_{2} R_{3} \to R_{3} - R_{1} 100200 - 3 00 023469 R_{3} \to \frac{1}{3} R_{3} 100200 - 3 00 021463 R_{2} \to R_{2} - 2 R_{3} R_{2} \to \frac{1}{2} R_{2} 100200 - 3 00 010430 RREF

The first and fourth columns are pivot columns. The first two rows are pivot rows.

$x_{1}$ and $x_{3}$ are basic variables. $x_{2}$ and $x_{3}$ are free variables. When we see that the system is consistent, we assign parameters to the free variables and express the basic variables in terms of these parameters.

Notation: $M_{m \times n} (F)$ .

Definition

Let $A$ be any matrix, the rank is the number of pivots $rank (A) = r$ .

There are bounds to the rank. $rank (A) \leq min {m, n}$ .

Definition

System is consistent iff $rank (A) = rank ([A b])$ .

Proof:

Let $A$ and $[A b]$ be as given.

Let $[R c]$ be $RREF ([A b])$ .

Note that every pivot of $R$ is a pivot of $[R c]$ . This means $rank (A) \leq rank ([A b])$ .

$(⟹)$ First assume the system is consistent. Then $[R c]$ does not have a row of the form $[0 \dots 01]$ . That is, $[R c]$ does not have a pivot of $R$ . Hence $rank (A) = rank ([A b])$ .

$(⟸)$ Assume the system is inconsistent.

Therefore $[R c]$ has a row of the form $[0 \dots 01]$ . That $1$ is a pivot of $[R c]$ that is not a pivot of $R$ . Hence $rank (A) < rank ([A b])$ . That is $rank (A) = rank ([A b])$ .

Theorem

System Rank Theorem: Let $A \in M_{m \times n} (F)$ with $rank (A) = r$ . a) Let $b \in F^{m}$ . If the system of equations with augmented matrix $[A b]$ is consistent, then the solution set to this system will contain $n - r$ parameters. b) System with augmented matrix $[A b]$ is consistent for every $b \in F^{m}$ if and only if $r = m$ .

Sketch proof

$n$ is the number of columns $⟹$ $n$ is the number of variables. Rank is $r$ means $r$ pivots $⟹$ $r$ basic variables. $⟹$ $n - r$ free variables, $⟹$ $n - r$ parameters

$(⟸)$

Assume $r = m$ . Let $b \in F^{m}$ . Let $[R c]$ be $RREF ([A b])$ pivot in every row of $R$ . No $[0 \dots 01] ⟹$ consistent.

$(⟹)$

Assume $r \neq = m$ . Let $R = RREF (A)$ . There is a row without a pivot in $R$ . Hence $R$ has a zero-row. Say it is the $i$ th row. Hence $[R e_{i}]$ is inconsistent.

Using ERO in reverse, we get $[A b]$ which is inconsistent.

$nullity (A) = n - r$ .

Homogeneous Solutions: All elements on the right hand side are zero. Otherwise it is a non-homogeneous solution.

For homogeneous solutions, trivial solution $x_{1} = x_{2} = \dots = 0$ .

Solution to homogeneous system is called the nullspace of $A$ .

Matrix-Vector Multiplication

230 1 - 2 1 014 201 = 2 \cdot 2 + 1 \cdot 0 + 0 (- 1) 3 \cdot 2 + (- 2) 0 + 1 (- 1) 0 \cdot 2 + 1 \cdot 0 + 4 (- 1) = 2230 + 0 1 - 2 1 + (- 1) 614 = 45 - 4 = 45 - 4

Row Vector

$row_{i} (A) = [a_{i 1} a_{i 2} \dots a_{in}]$ .

Number of columns must be the same but $m$ doesn’t have to equal $n$ .

$[A b]$ can be written as $A x = b$ .

GJA works over $C$ also.

Example

$x_{1} - x_{2} - x_{3} - x_{4} = 1 x_{1} + x_{3} + x_{4} = 2 2 x_{1} - x_{2} = 3$

A = 112 - 1 0 - 1 - 1 10 - 1 10 b = 123

[A b] rref 100010120120210 x_{1} = - x_{3} - x_{4} + 2 x_{2} = - 2 x_{3} - 2 x_{4} + 1

x = x_{1} x_{2} x_{3} x_{4} = - x_{3} - x_{4} + 2 - 2 x_{3} - 2 x_{4} + 1 x_{3} x_{4} = 2100 + x_{3} - 1 210 + x_{4} - 1 - 2 01

$b$ determines whether or not the system is consistent. Structure really depends on $A$ .

[A 0] rref x = x_{3} - 1 210 + x_{4} - 1 - 2 01

Can partially/mostly understand $[A b]$ once we understand $[A 0]$ .

Notice $[A 0]$ is consistent. Note $0$ is a solution. Call it the trivial solution.

The set of all solutions to $A x = 0$ is called the nullspace of $A$ , written as $Null (A)$ .

Example

$Null (A) = ⎩ ⎨ ⎧ r - 1 210 + s - 1 - 2 01 : r, s \in R ⎭ ⎬ ⎫ = Span ⎩ ⎨ ⎧ - 1 210, - 1 - 2 01 ⎭ ⎬ ⎫$

Proposition: Let $S = Null (A)$ for some $A \in M_{m \times n}$ .

Let $u, v \in S$ . Let $c \in F$ . Then $u + v \in S$ and $c u \in S$ .

Proof:

To show $u + v \in Null (A)$ , we must show $A (u + v) = 0$ . Well, $A (u + v) = A u + A v = 0 + 0 = 0$ .

Proposition: Let $A \in M_{m \times n}$ . Let $b \in R^{m}$ such that $A x = b$ is consistent.

Let $c$ be a solution to $A x = b$ .

Let $T$ be the solution set to $A x = b$ .

Then $T = {c + y : y \in Null (A)} \leftarrow X$ .

So every solution to $A x = b$ is $c \cdot ($ a solution to $A x = 0)$ .

Proof:

Let $z \in X$ . So $z = c + v : v \in Null (A)$ .

We want to show $z \in T$ , i.e. that $A z = b$ .

Well, $A z = A (c + v) = A c + A v = b + 0 = b$ .

Let $z \in T$ . So $A z = b$ .

We want to show $z \in X$ , we want to show $z = c + Null (A)$ .

Note $A (z - c) = A z - A c = b - b = 0$ . So $z - c \in Null (A)$ .

So $z = c + \in Null (z - c)$ , so $z \in X$ .

$A x = b$ and $A x = 0$ are associated homogeneous systems.

Let $S$ be the solution set of $A x = b$ .

Let $T$ be the solution set of $A x = 0$ .

Suppose $c$ is a solution of $A x = b$ .

Then, $S = {c + z : z \in T}$ .

Suppose $A x = 0$ has solution set

⎩ ⎨ ⎧ r 1100 + s 1234 : s, r, \in R ⎭ ⎬ ⎫

Suppose $9999$ is a solution to $A x = b$ .

Give two more solutions.

101099 \to r = 1, s = 0 11121213 \to r = 1, s = 1

Consider now $A x = b_{1}$ , solution set $S_{1} \neq = \emptyset$ . Consider $A x = b_{2}$ , solution set $S_{2} \neq = \emptyset$ .

Suppose $c_{1}$ is a solution to $A x = b_{1}$ and $c_{2}$ is a solution to $A x = b_{2}$ .

Suppose $z$ is a solution to $A x = b_{1}$ .

Then $z - c_{1}$ is a solution to $A x = 0$ .

Then $z - c_{1} + c_{2}$ is a solution to $A x = b_{2}$ .

Theorem

$S_{2} = {z - c_{1} + c_{2} : z \in S_{1}}$

$A, b$ determines whether or not $A x = b$ is consistent. $A$ solely determines the structure of the set of all solutions.

Matrices

Let $A \in M_{m \times n}$ . Write $A = [a_{1} \dots a_{n}]$ with each $a_{i} \in R^{m}$ .

Column Space of $A$ , written as $Col (A)$ , is the $Span {a_{1}, \dots, a_{n}}$ .

A = [1324] Col (A) = Span {[13], [24]}

Let $A \in M_{m \times n} (F)$ and $b \in F^{m}$ . The system of linear equations $A x = b$ is consistent if and only if $b \in Col (A)$ .

Proof:

$(⟹)$

Assume $A x = b$ is consistent.

$\exists y = y_{1} ⋮ v y_{n}$ such that $A y = b$ .

So $b = y_{1} a_{1} + \dots + y_{n} a_{n}$ . So $b \in Col (A)$ .

$(⟸)$

Assume $b \in Col (A)$ . Thus $\exists c_{1}, \dots, c_{n} \in F$ .

Such that $c_{1} a_{1} + \dots c_{n} a_{n} = b$ .

So $A c_{1} ⋮ c_{n} = b$ .

So $c$ is a solution to $A x = b$ . So $A x = b$ is consistent.

Let $A \in M_{m \times n} (F)$ . We define the transpose of $A$ , denoted $A^{⊺}$ , by $(A^{⊺})_{ij} = (A)_{ji}$ .

Note: Rows become columns, columns become rows.

Example

$A = [142536] \to A^{⊺} = 123456$

Let $A \in M_{m \times n} (F)$ . We define the row space of $A$ , denoted by $Row (A)$ , to be the span of the transposed rows of $A$ . That is,

Row (A) = Span {(row_{1} (A))^{⊺}, (row_{2} (A))^{⊺}, \dots, (row_{m} (A))^{⊺}}

Note: Turn rows into vectors and then take their linear combinations. $Row (A) = Col (A^{⊺})$ .

Example

$A = [142536] Row (A) = Span ⎩ ⎨ ⎧ 123, 456 ⎭ ⎬ ⎫$

Let $A, B \in M_{m \times n} (F)$ . If $B$ is row equivalent to $A$ , then

Row (B) = Row (A)

EROs do not change the row space, but EROs do change the column space.

Let $A, B \in M_{m \times n} (F)$ . Prove that $A x = a_{i}$ is consistent for $1 \leq i \leq n$ .

Proof:

A e_{i} = 0 a_{1} + 0 a_{2} + \dots + 1 a_{i} + \dots + 0 a_{n} = a_{i}

$a_{i}$ is in $Col (A)$ , thus $a_{i}$ is consistent.

Let $A = [a_{1} \dots a_{n}] \in M_{m \times n} (F)$ . Then $A e_{i} = a_{i}$ for all $i = 1, \dots, n$ .

In other words, the matrix-vector multiplication of $A$ and the $i$ th standard basis vector $e_{i}$ yields the $i$ th column of $A$ . Useful result used later.

A = [142536] A 010 = [25]

Let $A, B \in M_{m \times n} (F)$ . Then

A = B ⟺ A x = B x \forall x \in F^{n}

$(⟹)$ Assume $A = B$ , then $A x = B x$ $\forall x \in F^{m}$ .

$(⟸)$ Assume $A x = B x$ $\forall x \in F^{m}$ .

So $A e_{i} = B e_{i}$ for $1 \leq i \leq n$ .

By column extraction, $A e_{i} = a_{i}$ , $B e_{i} = b_{i}$ .

So $a_{i} = b_{i}$ . So the columns of $A$ and $B$ match. So $A = B$ .

Matrix Product

Let $A \in M_{m \times n} (F)$ and $B \in M_{n \times p} (F)$ . We define the matrix product $A B = C$ to be the matrix $C \in M_{m \times p} (F)$ , constructed as follows:

C = A B = A [b_{1} b_{2} \dots b_{p}] = [A b_{1} A b_{2} \dots A b_{p}]

That is, the $j$ th column of $C$ , $c_{j}$ is obtained by multiplying the matrix $A$ by the $j$ th column of the matrix $B$ :

c_{j} = A b_{j}, \forall j = 1, \dots, p

Note: Number of columns of first matrix must match the number of rows of the second matrix.

Note: Each column of $A B$ is an element of $Col (A)$ .

A B = [10 - 3 5] [0 - 1 24] = [1 (0) + (- 3) (- 1) 0 (0) + 5 (- 1) 1 (2) + (- 3) (4) 0 (2) + 5 (4)] = [3 - 5 - 10 20]

If $A B = C$ , then to find $C_{ij}$ , take the “dot product” of $i$ th row of $A$ and $j$ th column of $B$ .

C_{ij} = k = 1 \sum n a_{ik} b_{kj}

Matrix Sum

Let $A, B \in M_{m \times n} (F)$ . We define the matrix sum $A + B = C$ to be the matrix $C \in M_{m \times n} (F)$ whose $(i, j)$ th entry is $c_{ij} = a_{ij} + b_{ij}$ , for all $i = 1, \dots, m$ and $j = 1, \dots, n$ .

The matrices must be the same size.

[1 - 2 31] + [- 1 0 52] = [0483]

Properties:

$A + B = B + A$
$A + B + C = (A + B) + C = A + (B + C)$

The $m \times n$ zero matrix is the matrix $O_{m \times n} \in M_{m \times n} (F)$ all of whose entries are $0$ .

Let $A \in M_{m \times n} (F)$ . We define the additive inverse of $A$ to be the matrix $- A$ whose $(i, j)$ th entry is $- a_{ij}$ for all $i = 1, \dots, m$ and $j = 1, \dots, n$ .

If $A \in M_{m \times n} (F)$ , then

$O + A = A + O = A$
$A + (- A) = (- A) + A = O$

If $A, B \in M_{m \times n} (F)$ , $C, D \in M_{n \times p} (F)$ and $E \in M_{p \times q} (F)$ , then

$(A + B) C = A C + BC$
$A (C + D) = A C + A D$
$(A C) E = A (CE) = A CE$

Proof of $(A + B) C = A C + BC$

[(A + B) C]_{ij} = k = 1 \sum n [A + B]_{ik} c_{kj} = k = 1 \sum n (a_{ik} + b_{ik}) c_{kj} = k = 1 \sum n (a_{ik} c_{kj} + b_{ik} + c_{kj}) = k = 1 \sum n a_{ik} c_{kj} + k = 1 \sum n b_{ik} c_{kj} = [A C]_{ij} + [BC]_{ij} = [A C + BC]_{ij}

Let $A \in M_{m \times n} (F)$ and $c \in F$ . We define the product of $c$ and $A$ to be the matrix $c A \in M_{m \times n} (F)$ whose $(i, j)$ th entry is $(c A)_{ij} = c a_{ij}$ for all $i = 1, \dots, m$ and $j = 1, \dots, n$ .

2 [1324] = [2648]

If $A, B \in M_{m \times n} (F)$ and $C \in M_{n \times k} (F)$ , then

$s (A + B) = s A + s B$
$(r + s) A = r A + s A$
$r (s A) = (rs) A$
$s (A C) = (s A) C = A (s C)$ . Thus we may write $s A C$ for any of these three quantities unambiguously.

Also, $(- 1) A = - A$ .

More properties for transpose:

$(A + B)^{⊺} = A^{⊺} + B^{⊺}$
$(s A)^{⊺} = s A^{⊺}$
$(A C)^{⊺} = C^{⊺} A^{⊺}$
$(A^{⊺})^{⊺} = A$

Proof of $(A + B)^{⊺} = A^{⊺} + B^{⊺}$ .

[(A + B)^{⊺}] = [A + B]_{ji} = a_{ji} + b_{ji} = [A^{⊺}]_{ij} + [B^{⊺}]_{ij} = [A^{⊺} + B^{⊺}]_{ij}

A matrix $A \in M_{n \times n} (F)$ where the number of rows is equal to the number of columns is called a square matrix.

Let $A \in M_{n \times n} (F)$ . We say that $A$ is upper triangular if $a_{ij} = 0$ for $i > j$ with $i = 1, \dots, n$ and $j = 1, \dots, n$ .

Square matrices in REF or RREF are upper triangular.

Let $B \in M_{n \times n} (F)$ . We say that $B$ is lower triangular if $b_{ij} = 0$ for $i < j$ with $i = 1, \dots, n$ and $j = 1, \dots, n$ .

We say that an $n \times n$ matrix $A$ is diagonal if $a_{ij} = 0$ for $i \neq = j$ with $i = 1, \dots, n$ and $j = 1, \dots, n$ . We refer to the entries $a_{ii}$ as the diagonal entries of $A$ , and denote our matrix $A$ by $A = diag (a_{11}, a_{22}, \dots, a_{nn})$ .

Diagonal matrices are both upper and lower triangular. If $A$ is upper triangular, then $A^{⊺}$ is lower triangular. If $A$ is lower triangular, then $A^{⊺}$ is upper triangular.

If $A$ is diagonal then $A^{⊺} = A$ .

The diagonal matrix $diag (1, 1, \dots, 1)$ is called the identity matrix, and is denoted by $I$ . If we wish to indicate that the size of the identity matrix is $n \times n$ , we add a subscript $n$ and write $I_{n}$ .

The identity matrix is the multiplicative identity. $A \in M_{m \times n}$ $I_{m} A = A$ and $A I_{n} = A$ .

Also, $c I_{n} = diag (c, c, \dots, c)$ .

Question

Does there exist $A \in M_{2 \times 2} (R)$ where $A \neq = O_{2}$ , such that $A^{2} = O_{2}$ .

[11 - 1 - 1] [11 - 1 - 1] = [0000]

A square matrix $P$ is called idempotent if $P^{2} = P$ .

A matrix that can be obtained by performing a single ERO on the identity matrix is called an elementary matrix.

Let $A \in M_{m \times n} (F)$ and suppose that a single ERO is performed on it to produce matrix $B$ . Suppose, also, that we perform the same ERO on the matrix $I_{m}$ to produce the elementary matrix $E$ . Then

B = E A

Let $A \in M_{m \times n} (F)$ and suppose that a finite number of EROs, numbered 1 through $k$ , are performed on $A$ to produce a matrix $B$ . Let $E_{i}$ denote the elementary matrix corresponding to the $i$ th ERO $(1 \leq i \leq k)$ applied to $I_{m}$ . Then

B = E_{k} \dots E_{2} E_{1} A

We say that an $n \times n$ matrix $A$ is invertible if there exist $n \times n$ matrices $B$ and $C$ such that $A B = C A = I_{n}$ .

Note: Inverses don’t always exist. Try to find an inverse of $[1000]$ .

[1000] [a c b d] = [a 0 b 0]

won’t ever equal the identity $I_{2}$ .

Let $A \in M_{n \times n} (F)$ . If there exists matrices $B$ and $C$ in $M_{n \times n} (F)$ such that $A B = C A = I_{n}$ , then $B = C$ .

If left and right inverses exist, then they must be equal.

Assume $A B = I_{n}$ , $C A = I_{n}$ .

B = I_{n} B = \underline{C A} B = C \underline{A B} = C I_{n} = C

For $A \in M_{n \times n} (F)$ , there exists an $n \times n$ matrix $B$ such that $A B = I_{n}$ if and only if there exists an $n \times n$ matrix $C$ such that $C A = I_{n}$ .

Proof

( $⟹$ )

Assume $A B = I_{n}$ .

Consider the homogeneous system $B v = 0$ .

A B x I_{n} x x = A 0 = 0 = 0

So $B x = 0$ has a unique solution $⟹$ no parameters.

So by System-Rank $rank (B) = n$ .

So by System-Rank $B x = v ec b$ is consistent $\forall b \in F^{n}$ . So $\exists y \in F^{n}$ such that $B y = b$ .

B A b = B A B y = B I_{n} y = B y = b = I_{n} b

So $\forall b \in F^{n}$ , $B A b = I_{n} b$ . So by Matrix Equality, $B A = I_{n}$ . So $B$ is a left inverse of $A$ . We have proved that if $B$ is a right inverse of $A$ , then $B$ is a left inverse of $A$ .

( $⟸$ )

Assume $C A = I_{n}$ .

(C A)^{⊺} = (I_{n})^{⊺} A^{⊺} C^{⊺} = I_{n}

So $C^{⊺}$ is the right inverse of $A^{⊺}$ . But by $⟹$ , $C^{⊺}$ is the left inverse of $A^{⊺}$ .

C^{⊺} A^{⊺} (A C)^{⊺} A C = I_{n} = I_{n} = I_{n}

So $C$ is a right inverse.

Question

Is the inverse unique?

Yes.

Assume $A B_{1} = A B_{2} = I_{n}$ .

A B_{1} B_{1} A B_{1} = A B_{2} = B_{1} A B_{2}

But if $B_{1}$ is a right inverse, it is also a left inverse. So, $B_{1} A = I_{n}$ .

I_{n} B_{1} B_{1} = I_{n} B_{2} = B_{2}

If an $n \times n$ matrix $A$ is invertible, we refer to the matrix $B$ such that $A B = I_{n}$ as the inverse of $A$ . We denote the inverse of $A$ by $A^{- 1}$ . The inverse of $A$ satisfies

A A^{- 1} = A^{- 1} A = I_{n}

Note: To check that a matrix $B$ is the inverse of $A$ , only need to show $A B = I_{n}$ .

Example

Let $A = [0110]$ . Prove that $A^{- 1} = A$ .

AA = [0110] [0110] = [1001]

So $A^{- 1} = A$ .

Let $A \in M_{n \times n} (F)$ . The following three conditions are equivalent:

a) $A$ is invertible

b) $rank (A) = n$

c) $RREF (A) = I_{n}$

Prove $a ⟹ b ⟹ c ⟹ a$ .

$a ⟹ b$

Assume $A$ is invertible. Then $\exists C$ , such that $C A = I_{n}$ . Use proof of forward direction of left invertible iff right invertible to get $rank (A) = n$ .

$b ⟹ c$

Assume $rank (A) = n$ . Since $A \in M_{n \times n}$ , then there is a pivot in every row and column of $RREF (A)$ . All of these pivots are 1. So $RREF (A) = I_{n}$ .

$c ⟹ a$

Assume $rank (A) = I_{n}$ . So $rank (A)$ = # of rows.

So $A x = b$ is consistent $\forall v \in F^{n}$ .

So $A x = e_{i}$ is consistent for $1 \leq i \leq n$ .

Let $b_{i}$ be the solution to $A x = e_{i}$ . So $A b_{i} = e_{i}$ .

Let $B = [b_{1} \dots b_{n}]$

A B = A [b_{1} \dots b_{n}] = [A b_{1} A b_{2} \dots A b_{n}] = [e_{1} e_{2} \dots e_{n}] = I_{n}

So $A B = I_{n}$ . So $B = A^{- 1}$ , and $A$ is invertible.

Proof of $c ⟹ a$ gives an algorithm on how to find $A^{- 1}$ .

Need to solve $A x = e_{1}, \dots, A x = e_{n}$ .

Solve using super augmented matrix.

[A e_{1} e_{2} \dots e_{n}] = [A I_{n}]

If $RREF (A) = I_{n}$ then the right side of $RREF (A ∣ I_{n})$ will be $A^{- 1}$ .

If $RREF (A) \neq = I_{n}$ then $A$ is not invertible.

Let $A = [a c b d]$ . Then $A$ is invertible if and only if $a d - b c \neq = 0$ . Furthermore, if $a d - b c \neq = 0$ , then

A^{- 1} = \frac{1}{a d - b c} [d - c - b a]

Linear Transformations

Let $A \in M_{n \times n} (F)$ . The function determined by the matrix $A$ is the function

T_{A} : F^{n} \to F^{m}

defined by

T_{A} (x) = A x

In linear algebra, we use the words transformation or mapping instead of function.

We say that the function $T : F^{n} \to F^{m}$ is a linear transformation if, for any $x$ , $y \in F^{n}$ and any $c \in F$ , the following two properties hold.

$T (x + y) = T (x) + T (y)$ (called linearity over addition)
$T (c x) = c T (x)$ (called linearity over scalar multiplication)

We refer to $F^{n}$ here as the domain of $T$ and $F^{m}$ as the codomain of $T$ , as we would for any function.

Question

Is $T_{A}$ a linear transformation?

T_{A} (x + y) T_{A} (c x) = A (x + y) = A x + A y = T_{(} x) + T_{A} (y) = A (c x) = c A (x) = c T_{A} (x)

Let $A \in M_{n \times n} (F)$ and let $T_{A}$ be the function determined by the matrix $A$ . Then $T_{A}$ is linear; that is, for any $x, y \in F^{n}$ and any $c \in F$ , the following two properties hold.

$T_{A} (x + y) = T_{A} (x) + T_{A} (y)$
$T_{A} (c x) = c T_{A} (x)$

We will call $T_{A}$ the linear transformation determined by $A$ .

Let $T : F^{n} \to F^{m}$ be a function. Then $T$ is a linear transformation if and only if for any $x, y \in F^{n}$ and any $c \in F$ ,

T (c x + y) = c T (x) + T (y)

When proving a transformation is linear, it can be shorter to prove this version.

Let $T : F^{n} \to F^{m}$ be a linear transformation. Then

T (0_{F^{n}}) = 0_{F^{m}}

Proof:

T (0_{F^{n}}) = T (0_{x}) x \in F^{n} = 0 T (x) by linearity = 0_{F^{m}}

Useful to show that a transformation is not linear.

T_{1} T_{1} x_{1} x_{2} x_{3} = R^{3} \to R^{2} = [x_{1} + x_{2} 2]

T_{1} 000 = [02] \neq = [00]

$T_{1}$ is not linear.

Applying ideas about functions to linear transformations.

Range
Onto
One-to-one

Let $T : F^{n} \to F^{m}$ be a linear transformation. We define the range of $T$ , denoted $Range (T)$ , to be the set of all outputs of $T$ . That is,

Range (T) = {T (x) : x \in F^{n}}

The range of $T$ is a subset of $F^{m}$ .

Note: $T (0_{F^{n}}) = 0_{F^{m}}$ . So $Range (T) \neq = \emptyset$ .

Let $A \in M_{m \times n} (F)$ , and let $T_{A} : F^{n} \to F^{m}$ be the linear transformation determined by $A$ .Then range is the column space, $Range (T_{A}) = Col (A)$ .

Proof

x \in Range (T_{A}) ⟺ x = A y for some y \in F^{m} ⟺ x \in Col (A)

A system of linear equations $A x = b$ is consistent if and only if $b \in Range (T_{A})$ .

We say that the transformation $T : F^{n} \to F^{m}$ is onto (or surjective) if $Range (T) = F^{n}$ .

Scaling is onto. Projection onto x-axis is not onto.

Let $A \in M_{m \times n} (F)$ and let $T_{A}$ be the linear transformation determined by the matrix $A$ . The following statements are equivalent.

a) $T_{A}$ is onto

b) $Col (A) = F^{m}$

c) $rank (A) = m$

$a ⟹ b$

Assume $T_{A}$ is onto. $Range (T_{A}) = F^{m}$ . $Range (T_{A}) = Col (A)$ . So $Col (A) = F^{m}$ .

$b ⟹ c$

Assume $Col (A) = F^{m}$ . Since $Col (A) = F^{m}$ then $A x = b$ is consistent for all $b \in F^{m}$ . So $rank (A) = m$ by System Rank Theorem.

$c ⟹ a$

Assume $rank (A) = m$ .

$A x = b$ is consistent $\forall b \in F^{m}$ (System Rank). So $Col (A) = F^{m} = Range (T_{A}) = F^{m}$ .

Let $T : F^{n} \to F^{m}$ be a linear transformation. We define the kernel of $T$ , denoted by $Ker (T)$ , to be the set of inputs of $T$ whose output is zero. That is,

Ker (T) = {x \in F^{n} : T (x) = 0_{F^{m}}}

The kernel of $T$ is a subset of $F^{n}$ .

Since $T$ is linear, $T (0_{F^{n}}) = 0_{F^{m}}$ . So $0_{F^{n}} \in Ker (T)$ . So $Ker (T) \neq = \emptyset$ .

Let $A \in M_{m \times n} (F)$ and let $T_{A} : F^{n} \to F^{m}$ be the linear transformation determined by $A$ . Then

Ker (T_{A}) = Null (A)

Note:

Let x \in Ker (T_{A}) ⟺ T_{A} (x) = 0_{F^{m}} ⟺ A x = 0 ⟺ x \in Null (A)

$Ker (T_{A}) =$ solution set of $A x = 0$ .

We say that the transformation $T : F^{n} \to F^{m}$ is one-to-one (or injective) if whenever $T (x) = T (y)$ then $x = y$ .

Contrapositive: $x \neq = y ⟹ T (x) \neq = T (y)$ .

Distinct inputs map to distinct outputs.

Let $T : F^{n} \to F^{m}$ be a linear transformation. Then

T is one-to-one ⟺ Ker (T) = {0_{F^{n}}}

( $⟹$ )

Assume $T$ is one-to-one.

We know that ${0_{F^{n}}} \subseteq Ker (T)$ .

Let $x \in Ker (T)$ . So $T (x) = 0_{F^{m}} = T (0_{F^{n}})$ But $T$ is one-to-one so $x = 0_{F^{m}}$ .

( $⟸$ )

Assume $Ker (T) = {0_{F^{n}}}$

Let $x$ and $y \in F^{n}$ . Assume $T (x) = T (y)$ .

T (x) - T (y) T (x - y) = 0_{F^{m}} = 0_{F^{m}}

Let $A \in M_{n \times n} (F)$ and let $T_{A}$ be the linear transformation determined by the matrix $A$ . The following statements are equivalent.

a) $T_{A}$ is one-to-one

b) $Null (A) = {0_{F^{n}}}$

c) $nullity (A) = 0$

d) $rank (A) = n$ .

$a ⟹ b$

Assume $T_{A}$ is one-to-one. $Ker (T_{A}) = {0_{F^{n}}}$ . $Ker (T_{A}) = Null (A)$ .

$b ⟹ c$

Assume $Null (A) = {0_{F^{n}}}$ .

So $A x = 0$ has a unique solution $(0_{F^{n}})$ . So no parameters $⟹$ $nullity (A) = 0$ .

$c ⟹ d$

Assume $nullity (A) = 0$ . So $n - rank (A) = 0$ . So $rank (A) = n$ .

$d ⟹ a$

Assume $rank (A) = n$ .

Consider $A x = 0_{F^{n}}$

We know $x = 0_{F^{n}}$ is a solution so the system is consistent. Since $rank (A) = n$ the number of parameters $= 0$ . So $x = 0_{F^{n}}$ is the only solution. So $Null (A) = {0_{F^{n}}} = Ker (T_{A})$ .

Let $A \in M_{n \times n} (F)$ be a square matrix and let $T_{A}$ be the linear transformation determined by the matrix $A$ . The following statements are equivalent.

a) $A$ is invertible

b) $T_{A}$ is one-to-one

c) $T_{A}$ is onto

d) $Null (A) = {0}$ . That is, the only solution to the homogeneous system $A x = 0$ is the trivial solution $x = 0$ .

e) $Col (A) = F^{n}$ . That is, for every $b \in F^{n}$ , the system $A x = b$ is consistent.

f) $nullity (A) = 0$

g) $rank (A) = n$

h) $RREF (A) = I_{n}$

Let $T : F^{n} \to F^{m}$ be a linear transformation. We define the standard matrix of $T$ , denoted by $[T]_{ε}$ , to be $m \times n$ matrix whose columns are the images under $T$ of the vectors in the standard basis of $F^{n}$ :

[T]_{ε} = [T (e_{1}) T (e_{2}) T (e_{n})] = T 10 ⋮ 0 T 01 ⋮ 0 T 00 ⋮ 1

Let $T : F^{n} \to F^{m}$ be a linear transformation and let $[T]_{ε}$ be the standard matrix of $T$ . Then for all $x \in F^{n}$ ,

T (x) = [T]_{ε} x

That is, $T = T_{[T]_{ε}}$ is the linear transformation determined by the matrix $[T]_{ε}$

We can express every linear transformation in a compact way using multi-vector multiplication.

We can find it by finding $T (e_{i})$ $\forall i$ .

We can calculate $T (x)$ using matrix-vector multiplication.

Question

Is $p ro j_{w}$ onto?

Range (p ro j_{w}) = Col (\frac{1}{w _{1}^{2} + w _{2}^{2}}) [w_{1}^{2} w_{1} w_{2} w_{1} w_{2} w_{2}^{2}] = Span {\frac{w _{1}}{w _{1}^{2} + w _{2}^{2}} [w_{1} w_{2}], \frac{w _{2}}{w _{1}^{2} + w _{2}^{2}} [w_{1} w_{2}]} = Span {[w_{1} w_{2}]} \neq = R^{2}

So it’s not onto. This geometrically makes sense.

Given linear transformation $T : R^{n} \to R^{m}$ we can find an $m \times n$ matrix $[T]_{ε}$ such that $T (x) = [T]_{ε} x$ .

Given $A \in M_{m \times n} (F)$ we can create $T_{A} : R^{n} \to R^{m}$ where $T_{A} (x) = A x$ .

Let $A \in M_{m \times n} (F)$ , let $T_{A} : F^{n} \to F^{m}$ be the linear transformation determined by $A$ , and let $T : F^{n} \to F^{m}$ be a linear transformation. Then

a) $T_{[T]_{ε}} = T$

b) $[T_{A}]_{ε} = A$

c) $T$ is onto if and only if $rank ([T]_{ε}) = m$

d) $T$ is one-to-one if and only if $rank ([T]_{ε}) = n$

a)

$\forall x \in F^{n}$

T_{[T]_{ε}} x = [T]_{ε} x = T (x)

So $T_{[T]_{ε}}$ and $T$ determine the same transformation.

b)

[T_{A}]_{ε} = [T_{A} (e_{1}) \dots T_{A} (e_{n})] = [A e_{1} \dots A e_{n}] = [a_{1} \dots a_{n}] = A

c)

Follows from onto criteria.

d)

Follows from one-to-one criteria.

Let $T_{1} : F^{n} \to F^{m}$ and $T_{2} : F^{m} \to F^{p}$ be linear transformations. We define the function $T_{2} \circ T_{1} : F^{n} \to F^{p}$ by

(T_{2} \circ T_{1}) (x) = T_{2} (T_{1} (x))

The function $T_{2} \circ T_{1}$ is called the composite function of $T_{2}$ and $T_{1}$ .

Let $T_{1} : F^{n} \to F^{m}$ and $T_{2} : F^{m} \to F^{p}$ be linear transformations. Then $T_{2} \circ T_{1}$ is a linear transformation.

Proof:

(T_{2} \circ T_{1}) (c x + y) = T_{2} (T_{1} (c x + y)) = T_{2} (c T_{1} (x) + T_{1} (y)) = c T_{2} (T_{1} (x)) + T_{2} (T_{1} (y)) = c (T_{2} \circ T_{1}) (x) + (T_{2} \circ T_{1}) (x)

So $T_{2} \circ T_{1}$ is linear.

Let $T_{1} : F^{n} \to F^{m}$ and $T_{2} : F^{m} \to F^{p}$ be linear transformations. Then the standard matrix of $T_{2} \circ T_{1}$ is equal to the product of standard matrices of $T_{2}$ and $T_{1}$ . That is,

[T_{2} \circ T_{1}]_{ε} = [T_{2}]_{ε} [T_{1}]_{ε}

Proof

Let $x \in F^{n}$

[T_{2} \circ T_{1}]_{ε} x = (T_{2} \circ T_{1}) (x) = T_{2} (T_{1} (x)) = T_{2} ([T_{1}]_{ε} x) = [T]_{ε} ([T_{1}]_{ε} x) = ([T_{2}]_{ε} [T_{1}]_{ε}) x [T_{2} \circ T_{1}]_{ε} = [T_{1}]_{ε} [T_{2}]_{ε}

Let $T : R^{2} \to R^{2}$ be the linear transformation which rotates a vector counterclockwise about the origin by an angle of $α$ and then rotates the result counterclockwise about the origin by an angle of $β$ . Find the standard matrix of the transformation of $T$ .

[R_{β} \circ R_{α}] = [R_{β}]_{ε} [R_{α}]_{ε} = [cos β sin β - sin β cos β] [cos α sin α - sin α cos α] = [cos β cos α - sin β sin α sin β cos α + cos β sin α - cos β sin α - sin β cos α - sin α sin β + cos β cos α] = [cos (β + α) sin (β + α) - sin (β + α) cos (β + α)]

Determinants

$A = [a c b d]$ and $a d - b c \neq = 0$ then $A^{- 1} = \frac{1}{a d - b c} [d - c - b a]$ .

Goal is to identify a single value that tells us if a matrix is invertible.

Let $A = [a_{11}] \in M_{1 \times 1} \in F$ .

Determinant is $det (A) = a_{11}$ .

Let $A = [a_{11} a_{21} a_{12} a_{22}]$ .

Determinant is $det (A) = a_{11} a_{22} \cdot a_{12} a_{21}$ .

Examples of submatrices and minors

Let $A = 223 2 - 5 0 - 1 14$

Then $M_{12} (A) = [2314]$

Delete the first row and second column.

The $(1, 2)$ minor of $A$ is $det ([2314]) = 5$

The determinant of an $n \times n$ matrix is

det (A) = j = 1 \sum n a_{ij} (- 1)^{1 + j} det (M_{1 j} (A)) for \in M_{n \times n}

Example of a $3 \times 3$ determinant.

det (A) = a_{11} (- 1)^{1 + 1} det (M_{11} (A)) + a_{12} (- 1)^{1 + 2} det (M_{12} (A)) + a_{13} (- 1)^{1 + 3} det (M_{13} (A)) = 2 (- 1)^{2} det ([- 5 0 14]) + 2 (- 1)^{3} det ([2314]) + (- 1) (- 1)^{4} det ([23 - 5 0]) = 2 (- 20) - 2 (5) - 15 = - 65

Revisiting $2 \times 2$ example

det ([2314]) = a_{11} (- 1)^{1 + 1} det ([4]) + = a_{12} (- 1)^{1 + 2} det ([3]) = 2 (- 1)^{2} (4) + 1 (- 1)^{3} (3) = 8 - 3 = 5

Same result as $2 (4) - 1 (3)$ .

Can also fix $i$ to be any row. Can also fix $j$ to be any column, and iterate by $i$ .

If row has all $0$ , $det (A) = 0$ . If col has all $0$ , $det (A) = 0$ .

If upper-triangular / lower-triangular, $det =$ product of diagonal.

$det (I_{n}) = 1$ .

If $A \in M_{n \times n} (F)$ . Then $det (A) = det (A^{⊺})$ .

EROs and Determinants

Applying $R_{1} \to 2 R_{1}$ to $A$ gives

423 4 - 5 0 - 2 14

and the determinant of this is $2 (- 65) = - 130$ .

Applying $R_{2} \leftrightarrow R_{3}$ to $A$ gives

232 20 - 5 - 1 41

and the determinant of this is $(- 1) (- 65) = 65$ .

Row addition (adding multiple of one row to another row) does not change the determinant.
Row swap (if $B$ is obtained by swapping $A$ , $det (B) = - det (A)$ )
Row scale (if $B$ is obtained by scaling $A$ , $det (B) = - det (A)$ )

If $A$ has two identical rows or cols then $det (A) = 0$ .

$det (E) \neq = 0$ for any elementary matrix $E$ .

Let $A \in M_{n \times n} (F)$ . Then $A$ is invertible iff $det (A) \neq = 0$ .

Proof:

Let $A \in M_{n \times n} (F)$ . Let $R = RREF (A)$ then $R = E_{k} \dots E_{2} E_{1} A$ for some elementary matrices $E_{1}, E_{2}, \dots, E_{k}$ .

And we just saw that this means $det (R) = det (E_{k}) \dots det (E_{2}) det (E_{1}) det (A)$ .

$(⟹)$ Suppose $A$ is invertible.

Then $R$ ( $R = RREF (A)$ ) $= I_{n}$ and so $det (R) = 1$ . Hence $det (A) \neq = 0$ .

( $⟸$ ) Suppose $A$ is not invertible.

Then $R$ has a row of zeroes. Thus $det (R) = 0$ . Since $det (E_{i}) \neq = 0$ for $i = 1, \dots, k$ we get $det (A) = 0$ .

Question

For what values of $110211 k 21$ invertible?

Using result just proved, it will be invertible if and only if the determinant is not zero.

1 (1) (1 (1) - 2 (1)) + 1 (- 1) (2 - k) = - 3 + k

Hence it is invertible as long as $k$ is not $3$ .

det (A B) det (A B) = det (A) det (B) = det (B A) even if B A \neq = A B

Let $A$ be invertible, $det (A^{- 1}) = \frac{1}{d e t ( A )}$ . Since $A A^{- 1} = I_{n}$ and $det (A) \neq = 0$ since $A$ is invertible.

Cofactors and Adjugate Examples

Let $A = 24 - 1 305 - 2 - 6 2$ . Note $det (A) = 14$ .

$C_{12} (A) = (- 1)^{3} det ([4 - 1 - 6 2]) = - 2$

(Adj (A))^{⊺} = matrix of cofactors 30 - 16 - 18 - 2 24 20 - 13 - 12

So, the $adj (A) = 30 - 2 20 - 16 2 - 13 - 18 4 - 12$

adj (A) A = 30 - 2 20 - 16 2 - 13 - 18 4 - 12 24 - 1 305 - 2 - 6 2 = 140001400014 = det (A) I_{3}

Theorem

$A adj (A) = adj (A) A = det (A) I_{n}$

Inverse by Adjugate

If det (A) \neq = 0, A^{- 1} = \frac{1}{det ( A )} adj (A)

Cramers Rule

Let $A \in M_{n \times n} (F)$ and consider $A x = b$ where $b \in F^{n}$ and $det (A) \neq = 0$ .

$B_{j}$ from $A$ by replacing the $j$ th column of $A$ by the column vector $b$ , then the solution $A x = b$ is $x_{j} = \frac{d e t ( B _{j} )}{d e t ( A )}$ , for all $j = 1, \dots, n$ .

Useful when you care about the value of one of the variables in the solution to a system of equations with a square coefficient matrix $A$ , where $det (A) \neq = 0$ .

Let $v = [v_{1} v_{2}]$ and $w = [w_{1} w_{2}]$ be vectors in $R^{2}$ .

The area of the parallelogram with sides $v$ and $w$ is $det ([v_{1} v_{2} w_{1} w_{2}])$ .

How does projection onto the line with equation

l = t [w_{1} w_{2}], t \in R

affect area.

Expect scaling factor of $0$ .

[p ro j_{w}]_{ε} ∣ det [p ro j_{w}]_{ε} ∣ = \frac{1}{w _{1}^{2} + w _{2}^{2}} [w_{1}^{2} w_{1} w_{2} w_{1} w_{2} w_{2}^{2}] = (\frac{1}{w _{1}^{2} + w _{2}^{2}})^{2} det [w_{1}^{2} w_{1} w_{2} w_{1} w_{2} w_{2}^{2}] = (\frac{1}{w _{1}^{2} + w _{2}^{2}})^{2} (w_{1}^{2} w_{2}^{2} - w_{1} w_{2} w_{1} w_{2}) = 0

Eigenvalues and Diagonalization

Eigenvalues and eigenvalues help us understand all linear transformations.

Non zero vector $x$ is an eigenvector of $A$ over $F$ if there exists a scalar $λ \in F$ such that

A x = eigenvalue λ x (λ, x) is an eigenpair

Consider projections onto $y = x$ . We have $A = [\frac{1}{2} \frac{1}{2} \frac{1}{2} \frac{1}{2}]$ .

Comes from earlier work to derive $[p ro j_{w}]_{ε}$

[\frac{1}{2} \frac{1}{2} \frac{1}{2} \frac{1}{2}] [t t] = [t t] = 1 \cdot [t t]

Thus $λ = 1$ is an eigenvalue for $A$ . An eigenpair is $(1, [66])$ .

Note

[\frac{1}{2} \frac{1}{2} \frac{1}{2} \frac{1}{2}] [t - t] = [00] = 0 [t - t]

Thus $λ = 0$ is another eigenvalue and an eigenpair is $(0, [1 - 1])$ .

Only 2 eigenvalues (with infinite eigenpairs).

0 is an eigenvalue ⟺ A x = 0 x = 0 for some x = 0 ⟺ x \in Null (A) for some x \neq = 0 ⟺ Null (A) \neq = {0} ⟺ A is not invertible

Fixed points

$T (x) = x$
$A x = x$
$λ = 1$ is an eigenvalue

We saw that $[t t]$ is a fixed point of projection onto $y = x$ .

Projection onto the y-axis.

Then $A = [0001]$

Note that $[0001] [0 t] = 1 [0 t]$ .

Thus all points on the y-axis are fixed points.

Rotation by $\frac{π}{2}$ . Then $A = [01 - 1 0]$ . Expect no fixed points.

Indeed $[01 - 1 0] [x y] = [x y] = [- y x]$ .

This would mean $x = - y$ , $x = y$ . Then $x = y = 0$ . But $0$ cannot be an eigenvector.

Finding eigenvalues

A x = λ x ⟺ A x - λ x = 0 ⟺ A x - λ I_{n} x = 0 ⟺ (A - λ I_{n}) x = 0

Then an eigenvector $x \neq = 0$ exists iff there is a $λ \in F$ such that $(A - λ I_{n}) x = 0$ .

That is iff $Null (A - λ I_{n}) \neq = {0}$ iff $A - λ I_{n}$ is not invertible.

That is, iff $det (A - λ I_{n}) = 0$ .

Characteristic Polynomial

$C_{A} = det (A - λ I_{n})$ . $C_{A} (λ) = 0$ .

Examples

Projection onto $y = x$ .

C_{A} (λ) = det (A - λ I_{2}) = det ([\frac{1}{2} \frac{1}{2} \frac{1}{2} \frac{1}{2}] - [λ 0 0 λ]) = det ([\frac{1}{2} - λ \frac{1}{2} \frac{1}{2} \frac{1}{2} - λ]) = (\frac{1}{2} - λ)^{2} - (\frac{1}{2}) = λ^{2} - λ

Solving $C_{A} (λ) = 0$ gives $λ = 1$ and $λ = 0$ .

Rotation by $\frac{π}{2}$ .

$A = [01 - 1 0]$ . We want to solve

000 = det ([01 - 1 0] - [λ 0 0 λ]) = det ([- λ 1 - 1 - λ]) = λ^{2} + 1

The eigenvalues are $\pm i$ (no real eigenvalues).

Another example. $A = 200122133$

det 200122133 - λ 00 0 λ 0 00 λ = 0 det 2 - λ 00 1 2 - λ 2 13 3 - λ = 0 = (2 - λ) det ([2 - λ 2 3 3 - λ]) = (2 - λ) ((2 - λ) (3 - λ) - 6) = (2 - λ) (λ^{2} - 5 λ) = 0 = λ (2 - λ) (λ - 5)

Eigenvalues are $0, 2, 5$ .

Investigating the Characteristic Polynomial

a_{11} - λ a_{21} a_{m 1} a_{12} a_{22} - λ \dots a_{1 n} a_{2 n} a_{mn} - λ

$C_{A} (λ)$ is the determinant of the above.

Polynomial of degree $n$ in $λ$ .

C_{A} (λ) = (a_{n} - λ) (a_{22} - λ) \dots (a_{m} - λ) + t (λ)

Definition

Trace: Sum of the numbers on the diagonal, $tr (A)$ .

Properties:

C_{A} (λ) = c_{n} λ^{n} + c_{n - 1} λ^{(n - 1)} + c_{1} λ + c_{0}

where

c_{n} c_{n - 1} c_{0} = det (A) = (- 1)^{n} = (- 1)^{(n - 1)} tr (A)

Coefficients of the $C_{A} (λ)$ capture key info about $A$ .

Question

What happens when $F = C$ ?

We get exactly $n$ roots (maybe with repetitions). That is, $n$ eigenvalues.

So we can write

C_{A} (λ) = (- 1)^{n} (λ - λ_{1}) (λ - λ_{2}) \dots (λ - λ_{n})

then

c_{0} = (- 1)^{n} (- λ_{1}) (- λ_{2}) \dots (- λ_{n}) = (- 1)^{2 n} λ_{1} λ_{2} λ_{3} \dots λ_{n}

and

c_{n - 1} = (- 1)^{n} [(- λ_{1}) + (- λ_{2}) + \dots + (- λ_{n})] = (- 1)^{n + 1} tr (A) (λ_{1} + λ_{2} + \dots + λ_{n})

Corollary:

i = 1 \sum n λ_{i} i = 1 \prod n λ_{i} = tr (A) = det (A)

Question

Is there a $3 \times 3$ real matrix with 2 real eigenvalues?

No, by the conjugate root theorem.

Given $A$ and $λ$ we can find an eigenvector $x$ by solving

A x = λ x or (A - λ I_{n}) x = 0

That is, we need to compute

Null (A - λ I_{n}) = 0

Eigenspace

E_{λ} (A) = Null (A - λ I_{n})

Powers of Matrix

Prove by induction that

[3 - 1 20]^{n} = [2^{n - 1} - 1 1 - 2^{n} 2^{n + 1} - 2 2 - 2^{n}]

[3 - 1 20] = P [- 1 1 - 2 1] D [1002] P^{- 1} [1 - 1 2 - 1]

A^{n} = (P D P^{- 1})^{n} = P D P^{- 1} P D P^{- 1} \dots P D P^{- 1} = P D^{n} P^{- 1} = P [1^{2} 0 0 2^{n}] P^{- 1} = [- 1 2 - 2 1] [1^{n} 0 0 2^{n}] [1 - 1 - 1 2] = [- 1 + 2^{n - 1} 1 - 2^{n} - 2 + 2^{n + 1} 2 - 2^{n}]

$A$ is similar to $B$ over $F$ if there exists an invertible matrix $P$ such that $A = PB P^{- 1}$ .

In the previous example $A$ is similar to $B$ . $A$ is similar to $B$ iff $B$ is similar to $A$ .

A P^{- 1} A P^{- 1} A P P^{- 1} A P = PB P^{- 1} = P^{- 1} PB P^{- 1} = B P^{- 1} P = B

If $A$ and $B$ are similar over $F$ , they have the same characteristic polynomial $⟹$ same eigenvalues in $F$ .

Proof: Assume $A$ is similar to $B$ .

A C_{A} (λ) = PB P^{- 1} = det (A - λ I) = det (PB P^{- 1} - λ P P^{- 1}) = det (P (B - λ I) P^{- 1}) = det (P) \cdot det (B - λ I) \cdot det (P^{- 1}) = det (P) \cdot det (P^{- 1}) det (B - λ I) = det (B - λ I) = C_{B} (λ)

So eigenvalues of $A$ are the same as the eigenvalues of $B$ .

We say that $A$ is diagonalizable over $F$ if it is similar over $F$ to a diagonal matrix $D$ . That is thre is an invertible matrix $P$ such that $P A P^{- 1} = D$ .

Matrix $P$ diagonalize $A$

A D A D = [3 - 1 20] is diagonalizable = [1002] = P D P^{- 1} = P^{- 1} A P

Note: $F$ is important. May be diagonalizable over $C$ but not $R$ .

We will see other applications of diagonalizability. All diagonalizable.

If $A$ is diagonalizable over $F$ , the characteristic polynomial has $n$ roots.

If $D$ diagonalizes $A$ , the diagonal entries of $\overset{ˉ}{D} = P^{- 1} A P$ are the eigenvalues of $A$ .

Note, over $C$ , $A \in M_{n \times n} (C)$ will always have $n$ eigenvalues. Contrapositive, if we don’t have $n$ eigenvalues even with repetition, then not diagonalizable.

Proof:

Assume $A$ is diagonalizable over $F$ . $\exists P \in M_{n \times n} (F)$ such that $P^{- 1} A P = D$ where $D$ is diagonal. So $A$ and $D$ are similar.

C_{A} (λ) = C_{D} (λ) = det d_{1} - λ 0 ⋮ 0 d_{2} - λ ⋱ 0000 = tr (matrix above) = (d_{1} - λ) (d_{2} - λ) (d_{n} - λ) = det (D - λ I)

So $λ_{1} = d_{1}, λ_{2} = d_{2} \dots, λ_{n} = d_{n}$ are eigenvalues of $D$ and $A$ , so we have $n$ eigenvalues.

Let $A \in M_{n \times n} (F)$ have $n$ distinct eigenvalues $λ_{1}, λ_{2}, \dots, λ_{n}$ .

Let $(λ_{1}, v_{1}), \dots, (λ_{n}, v_{n})$ be corresponding eigenpairs over $F$ and let $P = [v_{1}, \dots, v_{n}]$ . Then

$P$ is invertible, and
$P^{- 1} A P = D = diag (λ_{1}, λ_{2}, \dots, λ_{n})$

Subspaces and Bases

Subspaces

Subset of $V$ of $F^{n}$ is a subspace of $F^{n}$ if

$0 \in V$
$\forall x, y \in V, x + y \in V$
$\forall x \in R, \forall c \in F, c x \in V$

Non-empty set of vectors closed under addition and scalar multiplication.

Proposition: Examples of subspaces

a) ${0}$ and $F^{n}$ are subspaces of $F^{n}$

b) If ${v_{1}, v_{2}, \dots,}$ is a subset of $F^{n}$ , then $Span {v_{1}, v_{2}, \dots, v_{k}}$ is a subspace of $F^{n}$ .

c) If $A \in M_{n \times n} (F)$ then column set to homogeneous system $A x = 0$ is a subspace of $F^{n}$ .

Proof Examples of Subspaces (b)

Let $v_{1}, v_{2}, v_{3}, \dots, v_{k} \in F^{n}$ and let $S = Span {v_{1}, \dots, v_{k}}$ .

Then $0 v_{1} + 0 v_{2} + \dots + 0 v_{k} = 0 \in S$ by definition of span.

Next let $x, y \in S$ .

Then there exists scalars $c_{1}, \dots, c_{k}, d_{1}, \dots, d_{k} \in F$ such that

x y = v_{1} v_{1} + \dots c_{k} v_{k} = d_{1} v_{1} + \dots d_{k} v_{k}

Thus $x + y$ is just $(c_{1} + d_{1}) v_{1} + \dots (c_{k} + d_{k}) v_{k}$ . Since $c_{i} + d_{i} \in F$ for $i = 1, \dots, k$ .

We know $x + y$ is in the span.

Let $x \in S$ and $x = c_{1} v_{1} + \dots c_{k} v_{k}$ as before.

Then for $c \in F, c x = (c c_{1}) v_{1} + \dots + (c c_{k}) v_{k}, c c_{i} \in F$ for all $i = 1, \dots, k$ we know $c x \in S$ .

Proposition: More Examples

a) $A \in M_{n \times n} (F)$ , then $Col (A)$ is a subspace of $F^{m}$ .

Since $Col (A) = Span {a_{1}, \dots, a_{n}}$ where $a_{1}, \dots, a_{n}$ are the columns of $A$ , we are done by part b) of the previous proposition.

b) If $T : F^{n} \to F^{m}$ is a linear transformation, then the range of $T$ , $range (T)$ , is a subspace of $F^{m}$ .

$Range (T) = Col ([T]_{ε})$ . Thus by part a) we are done.

c) $T : F^{n} \to F^{m}$ , then the kernel ( $Ker (T)$ ), is a subspace of $F^{n}$ .

Since $Ker (T) = Null ([T]_{ε})$ , this follows from part c of previous.

d) $A, λ \in F$ , then $E_{λ}$ is a subspace of $F^{n}$ .

Similarly true since $E_{λ} = Null (A - λ I)$ .

Subspace Test

$V$ is a subset of $F^{n}$ . $V$ is a subspace of $F^{n}$ if and only if

a) $V$ is non-empty

b) $\forall x, y \in V$ and $c \in F, c x + y \in V$

Proof of subspace test

$(⟹)$

Assume $v$ is a subspace of $F^{n}$ where $v \subseteq F^{n}$ .

(a) by (1)
(b) by (3) then (2)

$(⟸)$

(1) $v$ exists by (a) $⟹ - v + v = 0 \in V$
(2) Pick $c = 1$
(3) Pick $y = 0$

Non-Examples

⎩ ⎨ ⎧ x_{1} x_{2} x_{3} \in R^{3} : x_{1} + x_{2} = x_{3} + 1 ⎭ ⎬ ⎫

Not a subspace because $0$ does not satisfy

⎩ ⎨ ⎧ x_{1} x_{2} x_{3} \in R^{3} : ∣ x_{1} ∣ + ∣ x_{2} ∣ = ∣ x_{3} ∣ ⎭ ⎬ ⎫

Not a subspace, count example $112 + - 2 02 = - 1 14$

Exercises

Let $w$ be a subspace of $F^{n}$

a) Is $\overset{w}{ˉ}$ a subspace?

No because $0 \in \overset{ˉ}{W}$ .

b) Is $\overset{ˉ}{W} \cup {0}$ a subspace?

It can be (e.g. ${0}$ ). But it might not be (e.g. $W = Span {[11]}$ )

Is $R$ a subspace of $C$ ?

No (violates $c \in C$ , $x \in V, c x \neq \in V$ ). The scalar is in field of what subspace is in.

Efficiently Describing Subspaces

Let $v_{1} = [11], v_{2} = [10], v_{3} = [1 - 1]$ .

Let $S_{1} = Span {v_{1}, v_{2}, v_{3}}$ . Let $S_{2} = Span {v_{1}, v_{2}}$ .

Note that $v_{3} = 2 v_{2} - v_{1}$ .

We can prove that $S_{1} = S_{2}$ .

Let $x \in S_{1}$ . Then $x = a v_{1} + b v_{2} + c v_{3}$ for some $a, b, c, \in F$ .

Then

x = a v_{1} + b v_{2} + c (2 v_{2} - v_{1}) = a v_{1} + b v_{2} + 0 v_{3} \in S_{1}

Thus $S_{1} = S_{2}$ .

Can rewrite to get: $- v_{1} + 2 v_{2} - v_{3} = 0$ . $v_{1}, v_{2}, v_{3}$ are linearly dependent.

Linear Dependence

Vectors $v_{1}, \dots, v_{k} \in F$ are linearly dependent if there exists scalars $c_{1}, c_{2}, \dots, c_{k}$ , not all zero, such that $c_{1} v_{1} + \dots + c_{k} v_{k} = 0$ .

If $U = {v_{1}, \dots, v_{k}}$ then $U$ is a linearly dependent set.

Are $v_{1}, v_{2}$ linearly dependent?

Proof

a v_{1} + b v_{2} = 0 ⟹ [a a] + [b 0] = [00] ⟹ a + b = 0 a = 0 ⟹ a = b = 0

$v_{1}, v_{2}$ are linearly independent.

Linear Independent

(Not linear dependent). Only solution to equation is trivial solution (all scalars are 0).

Note:

Consider empty set $\to$ Linearly Independent
$e_{1}, e_{2}, \dots, e_{n}$ $\to$ Linearly Independent because $c_{1} e_{1} + \dots + c_{n} e_{n} ⟹ c_{1} = c_{n} = 0$ .

Basis

$V$ is a subspace. $B = {v_{1}, \dots, v_{k}}$ in $V$ . $B$ is a basis for $V$ if

$B$ is linearly independent
$V = Span {B}$

${v_{1}, v_{2}}$ is a basis for $S_{1} = S_{2}$ .

a) Vectors are linearly dependent if and only if one of the vectors can be written as a linear combination of other vectors

b) Vectors are linearly independent if and only if $c_{1} v_{1} + \dots c_{n} v_{n} = 0$ implies $c_{1} = \dots c_{n} = 0$ . (This is the definition of linear dependence).

Proof of a)

$(⟹$ )

Suppose $v_{1}, \dots, v_{k}$ are linearly dependent.

Then $c_{1} v_{1} + \dots + c_{k} v_{k} = 0$ for some $c_{1}, \dots, c_{k} \in F$ where $c_{1}, \dots, c_{k}$ are not all $0$ .

Without loss of generality, we assume $c_{1} \neq = 0$ .

Then

v_{1} = (\frac{- c _{2}}{c _{1}}) v_{2} + \dots + (\frac{- c _{k}}{c _{1}}) v_{k}

$(⟸)$

Suppose without loss of generality

v_{1} = c_{2} v_{2} + \dots + c_{k} v_{k} - v_{1} + c_{2} v_{2} + \dots + c_{k} v_{k} = 0

Since $- 1 \neq = 0, v_{1}, \dots, v_{k}$ are linearly dependent.

Let $S \subseteq F^{n}$

a) If $0 \in S$ , then $S$ is linearly dependent.

1360 + 0 v_{1} + \dots 0 v_{k} = 0

b) If $S = {x}$ (only 1 vector), then $S$ is linearly dependent if and only if $x = 0$ .

⟹ c x = 0 where c \neq = 0 ⟹ x must be the zero vector ⟸ (a)

c) If $S = {x, y}$ contains 2 vectors, $S$ is linearly dependent iff the vectors are scalar multiples.

True or False

Let $S \subseteq F^{n}$

If $S$ is linearly independent, then every subset of $S$ is linearly independent.

True: Prove the contrapositive.

$T \subseteq S$ , $T$ is linearly dependent.

c_{1} v_{1} + \dots + c_{k} v_{k} = 0

Add in vectors in $S$ that are not in $T$ with zero as a scalar.

If $S$ is linearly dependent then every subset of $S$ is linearly dependent.

False: Empty set

If $S$ is linearly dependent then every non-empty subset of $S$ is linearly dependent.

False:

123, 456, 000

The entries of two linearly dependent sets is linearly dependent.

True: Just throw 0’s onto the new one.

The vision of two linearly independent sets is linearly independent.

False: ${[11]}, {[22]}$

Are these linearly dependent or linearly dependent?

v_{1} 1 - 1 2, v_{2} 3 - 3 5, v_{3} 407

We want to solve

c_{1} v_{1} + c_{2} v_{2} + c_{3} v_{3} = 0

So we consider the coefficient matrix $A = [v_{1} v_{2} v_{3}]$ . $rank (A) = 3$ . Only one solution $⟹$ linear independence.

v_{1}, v_{2}, v_{3}, 123

$rank = 3$ (but 4 columns). Thus there are non-trivial solutions $⟹$ linear dependence.

Connection to Pivots

$S = {v_{1}, \dots, v_{k}}$ be set of $k$ vectors in $F^{n}$ .

$A = [v_{1} \dots v_{k}]$ $n \times k$ matrix, $v \in S$ .

$Rank (A) = r$ and $A$ has pivot columns $q_{1}, q_{2}, q_{3}, q_{r}$ .

Let $U = {v_{q_{1}}, v_{q_{2}}, \dots, v_{q_{r}}}$ set of columns of $A$ that correspond to pivot columns.

Then

a) $S$ is linearly dependent iff $r = k$ .

b) $U$ is linearly independent.

Proof of a)

Then $S$ is linearly independent iff $A c = 0$ has a unique solution.

That is, iff $rank (A) = k$ .

Proof of b)

As before we will consider

[v_{q_{1}} \dots v_{q_{1}}] d = 0

The pivots in this coefficient matrix must be the same as those in $RREF (A)$ .

That is, there are $r$ pivots which is the number of columns. Hence this has a unique solution. Thus $U$ is linearly independent.

c) If $v$ is in $S$ but not in $U$ then the set ${v_{q_{1}}, \dots, v_{q_{v}}, v}$ is linearly dependent.

Proof of c)

Consider $[v_{q_{1}}, \dots, v_{q_{2 r}}, v] f = 0$ .

As before we have $r$ pivots but it has $r + 1$ pivots.

Hence ${v_{q_{1}}, \dots, q_{r}, v}$ is linearly dependent.

Proof of d) $Span (U) = Span (V)$ .

Since $U \subseteq S$ . $Span (U) \subseteq Span (S)$ .

We must show $Span (S) \subseteq Span (U)$ .

If $U = S$ we are done. Otherwise, we consider $v \in S - U$ .

From our proof of c), we know $f_{1} v_{q_{1}} + \dots f_{r} v_{q_{r}} + α v = 0$ has a non-trivial solution.

By part b) it must be that $α \neq = 0$ .

Thus $v = \frac{- f _{1}}{α} v_{q_{1}} - \dots \frac{f _{r} v _{q_{r}}}{α}$ . That is $v \in Span (U)$ .

It follows $Span (S) \subseteq Span (U)$ .

Corollary

Bound on Number of Linearly Independent Vectors

Let $S = {v_{1}, v_{2}, \dots, v_{k}}$ be the set of $k$ vectors in $F^{n}$ .

If $n < k$ , then $S$ is linearly independent.

Rank of matrix is at most $n$ . Hence, to be linearly independent, we need $rank = k$ .

Since $rank (A) = n$ , if $n < k ⟹ rank (A) < k$ , linearly dependent. $N$ must be at least $k$ .

e.g. 8 vectors in $R^{5}$ must be linearly dependent.

Also, given these 8 vectors, we can find a subset of them that have the same span and for which their subset is linearly independent.

That is we can find a basis for the span of these 8 vectors.

Let $V$ be a subspace.

If $V = Span {v_{1}, \dots, v_{k}}$ for some vec $v_{1}, \dots, v_{k}$ , then $V = Span {v_{1}, \dots, v_{k}, v}$ for all $v \in F^{n}$ .

False.

Counterexample: $Span {[10]}$ . Note, is true if we replace $\forall v \in F^{n}$ to $\forall v \in V$ .

Algorithm for finding a Basis of a Subspace

$B^{4}$ went from span to basis.

Let $V$ be a subspace.

$S = {}$

while $V \neq = Span (S)$
- find $v \in V - Span (S)$ such that $v \neq = 0$
- add $v$ to $S$

Notes:

Partly by convention this correctly gives ${}$ as a basis for $V = {0}$ . Won’t discuss how to find $v$ . When we terminate, $V = Span (S)$ . $S$ always linearly independent. Thus when we terminate, we get a basis for $V$ . Algorithm terminates by our bound on the number of linearly independent vectors.

Every subspace has a spanning set.

Every subspace has a basis.

Question

How do we test if $V = Span (S)$ ?

$Span (S) \subseteq V$ follows from the definition of subspace. $V \subseteq Span (S)$ means for all $v \in V, v \in Span (S)$ which is true if $[v_{1}, \dots, v_{k}] x = v$ is consistent for all $v \in V$ .

That is, $rank ([v_{1} \dots v_{k}]) = rank ([v_{1} \dots v_{k} v])$

Special case of $V = F^{n}$ Here, $Span (S) = F^{n} ⟺ A x = b$ is consistent for all $x \in F^{n} [v_{1}, \dots, v_{k}]$ where $S = {v_{1}, \dots, v_{k}} ⟺ rank (A) = n$ .

Size of basis for $F^{n}$

To span, $rank (A) = n \leq k$ (number of columns)

To be linearly independent $k \leq n$ by bounds.

Summary

We need at least $n$ vectors to span $F^{n}$ .

Can have at most $n$ vectors in $F^{n}$ if linearly independent.

Many sets of $n$ vectors which are not a basis.

$S$ is linearly independent if and only if $Span (S) = F^{n}$ .

A set of $n$ vectors will span $F^{n}$ if and only if they are linearly independent. Why? Spans $⟺ rank (A) = n$ and linearly independent $⟺ rank (A) = n$ .

We have a method to shrink a spanning set for a subspace into a basis for the subspace. We have a method to grow a linearly independent subset of a subspace into a basis for the subspace. All bases for $F^{n}$ consist of $n$ vectors, but not all sets of $n$ vectors are a basis.

Determine all values of $a \in R$ for which

⎩ ⎨ ⎧ a 2 a 2, 12 2 a, 1 2 a 2 a + 2 ⎭ ⎬ ⎫

is a basis of $R^{3}$ .

Solution:

Vectors will form a basis if and only if $rank (A) = 3$ where $A = a 2 a 2 12 2 a 1 2 a 2 a + 2$

And rank (A) = 3 ⟺ A is invertible ⟺ det (A) \neq = 0 ⟺ det a 02 10 2 a 1 2 a - 2 2 a + 2 \neq = 0 ⟺ - (2 a - 2) (2 a^{2} - 2) \neq = 0 ⟺ - (a - 1) (a^{2} - 1) \neq = 0 ⟺ - (a + 1) (a - 1)^{2} \neq = 0 ⟺ a \neq = \pm 1

Running Example

Let A = 101 - 1 011 - 1 2 - 1 1 - 1 314 - 4 0012

We can get

RREF (A) = 10000100 2 - 1 00 31000010

Basis for $Col (A)$

By pivots and linearly independence,

B = ⎩ ⎨ ⎧ 101 - 1, 011 - 1, 0012 ⎭ ⎬ ⎫

is a basis for $Col (A)$ .

Basis for $Null (A)$ .

Null (A) = ⎩ ⎨ ⎧ - 2 - 3 t s - t s t : s, t \in F ⎭ ⎬ ⎫ = Span ⎩ ⎨ ⎧ - 2 1100, - 3 - 1 010 ⎭ ⎬ ⎫

are they linearly independent? Yes.

If $c_{1} - 2 1100 + c_{2} - 3 - 1 010 = 0$ then $c_{1}$ and $c_{2} = 0$ by inspecting third and fourth components.

Dimension

Number of elements in a basis for subspace $V$ of $F^{n}$ is called the dimension of $V$ . We denote this by $dim (V)$ .

Examples

$dim (F^{n}) = n$

Let $d \in F^{n}$ where $d \neq = 0$ . Consider $L = {t d : t \in F} = Span {d}$ Thus a line through the origin is a subspace of dimension 1.

Let $a, v \in F^{n}$ where $a, b \neq = 0$ and $a \neq = k b$ for any $k \in F$

Consider

B = {s a + t b : s, t \in F} = Span {a, b}

Thus a plane is a subspace of dimension 2.

Proof of bound

A basis of $V$ consists of $n$ linear independent vectors. Hence its dimension is not at most $n$ by our bound for sets of linear independent vectors.

Rank and Nullity as Dimensions

dim (V) nullity (A) rank (A) \leq n = dim (Null (A)) = dim (Col (A))

Rank-Nullity Theorem

n = rank (A) + nullity (A) = dim (Col (A)) + dim (Null (A))

Dimension Exercises

Let $V, W$ be subspaces of $F^{n}$ where $W \subseteq V$ . Then
1. $dim (W) \leq dim (V)$
2. $W = V ⟺ dim (W) = dim (V)$
Let $S$ be the subspace consisting of all vectors orthogonal to $1111$ and $0111$ . What is $dim (S)$ ?

a) We can grow a basis for $W$ into a basis for $V$ . b) $⟹ ✓$ . $⟸$ contrapositive. Use $v \in V - W$ to create a larger basis for $V$ .

$S = Null ([10111111]) = 2 ( 2 free variables ) = 4 - 2 (Col - Pivots)$

Unique Representation Theorem

$B = {v_{1}, \dots, v_{n}}$ basis for $F^{n}$ . For every vector $v \in F^{n}$ , $\exists$ unique scalars $c_{1} v_{1} + \dots + c_{n} v_{n} = v$ .

Proof of URT

Existence comes immediately from the fact that $B$ spans $F^{n}$ .

Let $v = c_{1} v_{1} + \dots + c_{n} v_{n}$ and $v = d_{1} v_{1} + \dots + d_{n} v_{n}$ for some scalars $c_{1}, \dots, c_{n}, d_{1}, \dots d_{n}$ .

Thus

c_{1} v_{1} + \dots + c_{n} v_{n} = d_{1} v_{1} + \dots + d_{n} v_{n}

Equivalently,

(c_{1} - d_{1}) v_{1} + \dots + (c_{n} - d_{n}) v_{n} = 0

Since $B$ is a basis, it is linearly independent. $c_{i} = d_{i}$ for all $i = 1, \dots, n$ .

Scalars $c_{1}, c_{2}, \dots, c_{n}$ are the coordinates of $v$ with respect to Bases.

Example

Let $B = ⎩ ⎨ ⎧ 100, 110, 111 ⎭ ⎬ ⎫$

$v = [v]_{ε} = 653$

What is $[v]_{β}$ , $v = 123$

Can find this by solving

100110111 c_{1} c_{2} c_{3} = 653

Given $[w]_{B} = - 1 30$ . What is $w$ ?

w = 100110111 - 1 30 = 230

Linearity

To prove we can show $[c x + y]_{B} = c [x]_{B} + [y]_{B}$ .

Moving From/To $ε$ in $R^{3}$

$B = {v_{1}, v_{2}}$ .

[v]_{ε} = v = [v_{1} v_{2}] = c_{1} v_{1} + c_{2} v_{2} = v_{1} c_{1} + c_{1} + v_{2}

$[v]_{B} = [c_{1} c_{2}]$

$B$ to $ε$

Given $[11]$ , want $v$ . We multiply $[12 3 - 1] [11] = v = [41]$
Given $[v]_{B}$ , want $v$ . Compute $[v_{1} v_{2}] [v_{B}]$

$ε$ to $B$

Given $[41]$ . Want $[11]$

Solve

[12 3 - 1] [v_{1} v_{2}] = [41]

Thus

[v_{1} v_{2}] [v_{1} v_{2}] = [12 3 - 1]^{- 1} [41] = \frac{- 1}{7} [- 1 2 - 3 1] [41] = [\frac{1}{7} \frac{2}{7} \frac{3}{7} \frac{- 1}{7}] = [11]

$ε$ to $B$

Given $v$ . Want $[v]_{B}$ .

Solve $[v_{1}, v_{2}] [v]_{B} = [v]_{ε}$

Can compute

[V_{B}] = [v_{1} v_{2}]^{- 1} [v]_{ε}

Change of Basis, $B$ to $C$

_{C} [I]_{B} = [[v_{1}]_{C}, \dots, [v_{n}]_{C}]

Diagonalization

Linear Operator

Linear transformation $T : F^{n} \to F^{m}$ where $n = m$ is called a linear operator.

T (x) = [T]_{ε} x = [T (e_{1}) T (e_{2})] x

$[T]_{B}$ is an ordered basis.

[T]_{B} [T (v)]_{B} = [[T (v_{1})]_{B} [T (v_{2})]_{B} \dots] = [T]_{B} [v]_{B}

Consider projection onto $Span {[w_{1} w_{2}]}$

Let $B = ⎩ ⎨ ⎧ fixed point [w_{1} w_{2}], orthogonal [- w_{2} w_{1}] ⎭ ⎬ ⎫$

Then $[T]_{B} = [[T ([w_{1} w_{2}])]_{B} [T ([- w_{2} w_{1}])]_{B}]$

That is $[T]_{B} = [[w_{1} w_{2}]_{B} [00]_{B}] = [1000]$ . By proposition 9.1.3

Applying and then converting is the same as converting then applying.

Proof of 9.1.3

Let $v \in F^{n}$ where $v = c_{1} v_{1} + \dots + c_{n} v_{n}$ .

Then

[T (v)]_{B} = [T (c_{1} v_{1} + \dots + c_{n} v_{n}]_{B} = c [T (v_{1})]_{B} + \dots c_{n} [T (v_{n})]_{B} by linearity of T = [[T (v_{1})]_{B} \dots [T (v_{n})]_{B}] c_{1} ⋮ c_{n} = [T]_{B} [v]_{B}

Example:

Let $v = [w_{1} - w_{2} w_{1} + w_{2}] = [w_{1} w_{2}] + [- w_{2} w_{1}]$

Question

What is $T (v)$ ?

Well, [T (v)]_{B} = [T]_{B} [v]_{B} = [1000] [11] = [10]

Thus, $T (v) = [w_{1} w_{2}]$ (another fixed point).

Can verify this algebraically, can also verify geometrically.

Question

Given any $T$ , how do we find a basis $B$ such that $[T]_{B}$ is nice?

To answer this, we ask how $[T]_{ε}$ is related to $[T]_{B}$ ?

[T]_{ε} = (_{B} [I]_{ε})^{- 1} [T]_{B}_{B} [I]_{ε}

Same as $P^{- 1} D P$ .

The essence of the linear operator does not change when you change the basis. That is, making the computation easier doesn’t change what is happening theoretically.

Connection to similarity

[T]_{C} =_{C} [I]_{B} [T]_{B}_{B} [T]_{C} = (_{B} [I]_{C})^{- 1} [T]_{B}_{B} [I]_{C}

This result makes sense

[T]_{C} [x]_{C} =_{C} [I]_{B} [T]_{B}_{B} [I]_{C} [x]_{C} =_{C} [I]_{B} [T]_{B} [x]_{B} =_{C} [I]_{B} [T (x)]_{B} = [T (x)]_{C} = [T]_{C} [x]_{C}

Example of Corollary

Let $T : R^{2} \to R^{2}$ be reflection in $y = m x$ .

We know what $[T]_{ε}$ is.

The direction vector is $[1 m]$ .

Thus $[T]_{ε} = \frac{1}{1 + m ^{2}} [2 - m^{2} 2 m 2 m m^{2} - 1]$ .

Note, $T ([1 m]) = [1 m]$ and $T ([- m 1])$ .

So we chose $B = {[1 m], [- m 1]}$

Then

[T]_{B} = [[1 m]_{B} [m - 1]_{B}] = [10 0 - 1] nice

[T]_{ε} = [1 m - m 1] [10 0 - 1] [1 m - m 1]^{- 1} = [1 - m^{2} 2 m 2 m m^{2} - 1]

Proof of compaction

Let $c = {w_{1}, \dots, w_{n}}$

Then

[T]_{C} = [[T (w_{1})]_{C} \dots [T (w_{n}]_{C}] = [_{C} [I]_{B} [T (w_{1})]_{B} \dots_{C} [I]_{B} [T (w_{n})]_{B}] =_{C} [I]_{B} [[T (w_{1})]_{B} \dots [T (w_{n})]_{B}] =_{C} [I]_{B} [[T]_{B} [w_{1}]_{B} \dots [T]_{B} [w_{n}]_{B}] =_{C} [I]_{B} [T]_{B} [[w_{1}]_{B} \dots [w_{n}]_{B}] =_{C} [I]_{B} [T]_{B}_{B} [I]_{C} ■

(not proving inverse part).

T (x) = λ x ⟺ [T (x)]_{B} = [λ x]_{B} ⟺ [T]_{B} [x]_{B} = λ [x]_{B}

$T$ is diagonalizable $⟺ \exists$ some ordered basis $B = {v_{1}, v_{2}, \dots, v_{n}}$ for $F^{m}$ consisting of eigenvectors of $T$ .

Diagonalize Linear Operator

$T : F^{n} \to F^{n}$ , $T$ is diagonalizable if $\exists B [T]_{B}$ is diagonal.

Equivalently,

$T$ is diagonalizable
$\exists$ basis $B$ such that $[T]_{B}$ is diagonal
$\exists$ basis $B$ of eigenvectors of $T$
$[T]_{C}$ is diagonalizable $\forall C$
$[T]_{ε}$ is diagonalizable

D = [T]_{B} =_{B} [T]_{ε} [T]_{ε}_{ε} [T]_{B} = P^{- 1} [T]_{ε} P P =_{B} [T]_{ε} = [v_{1}, \dots, v_{n}]

For $D$ to be diagonal, we need to $B$ to have only eigenvectors.

Consider $T : R^{3} \to R^{3}$ defined by

T x y z = - 2 y - 5 z - 2 x - 3 z - 2 x + 2 y + z

Determine if $T$ is diagonalizable over $R$ .

Solution

[T]_{ε} = 0 - 2 - 2 - 2 02 - 3 - 3 1

$T$ is diagonalizable iff $[T]_{ε}$ is diagonalizable.

P = - 1 - 1 1 - 2 - 1 2 110 D = 100020 00 - 2

Therefore, the eigenvalues of $T$ are $(1, 2, - 2)$ with eigenvectors $1, - 1 - 1 1, - 2 - 1 2, 2, 110, - 2$ .

If we have $n$ distinct eigenvalues, we can choose an eigenvector from such of the $n$ eigenspaces to get a basis of eigenvectors. We can use them to form $P$ .

What if not all eigenvalues are distinct.

$a_{λ_{i}} = #$ of times that root $λ_{i}$ is repeated.

Ex. $C_{A} (x) = (λ - 3)^{4} (λ + 8)^{2} (λ - 1) (λ + i)$ , $a_{3} = 4, a_{i} = 1, a_{- 1} = 1, a_{- 8} = 2$ .

Eigenspace $E_{λi} (= Null (A - λ_{i} I))$

$g_{λi} = dim (E_{λi})$

$g_{λi}$ = large number of linearly independent vectors we can get from $E_{λi}$ .

Example

A = 1 - 2 - 6 256 - 2 - 2 3

$C_{A} (x) = - (λ - 3)^{2} (λ + 3)$ .

Eigenvalues are $3, - 3$ .

For $λ = 3$ , RREF $(A - 3 I) = 100 - 1 00 100$ . Nullify $(A - 3 I) = 2$ , so $g_{3} = 2$ .

We also get Nullify( $A + 3 I) = 1 = g_{- 3}$ .

$1 \leq g_{λ_{i}} \leq a_{λ_{i}}$ .

Let $λ_{1}, λ_{2}, \dots, λ_{m}$ be the distinct eigenvalues of $T$ .

For each $i$ , let $E_{λ_{i}}$ be the eigenspace corresponding to $λ_{i}$ , and let $B_{i}$ be a basis for $E_{λ_{i}}$ .

We claim that $B = B_{1} \cup B_{2} \cup \dots \cup B_{m}$ is linearly independent.

Suppose

B_{1} B_{2} B_{3} = {x_{1}, x_{2}, \dots} = {y_{1}, y_{2}, \dots} = {z_{1}, z_{2}, \dots}

and consider a linear combination equal to zero:

a_{1} x_{1} + a_{2} x_{2} + \dots + b_{1} y_{1} + b_{2} y_{2} + \dots + c_{1} z_{1} + c_{2} z_{2} + \dots = 0

Group the terms according to their eigenspaces:

\in E_{λ_{1}} (a_{1} x_{1} + a_{2} x_{2} + \dots) + \in E_{λ_{2}} (b_{1} y_{1} + b_{2} y_{2} + \dots) + \in E_{λ_{3}} (c_{1} z_{1} + c_{2} z_{2} + \dots) + \dots = 0

Since eigenspaces corresponding to distinct eigenvalues are linearly independent, $E_{λ_{1}} + \dots + E_{λ_{m}} = E_{λ_{1}} \oplus \dots \oplus E_{λ_{m}}$ .

Therefore each grouped term must be zero: $a_{1} x_{1} + a_{2} x_{2} + \dots = 0$ , $b_{1} y_{1} + b_{2} y_{2} + \dots = 0$ , $c_{1} z_{1} + c_{2} z_{2} + \dots = 0$ , and so on.

But each $B_{i}$ is a basis, hence is linearly independent. Thus $a_{1} = a_{2} = \dots = 0$ , $b_{1} = b_{2} = \dots = 0$ , $c_{1} = c_{2} = \dots = 0$ , and similarly for every $i$ . Hence $B_{1} \cup B_{2} \cup \dots \cup B_{m}$ is linearly independent.

Let distinct eigenvalues of $A$ be $λ_{1}, \dots, λ_{m}$ .

Every eigenvector belongs to an eigenspace.

The most linear independent eigenvalues we can get from $E_{λi}$ is $g_{λi} (= dim (E_{λi}))$ .

The union of the bases for each of the eigenspaces is the largest number of its linearly independent eigenvectors we can get.

This is equal to $g_{λi} + \dots + g_{λm}$ .

Since $g_{λi} \leq a_{λi}$ then $g_{λi} + \dots + g_{λm} \leq a_{λi} + \dots + a_{λm}$ .

$n$ is the largest number of linearly independent eigenvectors we can get.

$T$ is diagonalizable iff $[T]_{P}$ is diagonal for some ordered basis. $T$ is diagonalizable iff $[T]_{C}$ is diagonalizable $\forall$ ordered basis $C$ . $[T]_{C}$ is diagonalizable $\forall$ ordered basis $C$ iff $[T]_{ε}$ is diagonalizable. $T$ is diagonalizable iff there are $n$ linearly independent eigenvectors of $T$ iff $[T]_{ε}$ .

Key observation. We want $P$ to be invertible.

P^{- 1} exists ⟺ Col (P) = F^{n} ⟺ columns of P are n linear independent eigenvectors

Question

Can we find $n$ linear independent eigenvectors?

Driving Examples

a) P = [w_{1} w_{2} - w_{2} w_{1}] D = [1000] b) P = [1 m - m 1] D = [10 0 - 1] c) P = 10 - 1 111 1 - 2 1 D = 100010 00 - 1

Possible issues

$< n$ eigenvalues (including repeats)
$n$ eigenvalues but not $n$ linear independent eigenvectors.

Algebraic multiplicity

c) $a_{1} = 2, a_{- 1} = 1$

Geometric multiplicity

c) $E_{1} = Span ⎩ ⎨ ⎧ - 2 10, 101 ⎭ ⎬ ⎫$ , $g_{1} = 2$ .

Proposition: All eigenvectors from eigenspace are linear independent.

Special proof

λ_{1} \neq = λ_{2} λ_{1} \neq = λ_{3} λ_{2} \neq = λ_{3}

B_{λ_{1}} B_{λ_{2}} B_{λ_{3}} = {v_{1}, v_{2}, v_{3}} = {v_{4}} = {v_{5}, v_{6}}

These are bases of $E_{λi}$ .

Assume

w_{1} \in E_{λ_{1}} c_{1} v_{1} + c_{2} v_{2} + c_{3} v_{3} + w_{2} \in E_{λ_{2}} c_{4} v_{v} + w_{3} \in E_{λ_{3}} c_{5} v_{5} + c_{6} v_{6} = 0 Since c_{1} = c_{6} = 0 (must be trivial)

9.3.4 tells us that if these are eigenvectors they are linear independent.

Thus $w_{1} = w_{2} = w_{3} = 0$ .

Since $B_{λi}$ is a basis for $i = 1, 2, 3$ .

Hence ${v_{1}, v_{2}, v_{3}, v_{4}, v_{5}, v_{6}}$ are linear independent.

We want $n$ eigenvectors. Every eigenvector is in an eigenspace. Thus we get at most

g_{λ_{1}} + g_{λ_{2}} + \dots + g_{λ_{k}} LI eigenvectors \leq a_{λ_{1}} + a_{λ_{2}} + \dots a_{λ_{k}} by our bound \leq n by MATH135

This gives us the diagonalizability test.

C_{A} (λ) = (λ - λ_{i})^{a_{λ_{1}}} \dots (λ - λ_{n})^{a_{λ_{k}}} h (λ)

$A$ is diagonalizable iff $h (x)$ is a constant polynomial and $a_{λ_{i}} = g_{λ_{i}}$ for each $i = 1, \dots, k$ .

Question

Is $T$ diagonalizable

Compute $C_{A} (λ)$
Fully factor $C_{A} (λ)$
if $h (λ)$ is not constant $⟹$ NO
elif $a_{λ_{i}} = 1$ for $i = 1, \dots, k$ $⟹$ YES
elif $a_{λ_{i}} = g_{λ_{i}}$ for $i = 1, \dots k$ $⟹$ YES
else $⟹$ NO

Table of Contents

Backlinks

MATH136 Course Notes

Vectors in $R^{n}$

Spans, Lines, and Planes

Systems of Linear Equations

Matrices

Linear Transformations

Determinants

Eigenvalues and Diagonalization

Subspaces and Bases

Diagonalization

Table of Contents

Backlinks

MATH136 Course Notes

Vectors in Rn

Spans, Lines, and Planes

Systems of Linear Equations

Matrices

Linear Transformations

Determinants

Eigenvalues and Diagonalization

Subspaces and Bases

Diagonalization

Vectors in $R^{n}$