# 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. –  Jean-Claude Arbaut Nov 29 '13 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. –  user1551 Nov 29 '13 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? –  Vedran Šego Nov 29 '13 at 15:38
Indeed, some savings are possible, e.g., if $R$ is banded. Otherwise the update can be quite costly. –  Algebraic Pavel Nov 29 '13 at 18:13
@AlgebraicPavel Unfortunately, $R$ is just a general triangular matrix, with no extra "nicer" structure. –  Vedran Šego Nov 29 '13 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.