0
$\begingroup$

I have a matrix which is already up-triangular like :

$\begin{bmatrix}A & B\\ 0 & C\end{bmatrix}$

in which A and C is up-triangular block, now I add a block row then get :

$\begin{bmatrix}A & B\\ 0 & C \\ D & E\end{bmatrix}$

I want to apply a qr decomposition to keep this matrix up-triangular while keep A is not changed:

$ Q*\begin{bmatrix}A & B\\ 0 & C \\ D & E\end{bmatrix} = \begin{bmatrix} A & F \\ 0 & G \\ 0 & 0 \end{bmatrix}$

I know this could be achieved by gauss elimination method, because A is already up-triangular, we can modify the D col by col according the data from A, this could also keep A not changed.

but col by col operation is not computation efficient. I know the givens rotation or householder reflection is the common method for QR, but I think they can't keep A not changed, so any more efficient method than gauss elimination ?


and I have an advance question, I have an up-triangular matrix like, which means a linear solve system :

$ \begin{bmatrix} A & B &C \\ 0 & D & E \\ 0 & 0 & F \end{bmatrix} $

A,D,F is up-triangular block. with some variables permute I can get another linear system:

$ \begin{bmatrix} D & 0 & E \\ B & A & C \\ 0 & 0 & F \end{bmatrix} $

I want apply a qr decomposition while keep A not changed, which mean:

$ Q* \begin{bmatrix} D & 0 & E \\ B & A & C \\ 0 & 0 & F \end{bmatrix} = \begin{bmatrix} G & H & I \\ 0 & A & J \\ 0 & 0 & K \end{bmatrix}$

I think even gauss elimination can't achieve this purpose. is there any solution :)?

$\endgroup$
2
$\begingroup$

First case

Note that multiplication by an orthogonal matrix preserves the $2$-norm of vectors. It's therefore impossible to achieve what you want unless $D=0$.


Second case

Likewise, you must have $H=0$.

Now assume further that $A$ is regular (since it's upper triangular, this means it has no zero on the diagonal). Then, cut $Q$ in blocks so that $Q^T$ matches the block structure of the other two matrices.

Then multiplying $Q$ by the middle block-column, $Q_{12}A=0$, $Q_{22}A=A$, $G_{32}A=0$, hence $Q_{12}=0, Q_{22}=I, Q_{32}=0$.

Since the column vectors of $Q$ are orthogonal, you must also have $Q_{21}=0$ and $Q_{23}=0$. Then multiplying $Q$ by the first block column, you must have $B=0$, and multiplying by the last block-column, $C=J$.

But then, the matrix to triangularize is already upper triangular, so you may as well pick $Q=I$.

Note that when $A=0$ (it's then not regular anymore), it's possible to achieve the $QR$ decomposition.

$\endgroup$
  • $\begingroup$ thank you for your advise , I think I have mistaken the gauss elimination operation as an orthogonal transform. $\endgroup$ – Mr.Guo May 21 at 0:40
  • $\begingroup$ as your advice, I plan to modify my method by : $ Q*\begin{bmatrix}A & B\\ 0 & C \\ D & E\end{bmatrix} = \begin{bmatrix} H & F \\ 0 & G \\ 0 & 0 \end{bmatrix} \approx \begin{bmatrix} A & F \\ 0 & G \\ 0 & 0 \end{bmatrix} $ what's your opinion ? actually I'm planning to achieve the schmidt-kalman filter by qr method, in skf method , the covariance is updated but some block is not changed, maybe I could apply qr decom while keep A not changed, I think they are equivalent operations , right ? $\endgroup$ – Mr.Guo May 21 at 0:51
  • $\begingroup$ also for the second case , like : $ Q* \begin{bmatrix} D & 0 & E \\ B & A & C \\ 0 & 0 & F \end{bmatrix} = \begin{bmatrix} G & H & I \\ 0 & L & J \\ 0 & 0 & K \end{bmatrix} \approx \begin{bmatrix} G & H & I \\ 0 & A & J \\ 0 & 0 & K \end{bmatrix} $ $\endgroup$ – Mr.Guo May 21 at 0:53
  • $\begingroup$ @Mr.Guo I can't help you much with the Schmidt-Kalman filter, but regarding the QR decomposition, as long as you keep in mind the properties of orthogonal matrices, it should be fine. That is, $H$ and $L$ can't be equal to $A$, and theirs columns must account for the norm of $D$ and $H$ respectively. $\endgroup$ – Jean-Claude Arbaut May 21 at 4:52
  • $\begingroup$ ok thank you any way :) $\endgroup$ – Mr.Guo May 22 at 5:28

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.