MATH 323 Lecture 20

« previous | Tuesday, November 6, 2012 | next »

Orthogonality

${\vec {x}}\perp {\vec {y}}\iff {\vec {x}}\cdot {\vec {y}}=0\iff \theta ={\frac {\pi }{2}}$

Subspaces $X,Y\subset \mathbb {R} ^{n}$: $X\perp Y\iff {\vec {x}}\perp {\vec {y}}\forall {\vec {x}}\in X\forall {\vec {y}}\in Y$

If $X\cap Y\neq \{{\vec {0}}\}$, then take ${\vec {v}}\cdot {\vec {v}}=\left\|{\vec {v}}\right\|^{2}\neq 0$ for ${\vec {v}}\in X\cap Y\neq {\vec {0}}$: $X$ is not orthogonal to $Y$.

$X\subset \mathbb {R} ^{n}$, $X^{\perp }=\left\{{\vec {y}}\in \mathbb {R} ^{n}:{\vec {y}}\perp X\right\}$ is orthogonal complement. For example, a plane and a normal vector.

Range

$R(A)$ for $m\times n$ matrix $A$ and $L_{A}:\mathbb {R} ^{n}\to \mathbb {R} ^{m}$ is defined as

$R(L_{A})=R(A)=\left\{{\vec {y}}\in \mathbb {R} ^{m}:{\vec {y}}=A{\vec {x}}\exists {\vec {x}}\in \mathbb {R} ^{n}\right\}\subset \mathbb {R} ^{m}$

For transpose matrix, $R(A^{T})\subset \mathbb {R} ^{n}$

Note: Range is nothing more than the column space of a matrix

Theorem 5.2.1

Fundamental subspaces theorem

1. $N(A)=R(A^{T})^{\perp }$
2. $N(A^{T})=R(A)^{\perp }$

Proof

Prove one, then the proof of the second follows from the first: Let $B=A^{T}$, then $N(A^{T})=N(B)=R(B^{T})^{\perp }=R(A)^{\perp }$

Example

${\begin{aligned}A&={\begin{bmatrix}1&0\\2&0\end{bmatrix}}&A^{T}&={\begin{bmatrix}1&2\\0&0\end{bmatrix}}\\R(A)&=\mathrm {Span} {\begin{pmatrix}1\\2\end{pmatrix}}=\left\{\alpha {\begin{pmatrix}1\\2\end{pmatrix}}:\alpha \in \mathbb {R} \right\}\\N(A)&=\ldots =\mathrm {Span} ({\vec {e}}_{2})\\R(A^{T})&=\mathrm {Span} \left({\begin{pmatrix}1\\0\end{pmatrix}},{\begin{pmatrix}2\\0\end{pmatrix}}\right)=\mathrm {Span} ({\vec {e}}_{1})\\N(A^{T})&=\ldots =\mathrm {Span} {\begin{pmatrix}-2\\1\end{pmatrix}}\end{aligned}}$

1. $N(A)\perp R(A^{T})$
2. $N(A^{T})\perp R(A)$

Theorem 5.2.2

If $S$ is a subspace of $\mathbb {R} ^{n}$, then $\dim S+\dim S^{\perp }=n=\dim \mathbb {R} ^{n}$

Furthermore, if $\{{\vec {x}}_{1},\ldots ,{\vec {x}}_{r}\}$ is a basis for $S$ and $\{{\vec {x}}_{r+1},\ldots ,{\vec {x}}_{n}\}$ is a basis for $S^{\perp }$, then $\{{\vec {x}}_{1},\ldots {\vec {x}}_{r},{\vec {x}}_{r+1},\ldots ,{\vec {x}}_{n}\}$ is a basis for $\mathbb {R} ^{n}$

Proof

If $S\neq \{{\vec {0}}\}$ and $\{{\vec {x}}_{1},\ldots ,{\vec {x}}_{r}\}$ is a basis for $S$, then $\dim S=r$.

Let $X=({\vec {x}}_{i}^{T})$ be a $r\times n$ matrix formed by using the basis vectors as rows of $X$. The rank of $X$ is $r$, and $R(X^{T})=S$.

$S^{\perp }=R(X^{T})^{\perp }=N(X)$ by equation 1 of the previous theorem, so $\dim S^{\perp }=\dim N(X)=n-r$

Therefore $\dim S+\dim S^{\perp }=r+(n-r)=n$. This proves the first part of the theorem.

