I just started learning about Gram-Schmidt, and I understand what it does, but I'm having trouble showing why it works.
For example, let $P_k$ for $k=1,...,p$ be a projection matrix for a matrix $A_{1:k}$ (so the first $k$ columns). Then let's say we have $u_1 = a_1$, and any $u_k = (I-P_{k-1})a_k$ for each $k$. How do I:
1) Show that the $u_k$ are orthogonal
2) Show that the span of $u_1,...,u_k$ is the same as the span of $a_1,...,a_k$ for each $k=1,...,p$.
I feel a bit dumb because I realize that both these results are the the whole point of Gram-Schmidt. #2 I thought should be especially obvious but when I tried to prove it I got no where fast. I was trying to take advantage of the fact that $P$ is symmetric/idempotent, but maybe that's not the approach to take? Can anyone help? I'd really appreciate it.
Let $V_k = [\{a_1,a_2,\cdots,a_k\}]$ be the linear span of the first $k$ basis elements, and let $P_k$ be the orthogonal projection of the full space $V$ onto the subspace $V_k$. The dimension of $V_k$ is $k$. By definition of $P_k$, the vector $P_kx$ is the unique vector for which $$ P_kx \in V_k,\;\;\;(x - P_k x)\perp V_{k-1}. $$ (Special handling is required for $k=1$ of course.) Therefore $v_k = a_k-P_{k-1}a_k$ is in $V_k$ and $v_k \perp V_{k-1}$, which gives $$ v_k \perp v_{j},\;\;\; j=1,2,\cdots,k-1. $$ None of the $v_k$ can be $0$ because $v_k =a_k-P_{k-1}a_k\notin V_{k-1}$. So $\{ v_1,v_2,\cdots,v_k\}$ is a set of non-zero mutually orthogonal vectors whose span is contained in $V_k$, which means that $\{ v_1,v_2,\cdots,v_k\}$ is a basis of $V_k$, because of dimension.