MATH 323 Lecture 20

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

Orthogonality

$\overrightarrow{x}\perp \overrightarrow{y}⟺\overrightarrow{x}\cdot \overrightarrow{y}=0⟺\theta =\frac{\pi }{2}$

Subspaces $X,Y\subset {\mathbb{ℝ}}^n$: $X\perp Y⟺\overrightarrow{x}\perp \overrightarrow{y}\mathrm{\forall }\overrightarrow{x}\in X\mathrm{\forall }\overrightarrow{y}\in Y$

If $X\cap Y\ne \{\overrightarrow{0}\}$, then take $\overrightarrow{v}\cdot \overrightarrow{v}={\Vert \overrightarrow{v}\Vert }^2\ne 0$ for $\overrightarrow{v}\in X\cap Y\ne \overrightarrow{0}$: $X$ is not orthogonal to $Y$.

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

Range

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

$R(L_A)=R(A)=\{\overrightarrow{y}\in {\mathbb{ℝ}}^m:\overrightarrow{y}=A\overrightarrow{x}\mathrm{\exists }\overrightarrow{x}\in {\mathbb{ℝ}}^n\}\subset {\mathbb{ℝ}}^m$

For transpose matrix, $R(A^T)\subset {\mathbb{ℝ}}^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{array}{rlrl}A& =\left[\begin{array}{cc}1& 0\\ 2& 0\end{array}\right]& A^T& =\left[\begin{array}{cc}1& 2\\ 0& 0\end{array}\right]\\ R(A)& =\mathrm{S}\mathrm{p}\mathrm{a}\mathrm{n}\left(\begin{array}{c}1\\ 2\end{array}\right)=\{\alpha \left(\begin{array}{c}1\\ 2\end{array}\right):\alpha \in \mathbb{ℝ}\}\\ N(A)& =\dots =\mathrm{S}\mathrm{p}\mathrm{a}\mathrm{n}({\overrightarrow{e}}_2)\\ R(A^T)& =\mathrm{S}\mathrm{p}\mathrm{a}\mathrm{n}(\left(\begin{array}{c}1\\ 0\end{array}\right),\left(\begin{array}{c}2\\ 0\end{array}\right))=\mathrm{S}\mathrm{p}\mathrm{a}\mathrm{n}({\overrightarrow{e}}_1)\\ N(A^T)& =\dots =\mathrm{S}\mathrm{p}\mathrm{a}\mathrm{n}\left(\begin{array}{c}-2\\ 1\end{array}\right)\end{array}$

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{ℝ}}^n$, then $\dim S+\dim S^{\perp }=n=\dim {\mathbb{ℝ}}^n$

Furthermore, if $\{{\overrightarrow{x}}_1,\dots ,{\overrightarrow{x}}_r\}$ is a basis for $S$ and $\{{\overrightarrow{x}}_{r+1},\dots ,{\overrightarrow{x}}_n\}$ is a basis for $S^{\perp }$, then $\{{\overrightarrow{x}}_1,\dots {\overrightarrow{x}}_r,{\overrightarrow{x}}_{r+1},\dots ,{\overrightarrow{x}}_n\}$ is a basis for ${\mathbb{ℝ}}^n$

Proof

If $S\ne \{\overrightarrow{0}\}$ and $\{{\overrightarrow{x}}_1,\dots ,{\overrightarrow{x}}_r\}$ is a basis for $S$, then $\dim S=r$.

Let $X=({\overrightarrow{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 $\overrightarrow{x}$s to determine whether it is a valid basis of ${\mathbb{ℝ}}^n$.

$\underset{y}{\underbrace{c_1{\overrightarrow{x}}_1+\dots +c_r{\overrightarrow{x}}_r}}+\underset{z}{\underbrace{c_{r+1}{\overrightarrow{x}}_{r+1}+\dots +c_n{\overrightarrow{x}}_n}}=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 }=\{\overrightarrow{0}\}$, so $y=z=\overrightarrow{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{ℝ}}^n$, then ${\mathbb{ℝ}}^n=S\oplus S^{\perp }$. In other words (or lack thereof):

$S\subset {\mathbb{ℝ}}^n⟹{\mathbb{ℝ}}^n=S\oplus S^{\perp }$

Proof

Let $\{{\overrightarrow{x}}_1,\dots ,{\overrightarrow{x}}_r,{\overrightarrow{x}}_{r+1},\dots ,{\overrightarrow{x}}_n\}$ be a basis for ${\mathbb{ℝ}}^n$, then

$\overrightarrow{x}=\underset{\overrightarrow{y}}{\underbrace{c_1{\overrightarrow{x}}_1+\dots +c_r{\overrightarrow{x}}_r}}+\underset{\overrightarrow{z}}{\underbrace{c_{r+1}{\overrightarrow{x}}_{r+1}+\dots +c_n{\overrightarrow{x}}_n}}=\overrightarrow{y}+\overrightarrow{z}$

$\begin{array}{rlrl}\overrightarrow{x}& =\overrightarrow{u}+\overrightarrow{v}& \overrightarrow{x}& =\overrightarrow{y}+\overrightarrow{z}\end{array}$

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

Theorem 5.2.4

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

Example

$A=\left[\begin{array}{ccc}1& 1& 2\\ 0& 1& 1\\ 1& 3& 4\end{array}\right]$

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

$\mathrm{r}\mathrm{r}\mathrm{e}\mathrm{f}A=\left[\begin{array}{ccc}1& 0& 1\\ 0& 1& 1\\ 0& 0& 0\end{array}\right]$

Therefore, $⟨1,0,1⟩,⟨0,1,1⟩$ is a basis for $R(A^T)$.

$N(A)=\alpha ⟨-1,-1,1⟩$, so $⟨-1,-1,1⟩$ is basis for $N(A)$.

Repeat above steps for $A^T=\left[\begin{array}{ccc}1& 0& 1\\ 1& 1& 3\\ 2& 1& 4\end{array}\right]$

Section 5.3: Least Squares

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

Theorem 5.3.1

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

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

$\Vert \overrightarrow{b}-\overrightarrow{y}\Vert >\Vert \overrightarrow{b}-\overrightarrow{p}\Vert$ for any $\overrightarrow{y}\ne \overrightarrow{p}\in S$

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

Definition: Residual Vector

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

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

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

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