reorder variables in upper triangular matrix

Question

I have an upper triangular system

$$ \begin{bmatrix} a_{00} & a_{01} & a_{02} & a_{03} \\ 0 & a_{11} & a_{12} & a_{13} \\ 0 & 0 & a_{22} & a_{23} \\ 0 & 0 & 0 & a_{33} \\ \end{bmatrix} \begin{bmatrix} x_0 \\ x_1 \\ x_2 \\ x_3 \end{bmatrix} = \begin{bmatrix} b_0 \\ b_1 \\ b_2 \\ b_3 \end{bmatrix}. $$

My goal is to remove $x_1$ from the system and just have

$$ \begin{bmatrix} a_{00}' & a_{01}' & a_{02}' \\ 0 & a_{11}' & a_{12}' \\ 0 & 0 & a_{22}' \\ \end{bmatrix} \begin{bmatrix} x_0 \\ x_2 \\ x_3 \end{bmatrix} = \begin{bmatrix} b_0' \\ b_1' \\ b_2' \\ \end{bmatrix}. $$

I think this is possible by reordering the states and then doing a QR factorization which would give something like the following from which the top row could be removed.

$$ \begin{bmatrix} a_0'' & a_1'' & a_2'' & a_3'' \\ 0 & a_{00}' & a_{01}' & a_{02}' \\ 0 & 0 & a_{11}' & a_{12}' \\ 0 & 0 & 0 & a_{22}' \\ \end{bmatrix} \begin{bmatrix} x_1 \\ x_0 \\ x_2 \\ x_3 \end{bmatrix} = \begin{bmatrix} b'' \\ b_0' \\ b_1' \\ b_2' \end{bmatrix} $$

Answer 1

I figured it out, I'll leave my method here to help others solve the problem in the future. Given a system $A \bar{x} = \bar{b}$

$$ \begin{bmatrix} a_{00} & a_{01} & a_{02} & a_{03} \\ 0 & a_{11} & a_{12} & a_{13} \\ 0 & 0 & a_{22} & a_{23} \\ 0 & 0 & 0 & a_{33} \\ \end{bmatrix} \begin{bmatrix} x_0 \\ x_1 \\ x_2 \\ x_3 \end{bmatrix} = \begin{bmatrix} b_0 \\ b_1 \\ b_2 \\ b_3 \end{bmatrix}, $$

first we'll reorder the state vector so the states to be dropped are at the beginning

$$ \begin{bmatrix} a_{01} & a_{00} & a_{02} & a_{03} \\ a_{11} & 0 & a_{12} & a_{13} \\ 0 & 0 & a_{22} & a_{23} \\ 0 & 0 & 0 & a_{33} \\ \end{bmatrix} \begin{bmatrix} x_1 \\ x_0 \\ x_2 \\ x_3 \end{bmatrix} = \begin{bmatrix} b_0 \\ b_1 \\ b_2 \\ b_3 \end{bmatrix}. $$

Call the above $A_\text{reorder} \bar{x}_\text{reorder} = \bar{b}$. Then take the QR factorization of the matrix

$$ QR = A_\text{reorder}, $$

and apply the rotation to $\bar{b}$

$$ \bar{b}'' = Q^T \bar{b}. $$

We now have a new upper triangular system $R \bar{x}_\text{reorder} = \bar{b}''$, and so we can just extract the bottom three equations

$$ \begin{align} A' &= R[2:4, 2:4], \\ \vec{b}' &= \bar{b}''[2:4]. \end{align} $$

This gives us our desired system

$$ \begin{bmatrix} a_{00}' & a_{01}' & a_{02}' \\ 0 & a_{11}' & a_{12}' \\ 0 & 0 & a_{22}' \\ \end{bmatrix} \begin{bmatrix} x_0 \\ x_2 \\ x_3 \end{bmatrix} = \begin{bmatrix} b_0' \\ b_1' \\ b_2' \\ \end{bmatrix}. $$

Simple example in python:

from numpy import *
from numpy.linalg import solve
from scipy.linalg import qr

b = array([0, 1, 2, 3])
A = array([[2, 3, 7, 1], [0, 2, 4, 5], [0, 0, 1, 8], [0, 0, 0, 2]])

indices_drop = [1]
indices_keep = [0, 2, 3]

x = solve(A, b)

indices = indices_drop + indices_keep

A_reorder = A[:, indices]

[Q, R] = qr(A_reorder, mode="full")

b_pp = Q.T @ b

A_p = R[-len(indices_keep) :, -len(indices_keep) :]
b_p = b_pp[-len(indices_keep) :]

x_p = solve(A_p, b_p)
```

Answer 2

From the second row

$ x_1 = \dfrac{1}{a_{11}} \left( b_1 - a_{12} x_2 - a_{13} x_3 \right)$

The third and fourth equations will not change, because they do not depend on $x_1$. For the first equation, it'll become

$ a_{00} x_0 + \dfrac{a_{01}}{a_{11}} \left( b_1 - a_{12} x_2 - a_{13} x_3 \right) + a_{02} x_2 + a_{03} x_3 = b_0$

Thus the first equation becomes

$ a_{00} x_0 + \left( a_{02} - \dfrac{a_{01} a_{12}}{a_{11}}\right) x_2 + \left(a_{03} - \dfrac{ a_{01} a_{13}}{a_{11}}\right) x_3 = b_0 - \dfrac{a_{01}}{a_{11}} b_1 $