# Backward triangularization

### From Glossary

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 *:

The column counts are . We thus put column at the rear, assigned to pivot on row , and consider the remaining submatrix:

The remaining column counts (for ) are , so column is placed at the (new) rear, pivoting on row :

The remaining column counts are , so we reach the final rearrangement, which is triangular:

Example 2: Column counts are shown below the matrix.

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.

The final rearrangement () has one spike.