Symmetric permutations to block triangular form
We assume that a row permutation Pi has been computed so that Pi A has entries on every position on its diagonal (unless A is symbolically singular), and we now wish to find a symmetric permutation that will put the matrix into block lower triangular form. That is, we wish to find a permutation matrix Q such that QT (PiA)Q has the form
where each Bn cannot itself be symmetrically permuted to block triangular form. Then, with P = QTP1, we will have achieved the desired permutation (6.1.2). We will show (Section 6.6) that symmetric permutations are all that is required once the transversal has been found. While any row and column singletons will usually have been removed, we do not rely on this.
It is convenient to describe algorithms for this process with the help of the digraphs (directed graphs) associated with the matrices (see Section 1.2). With only symmetric permutations in use, the diagonal entries play no role so we have no need for self-loops associated with diagonal entries. Applying a symmetric permutation to the matrix causes no change in the associated digraph except for the relabelling of its nodes. Thus, we need only consider relabelling the nodes of the digraph, which we find easier to explain than permuting the rows and columns of the matrix.
If we cannot find a closed path (cycle), as defined in Chapter 1, through all the nodes of the digraph, then we must be able to divide the digraph into two parts such that there is no path from the first part to the second. Renumbering the first group of nodes 1, 2,..., k and the second group k + 1,..., n will produce a
Fig. 6.5.1. A 5 x 5 matrix and its digraph.
corresponding (permuted) matrix in block lower triangular form. An example is shown in Figure 6.5.1, where there is no connection from nodes (1,2) to nodes (3, 4, 5). The same process may now be applied to each resulting block until no further subdivision is possible. The sets of nodes corresponding to the resulting diagonal blocks are called strong components. For each, there is a closed path passing through all its nodes but no closed path includes these and other nodes. The digraph of Figure 6.5.1 contains just two strong components, which correspond to the two irreducible diagonal blocks.
A triangular matrix may be regarded as the limiting case of the block triangular form in the case when every diagonal block has size 1 x 1. Conversely, the block triangular form may be regarded as a generalization of the triangular form with strong components in the digraph corresponding to generalized nodes. This observation forms the basis for the algorithms in the next three sections.