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!


To get your statement, combine Facts 1 and 2 below.

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 $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.