I am reading through "Matrix Computations" by Gene H. Golub and Charles F. Van Loan and have come across a proof on the properties of Tridiagonal Decomposition that seems to gloss over parts I do not understand. The theorem (theorem 8.3.1) states that:
If $Q^TAQ=T$ is the tridiagonal decomposition of symmetric matrix $A \in \mathbb{R}^{n \times n}$, then $Q^TK(A,Q(:,1),n)=R$ is upper triangular. If $R$ is nonsingular, then $T$ is unreduced. If $R$ is singular and k is the smallest index so $r_{kk}=0$, then $k$ is also the smallest index so $t_{k,k-1}$ is zero.
Here $K(A,v,k)=\left[v,Av,\cdots,A^{k-1}v\right]$, a Krylov matrix, and $Q(:,1)$ is the first column of $Q$.
The proof given simply says that the result is clear.
For the first statement it gives a line of working: $$Q^TK(AQ(:,1),n)=\left[Q^Tq_1,(Q^TAQ)(Q^Tq_1),\dots,(Q^TAQ)^{n-1}(Q^Tq_1)\right]=\left[e_1,Te_1,\dots,T^{n-1}e_1\right]=R $$ where $q_1$ is the first column of $Q$. I can follow this through until the last equality. If $T$ is tridiagonal, why do the first columns of powers of it form an upper triangular matrix? Through experimentation I can see this is true, but I can't work out why.
All it says for the second statement is that it is obvious. I do not understand how it is clear! Could anyone explain why this is the case?
Similarly, for the third statement the proof just restates it and includes no explanation at all.
Any elaboration on these points would be much appreciated!
Golub and Van Loan's proof can be fleshed out by a straightforward induction as follows.
Let $T$ be a square tridiagonal matrix and denote the $(i, j)$ element of $T^m$ by $t_{_{i,j} }^{\left( m \right)}$. First we’ll establish a mini-lemma that the $m$-th power of a square tridiagonal matrix is zero below the $m$-th subdiagonal. This is obviously true for $m=1$, so let $m>1$.
Since $T^m = T^{m - 1} T$, we have that $t_{_{i,j} }^{\left( m \right)} = \sum\limits_{k = 1}^n {t_{_{i,k} }^{\left( {m - 1} \right)} t_{_{k,j} }^{\left( 1 \right)} }$. Since $T$ is tridiagonal, $t_{_{k,j} }^{\left( 1 \right)}$ can only be nonzero if $k\le j + 1$. We also have that that $t_{_{i,k} }^{\left( {m - 1} \right)}$ can only be nonzero if $i \le k + (m - 1)$ by induction (i.e., $T^{m-1}$ can be nonzero only above the $m$-th subdiagonal). Therefore, the product $t_{_{i,k} }^{\left( {m - 1} \right)} t_{_{k,j} }^{\left( 1 \right)}$ can only be nonzero if $i \le k + (m - 1) \le \left( {j + 1} \right) + (m - 1) = j + m$ which shows that $t_{_{i,j} }^{\left( m \right)} = \sum\limits_{k = 1}^n {t_{_{i,k} }^{\left( {m - 1} \right)} t_{_{k,j} }^{\left( 1 \right)} } = 0$ whenever $i > j+m$. In other words, $T^m$ is zero below the $m$-th subdiagonal. In particular, we see that the first column of $T^m$ is zero below the $(m+1)$st row, and this shows that the matrix $R$ is upper triangular.
If we want to look at the closed form for the diagonal elements of $R$, we can again use induction. First, note that $r_{1,1} = 1$ and $r_{2,2} = t_{2,1}$. Consider the case where $m>1$. Since $T^m = TT^{m - 1}$ we have that $r_{m + 1,m + 1} = t_{m + 1,1}^{^{\left( m \right)} } = \sum\limits_{k = 1}^n {t_{m + 1,k}^{^{\left( 1 \right)} } t_{k,1}^{^{\left( {m - 1} \right)} } }$. Since $T$ is tridiagonal, we know that $t_{m + 1,k}^{^{\left( 1 \right)} } = 0$ for $k<m$. But if $k>m$, we have that $t_{k,1}^{^{\left( {m - 1} \right)} } = 0$ from our mini-lemma. This means, that all terms of our expression for $r_{m + 1,m + 1}$ are zero except when $k=m$. In other words, $r_{m + 1,m + 1} = t_{m + 1,m}^{^{\left( 1 \right)} } t_{m,1}^{^{\left( {m - 1} \right)} } = t_{m + 1,m} t_{m,1}^{^{\left( {m - 1} \right)} }$. Therefore $r_{m + 1,m + 1} = \prod\limits_{k = 1}^m {t_{k + 1,k} }$ by induction.
For your other questions, first note that if $R$ is nonsingular, its determinant must be nonzero and therefore, from our expression for $r_{m+1,m+1}$, we see that none of the elements $t_{k + 1,k}$ can be zero. Since $T$ is symmetric (which follows since $A$ is symmetric), we have that the other off diagonal elements $t_{k,k + 1}$ must also be nonzero. Therefore, $T$ is unreduced.
The last statement follows directly from $r_{k,k} = \prod\limits_{i = 1}^{k - 1} {t_{i + 1,i} } = t_{k,k - 1} \prod\limits_{i = 1}^{k - 2} {t_{i + 1,i} } = 0$, since $r_{j - 1,j - 1} = \prod\limits_{i = 1}^{j - 2} {t_{i + 1,i} }$ is assumed to be nonzero for all $2 \le j\le k$.