MATLAB Answers

Permuting elements in an symmetrical matrix with restricted outcomes

34 views (last 30 days)
Maxwell Day
Maxwell Day on 14 Jan 2020
Commented: Adam Danz on 27 Feb 2020
I would like to derive all possible permutations of a matrix A = [0 2 0 1; 2 0 1 0; 0 1 0 1; 1 0 1 0] by permuting the positions of elements with the following restrictions:
[1] Diagonal elements can only be "0" or "2" (i.e. the permuated matrix A = [0 2 0 1; 0 1 2 0; 0 1 0 1; 1 0 1 0] would NOT be valid as "1" is a diagonal element
[2] The positions and values (i.e. 0, 1 or 2) of elements (not including diagonal elements) must be "mirrored" across the diagonal (i.e. the permuted matrix A = [0 2 0 1; 2 0 1 0; 1 0 0 1; 0 1 1 0] is NOT valid
Can someone help me with a code for this ?
Thus far I have been generating all possible permutation matrices for this 4 x 4 matrix (4!) and iteratively multiplying the matrix A by each permutation matrix but I am not sure if I can derive all possible permutations using this method (not to mention it being extremely time consuming as eventually I will be permuting many more, larger matrices)

Accepted Answer

Adam Danz
Adam Danz on 14 Jan 2020
Edited: Adam Danz on 16 Jan 2020
Since the permuted matrices are all symmetric, you really only need to permute the lower (or upper) triangle of the matrix, excluding the diagonal, and then reflect the values. Since your matrix is 4x4, there are 6 values in the lower triangle excluding the diagonal. That results in 6! permutations (720). But there are also 16 variations of the diagonal (4 choices from 2 values [0,2] with replacement; if that's what you're looking for since it was unlcear).
so in total, there are 720 * 16 = 11520 permutations of matrix A.
Some of the lines below could be combined but I chose to keep them separated to increase readability. There may be additional shortcuts that I didn't think of but the code completes in less than 150 milliseconds.
The code requires Jos' permn() function from the file exchange in order to compute the permutations of diagonal elements with replacement.
See the inline comments for detials.
% Input matrix
A = [0 2 0 1; 2 0 1 0; 0 1 0 1; 1 0 1 0];
% Get index of lower triangle values (below diagonal)
trilMat = tril(reshape(1:numel(A),size(A)),-1);
trilIdx = trilMat(trilMat>0);
% List all permutation of lower triangle indices
trilPerms = perms(trilIdx);
% List accepted diagonal values
diagPermitted = [0,2];
% List all permutation of diagonal values (with replacement)
% https://www.mathworks.com/matlabcentral/fileexchange/7147-permn
diagPerms = permn(diagPermitted,numel(diag(trilMat)));
% Loop through all lower-triangle-permutation and diagonal-permutations
diagMask = logical(eye(size(A)));
nPerms = size(trilPerms,1) * size(diagPerms,1); % total number of permutations
A_PERM = nan([size(A),nPerms]); % all permutations
for i = 1:size(trilPerms,1)
for j = 1:size(diagPerms,1)
c = (i-1)*size(diagPerms,1)+j;
base = zeros(size(A));
base(trilIdx) = A(trilPerms(i,:)); % permute lower triangle
base = base + tril(base,-1).'; % reflect lower triangle
base(diagMask) = diagPerms(j,:); % permute diagonal
if ~issymmetric(base)
% Sanity check: matrix is symmetric
error('Matrix not symmetic. i = %d j = %d',i,j)
end
A_PERM(:,:,c) = base; % store matrix
end
end
A_PERM is a [4 x 4 x 11520] array containing all 11520 permutations of the 4x4 matrix A.
[addendum]
"I would like to restrict the resultant, permuted matrices to also have rows and columns that sum to 3,3,2,2, more specifically two of the rows (or columns) in the "accepted" permuted matrices must sum to 2 and the other two must sum to 3, the order of the row (column) sums does not matter."
It would be complicated to work that restriction into the permutation rules. Instead, keep all of the code above, produce all permutations, and then eliminate any that do no follow that rule. That just requires adding the the following two lines below at the end of the code above.
goodRows = ismember(squeeze(sort(sum(A_PERM,2))).',[2 2 3 3],'rows');
A_PERM(:,:,~goodRows) = [];
To see the sum of each row,
sum(A_PERM,2)
[addendum II]
Extract the unique matrices (see the discussion below for details).
% Extract unique matrices.
% Each matrix is collapsed to a row vector and all
% row vector are combined into a mega-matrix that
% contains all of the A_PERM data. Then we'll
% identify unique rows numbers.
megaMat = squeeze(reshape(A_PERM,1,prod(size(A_PERM,[1,2])),size(A_PERM,3))).';
[~, unqRowIdx] = unique(megaMat,'rows');
A_PERM_UNQ = A_PERM(:,:,unqRowIdx);
  18 Comments
Adam Danz
Adam Danz on 16 Jan 2020
No error when I try it. A_PERM_UNQ is a 4x4x36 array it produces the figure.

Sign in to comment.

More Answers (2)

Maxwell Day
Maxwell Day on 26 Jan 2020
Hey @Adam Danz
The code is working great so far thanks again. I have another interesting problem if you are interested.
After executing the code and generating a set of unique (valid) permuted matrices (A1, A2...An) I would like to determine which of these matrices correspond to non-isomorphic (topologically distinct) graphs (G1,G2...Gn).
Two graphs G1 (from matrix A1) and G2 (from matrix A2) are isomorphic only if there exists a permutation matrix P such that:
(P)(A1)(P^-1) = A2
Here P^-1 is simple the inverted permutation matrix P.
Doing this for certain matrices is not possible as they will have a determinant of 0 and therfore not be invertible.
Is there a way to determine which matrices in a set generate isomorphic graphs by getting MatLab to determine if a permutation matrix P exists that satisfies the above equation? If this permutation matrix P exists we can then say G1 is isomorphic with G2 and eliminate either A1 or A2 (as they are effectively the same), if P did not exist we would keep both A1 and A2.
Such a code would have to apply the above equation to each unique combination of matrices in set. I.e. if we have 12 matrices there would be 66 unique combinations of two matrices as order doesnt matter and there is no reason to pair a matrix with itself.
A1-2,-3,-4,-5,-6,-7,-8,-9,-10,-11,-12
A2-3,-4,-5,-6,-7,-8,-9,-10,-11,-12
A3-4,-5,-6,-7,-8,-9,-10,-11,-12
etc.
Depending on the size of the matrix, this may be a very large and intensive calculation, let me know if this is possible, thanks.
-Max
  3 Comments
Adam Danz
Adam Danz on 26 Jan 2020
A_PERM_UNQ came from my answer - it contains the the permutations of A.
I don't know what A1 is supposed to be.

Sign in to comment.


Maxwell Day
Maxwell Day on 1 Feb 2020
Edited: Stephen Cobeldick on 1 Feb 2020
Hello @Adam Danz
I seem to be running into error related to exceeding the maximum array size with a 6 x 6 matrix, I was under the impression the code we had developed could handle matrices of this size.
I tried to permute the following matrix using the following code and recieved this error:
>>
% Input matrix
A = [0 1 1 1 1 0; 1 0 1 1 1 0; 1 1 0 0 0 0; 1 1 0 0 0 1; 1 1 0 0 0 0; 0 0 0 1 0 0];
% Get index of lower triangle values (below diagonal)
trilMat = tril(reshape(1:numel(A),size(A)),-1);
trilIdx = trilMat(trilMat>0);
% List all permutation of lower triangle indices
trilPerms = perms(trilIdx);
% List accepted diagonal values
diagPermitted = [0,2];
% List all permutation of diagonal values (with replacement)
% https://www.mathworks.com/matlabcentral/fileexchange/7147-permn
diagPerms = permn(diagPermitted,numel(diag(trilMat)));
% Loop through all lower-triangle-permutation and diagonal-permutations
diagMask = logical(eye(size(A)));
upperMask = triu(true(size(A)),1);
lowerMask = tril(true(size(A)),-1);
nPerms = size(trilPerms,1) * size(diagPerms,1); % total number of permutations
A_PERM = nan([size(A),nPerms]); % all permutations
for i = 1:size(trilPerms,1)
for j = 1:size(diagPerms,1)
c = (i-1)*size(diagPerms,1)+j;
base = zeros(size(A));
base(trilIdx) = A(trilPerms(i,:)); % permute lower triangle
base = base + tril(base,-1).'; % reflect lower triangle
base(diagMask) = diagPerms(j,:); % permute diagonal (not changed, but comes after reflection)
if ~issymmetric(base) % #UPDATED
% Sanity check: matrix is symmetric
error('Matrix not symmetic. i = %d j = %d',i,j) % #UPDATED
end
A_PERM(:,:,c) = base; % store matrix
end
end
goodRows = ismember(squeeze(sort(sum(A_PERM,2))).',[1 3 3 3 3 3],'rows');
A_PERM(:,:,~goodRows) = []
Error using zeros
Requested 479001600x12 (42.8GB) array exceeds maximum array size preference. Creation of arrays
greater than this limit may take a long time and cause MATLAB to become unresponsive. See array size
limit or preference panel for more information.
Error in perms>permsr (line 49)
P = zeros(nn*m,nn);
Error in perms (line 31)
P = permsr(n);
Is there anyway around this? let me know, Thanks.
  10 Comments
Adam Danz
Adam Danz on 27 Feb 2020
goodRows = ismember(squeeze(sort(sum(A_PERM,2))).',[2 2 3 3],'rows');
goodRows (a column vector) is all False values. In other words, the [2 2 3 3] vector is not found anywhere in the permuration sums.
squeeze(sort(sum(A_PERM,2))).'

Sign in to comment.

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!