## On the block triangular form of symmetric matrices

### Iain S. Duff and Bora Uçar

Abstract.
We present some observations on the block triangular form (btf) of
structurally symmetric, square, sparse matrices. If
the matrix is structurally rank deficient, its canonical
btf has at least one underdetermined and one overdetermined block. We
prove that these blocks are transposes of each other. We further prove
that the square block of the canonical btf, if present, has a special
fine structure. These findings help us recover symmetry around the
anti-diagonal in the block triangular matrix. The uncovered symmetry helps us
to permute the matrix in a special form which is symmetric along the main diagonal while
exhibiting the blocks of the original btf.
As the square block of the
canonical btf has full structural rank, the observation relating to the square
block applies to structurally nonsingular, square symmetric matrices as well.

Key words. sparse matrices, block triangular form, Dulmage-Mendelsohn decomposition, maximum cardinality matchings