# 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.

#### Solutions Collecting From Web of "QR factorization of a special structured matrix"

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.