MATH 323 Lecture 24

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

Theorem 5.6.1 (Gram-Schmidt Process)

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 \{ x_1, \ldots, 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 V, \langle \cdot, \cdot \rangle} . 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 u_1 = \tfrac{x_1}{\|x_1\|}} and define 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_2, \ldots, u_n} recursively by

$u_{k+1}={\frac {x_{k+1}-p_{k}}{\|x_{k+1}-p_{k}\|}}$

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 p_k = \langle x_{k+1}, u_1 \rangle u_1 + \langle x_{k+1}, u_2 \rangle u_2 + \dots + \langle x_{k+1}, u_k \rangle u_k} 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 x_{k+1}} 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 v_k = \mathrm{Span}(u_1,\ldots,u_k) = \mathrm{Span}(x_1,\ldots,x_k)} .

The set 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_1,\ldots,u_n\}} is an orthonormal 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 V} .

Notation

From now on,

${\begin{aligned}r_{kk}&=\|x_{k}-p_{k-1}\|r_{ik}&=\langle x_{k},u_{i}\rangle \end{aligned}}$

Proof by Induction

$\mathrm {Span} (x_{1})=\mathrm {Span} (u_{1})$ and $u_{1}$ is an orthonormal basis for $V_{1}$

Suppose $u_{1},\ldots ,u_{k}$ are constructed so they are an orthonormal basis for $v_{k}$ and $\mathrm {Span} \{x_{1},\ldots ,x_{k}\}=\mathrm {Span} \{u_{1},\ldots ,u_{k}\}$.

$p_{k}\in \mathrm {Span} \{u_{1},\ldots ,u_{k}\}\implies x_{k+1}-p_{k}\in \mathrm {Span} \{x_{1},\ldots ,x_{k},x_{k+1}\}$

$x_{k+1}-p_{k}\neq 0$ because $x_{1},\ldots ,x_{k+1}$ are linearly independent.

$x_{k+1}-p_{k}=x_{k+1}-\sum _{i=1}^{k}c_{i}\,x_{i}$, where $c_{i}=\langle x_{k+1},u_{i}\rangle$

Therefore $u_{1},\ldots ,u_{k+1}$ is an orthonormal set of vectors in $\mathrm {Span} \{x_{1},\ldots ,x_{k+1}\}$, and is a basis for subspace of dimension $k+1$.

Thus the theorem holds by induction.

Q.E.D.

Example

Find an orthonormal basis for the range of the following matrix:

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

Column space is defined by $\mathrm {Span} \left\{{\begin{pmatrix}1\\1\\1\\1\end{pmatrix}},{\begin{pmatrix}-1\\4\\4\\-1\end{pmatrix}},{\begin{pmatrix}4\\-2\\2\\0\end{pmatrix}}\right\}=\mathrm {Span} \{{\vec {a}}_{1},{\vec {a}}_{2},{\vec {a}}_{3}\}$

${\begin{aligned}r_{11}&=\left\|{\vec {a}}_{1}\right\|={\sqrt {1^{2}+1^{2}+1^{2}+1^{2}}}=1\\{\vec {q}}_{1}&={\frac {{\vec {a}}_{1}}{r_{11}}}=\left\langle {\tfrac {1}{2}},{\tfrac {1}{2}},{\tfrac {1}{2}},{\tfrac {1}{2}}\right\rangle \\r_{12}&=\langle {\vec {a}}_{2},{\vec {q}}_{1}\rangle =3\\{\vec {p}}_{1}&=r_{12}\,{\vec {q}}_{1}=3{\vec {q}}_{1}\\{\vec {a}}_{2}-{\vec {p}}_{1}&=\left\langle -{\frac {5}{2}},{\frac {5}{2}},{\frac {5}{2}},-{\frac {5}{2}}\right\rangle \\r_{22}&=\|{\vec {a}}_{2}-{\vec {p}}_{1}\|=5\\q_{2}&={\frac {{\vec {a}}_{2}-{\vec {p}}_{1}}{r_{22}}}=\left\langle -{\frac {1}{2}},{\frac {1}{2}},{\frac {1}{2}},-{\frac {1}{2}}\right\rangle \\r_{13}&=\langle {\vec {a}}_{3},{\vec {q}}_{1}\rangle =2\\r_{23}&=\langle {\vec {a}}_{3},{\vec {q}}_{2}\rangle =-2\\{\vec {p}}_{2}&=r_{13}\,{\vec {q}}_{1}+r_{23}\,{\vec {q}}_{2}=\left\langle 2,0,0,2\right\rangle \\{\vec {a}}_{3}-{\vec {p}}_{2}=\left\langle 2,-2,2,-2\right\rangle \\r_{33}=\|{\vec {a}}_{3}-{\vec {p}}_{2}\|=4\\q_{3}={\frac {{\vec {a}}_{3}-{\vec {p}}_{2}}{r_{33}}}=\left\langle {\frac {1}{2}},-{\frac {1}{2}},{\frac {1}{2}},-{\frac {1}{2}}\right\rangle \end{aligned}}$

Therefore, $\{{\vec {q}}_{1},{\vec {q}}_{2},{\vec {q}}_{3}\}=\left\{{\begin{pmatrix}{\frac {1}{2}}\\{\frac {1}{2}}\\{\frac {1}{2}}\\{\frac {1}{2}}\end{pmatrix}},{\begin{pmatrix}-{\frac {1}{2}}\\{\frac {1}{2}}\\{\frac {1}{2}}\\-{\frac {1}{2}}\end{pmatrix}},{\begin{pmatrix}{\frac {1}{2}}\\-{\frac {1}{2}}\\{\frac {1}{2}}\\-{\frac {1}{2}}\end{pmatrix}}\right\}$ is an orthonormal basis for the range of $A$.

