MATH 323 Lecture 24

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

Theorem 5.6.1 (Gram-Schmidt Process)

Let $\{x_1,\dots ,x_n\}$ be a basis for $V,⟨\cdot ,\cdot ⟩$. Let $u_1=\frac{x_1}{\Vert x_1\Vert }$ and define $u_2,\dots ,u_n$ recursively by

$u_{k+1}=\frac{x_{k+1}-p_k}{\Vert x_{k+1}-p_k\Vert }$

Where $p_k=⟨x_{k+1},u_1⟩u_1+⟨x_{k+1},u_2⟩u_2+\dots +⟨x_{k+1},u_k⟩u_k$ is the projection of $x_{k+1}$ onto $v_k=\mathrm{S}\mathrm{p}\mathrm{a}\mathrm{n}(u_1,\dots ,u_k)=\mathrm{S}\mathrm{p}\mathrm{a}\mathrm{n}(x_1,\dots ,x_k)$.

The set $\{u_1,\dots ,u_n\}$ is an orthonormal basis for $V$.

Notation

From now on,

$\begin{array}{rlr}{r}_{kk}& =\Vert x_k-p_{k-1}\Vert r_{ik}& =⟨x_k,u_i⟩\end{array}$

Proof by Induction

$\mathrm{S}\mathrm{p}\mathrm{a}\mathrm{n}(x_1)=\mathrm{S}\mathrm{p}\mathrm{a}\mathrm{n}(u_1)$ and $u_1$ is an orthonormal basis for $V_1$

Suppose $u_1,\dots ,u_k$ are constructed so they are an orthonormal basis for $v_k$ and $\mathrm{S}\mathrm{p}\mathrm{a}\mathrm{n}\{x_1,\dots ,x_k\}=\mathrm{S}\mathrm{p}\mathrm{a}\mathrm{n}\{u_1,\dots ,u_k\}$.

$p_k\in \mathrm{S}\mathrm{p}\mathrm{a}\mathrm{n}\{u_1,\dots ,u_k\}⟹x_{k+1}-p_k\in \mathrm{S}\mathrm{p}\mathrm{a}\mathrm{n}\{x_1,\dots ,x_k,x_{k+1}\}$

$x_{k+1}-p_k\ne 0$ because $x_1,\dots ,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=⟨x_{k+1},u_i⟩$

