Determine if Matrix can be permutated into Block Diagonal Matrix

Problem

Given an $n\times n$ matrix $A=(a_{ij})$, determine if it is possible to find a permutation matrix $P=(p_{ij})$ and square matrices $B$ and $C$ such that $$ PAP^{\intercal}=\begin{pmatrix}B & 0\\ 0 & C \end{pmatrix}. $$

Note: By grouping blocks, any matrix with three or more diagonal blocks can also be considered as a matrix with two diagonal blocks. For example,

$$ \begin{pmatrix}B\\ & C\\ & & D \end{pmatrix}=\begin{pmatrix}B\\ & \begin{pmatrix}C\\ & D \end{pmatrix} \end{pmatrix} $$

Solution

Let $G=(V,E)$ denote the undirected adjacency graph of $A$. That is, $V$ and $E$ are defined by $$ V=\{1,\ldots,n\}\qquad\text{and}\qquad E=\left\{ (i,j)\in V\times V\colon a_{ij}\neq0\text{ or }a_{ji}\neq0\right\}. $$ Now, our original problem is equivalent to determining whether $G$ is a graph with two or more disjoint components.

This is accomplished with a breadth-first search (or depth-first search) started at an arbitrary vertex, call it $v_{1}$. Let $V^{\prime}=\{v_{1},\ldots,v_{k}\}$ be the set of vertices visited by the search. Then, the answer to our original problem is in the affirmitive if and only if $V^{\prime}$ is a proper subset of $V$.

Example

Let's apply the algorithm to the matrix $$ A=\begin{pmatrix}0 & 0 & 7 & 0 & 0\\ 0 & 0 & 0 & 0 & 3\\ 5 & 0 & 0 & 1 & 0\\ 0 & 0 & 2 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 \end{pmatrix}. $$

Let's run the search algorithm:

• Pick $v_{1}=1$ corresponding to the first row.
• The only nonzero entry in this row is $a_{v_{1}3} = 7$ so we pick $v_{2}=3$ as the next row to visit.
• The only nonzero entries in this row are $a_{v_{2}1} = 5$ and $a_{v_{2}4} = 1$. We have already visited the first row so we pick $v_{3}=4$ as the next row to visit.
• The only nonzero entry in this row is $a_{v_{3} 3} = 2$. We have already visited the third row and hence the search terminates.

The final vertex set is $V^{\prime}=\{v_1,v_2,v_3\}=\{1,3,4\}$. Next, make any permutation matrix that satisfies $p_{1v_{1}}=p_{2v_{2}}=p_{3v_{3}}=1$. For example, we could take $$ P=\begin{pmatrix}1 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 0\\ 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 \end{pmatrix}. $$ You can check that $PAP^{\intercal}$ has two diagonal blocks: $$ PAP^{\intercal}=\begin{pmatrix}0 & 7 & 0 & 0 & 0\\ 5 & 0 & 1 & 0 & 0\\ 0 & 2 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 3\\ 0 & 0 & 0 & 1 & 0 \end{pmatrix}. $$

MATLAB implementation

The code below can be used to make the matrix P described above from an input matrix A. Just call perm_mat_to_make_block_diag(A).

Note: I don't have access to MATLAB and GNU Octave has not implemented the breadth-first search function bfsearch, so I was unable to test the code below. If someone could test it for me, that would be great.

function P = perm_mat_to_make_block_diag(A)
    % Make the undirected adjacency graph for A.
    nonzero = A != 0;
    adjacency = nonzero + nonzero';
    G = graph(A);

    % Perform breadth-first search.
    v_1 = 1;
    V_prime = bfsearch(G, v_1);
    n = length(A);
    if length(V_prime) == n
        error('Input is not permutation-similar to a block-diagonal matrix.');
    end

    % Make the permutation matrix.
    i = (1:n)';
    V_prime_complement = setdiff(i, V_prime);
    j = [V_prime; V_prime_complement];
    P = sparse(i, j, ones(n, 1), n, n);
end