# Backward triangularization

An algorithm to rearrange a matrix by recursively assigning a singleton column to the rear (with its only row as its pivot). The recursion applies to the submatrix defined by omitting the assigned column and row (and reducing remaining column counts accordingly). This results in a lower-triangular rearrangement if and only if such a rearrangement exists. Otherwise, the algorithm reaches a submatrix will all columns having more than one element, of which one is selected to be a spike that is assigned to the rear of the matrix. The process then continues on the submatrix.

Example 1: Let the nonzeros be denoted by *:

$LaTeX:

 A = \begin{bmatrix} * & & & \\ * & * & * & * \\ * & & & * \\ * & & * & * \end{bmatrix}

$

The column counts are $LaTeX: (4,1,2,3)$. We thus put column $LaTeX: 2$ at the rear, assigned to pivot on row $LaTeX: 2$, and consider the remaining $LaTeX: 3\times 3$ submatrix:

$LaTeX:

A^1 = \begin{bmatrix} * & & & \cdot & \\ * & & * & \cdot & \\ * & * & * & \cdot & \\ \cdot & \cdot & \cdot & \cdot & \cdot \\ * & * & * & \cdot & * \end{bmatrix}

$

The remaining column counts (for $LaTeX: A^1$) are $LaTeX: (3,1,2)$, so column $LaTeX: 2$ is placed at the (new) rear, pivoting on row $LaTeX: 3$:

$LaTeX:

A^2 = \left[\begin{array}{cc|cc} * & & & \\ * & * & & \\ \hline * & * & * & \\ * & * & * & * \end{array}\right]

$

The remaining column counts are $LaTeX: (2,1)$, so we reach the final rearrangement, which is triangular:

$LaTeX:

A^3 = \left[\begin{array}{cc cc} * & & & \\ * & * & & \\ * & * & * & \\ * & * & * & * \end{array}\right]

$

Example 2: Column counts are shown below the matrix.

$LaTeX:

\begin{array}{l} A = \left[\begin{array}{cccc} * & & & \\ * & * & * & * \\ * & * & & * \\ * & & * & * \end{array}\right] \\ \phantom{A = \left[\right.}~ \begin{array}{cccc} 4 & 2 & 2 & 3 \end{array} \end{array}

$

All column counts are greater than one, so we select a column to be a spike, and we assign it to the rear with a pivot row (some algorithms delay the pivot row assignment). For this example, we choose a column with minimum count and pick the pivot row with maximum count.

$LaTeX:

\begin{array}{l@{\,\Rightarrow\,}l} A^1 = \left[\begin{array}{ccc | c} * & & & \\ * & * & & \\ * & & * & * \\ \hline * & * & * & * \end{array}\right] & A^2 = \left[\begin{array}{cc |cc} * & & & \\ * & * & & * \\ \hline * & & * & \\ * & * & * & * \end{array}\right] = A^3. \end{array}

$

The final rearrangement ($LaTeX: A^3$) has one spike.