StronglyConnectedBlocks - Maple Help

LinearAlgebra

 StronglyConnectedBlocks
 compute the strongly connected blocks of a square Matrix

 Calling Sequence StronglyConnectedBlocks(M, opts)

Parameters

 M - n x n square matrix with some sparsity opts - options controlling the output

Description

 • The StronglyConnectedBlocks(M) function computes and returns a list containing the nonzero strongly connected blocks contained in the input Matrix M, i.e. [M_1, ..., M_r]. The strongly connected blocks are square sub-matrices of the input Matrix after a sequence of row and column exchanges have been performed to minimize the size of the blocks. Note that these sub-matrices do not contain all the entries present in the input Matrix, but rather only those needed to compute the determinant, characteristic polynomial, or eigenvalues of the Matrix. In addition, any zero blocks are not output.
 • In order for StronglyConnectedBlocks to provide a benefit, the input Matrix should have some sparsity. If the input Matrix is fully dense, the command outputs a list containing only the input Matrix (without sparsity no break-down into blocks is possible).
 • For an input n x n Matrix M, if we let m = sum( Row/ColumnDimension(M_i), i=1..r ) for the output Matrix list [M_1, ..., M_r], then m <= n, where the inequality is needed for any zero blocks contained in the matrix.
 • The output blocks satisfy the following:

Determinant(M) is zero if m < n and product(Determinant(M_i), i=1..r) otherwise.

CharacteristicPolynomial(M,x) = x^(n-m) * product( CharacteristicPolynomial(M_i,x), i=1..r)

 • The option returnsingular is true by default, but when set to false, the block matrices are not formed when the input Matrix is singular (i.e. has zero blocks). This is useful for efficient computation of a determinant (as a zero block means the determinant is zero, so there is no sense in forming the block matrices).
 • The option outputform is matrixlist by default, which returns a list of the strongly connected blocks in Matrix form as described above. If outputform is set to rowlist instead, it provides a list of the rows (columns) of the Matrix for each block.

Examples

 > $A≔\mathrm{Matrix}\left(\left[\left[a,b,c,d,e\right],\left[f,g,h,i,j\right],\left[0,0,0,0,k\right],\left[0,0,0,v,w\right],\left[0,0,0,x,y\right]\right]\right):$
 > $\mathrm{LinearAlgebra}:-\mathrm{StronglyConnectedBlocks}\left(A\right)$
 $\left[\left[\begin{array}{cc}{y}& {x}\\ {w}& {v}\end{array}\right]{,}\left[\begin{array}{cc}{a}& {b}\\ {f}& {g}\end{array}\right]\right]$ (1)
 > $\mathrm{LinearAlgebra}:-\mathrm{StronglyConnectedBlocks}\left(A,\mathrm{returnsingular}=\mathrm{false}\right)$
 ${0}$ (2)
 > $\mathrm{LinearAlgebra}:-\mathrm{StronglyConnectedBlocks}\left(A,\mathrm{outputform}=\mathrm{rowlist}\right)$
 $\left[\left[{5}{,}{4}\right]{,}\left[{3}\right]{,}\left[{1}{,}{2}\right]\right]$ (3)