Exercises — Gram-Schmidt orthogonalization — algorithm

$c=\frac{⟨v,u⟩}{⟨u,u⟩}.$ Why: we demand $⟨v-cu,u⟩=0$. Expand: $⟨v,u⟩-c⟨u,u⟩=0$, solve for $c$. The value is not a guess — it is forced by requiring zero leftover overlap. Look at the right triangle in the figure above: $cu$ is the base (shadow) and $v-cu$ is the vertical leg meeting it at a right angle.

$u_1=v_1=(4,0)$. Why: the very first vector has nothing earlier to be perpendicular to, so there is no overlap to subtract. Gram–Schmidt always starts by copying $v_1$.

$⟨v,u⟩=2\cdot 3+2\cdot 1=8$. $⟨u,u⟩=3\cdot 3+1\cdot 1=10$. These are exactly the two numbers you feed into the coefficient $c=8/10=0.8$.

$u_1=(2,0)$. $⟨v_2,u_1⟩=1\cdot 2+1\cdot 0=2$; $⟨u_1,u_1⟩=4$; so $c=2/4=\frac{1}{2}$. $u_2=(1,1)-\frac{1}{2}(2,0)=(1,1)-(1,0)=(0,1).$ Check: $⟨u_1,u_2⟩=2\cdot 0+0\cdot 1=0$ ✅. The leftover points straight up, perpendicular to the horizontal $u_1$.

$\Vert u_1\Vert =\sqrt{4}=2$, so $e_1=\frac{1}{2}(2,0)=(1,0)$. $\Vert u_2\Vert =\sqrt{1}=1$, so $e_2=(0,1)$. The orthonormal set is the standard basis $\{(1,0),(0,1)\}$ — clean and unit length.

$u_1=(0,5)$. $⟨v_2,u_1⟩=0\cdot 0+4\cdot 5=20$; $⟨u_1,u_1⟩=25$; $c=20/25=0.8$. $u_2=(4,4)-0.8(0,5)=(4,4)-(0,4)=(4,0).$ Check: $⟨u_1,u_2⟩=0\cdot 4+5\cdot 0=0$ ✅. Normalize: $\Vert u_1\Vert =5\Rightarrow e_1=(0,1)$; $\Vert u_2\Vert =4\Rightarrow e_2=(1,0)$.

$u_1=(1,1,1)$, $⟨u_1,u_1⟩=3$. $⟨v_2,u_1⟩=1+1+0=2$; $c=\frac{2}{3}$: $u_2=(1,1,0)-\frac{2}{3}(1,1,1)=\left(\frac{1}{3},\frac{1}{3},-\frac{2}{3}\right).$ $⟨u_2,u_2⟩=\frac{1}{9}+\frac{1}{9}+\frac{4}{9}=\frac{6}{9}=\frac{2}{3}$. Now $u_3$: subtract overlaps with both $u_1$ and $u_2$. $⟨v_3,u_1⟩=1$, coefficient $=1/3$. $⟨v_3,u_2⟩=1\cdot \frac{1}{3}+0+0=\frac{1}{3}$, coefficient $=\frac{1/3}{2/3}=\frac{1}{2}$. $u_3=(1,0,0)-\frac{1}{3}(1,1,1)-\frac{1}{2}\left(\frac{1}{3},\frac{1}{3},-\frac{2}{3}\right).$ $=(1,0,0)-\left(\frac{1}{3},\frac{1}{3},\frac{1}{3}\right)-\left(\frac{1}{6},\frac{1}{6},-\frac{1}{3}\right)=\left(\frac{1}{2},-\frac{1}{2},0\right).$ Check: $⟨u_3,u_1⟩=\frac{1}{2}-\frac{1}{2}+0=0$ ✅; $⟨u_3,u_2⟩=\frac{1}{6}-\frac{1}{6}+0=0$ ✅.

When we build $u_k$ we must make it perpendicular to every already-settled vector $u_1,\dots ,u_{k-1}$. For $u_2$ there is one earlier vector ($u_1$) → one subtraction. For $u_3$ there are two ($u_1,u_2$) → two subtractions. Each subtraction kills the overlap with exactly one clean direction, and because those clean directions are already mutually orthogonal, the subtractions do not interfere (this is why we project onto the $u_j$, not the raw $v_j$ — see Orthogonal projection).

