# Proving R is an upper triangular matrix

Let $A\in \mathbb{R}^{n\times n}$ be a symmetric positive definite matrix. Let $x\in \mathbb{R}^n$ with $\|{x}\|_2=1$ and consider the matrix $P=[x,Ax,\dots,A^{n-1}x]\in \mathbb{R}^{n \times n}$.

Suppose there is an orthogonal matrix $Q \in \mathbb{R}^{n \times n}$ such that $Q^TAQ=T$ where $T\in \mathbb{R}^{n \times n}$ is a symmetric tridiagonal matrix.

I want to show that if the first column of $Q$ is $x$, then $Q^TP^=R$ where $R$ is an upper triangular matrix.

This is obvious from the $QR$ factorisation, where simply by left multiplying by $Q$ it can be seen that $P=QR$ with $R$ upper triangular as $Q$ is orthogonal. However, I am having touble finding a proof that it's the case.

Currently I am on the track of writing the matrix multiplications as chunks of the matrices and breaking it down this way, but I am not getting very far. By writing $x_i=q_{i1}$, the multiplication becomes:

$$\begin{bmatrix} q_1^T \\ q_2^T \\ \vdots \\ q_n^T \end{bmatrix} \begin{bmatrix} q_1 & Aq_1 & \dots & A^{n-1}q_1 \end{bmatrix}= \begin{bmatrix} q_1^Tq_1 & q_1^TAq_1 & \dots & q_1^TA^{n-1}q_1 \\ q_2^Tq_1 & q_2^TAq_1 & \dots & q_2^TA^{n-1}q_1 \\ \vdots & \vdots & \dots & \vdots \\ q_n^Tq_1 & q_n^TAq_1 & \dots & q_n^TA^{n-1}q_1 \end{bmatrix}$$ where the $q_i$ are column vectors for $i=1,\dots,n$.

Using the summation expression of matrix multiplication, I know $(Aq_1)_i=\sum\limits_{j=1}^{n}a_{ij}q_{j1}$ and $(Q^TQ)_{ij}=\sum\limits_{k=1}^{n}q_{ki}q_{kj}=0$ when $i \ne j$ as $Q$ is orthogonal. Thus I can deduce that the first column of $R$ (ie. $q_i^Tq_1$ for $i=1,\dots,n$) is simply $e_1=\left[\begin{array}{c}1 \\ 0 \\ \vdots \\ 0 \end{array}\right]$.

However, trying to extend this to the remaining columns is not going well. I have found the $2^{nd}$ column of $R$ (ie. $q_i^TAq_1$ for $i=1,\dots,n$) to be $\sum\limits_{k=1}^{n}q_{ki}\left(\sum\limits_{j=1}^{n}a_{kj}q_{j1}\right)=\sum\limits_{k=1}^{n}\sum\limits_{j=1}^{n}a_{kj}q_{ki}q_{j1}$, but I don't know how to show from this that it must be $0$ for $i>2$ which it would need to be if $R$ was upper triangular - all I know is that the first entry is $>0$ by definition of $A$.  Is this even the right direction to be looking? I know that $A$ SPD $\implies x^TAx>0$ for any vector $x\in \mathbb{R}\backslash\{0\}$, and that $Q$ orthogonal $\implies Q^TQ=I$. Thus $A$ can be written as $QTQ^T$ and it can be deduced that $P$ can be split into sections: $P=\left[x\space |\space QTQ^Tx\space |\space QT^2Q^Tx\space |\space \cdots\space |\space QT^{n-1}Q^Tx\right]$. However, I am not sure if this helps show that $R$ is upper triangular. I am not sure how the fact $T$ is tridiagonal helps with the proof - or even if it does!

Any kind of help at all would be much appreciated!

Fact 1 If $Q^TAQ=T$, where $Q$ is square orthogonal and $T$ is upper Hessenberg (a tridiagonal matrix is upper Hessenberg as well) such that no entry one below the diagonal is zero, then $Q_k:=[q_1,\ldots,q_k]$ forms an orthonormal basis of $\mathrm{span}(q_1,Aq_1,\ldots,A^{k-1}q_1)$.
Proof: Obviously, the statement is true for $k=1$. From $Q^TAQ=T$, we have $AQ=QT$. Let's evaluate the $k$th column of this relation. We have $$Aq_k=(QT)_{:,k}=q_1t_{1,k}+\cdots+q_k t_{k,k}+q_{k+1} t_{k+1,k}.$$ By the assumption, $t_{k+1,k}\neq 0$ and hence $$q_{k+1}=\frac{1}{t_{k+1,k}}\left(Aq_k-q_1t_{1,k}-\cdots-q_k t_{k,k}\right).$$ Assume (for the induction) that the statement is true for $k$ so $q_i\in\mathrm{span}(q_1,Aq_1\ldots,A^{k-1}q_1)$. From the equation above, we have that $q_{k+1}\in\mathrm{span}(q_1,Aq_1,\ldots,A^kq_1)$. $\Box$
Fact 2 Let $M$ and $N$ are matrices. Then $\mathrm{Im}(M_k)\subseteq\mathrm{Im}(N_k)$ for $k=1,\ldots,n$, where $M_k$ denotes the matrix formed from the first $k$ columns of the matrix $M$, if and only if $M=NR$, where $R$ is upper triangular.
Proof: The proof is based entirely on the fact that the $k$th column of $M=NR$ reads $$m_k=n_1r_{1,k}+\ldots+n_kr_{k,k}. \quad \Box$$