Check linear independence of ${\vec {x}}$s to determine whether it is a valid basis of $\mathbb {R} ^{n}$.

$\underbrace {c_{1}\,{\vec {x}}_{1}+\dots +c_{r}\,{\vec {x}}_{r}} _{y}+\underbrace {c_{r+1}\,{\vec {x}}_{r+1}+\dots +c_{n}\,{\vec {x}}_{n}} _{z}=0$

In order for $y=-z$ to be true, $y$ and $z$ must be elements of $S\cap S^{\perp }$ Since $S$ and $S^{\perp }$ are orthogonal subspaces, $S\cap S^{\perp }=\{{\vec {0}}\}$, so $y=z={\vec {0}}$.

Direct Sum

If $U,V\subset W$ are subspaces of a vector space $W$, and each $w\in W$ can be written as a sum $u+v$, where $u\in U$ and $v\in V$, then $W$ is a direct sum of $U$ and $V$, written $W=U\oplus V$

Theorem 5.2.3

If $S$ is a subspcae of $\mathbb {R} ^{n}$, then $\mathbb {R} ^{n}=S\oplus S^{\perp }$. In other words (or lack thereof):

$S\subset \mathbb {R} ^{n}\implies \mathbb {R} ^{n}=S\oplus S^{\perp }$

Proof

Let $\{{\vec {x}}_{1},\ldots ,{\vec {x}}_{r},{\vec {x}}_{r+1},\ldots ,{\vec {x}}_{n}\}$ be a basis for $\mathbb {R} ^{n}$, then

${\vec {x}}=\underbrace {c_{1}\,{\vec {x}}_{1}+\dots +c_{r}\,{\vec {x}}_{r}} _{\vec {y}}+\underbrace {c_{r+1}\,{\vec {x}}_{r+1}+\dots +c_{n}\,{\vec {x}}_{n}} _{\vec {z}}={\vec {y}}+{\vec {z}}$

${\begin{aligned}{\vec {x}}&={\vec {u}}+{\vec {v}}&{\vec {x}}&={\vec {y}}+{\vec {z}}\end{aligned}}$

This must be unique since $S\cap S^{\perp }=\{{\vec {0}}\}$.

Theorem 5.2.4

$(S^{\perp })^{\perp }=S$

Example

$A={\begin{bmatrix}1&1&2\\0&1&1\\1&3&4\end{bmatrix}}$

Find basis for $N(A)$, $R(A^{T})$, $N(A^{T})$, and $R(A)$

$\mathrm {rref} A={\begin{bmatrix}1&0&1\\0&1&1\\0&0&0\end{bmatrix}}$

Therefore, $\left\langle 1,0,1\right\rangle ,\left\langle 0,1,1\right\rangle$ is a basis for $R(A^{T})$.

$N(A)=\alpha \left\langle -1,-1,1\right\rangle$, so $\left\langle -1,-1,1\right\rangle$ is basis for $N(A)$.

Repeat above steps for $A^{T}={\begin{bmatrix}1&0&1\\1&1&3\\2&1&4\end{bmatrix}}$

Section 5.3: Least Squares

Find best approximation of ${\vec {b}}$ (outside of a subspace) using vector ${\vec {p}}$ (in subspace)

Theorem 5.3.1

Let $S\subset \mathbb {R} ^{m}$ be a subspace.

For each ${\vec {b}}\in \mathbb {R} ^{m}$, there is a unique element ${\vec {p}}$ of $S$ that is closest to ${\vec {b}}$, i.e.

$\|{\vec {b}}-{\vec {y}}\|>\|{\vec {b}}-{\vec {p}}\|$ for any ${\vec {y}}\neq {\vec {p}}\in S$

Furthermore, ${\vec {b}}-{\vec {p}}\in S^{\perp }$

Definition: Residual Vector

A vector ${\hat {x}}$ is a solution to the least squares problem $A{\vec {x}}={\vec {b}}$ iff ${\vec {p}}=A{\vec {x}}$ is the vector in $R(A)$ that is closest to ${\vec {b}}$.

Thus we know that ${\vec {p}}$ is the projection of ${\vec {b}}$ onto $R(A)$

${\vec {b}}-{\vec {p}}={\vec {b}}-A{\hat {x}}=r({\hat {x}})\in R(A)^{\perp }$, where $r({\hat {x}})$ is the residual vector.

Thus ${\vec {x}}$ is a solution of the least squares problem iff $r({\hat {x}})\in R(A)^{\perp }$.