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