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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle U} and $V$, written $W=U\oplus V$

Theorem 5.2.3

If $S$ is a subspcae of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{R}^n} , then $\mathbb {R} ^{n}=S\oplus S^{\perp }$. In other words (or lack thereof):

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S \subset \mathbb{R}^n \implies \mathbb{R}^n = S \oplus S^\perp}

Proof

Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{ \vec{x}_1, \ldots, \vec{x}_r, \vec{x}_{r+1}, \ldots, \vec{x}_n \}} be a basis for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{R}^n} , then

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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}}

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} \vec{x} &= \vec{u} + \vec{v} & \vec{x} &= \vec{y} + \vec{z} \end{align}}

This must be unique since Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S \cap S^\perp = \{ \vec{0} \}} .

Theorem 5.2.4

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (S^\perp)^\perp = S}

Example

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A = \begin{bmatrix}1&1&2\\0&1&1\\1&3&4\end{bmatrix}}

Find basis for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N(A)} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R(A^T)} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N(A^T)} , and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R(A)}

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathrm{rref} A = \begin{bmatrix}1&0&1\\0&1&1\\0&0&0\end{bmatrix}}

Therefore, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left\langle 1,0,1 \right\rangle, \left\langle 0, 1, 1 \right\rangle} is a basis for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R(A^T)} .

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N(A) = \alpha \left\langle -1,-1,1 \right\rangle} , so Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left\langle -1,-1,1 \right\rangle} is basis for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N(A)} .

Repeat above steps for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A^T = \begin{bmatrix}1&0&1\\1&1&3\\2&1&4\end{bmatrix}}

Section 5.3: Least Squares

Find best approximation of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \vec{b}} (outside of a subspace) using vector Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \vec{p}} (in subspace)

Theorem 5.3.1

Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S \subset \mathbb{R}^m} be a subspace.

For each Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \vec{b} \in \mathbb{R}^m} , there is a unique element Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \vec{p}} of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S} that is closest to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \vec{b}} , i.e.

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \|\vec{b}-\vec{y}\| > \| \vec{b} - \vec{p} \|} for any Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \vec{y} \ne \vec{p} \in S}

Furthermore, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \vec{b} - \vec{p} \in S^\perp}

Definition: Residual Vector

A vector Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \hat{x}} is a solution to the least squares problem Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A\vec{x} = \vec{b}} iff Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \vec{p} = A \vec{x}} is the vector in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R(A)} that is closest to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \vec{b}} .

Thus we know that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \vec{p}} is the projection of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \vec{b}} onto Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R(A)}

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \vec{b} - \vec{p} = \vec{b} - A\hat{x} = r(\hat{x}) \in R(A)^\perp} , where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r(\hat{x})} is the residual vector.

Thus Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \vec{x}} is a solution of the least squares problem iff Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r(\hat{x}) \in R(A)^\perp} .