$u_1=(1,0,0)$. For $v_2=(2,0,0)$: $c=⟨v_2,u_1⟩/⟨u_1,u_1⟩=2/1=2$, so $u_2=(2,0,0)-2(1,0,0)=(0,0,0)$. $u_2=0$ because $v_2$ is just $2v_1$ — it lies entirely in the span of $u_1$, leaving zero leftover. This signals the input set is not linearly independent (see Linear independence). You cannot normalize a zero vector (division by zero).

From the parent: $u_1=(3,1)$, $u_2=(-0.4,1.2)$. $\Vert u_1\Vert =\sqrt{10}$, $\Vert u_2\Vert =\sqrt{1.6}$. $e_1=\frac{1}{\sqrt{10}}(3,1),e_2=\frac{1}{\sqrt{1.6}}(-0.4,1.2).$ $R$ entries are the projection/length data: $R_{11}=\Vert u_1\Vert =\sqrt{10}$, $R_{22}=\Vert u_2\Vert =\sqrt{1.6}$, and $R_{12}=⟨v_2,e_1⟩=\frac{⟨v_2,u_1⟩}{\Vert u_1\Vert }=\frac{8}{\sqrt{10}}$. $Q=\left(\begin{array}{cc}3/\sqrt{10}& -0.4/\sqrt{1.6}\\ 1/\sqrt{10}& 1.2/\sqrt{1.6}\end{array}\right),R=\left(\begin{array}{cc}\sqrt{10}& 8/\sqrt{10}\\ 0& \sqrt{1.6}\end{array}\right).$ Sanity: $R$ is upper-triangular (zero below the diagonal) and $R_{11}{R}_{22}=\sqrt{10}\cdot \sqrt{1.6}=4$, which equals $|\det A|=|3\cdot 2-1\cdot 2|=4$ ✅.

$e_1=(1,0)$ already unit length. $⟨v_2,e_1⟩=1$. Then $u_2=(1,1)-1\cdot (1,0)=(0,1)$, already unit, so $e_2=(0,1)$. Why no denominator: when we project onto a unit vector $e_j$, the coefficient is $\frac{⟨v,e_j⟩}{⟨e_j,e_j⟩}=\frac{⟨v,e_j⟩}{1}=⟨v,e_j⟩$. The self-inner-product is $1$, so the division disappears.

$⟨p_1,p_1⟩={\int }_{-1}^{1}1dx=2$, so $e_1=\frac{1}{\sqrt{2}}$. Overlap of $p_2$ with $p_1$: $⟨p_2,p_1⟩={\int }_{-1}^{1}xdx=0$ (odd function). So $u_2=x-0=x$. $⟨x,x⟩={\int }_{-1}^1{x}^{2}dx=\frac{2}{3}$, so $\Vert u_2\Vert =\sqrt{2/3}$ and $e_2=\sqrt{\frac{3}{2}}x$. Insight: the machine is identical — dot products just became integrals. These $e_1,e_2$ are the first two (normalized) Legendre polynomials.

Suppose $v_k\in \mathrm{span}(v_1,\dots ,v_{k-1})=\mathrm{span}(u_1,\dots ,u_{k-1})$ (the spans match by construction). Write $v_k={\sum }_{j<k}{\alpha }_j{u}_j$. The Gram–Schmidt formula subtracts precisely the projection onto that span: $u_k=v_k-{\sum }_{j<k}\frac{⟨v_k,u_j⟩}{⟨u_j,u_j⟩}{u}_j.$ Because the $u_j$ are orthogonal, $\frac{⟨v_k,u_j⟩}{⟨u_j,u_j⟩}={\alpha }_j$, so the sum reconstructs $v_k$ exactly, giving $u_k=v_k-v_k=0$. A zero residual means "nothing new" — no perpendicular leftover exists because $v_k$ added no new direction. Thus a zero $u_k$ is Gram–Schmidt's built-in dependence detector.

Coordinate along $e_1$: $⟨b,e_1⟩=3$. Along $e_2$: $⟨b,e_2⟩=5$. So $b=3e_1+5e_2$. Why so easy: in a general basis you'd solve a linear system. With an orthonormal basis, each coordinate decouples: $b={\sum }_k⟨b,e_k⟩e_k$, one independent dot product per axis. This is exactly why least squares uses Gram–Schmidt — the normal equations become diagonal (no cross-terms), so each best-fit coefficient is read off directly.

Every settled vector needs its own denominator ::: $⟨u_j,u_j⟩$, recomputed each time. A zero residual $u_k=0$ means ::: the input set was linearly dependent. Coordinates in an orthonormal basis are ::: single dot products $⟨b,e_k⟩$. $R_{11}{R}_{22}$ in a $2\times 2$ QR equals ::: $|\det A|$.