5
$\begingroup$

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}

$\endgroup$
5
  • $\begingroup$ Any matrix $A$ is already trivially block-diagonal in the sense that it can be written $[A]$. You might need to constrain your question further. $\endgroup$
    – parsiad
    Dec 2 '18 at 22:30
  • $\begingroup$ @parsiad, I thought the example made it clear that I'm talking about more than one block. Otherwise suggest how I should clarify my question please. $\endgroup$
    – gciriani
    Dec 2 '18 at 22:47
  • $\begingroup$ You could specify a minimum number of blocks or an exact number of blocks to make the problem nontrivial. $\endgroup$
    – parsiad
    Dec 2 '18 at 23:54
  • 1
    $\begingroup$ @parsiad, I added in the first paragraph "more than one block". I hope that helps. $\endgroup$
    – gciriani
    Dec 3 '18 at 0:38
  • $\begingroup$ BTW, your first example is incorrect (it is actually not permutation similar to a matrix with two block diagonals). I think you dropped one of the nonzero elements (namely, the number 2 appears twice before you permute and only once afterwards) $\endgroup$
    – parsiad
    Dec 3 '18 at 1:29
6
$\begingroup$

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
$\endgroup$
6
  • $\begingroup$ Is there an easy way to implement this in Matlab or Octave? $\endgroup$
    – gciriani
    Dec 3 '18 at 2:54
  • $\begingroup$ do you know how to extract the blocks? $\endgroup$
    – gciriani
    Dec 3 '18 at 16:02
  • $\begingroup$ To your first question, I just added a MATLAB implementation. To your second question, the two blocks are given by the indices in $V^\prime$ and $(V^\prime)^{\complement} \equiv V \setminus V^\prime$ (these are called V_prime and V_prime_complement in the MATLAB code). $\endgroup$
    – parsiad
    Dec 4 '18 at 1:44
  • $\begingroup$ Unfortunately I do not have Matlab, and use only Octave, so I cannot test your code either. However, I found an easy implementation, inspired by Calvin-Lin @MISC {277075, TITLE = {Easiest way to determine all disconnected sets from a graph?}, AUTHOR = {Calvin Lin (math.stackexchange.com/users/54563/calvin-lin)}, HOWPUBLISHED = {Mathematics Stack Exchange}, NOTE = {URL:math.stackexchange.com/q/277075 (version: 2013-01-13)}, EPRINT = {math.stackexchange.com/q/277075}, URL = {math.stackexchange.com/q/277075} } $\endgroup$
    – gciriani
    Dec 4 '18 at 19:34
  • $\begingroup$ ...continued. If A is the connection matrix, then C=((A>0) + I)^n where n is the size of the matrix, transforms it in a matrix with all possible paths of length n, which are identical for connected nodes, and different for each disconnected graph. Then with the command [Y,i,j]=Unique(C, 'rows') I obtain the different connection blocks and their respective positions. $\endgroup$
    – gciriani
    Dec 4 '18 at 19:49
1
$\begingroup$

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.)

$\endgroup$
5
  • $\begingroup$ I tried dmperm, but it doesn't seem to perform what I'm trying to determine. According to Octave's help, dmperm is used for block triangular form, which is not what I'm trying to accomplish. What I need is to determine the disjoint components. $\endgroup$
    – gciriani
    Dec 3 '18 at 13:38
  • $\begingroup$ If your original matrix is symmetric, then p=dmperm(A), B=A(p,p) will put the matrix into block upper triangular form, but since the matrix is symmetric, that will also be block diagonal form. Try it. $\endgroup$ Dec 3 '18 at 15:02
  • $\begingroup$ one of the elements of p turns out to be 0, and dmperm gives an error; my example [0 0 5 1 0; 0 0 0 0 3; 7 0 0 0 0; 2 0 0 0 0; 0 1 0 0 0] $\endgroup$
    – gciriani
    Dec 3 '18 at 16:42
  • $\begingroup$ Your example matrix isn't symmetric. $\endgroup$ Dec 3 '18 at 16:47
  • $\begingroup$ Even with a symmetric matrix [0 0 1 1 0; 0 0 0 0 1; 1 0 0 0 0; 1 0 0 0 0; 0 1 0 0 0], dmperm gives [3, 5, 1, 0, 2] as a result. $\endgroup$
    – gciriani
    Dec 4 '18 at 14:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.