Consider a $n \times n$ matrix $A$ that is decomposed as
$A = QR,$ where $Q$ is the matrix whose columns are generated via
a normalized Gram-schmidt process, i.e. given a basis of $A$ as
$\{v_1,…,v_k\},$
$$u_i = v_i – \sum_{j=1}^{i-1} proj_{u_j}(v_i),$$
$$Q_{,i} = \frac{u_i}{\|u_i\|}.$$
Take $Q = [e_1,…,e_k].$ I want to prove that $R$ is upper-triangular in
this decomposition. We see that
$$R = Q^{-1}A = Q^T A,$$
Since $Q$ is an orthonormal basis matrix. We
see that
$$R_{ij} = Q^T_{i,} \cdot A_{,j}
= (Q_{,i})^T \cdot A_{,j}$$
$$=\sum_{k=1}^n e_{i,k}A_{k,j},$$
But I am having some difficulty unfolding this calculation in terms of
$e_{i} = \frac{u_i}{\|u_i\|}.$ Any recommendations on what to do with this
calculation, in particular what happens when $i > j$?
Best Answer
Write the equation as $Q= AR^{-1}$.
(1) A matrix is upper triangular iff its inverse is. (verify this). So it suffices to show $R^{-1}$ is triangular.
(2) The $j$-th column of $Q$, the by the way matrix multiplication is defined, is the product of $A$ with the $j$-th column of $R^{-1}$.
(3) So it is the linear combination of columns of $A$ with coefficients coming from the entries of the $j$-th column of $R^{-1}$. (in the same order).
(4) In other words, the $j$-th vector in the orthonormal basis constructed is a linear combination of the columns of $A$ with coefficients coming from the $j$-th column of $R^{-1}$.
(5) Now the Gram-Schmidt formula when inspected closely reveals that the $j$ the vector of new basis is constructed by only using the first $j$ vectors of the original basis; that is the first $j$ columns of $A$.
This means, in $R^{-1}$ the entries below the $j$-th entry should be zero. Hence it is upper triangular.