Determine if a matrix can be be given a block diagonal form using rows and columns permutations

Question

Is there a way to determine if by permutation of rows and columns a matrix can be transformed into a block-diagonal matrix (EDIT: with more than one block)? For example the following matrix

\begin{bmatrix} 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{bmatrix} EDIT: set to 0 element in 2nd row that was =2.

By permuting first row with last row and first column with last column can be transformed into the following block-diagonal matrix. \begin{bmatrix} 0 &1 &0 &0 &0 \\ 3 &0 &0 &0 &0 \\ 0 &0 &0 &1 &5\\ 0 &0 &2 &0 &0 \\ 0 &0 &7 &0 &0 \end{bmatrix} Is there an algorithm to find out if it is possible and do it, or to determine the permutation matrix?

My problem is about representing points scored by players against each other in. I need to determine the relative strength of players by comparing their scores. Imagine the matrix is the score of a player against another player. Each row is a player, and each column is a player. The diagonal is empty, or zero. If nobody in a group of player has played against anybody in the other group of players, then I cannot rank one group against the other group, because I do not know their relative strength. So I'm trying to eventually decompose the matrix into several if they exist. In the example above they would be the two following ones \begin{bmatrix} 0 &1 &0 &0 &0 \\ 3 &0 &0 &0 &0 \\ 0 &0 &0 &0 &0\\ 0 &0 &0 &0 &0 \\ 0 &0 &0 &0 &0\ \end{bmatrix} \begin{bmatrix} 0 &0 &0 &0 &0 \\ 0 &0 &0 &0 &0 \\ 0 &0 &0 &1 &5\\ 0 &0 &2 &0 &0 \\ 0 &0 &7 &0 &0\end{bmatrix}

Answer 1

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

Answer 2

The Dulmage-Mendelsohn decomposition (dmperm in MATLAB) can be used to do this for symmetric matrices (or just turn your non-symmetric matrix into a matrix of 0's and 1's with 1's replacing all non-zero entries in the original matrix.)