Theorem 5.6.2 (Gram-Schmidt QR Factor)

If $A$ is an $m\times n$ matrix of rank $n$, then $A$ can be factored into a product $QR$, where $Q$ is an $m\times n$ matrix with orthonormal column vectors and $R$ is an upper triangular $n\times n$ matrix whose diagonal entries are all positive.

In the Gram-Schmidt Orthogonalization Process, ${\vec {p}}_{i}$ represents the projection vectors.

$r_{ij}={\begin{cases}\|{\vec {x}}_{1}\|&i=j=1\\\|{\vec {x}}_{i}-{\vec {p}}_{i}\|&i=j\\\langle {\vec {q}}_{i},{\vec {x}}_{j}\rangle &{\text{otherwise}}\end{cases}}$

We use the defined values above to form an upper triangular matrix $R$

$R=\left({\begin{cases}r_{ij}&i\leq j\\0&{\text{otherwise}}\end{cases}}\right)$

such 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 A = QR} , 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 Q = \left( \vec{q}_1, \ldots, \vec{q}_n \right)} .

Example

From previous 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 \begin{align} R &= \begin{bmatrix}r_{11} & r_{12} & r_{13} \\ 0 & r_{22} & r_{23} \\ 0 & 0 & r_{33} \end{bmatrix} Q &= (\vec{q}_1, \vec{q}_2, \vec{q}_3) \end{align}}

Polynomial Space Example

Consider 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 P_3} , the subspace consisting of quadratic polynomials, with an inner product:

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 \langle p, q \rangle = \sum_{i=1}^n p(c_i) \, q(c_i)} , 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 \vec{c} = \langle -1, 0, 1 \rangle}

$1$, 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 x} , 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 x^2} (represented by 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}} ) form 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 P_3} , but they are not orthonormal w.r.t. the inner product definition.

Find an orthonormal basis 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_1, u_2, u_3 \}} 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 P_3} .

---

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} \| x_1 \| &= \| 1 \| = \sqrt{\langle 1,1 \rangle} = \sqrt{1 \cdot 1 + 1 \cdot 1 + 1 \cdot 1 \sqrt{3}} \\ u_1 &= \frac{x_1}{\| x_1 \|} = \frac{1}{\sqrt{3}} \\ p_1 &= \left\langle x, \frac{1}{\sqrt{3}} \right\rangle \frac{1}{\sqrt{3}} = 0 \\ x_2 - p_1 &= x \\ \| x_2-p_1 \| &= \langle x, x \rangle = \sqrt{2} \\ u_2 &= \frac{x}{\sqrt{2}} \\ p_2 &= \left\langle x^2, \frac{1}{\sqrt{3}} \right\rangle \frac{1}{\sqrt{3}} + \left\langle x^2, \frac{x}{\sqrt{2}} \right\rangle \frac{x}{\sqrt{2}} = \frac{2}{3} \\ \| x^2-p_2 \| &= \left\langle x^2-\frac{2}{3}, x^2-\frac{2}{3}\right\rangle = \frac{\sqrt{6}}{2} \\ u_3 &= \frac{x^2 - \frac{2}{3}}{\sqrt{\frac{2}{3}}} \end{align}}

Eigenvalues and Eigenvectors

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 A} be an 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 \times n} matrix.

A scalar 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 \lambda} is an eigenvalue 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 A} if there is a nonzero 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{x} \in \mathbb{C}^n} such 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 A \, \vec{x} = \lambda \, \vec{x}}

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 said to be an eigenvector belonging 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 \lambda} .

All of the following are equivalent: 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 \lambda} is an eigenvalue 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 (A - \lambda \, I) \vec{x} = \vec{0}} has nonzero solution
• 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| A - \lambda \, I \right| = 0} This is important since it gives the characteristic equation
• 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 - \lambda \, I} is singular
• 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 - \lambda \, I) \ne 0}

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}4 & -2 \\ 1 & 1 \end{bmatrix}} , 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 x = \begin{bmatrix} 2 \\ 1 \end{bmatrix}}

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} = \begin{bmatrix}6\\3\end{bmatrix} = 3 \vec{x}} .

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 \lambda = 3} is the eigenvalue, 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 \vec{x} = \langle 2,1 \rangle} is an eigenvector belonging 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 \lambda = 3} .

If 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 an eigenvector belonging to $\lambda$, 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 \mu \, \vec{x}} is also an eigenvector belonging 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 \lambda} (for nonzero 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 \mu} ):

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(\mu \, \vec{x}) = \mu \, A \, \vec{x} = \mu \, \lambda \, \vec{x}}

Characteristic Equation

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 p(\lambda) = \|A - \lambda \, I \|} is called the characteristic polynomial

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 - \lambda \, I \| = 0} is called the characteristic equation

Either way, the form is

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{vmatrix}a_{11}-\lambda & \dots & a_{1n} \\ \vdots & \ddots & \vdots \\ a_{n1} & \dots & a_{nn}- \lambda\end{vmatrix}}

Example 1

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}3 & 2 \\ 3 & -2 \end{bmatrix}}

Characteristic equation is 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{vmatrix}3-\lambda & 2 \\ 3 & -2 - \lambda\end{vmatrix} = \lambda^2 - \lambda - 12} .

Solutions are 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 \lambda = 4, -3} .

Eigenvectors can be obtained by solving 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 - \lambda \, I) \vec{x} = 0} .