Can one help me to find Matlab coding to convert the given matrix to a symmetric matrix by rearranging rows?

I would like to covert a mtrix of dimension 12 x12 (Higher dimension )to symmetric matrix by rearranging rows of the marix. As I have matrices with big oder rewriting in symmetrical oder is diffucult.

[Paul]

Can you provide a small example matrix that illustrates what you're starting with and what the result should be?

Also, are there any known properties of the starting matrix thta can be exploited?

[Dr.SIMON RAJ F]

Thank you for showing interest to answer my question. I am looking for matlab program which can take a square matrix (say) A from the user and return the matrix B in which the rows of the matrix A are rearranged so that B is symmetrical matrix.

For Example if A= [ 3 9 0; 0 2 3;2 0 9] then matlab must return B=[0 2 3;2 0 9;3 9 0] If the dimension of matrix is small , it is easy problem, but if the dimension of the matrix A is more than 20 and above then we need a Matlab coding.

[John D'Errico]

I looked at your question the other day. But do you know a solution exists, such that a strict permutation of only the rows will produce a symmetric matrix? Or are you looking for a solutino that will take any matrix, and then produce something as symmetric as possible? And in that case, how would you define the metric that will denote an approximate solution?

[Dr.SIMON RAJ F]

Thank you Sir. This problem has no solution if A is not SYMMETRICABLE by REARRANGING rows or columns of A. I am not looking for an approximate answer. Kindly see the attachment. I came to arrive this problem when I try to draw a graph (Graph theory) using Matlab. But the matlab gave me error message saing that Adjacensy matrix is not symmetric . So I required the solution for this problem. Kindly help if any other matlab codding available to draw big graphs(Adjacency martix with order more than 10x10).

First step is , We must ensure that the every elements in A must present twice in the matrix A . If not, then there no way A can be symmetricable (if there is a word in english)

Answer 1

[Torsten]

Use intlinprog or bintprog to solve

min: sum_{i=1}^{n} sum_{j=1}^{n} (e_ij+) + (e_ij-)

under the constraints

E+ - E- - (P*A - (P*A)') = 0
sum_{i=1}^{n} p_ij = 1 for all 1 <= j <= n
sum_{j=1}^{n} p_ij = 1 for all 1 <= i <= n
E+, E- >= 0
p_ij in {0,1} for all i and j

If A is "symmetrizable", then the objective will give minimum value 0 and B is equal to P*A.

P is a permutation matrix that "reorders" the rows of A.

[Dr.SIMON RAJ F]

Dear Torsten ,

can you show with one example with output B matrix?

[Torsten]

This is a quick implementation for your test case with A=[ 3 9 0; 0 2 3;2 0 9].

f = [ones(9,1);ones(9,1);zeros(9,1)];
intcon = 19:27;
Aineq = [];
bineq = [];
Aeq= [1 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0; ...
      0 1 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 -9 -2 0 3 0 2 0 0 0; ...
      0 0 1 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 -3 -9 0 0 0 3 0 2; ...
      0 0 0 1 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 9 2 0 -3 0 -2 0 0 0; ...
      0 0 0 0 1 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0; ...
      0 0 0 0 0 1 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 -3 -9 9 2 0; ...
      0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 -1 0 0 0 3 9 0 0 0 -3 0 -2; ...
      0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 3 9 -9 -2 0; ...
      0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0; ...
      0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0  1 1 1 0 0 0 0 0 0; ...
      0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0  0 0 0 1 1 1 0 0 0; ...
      0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0  0 0 0 0 0 0 1 1 1; ...
      0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0  1 0 0 1 0 0 1 0 0; ...
      0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0  0 1 0 0 1 0 0 1 0; ...
      0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0  0 0 1 0 0 1 0 0 1];
beq = [zeros(9,1);ones(6,1)];  
lb = zeros(27,1);
ub = [Inf(18,1);ones(9,1)];
[xopt,fopt,status,output] = intlinprog(f,intcon,Aineq,bineq,Aeq,beq,lb,ub);
for i=1:3
    for j=1:3
        P(i,j) = xopt(18+(i-1)*3+j);
    end
end
A=[ 3 9 0; 0 2 3;2 0 9];
B = P*A

But if your matrices A are not bigger than 12x12 in size, you can check the 12 ! = 479 001 600

permutations of the rows and sort out the (or a ?) row-reordered matrix that is symmetric.

[Dr.SIMON RAJ F]

No, it is not working , as the dimension of P is not suitable for multiplying with 12x12 matrices. Kindly see the attachment.

[Torsten]

The A-matrix you gave for testing is

A=[ 3 9 0; 0 2 3;2 0 9];

not the A you used:

A = [0 2 0 0 0 6 0 0 9 0 0 0;...

0 2 0 4 0 0 7 0 0 0 0 0;...

1 0 3 0 0 0 0 8 0 0 0 0;...

0 0 3 0 5 0 0 0 0 0 0 12;...

0 0 0 4 0 6 0 0 0 0 11 0;...

1 0 0 0 5 0 0 0 0 10 0 0;...

0 0 3 0 0 0 0 8 0 0 0 12;...

0 2 0 0 0 0 7 0 9 0 0 0;...

1 0 0 0 0 0 0 8 0 10 0 0;...

0 0 0 0 0 6 0 0 9 0 11 0;...

% two lines missing here]

Of course, you must change the program if A changes.

[Torsten]

Here is a version that should work for general matrices A:

  % Prescribe matrix A
  A=[ 3 9 0; 0 2 3;2 0 9];
  %Usually, nothing needs to be changed after this line
  n = size(A,1);
  f = [ones(n^2,1);ones(n^2,1);zeros(n^2,1)];
  intcon = 2*n^2+1:3*n^2;
  Aeq11 = [eye(n^2), -eye(n^2)];
  Aeq12 = zeros(n^2);
  P = sym('P', [n n]);
  res = P*A-(P*A).';
  for i=1:n
    for j=1:n
      resij = res(i,j);
      for k=1:n
        for l=1:n
          resij_kl = diff(resij,P(k,l));
          Aeq12((i-1)*n+j,(k-1)*n+l) = double(resij_kl);
        end
      end
    end
  end
  Aeq12 = -Aeq12;
  Aeq21 = zeros(2*n,2*n^2);
  Aeq22 = [];
  for i=1:n
    Aeq22 = [Aeq22;[zeros(1,(i-1)*n),ones(1,n),zeros(1,(n-i)*n)]];   
  end
  Aeq22 = [Aeq22;repmat(eye(n),1,n)];
  Aeq = [Aeq11,Aeq12;Aeq21,Aeq22]; 
  beq = [zeros(n^2,1);ones(2*n,1)];
  Aineq = [];
  bineq = [];
  lb = zeros(3*n^2,1);
  ub = [Inf(2*n^2,1);ones(n^2,1)]; 
  [xopt,fopt,status,output] = intlinprog(f,intcon,Aineq,bineq,Aeq,beq,lb,ub);
  P = reshape(xopt(2*n^2+1:3*n^2),n,n)';  %assumes xopt is a column vector
  B = P*A;
  disp(B)

[Dr.SIMON RAJ F]

It does not work , Kindly see the attachment.

[Torsten]

Could you supply the complete matrix A in plain ascii here ?

I can't identify it completely from your included pdf document.

And this code should run faster for bigger matrices A:

 % Prescribe matrix A
  A=[ 3 9 0; 0 2 3;2 0 9];
  %Usually, nothing needs to be changed after this line
  n = size(A,1);
  f = [ones(n^2,1);ones(n^2,1);zeros(n^2,1)];
  intcon = 2*n^2+1:3*n^2;
  Aeq11 = [eye(n^2), -eye(n^2)];
  Aeq12 = zeros(n^2);
  P = zeros(n,n);
  for i=1:n
    for j=1:n
      P(i,j) = 1;
      res_ij = P*A-(P*A).';
      for k=1:n
        for l=1:n
          Aeq12((i-1)*n+j,(k-1)*n+l) = res_ij(k,l);          
        end
      end
      P(i,j) = 0;
    end
  end
  Aeq12 = -Aeq12;
  Aeq12 = Aeq12.';
  %Aeq12 = zeros(n^2); 
  %P = sym('P', [n n]);
  %res = P*A-(P*A).';
  %for i=1:n
  %  for j=1:n
  %    resij = res(i,j);
  %    for k=1:n
  %      for l=1:n
  %       resij_kl = diff(resij,P(k,l));
  %        Aeq12((i-1)*n+j,(k-1)*n+l) = double(resij_kl);
  %      end
  %    end
  %  end
  %end
  %Aeq12 = -Aeq12
  Aeq21 = zeros(2*n,2*n^2);
  Aeq22 = [];
  for i=1:n
    Aeq22 = [Aeq22;[zeros(1,(i-1)*n),ones(1,n),zeros(1,(n-i)*n)]];   
  end
  Aeq22 = [Aeq22;repmat(eye(n),1,n)];
  Aeq = [Aeq11,Aeq12;Aeq21,Aeq22] 
  beq = [zeros(n^2,1);ones(2*n,1)];
  Aineq = [];
  bineq = [];
  lb = zeros(3*n^2,1);
  ub = [Inf(2*n^2,1);ones(n^2,1)]; 
  [xopt,fopt,status,output] = intlinprog(f,intcon,Aineq,bineq,Aeq,beq,lb,ub);
  P = reshape(xopt(2*n^2+1:3*n^2),n,n)';
  B = P*A;
  disp(B)

[Dr.SIMON RAJ F]

Kindly see the attachment. for 12by12 matrix.

[Torsten]

If A were symmetrizable, you would get fopt = 0 as output from intlinprog.

In your case, fopt = 104. Thus A is not symmetrizable by changing rows only.

[Dr.SIMON RAJ F]

Thank you

[Torsten]

Observing the three 12's in the last row of the matrix, it should be obvious that it cannot be symmetrizable.

[Dr.SIMON RAJ F]

Thank you , can you please give one example of random matrix with order 20 by 20 , which can be made symmetric using your coding?

[Torsten]

A = [13    0    9   -5    4    1   11  -18   16    2   -9  -11   19   -1   -4   -2  -15    4    3    1;
    -2   -4  -12   -2   -2   -3   -6    0   -1    2  -13  -10    6    1   14    0    5   -7   13   -3;
    -1   13   10   17   -4   10   -2    3    0    0  -12   10    1    8    6   -1   -3   -3    10    7;
    -10   -7   15    5   -5    7   -3    4   -4   13   -5  -18   -5  -10    5    4   17  -16    -3    2;
    4    6   -8    0    3   18    9   19  -12    4  -13   -4  -16    5   18    0   15   -5     1   10;
    3   -3    8   14    5  -16    6    1    0   -2    7   13   10   -7   -2   -6    3    2     7   14;
    16   -2    0   -1   14   -3   -6   13   -1  -13   15  -11    4   -4   -5  -13  -13  -10     -1    3;
    -1   -2    6  -16    3    3    4   -5   -2   -2   12   -7    0    3    5    7   -8    5    17   14;
    -6   -6    2    4  -11    5   -8   11  -11    2   -7    1    9   -8  -11    1    2   -3    -2    6;
    -4    1   -1    3  -13  -10   -8   -1   10  -11  -12   10    5   18   -4    8   12  -10     8   -7;
    -5   14    2    5   -5   -1  -11   -4   -8    1   -7  -17   18   -4  -12  -19    5    5     6   -2;
    15  -13   14   12   13    3   -7   -9   -1   16   -6   11  -13  -12   -7   -8    3   -5   -12    7;
    14   -2   13    3    8    6  -11    4   -8  -14   13   17    3  -13   -5   11  -11   -5     -4    5;
    -11  -10    2   -7   17   -5    1  -11    0    5   11   10   -4   10  -17    6   10  -18     10   13;
    -1   -1    6   -2   -8   -2  -11   16  -14   -6   -1    0  -12   10   -8    3   -1   -4      0    0;
    -13    2   11   -2  -14    6    2    2   -6   14   16    5    4  -11    1   20   11   13     0   -2;
    -13    0  -11    7   11    2    1   -2    3   20   -8    6    0    8  -19    8    7    4    -1   -6;
    -3   -3    0    3    6  -18    5    1   -2    6    3   -5   18  -10   -1    2   -4    7     10  -16;   
    -13    5   -2   -8  -11   -4    2  -15   -1   11    3   10   15   12    5    7    0   17    -3    3;
    0  -12   -4    6   13    0    2    9    6   11   14    2   -8   -1    2  -11   -2   15    10    8];

To produce symmetrizable random matrices A of arbitrary size (here: n=20), you can use

n = 20;
C = randi([-10 10],[n n]);
B = (C+C.');
Per = eye(n);
Per = Per(randperm(n),:);
A = Per*B;