Robert Israel

6577 Reputation

21 Badges

18 years, 215 days
University of British Columbia
Associate Professor Emeritus
North York, Ontario, Canada

MaplePrimes Activity


These are replies submitted by Robert Israel

Note that the relative sizes of characters are determined by what font is being used, and that is under the user's control.  See "Styles..." under the Format menu.  I suspect that to get + and - the same size, you will need to use a fixed-width font.

As noted there, the Q_B Q_A^T you find (e.g. using IsSimilar) might not be a permutation matrix, even if one exists.  For example:

> with(LinearAlgebra):
    n:= 7:
    A:= RandomMatrix(n,n,generator=0..1);

                     [1    0    0    1    1    0    1]
                     [                               ]
                     [0    0    0    0    0    0    1]
                     [                               ]
                     [1    0    1    0    1    1    0]
                     [                               ]
                A := [0    1    1    0    0    1    1]
                     [                               ]
                     [1    1    0    1    1    1    0]
                     [                               ]
                     [0    1    1    1    0    0    0]
                     [                               ]
                     [1    1    0    1    1    1    0]

> p:= combinat[randperm](n):
  B:= Matrix(n,n,(i,j)-> A[p[i],p[j]]);

                     [1    1    1    0    0    1    0]
                     [                               ]
                     [1    1    1    1    1    0    0]
                     [                               ]
                     [0    0    0    1    1    1    1]
                     [                               ]
                B := [0    0    0    0    0    1    0]
                     [                               ]
                     [0    0    1    1    0    0    1]
                     [                               ]
                     [1    1    1    1    1    0    0]
                     [                               ]
                     [1    1    0    0    1    0    1]

> IsSimilar(A,B,output=[query,'C']);

             [-489    295    1977   -201   -1831   2199   1793]
             [---- ,  --- ,  ---- , ---- , ----- , ---- , ----]
             [370     148    1480   740     592    1480   592 ]
             [                                                ]
             [-7            1487   -7    1473            -1459]
             [--- , 7/370 , ---- , --- , ---- , 7/1480 , -----]
             [740           1480   740   2960            2960 ]
             [                                                ]
             [237    -319    -117    141   3767   -363   -3161]
             [--- ,  ---- ,  ---- ,  --- , ---- , ---- , -----]
             [185    370     148     370   1480   740    1480 ]
             [                                                ]
       true, [         -7     363           -1843   363   1089]
             [7/370 ,  --- ,  --- , 7/370 , ----- , --- , ----]
             [         185    740           1480    740   1480]
             [                                                ]
             [763    -823    -77    -22    3397   -363   -1681]
             [--- ,  ---- ,  --- ,  --- ,  ---- , ---- , -----]
             [740    740     74     185    1480   740    1480 ]
             [                                                ]
             [0 ,     0 ,     1 ,     0 ,     0 ,     0 ,    0]
             [                                                ]
             [-3      29      -27      13     -3              ]
             [-- ,    -- ,    --- ,    -- ,   -- ,   0 ,   6/5]
             [20      20      20       10     20              ]
     

Note also that there are isospectral graphs, for which the adjacency matrices are similar, but of course not by a permutation matrix.

As noted there, the Q_B Q_A^T you find (e.g. using IsSimilar) might not be a permutation matrix, even if one exists.  For example:

> with(LinearAlgebra):
    n:= 7:
    A:= RandomMatrix(n,n,generator=0..1);

                     [1    0    0    1    1    0    1]
                     [                               ]
                     [0    0    0    0    0    0    1]
                     [                               ]
                     [1    0    1    0    1    1    0]
                     [                               ]
                A := [0    1    1    0    0    1    1]
                     [                               ]
                     [1    1    0    1    1    1    0]
                     [                               ]
                     [0    1    1    1    0    0    0]
                     [                               ]
                     [1    1    0    1    1    1    0]

> p:= combinat[randperm](n):
  B:= Matrix(n,n,(i,j)-> A[p[i],p[j]]);

                     [1    1    1    0    0    1    0]
                     [                               ]
                     [1    1    1    1    1    0    0]
                     [                               ]
                     [0    0    0    1    1    1    1]
                     [                               ]
                B := [0    0    0    0    0    1    0]
                     [                               ]
                     [0    0    1    1    0    0    1]
                     [                               ]
                     [1    1    1    1    1    0    0]
                     [                               ]
                     [1    1    0    0    1    0    1]