Therefore $u_1,\dots ,u_{k+1}$ is an orthonormal set of vectors in $\mathrm{S}\mathrm{p}\mathrm{a}\mathrm{n}\{x_1,\dots ,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=\left[\begin{array}{ccc}1& -1& 4\\ 1& 4& -2\\ 1& 4& 2\\ 1& -1& 0\end{array}\right]$

Column space is defined by $\mathrm{S}\mathrm{p}\mathrm{a}\mathrm{n}\{\left(\begin{array}{c}1\\ 1\\ 1\\ 1\end{array}\right),\left(\begin{array}{c}-1\\ 4\\ 4\\ -1\end{array}\right),\left(\begin{array}{c}4\\ -2\\ 2\\ 0\end{array}\right)\}=\mathrm{S}\mathrm{p}\mathrm{a}\mathrm{n}\{{\overrightarrow{a}}_1,{\overrightarrow{a}}_2,{\overrightarrow{a}}_3\}$

$\begin{array}{rl}{r}_{11}& =\Vert {\overrightarrow{a}}_1\Vert =\sqrt{1^2+1^2+1^2+1^2}=1\\ {\overrightarrow{q}}_1& =\frac{{\overrightarrow{a}}_1}{r_{11}}=⟨\frac{1}{2},\frac{1}{2},\frac{1}{2},\frac{1}{2}⟩\\ r_{12}& =⟨{\overrightarrow{a}}_2,{\overrightarrow{q}}_1⟩=3\\ {\overrightarrow{p}}_1& =r_{12}{\overrightarrow{q}}_1=3{\overrightarrow{q}}_1\\ {\overrightarrow{a}}_2-{\overrightarrow{p}}_1& =⟨-\frac{5}{2},\frac{5}{2},\frac{5}{2},-\frac{5}{2}⟩\\ r_{22}& =\Vert {\overrightarrow{a}}_2-{\overrightarrow{p}}_1\Vert =5\\ q_2& =\frac{{\overrightarrow{a}}_2-{\overrightarrow{p}}_1}{r_{22}}=⟨-\frac{1}{2},\frac{1}{2},\frac{1}{2},-\frac{1}{2}⟩\\ r_{13}& =⟨{\overrightarrow{a}}_3,{\overrightarrow{q}}_1⟩=2\\ r_{23}& =⟨{\overrightarrow{a}}_3,{\overrightarrow{q}}_2⟩=-2\\ {\overrightarrow{p}}_2& =r_{13}{\overrightarrow{q}}_1+r_{23}{\overrightarrow{q}}_2=⟨2,0,0,2⟩\\ {\overrightarrow{a}}_3-{\overrightarrow{p}}_2=⟨2,-2,2,-2⟩\\ r_{33}=\Vert {\overrightarrow{a}}_3-{\overrightarrow{p}}_2\Vert =4\\ q_3=\frac{{\overrightarrow{a}}_3-{\overrightarrow{p}}_2}{r_{33}}=⟨\frac{1}{2},-\frac{1}{2},\frac{1}{2},-\frac{1}{2}⟩\end{array}$

Therefore, $\{{\overrightarrow{q}}_1,{\overrightarrow{q}}_2,{\overrightarrow{q}}_3\}=\{\left(\begin{array}{c}\frac{1}{2}\\ \frac{1}{2}\\ \frac{1}{2}\\ \frac{1}{2}\end{array}\right),\left(\begin{array}{c}-\frac{1}{2}\\ \frac{1}{2}\\ \frac{1}{2}\\ -\frac{1}{2}\end{array}\right),\left(\begin{array}{c}\frac{1}{2}\\ -\frac{1}{2}\\ \frac{1}{2}\\ -\frac{1}{2}\end{array}\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, ${\overrightarrow{p}}_i$ represents the projection vectors.

$r_{ij}=\{\begin{array}{ll}\Vert {\overrightarrow{x}}_1\Vert & i=j=1\\ \Vert {\overrightarrow{x}}_i-{\overrightarrow{p}}_i\Vert & i=j\\ ⟨{\overrightarrow{q}}_i,{\overrightarrow{x}}_j⟩& \text{otherwise}\end{array}$

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

$R=\left(\{\begin{array}{ll}{r}_{ij}& i\le j\\ 0& \text{otherwise}\end{array}\right)$

such that $A=QR$, where $Q=({\overrightarrow{q}}_1,\dots ,{\overrightarrow{q}}_n)$.

Example

From previous example,

$\begin{array}{rlr}R& =\left[\begin{array}{ccc}{r}_{11}& r_{12}& r_{13}\\ 0& r_{22}& r_{23}\\ 0& 0& r_{33}\end{array}\right]Q& =({\overrightarrow{q}}_1,{\overrightarrow{q}}_2,{\overrightarrow{q}}_3)\end{array}$

Polynomial Space Example

Consider $P_3$, the subspace consisting of quadratic polynomials, with an inner product:

$⟨p,q⟩=\sum _{i=1}^{n}p(c_i)q(c_i)$, where $\overrightarrow{c}=⟨-1,0,1⟩$

$1$, $x$, and $x^2$ (represented by $\overrightarrow{x}$) form a basis for $P_3$, but they are not orthonormal w.r.t. the inner product definition.

Find an orthonormal basis $\{u_1,u_2,u_3\}$ for $P_3$.

---

$\begin{array}{rl}\Vert x_1\Vert & =\Vert 1\Vert =\sqrt{⟨1,1⟩}=\sqrt{1\cdot 1+1\cdot 1+1\cdot 1\sqrt{3}}\\ u_1& =\frac{x_1}{\Vert x_1\Vert }=\frac{1}{\sqrt{3}}\\ p_1& =⟨x,\frac{1}{\sqrt{3}}⟩\frac{1}{\sqrt{3}}=0\\ x_2-p_1& =x\\ \Vert x_2-p_1\Vert & =⟨x,x⟩=\sqrt{2}\\ u_2& =\frac{x}{\sqrt{2}}\\ p_2& =⟨x^2,\frac{1}{\sqrt{3}}⟩\frac{1}{\sqrt{3}}+⟨x^2,\frac{x}{\sqrt{2}}⟩\frac{x}{\sqrt{2}}=\frac{2}{3}\\ \Vert x^2-p_2\Vert & =⟨x^2-\frac{2}{3},x^2-\frac{2}{3}⟩=\frac{\sqrt{6}}{2}\\ u_3& =\frac{x^2-\frac{2}{3}}{\sqrt{\frac{2}{3}}}\end{array}$

Eigenvalues and Eigenvectors

Let $A$ be an $n\times n$ matrix.

A scalar $\lambda$ is an eigenvalue of $A$ if there is a nonzero vector $\overrightarrow{x}\in {\mathbb{ℂ}}^n$ such that

$A\overrightarrow{x}=\lambda \overrightarrow{x}$

$\overrightarrow{x}$ is said to be an eigenvector belonging to $\lambda$.

All of the following are equivalent: $\lambda$ is an eigenvalue iff

• $(A-\lambda I)\overrightarrow{x}=\overrightarrow{0}$ has nonzero solution
• $|A-\lambda I|=0$ This is important since it gives the characteristic equation
• $A-\lambda I$ is singular
• $N(A-\lambda I)\ne 0$

Example

$A=\left[\begin{array}{cc}4& -2\\ 1& 1\end{array}\right]$, $x=\left[\begin{array}{c}2\\ 1\end{array}\right]$

$A\overrightarrow{x}=\left[\begin{array}{c}6\\ 3\end{array}\right]=3\overrightarrow{x}$.

Therefore, $\lambda =3$ is the eigenvalue, and $\overrightarrow{x}=⟨2,1⟩$ is an eigenvector belonging to $\lambda =3$.

If $\overrightarrow{x}$ is an eigenvector belonging to $\lambda$, then $\mu \overrightarrow{x}$ is also an eigenvector belonging to $\lambda$ (for nonzero $\mu$):

$A(\mu \overrightarrow{x})=\mu A\overrightarrow{x}=\mu \lambda \overrightarrow{x}$

Characteristic Equation

$p(\lambda )=\Vert A-\lambda I\Vert$ is called the characteristic polynomial

$\Vert A-\lambda I\Vert =0$ is called the characteristic equation

Either way, the form is

$\left|\begin{array}{ccc}{a}_{11}-\lambda & \dots & a_{1n}\\ ⋮& \ddots & ⋮\\ a_{n1}& \dots & a_{nn}-\lambda \end{array}\right|$

Example 1

$A=\left[\begin{array}{cc}3& 2\\ 3& -2\end{array}\right]$

Characteristic equation is $\left|\begin{array}{cc}3-\lambda & 2\\ 3& -2-\lambda \end{array}\right|={\lambda }^2-\lambda -12$.

Solutions are $\lambda =4,-3$.

Eigenvectors can be obtained by solving $(A-\lambda I)\overrightarrow{x}=0$.