# QR factorization of a special structured matrix

A friend asked me the following interesting question:

Let

$$A = \begin{bmatrix} R \\ \xi{\rm I} \end{bmatrix},$$

where $$R \in \mathbb{R}^{n \times n}$$ is an upper triangular and $${\rm I}$$ is an identity matrix, both of order $$n$$, and $$\xi \in \mathbb{R}$$ is a scalar.

Is there an efficient way to compute a QR factorization of $$A$$?

I have found this question with a very nice answer, but I'd like to avoid doing the SVD because it is computationally expensive and my $$R$$ is not a constant like $$W$$ in that other question. Also, my $$R$$ is already triangular, which I hope can somehow be used.

Edit: There was a comment (turned into an answer while I was writing this edit) on using Givens rotations. Since this is a logical first idea, I'd like to explain why I don't like it.

We could use Givens rotations to cancel out the elements of $$\xi{\rm I}$$, but each Givens rotation is computing two linear combinations of two rows. That means that if I cancel out the first element of $$\xi{\rm I}$$, I will also introduce a bunch of non-zeros to the rest of that row.

This means that I would need to go through the whole upper triangle of the bottom block, same as I'd have to do if $$\xi{\rm I}$$ was a general upper triangular matrix. Given that it is a diagonal matrix (with all its diagonal elements being the same, although I suspect this doesn't help much), I am hoping to get more efficient than that.

• You are right, Givens rotations do not help much. I delete the answer. Commented Nov 29, 2013 at 15:08
• If $A=Q\pmatrix{L^\top\\ 0}$, then $L$ is the matrix for Cholesky decomposition of $R^\top R + \xi^2I$. I don't recall any method to do a diagonal update to Cholesky decomposition in less than $O(n^3)$ time. Commented Nov 29, 2013 at 15:29
• @user1551 Good point. How about making it into an answer, so I have something to accept in case no one comes up with such an updating method? Commented Nov 29, 2013 at 15:38
• Indeed, some savings are possible, e.g., if $R$ is banded. Otherwise the update can be quite costly. Commented Nov 29, 2013 at 18:13
• @AlgebraicPavel Unfortunately, $R$ is just a general triangular matrix, with no extra "nicer" structure. Commented Nov 29, 2013 at 19:13

For sake of having an answer ... if $A=Q\pmatrix{L^\top\\ 0}$, then $L$ is the matrix for Cholesky decomposition of $R^\top R+\xi^2I$. As a Cholesky rank-one update already consumes $O(n^2)$ time, I find it hard to believe that a diagonal update can be done in $O(n^2)$ time. However, since this is not a general diagonal update, but a correction by scalar multiple of $I$, perhaps someone could really beat $O(n^3)$ time, although I wouldn't bet on it.