> IsSimilar(A,B,output=[query,'C']);

             [-489    295    1977   -201   -1831   2199   1793]
             [---- ,  --- ,  ---- , ---- , ----- , ---- , ----]
             [370     148    1480   740     592    1480   592 ]
             [                                                ]
             [-7            1487   -7    1473            -1459]
             [--- , 7/370 , ---- , --- , ---- , 7/1480 , -----]
             [740           1480   740   2960            2960 ]
             [                                                ]
             [237    -319    -117    141   3767   -363   -3161]
             [--- ,  ---- ,  ---- ,  --- , ---- , ---- , -----]
             [185    370     148     370   1480   740    1480 ]
             [                                                ]
       true, [         -7     363           -1843   363   1089]
             [7/370 ,  --- ,  --- , 7/370 , ----- , --- , ----]
             [         185    740           1480    740   1480]
             [                                                ]
             [763    -823    -77    -22    3397   -363   -1681]
             [--- ,  ---- ,  --- ,  --- ,  ---- , ---- , -----]
             [740    740     74     185    1480   740    1480 ]
             [                                                ]
             [0 ,     0 ,     1 ,     0 ,     0 ,     0 ,    0]
             [                                                ]
             [-3      29      -27      13     -3              ]
             [-- ,    -- ,    --- ,    -- ,   -- ,   0 ,   6/5]
             [20      20      20       10     20              ]
     

Note also that there are isospectral graphs, for which the adjacency matrices are similar, but of course not by a permutation matrix.

That's actually a very different, and much harder, question.

Consider the case where A and B are  adjacency matrices of graphs.  Then there is such a permutation matrix iff the two graphs are isomorphic.  Unfortunately no polynomial-time algorithm for the graph isomorphism problem is known.  See e.g. en.wikipedia.org/wiki/Graph_isomorphism

That's actually a very different, and much harder, question.

Consider the case where A and B are  adjacency matrices of graphs.  Then there is such a permutation matrix iff the two graphs are isomorphic.  Unfortunately no polynomial-time algorithm for the graph isomorphism problem is known.  See e.g. en.wikipedia.org/wiki/Graph_isomorphism

Caution: xavier's procedure G works on a list, not on a Matrix.  So to use G you must first convert each Matrix to a list.  Then I don't think G is so fast.  For example, on my computer the time to compare two 50 x 50 Matrices of distinct integers using my method shows as 0.  The time for

> evalb(G(map(op,convert(A,listlist)) = G(map(op,convert(B,listlist))))

was over 17 seconds.

Caution: xavier's procedure G works on a list, not on a Matrix.  So to use G you must first convert each Matrix to a list.  Then I don't think G is so fast.  For example, on my computer the time to compare two 50 x 50 Matrices of distinct integers using my method shows as 0.  The time for

> evalb(G(map(op,convert(A,listlist)) = G(map(op,convert(B,listlist))))

was over 17 seconds.

implicitplot(max(x^2+(y+2)^2-4,1-x^2 - (y+2)^2, abs(argument(x+(2+y)*I))-Pi/3) <= 0, x = -2 ..2, y = -4 .. 0,   
      grid=[50,50],filledregions=true,gridrefine=3,crossingrefine=3,view=[-2..2, -4..0]);
implicitplot(max(x^2+(y+2)^2-4,1-x^2 - (y+2)^2, abs(argument(x+(2+y)*I))-Pi/3) <= 0, x = -2 ..2, y = -4 .. 0,   
      grid=[50,50],filledregions=true,gridrefine=3,crossingrefine=3,view=[-2..2, -4..0]);

It should be ln(n) with no spaces.  Also, I recommend that you use Maple Notation input rather than 2D Math.
From the Tools menu, choose Options..., Display, and set Input display to Maple Notation.  Then click on Apply globally.

It should be ln(n) with no spaces.  Also, I recommend that you use Maple Notation input rather than 2D Math.
From the Tools menu, choose Options..., Display, and set Input display to Maple Notation.  Then click on Apply globally.

Occasionally you do run into one of the older packages that is based on tables rather than a module.  There are still some of those in Maple 12, e.g. DEtools and simplex.  Then it has to be DEtools[DEplot], not DEtools:-DEplot.


 

Occasionally you do run into one of the older packages that is based on tables rather than a module.  There are still some of those in Maple 12, e.g. DEtools and simplex.  Then it has to be DEtools[DEplot], not DEtools:-DEplot.


 

The main problem is that psi1 and psi2 contain the global variable nu, not the formal parameter nu of procedure k.

By the way, there should be no need to use implicitplot here.  Also, you will probably find it simpler to use piecewise instead of a procedure with an if statement. 
Try:

> plot(piecewise(h<=1, psi1, psi2), nu= 0 .. 10^14);

 

The main problem is that psi1 and psi2 contain the global variable nu, not the formal parameter nu of procedure k.

By the way, there should be no need to use implicitplot here.  Also, you will probably find it simpler to use piecewise instead of a procedure with an if statement. 
Try:

> plot(piecewise(h<=1, psi1, psi2), nu= 0 .. 10^14);

 

First 93 94 95 96 97 98 99 Last Page 95 of 187